Les membres ayant 30 points peuvent parler sur les canaux annonces, projets et hs du chat.
La shoutbox n'est pas chargée par défaut pour des raisons de performances. Cliquez pour charger.

Forum Casio - Projets de programmation


Index du Forum » Projets de programmation » Compylateur
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Compylateur

Posté le 08/05/2020 14:00

Bonjour à tous !

Il y a quelques temps j'ai fait un 'compilateur' qui permet d'exécuter un algorithme en langage naturel en le 'traduisant' en Python. Le code est atroce et repose sur un remplacement entre les commandes en langage naturel et les commandes en Python (à coup de dictionnaires et de tests conditionnels )… J'aimerais faire de ce projet un 'vrai' compilateur (on reste sur du Python ). Et j'ai quelques questions :

- La phase d'analyse lexicale repose pour l'instant sur une recherche et un replacement, avec un dictionnaire qui contient en clés les commandes en langage naturel, et en items, les commandes correspondantes en Python… Je me doute que ce n'est pas pertinent… En fait l'analyse lexicale est mélangée à la phase d'analyse syntaxique.

- Comment faire pour basculer du langage naturel au Python ? Faut-il forcément passer par un hard code, ou est-ce que d'autre technique plus esthétiques existent ?

- L'analyse syntaxique est un bête replace basé sur un dico… Du coup ça revient à la question précédente : comment éviter le hard code ?

- La phase sémantique… Je ne suis pas sûr d'avoir bien compris toutes les subtilités… Dans mon cas, après le remplacement bête et méchant, la syntaxe Python n'est pas bonne, du coup je passe à travers différents tests conditionnels pour avoir un 'vrai' script fonctionnel… Encore une fois le hard code à coup de if me plaît moyen…

- En derniers je refait un passage sur mon code généré et j'ajoute les alinéas. Est-ce que je devrais les gérer plus tôt (je pense à la phase d'analyse syntaxique… mais le placement des alinéas dépend du contexte du code, et sur une ligne donnée je vois pas trop comment faire…

Merci d'avance !


Précédente 1, 2, 3 ··· 8, 9, 10, 11, 12, 13, 14 ··· 18, 19, 20 Suivante
Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 14:06 | #


C'est pas mal... mais du coup tu as fait un truc plus compliqué que nécessaire. Tu peux lancer la récursion dès le premier PLUS/MINUS :

def somme():
    atome_1 = self.atome()
    if self.token_ahead.type not in ("PLUS", "MINUS"):
        return atome_1
    op = self.expect(["PLUS", "MINUS"])
    somme_1 = self.somme()
    return Node("Operation", op.value, atome_1, somme_1)

Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 14:07 | #


Ah ouais ! pas bête !
Et après je fais pareil avec produit ? en considérant que la puissance est un produit ?
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 14:09 | #


Tu fais pareil avec le produit, par contre la puissance c'est pas un produit ! Et c'est pas récursif, en général on n'autorise pas à écrire x**y**z. Il te faut donc une règle pour la puissance (non récursive) et une règle pour le produit qui utilise la puissance comme atome.

Et du coup les opérandes de + c'est des produits donc faut remplacer atome par produit dans la fonction juste ci-dessus
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 14:12 | #


J'essaye ça et je ramène le code ! Merci !
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Zezombye Hors ligne Rédacteur Points: 1756 Défis: 13 Message

Citer : Posté le 06/06/2020 14:13 | #


> Et c'est pas récursif, en général on n'autorise pas à écrire x**y**z

Ben pourquoi pas :o


Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 14:19 | #


En pseudo-code sur des algos de livres de maths c'est très rare… donc qu'on peut passer outre…

Du coup j'ai ce code avec les trois méthodes :

    def sum():
        atome_1 = self.product()
        if self.token_ahead.type not in ("PLUS", "MINUS"):
            return atome_1
        op = self.expect()
        sum_1 = self.sum()
        return Node("Operation", op.value, atome_1, sum_1)

    def product():
        atome_1 = self.exp()
        if self.token_ahead.type not in ("MULTI", "DIVI"):
            return atome_1
        op = self.expect()
        product_1 = self.somme()
        return Node("Operation", op.value, atome_1, product_1)

    def exp():
        atome_1 = self.atome()
        if self.token_ahead != "EXP":
            return atome_1
        op = self.expect()
        atome_2 = self.atome()
        return Node("Operation", op.value, atome_1, atome_2)

"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 14:19 | #


C'est pas utile, contrairement aux autres opérations c'est morphique donc ça revient à x**(y*z).

Bon après on peut le définir. Mon expérience (en maths comme en prog) c'est que les gens oublient que c'est associatif de droite-à-gauche et ça emmerde tout le monde donc personne s'en sert ^^"

Ajouté le 06/06/2020 à 14:21 :
self.token_ahead != "EXP" n'est pas bon, il manque un .type.

product_1 = self.somme() non plus, ça devrait être self.product() xD

Très bien du reste, il faut maintenant qu'on s'occupe de - et / qui passent pas bien : a-b-c donne a-(b-c) ce qui est faux.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 14:22 | #


Ouaip okay…

Oui, mais ça c'est de l’inattention xD
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 14:27 | #


Avant de passer à l'associativité de - et / je te propose qu'on affiche ton AST avec de l'indentation et tout le détail pour visualiser ce que tu as vraiment en sortie du parser. Ensuite je te montrerai comment faire la répétition et pourquoi ça nous aide pour la soustraction et la division. La répétition va "remplacer" la récursion dans le cas des expressions, mais c'est un cas un peu particulier et la récursion reste l'outil numéro 1 des grammaires, c'est pour ça que je voulais commencer par là.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 14:30 | #


Ouaip, pas de problème

Pour l'AST j'ai fait plusieurs tests :
compylateur("a+2")
--- Tokens ---
('VAR', 'a')
('PLUS', '+')
('NUM', '2')


--- AST ---
Operation : +
  Variable : a
  Number : 2

compylateur("a*2")
--- Tokens ---
('VAR', 'a')
('MULTI', '*')
('NUM', '2')


--- AST ---
Operation : *
  Variable : a
  Number : 2

compylateur("((a^2)+2) / c*3 - 5")
--- Tokens ---
('LPAR', '(')
('LPAR', '(')
('VAR', 'a')
('EXP', '^')
('NUM', '2')
('RPAR', ')')
('PLUS', '+')
('NUM', '2')
('RPAR', ')')
('DIVI', '/')
('VAR', 'c')
('MULTI', '*')
('NUM', '3')
('MINUS', '-')
('NUM', '5')


--- AST ---
Operation : -
  Operation : /
    Operation : +
      Operation : ^
        Variable : a
        Number : 2
      Number : 2
    Operation : *
      Variable : c
      Number : 3
  Number : 5

"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 14:33 | #


Eh bien, ça a une super tête ! Regarde ce que ça donne sur a-b+c-d-7.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 14:33 | #


Merci !!

J'ai ça :
>>> compylateur("a-b+c-d-7")
--- Tokens ---
('VAR', 'a')
('MINUS', '-')
('VAR', 'b')
('PLUS', '+')
('VAR', 'c')
('MINUS', '-')
('VAR', 'd')
('MINUS', '-')
('NUM', '7')


--- AST ---
Operation : -
  Variable : a
  Operation : +
    Variable : b
    Operation : -
      Variable : c
      Operation : -
        Variable : d
        Number : 7

"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 15:33 | #


Voilà donc comme tu le vois c'est faux parce que ça donne a-(b+(c-(d-7))) = a-b-c+d-7 au lieu de a-b+c-d-7.

Ce qu'on va faire c'est qu'on va changer la méthode grammaticale pour boucler au lieu de faire un appel récursif. Ça donne presque le même effet, mais ça nous permettra de contrôler le parenthésage.

L'objectif c'est d'obtenir ça :

Operation : +
  Variable : a
  Operation : - (moins unaire)
    Variable : b
  Variable : c
  Operation : - (moins unaire)
    Variable : d
  Operation : - (moins unaire)
    Number : 7

Donc plusieurs informations :
• D'abord ton + a plus de deux enfants, ce qui est beaucoup plus pratique pour énormément de raisons.
• Ensuite un ne représente pas la soustraction, on se contente d'ajouter l'opposé à l'aide du moins unaire. Ça aussi c'est plus pratique.
• Enfin, tu remarques que j'ai mis un moins unaire sur le 7 au lieu de simplement mettre -7, on verra plus tard comment faire ça si ça t'amuses (ça ne changera rien au résultat des calculs).

Chaud pour ça ?
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 15:35 | #


Okay, j'avoue que le coup des nombres négatifs je m'était dit que ça allait me poser des problèmes…

Et du coup carrément !
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 15:40 | #


Donc voilà comment on va faire, d'abord ta méthode grammaticale sera pas récursive mais utilisera une boucle while.

def somme():
    atomes = [self.atome()]

    while self.token_ahead.type in ("PLUS", "MINUS"):
        t = self.expect() # bien vu le coup de pas recopier les types acceptés !
        at = self.atome()
        if t.type == "MINUS":
          at = Node("Operation", "moins_unaire", at) # note le moins unaire comme tu veux
        atomes.append(at)

    return Node("Operation", "+", *atomes)

Ça te parle ça ? Tu vois où on va ?
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 15:47 | #


J'ai juste du mal avec la notation *atomes… atome est une liste et *atome permet de transformer la liste [1,2] en arguments de fonction 1, 2 ?

at c'est l'arbre qui est compléter au fur et à mesure… Après ce qui me pose le plus de problème c'est comment noter le "moins unaire"… ? je pense le mettre comme ça pour l'instant…

Edit : atome c'est bien product au début et pas atome ?
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 15:53 | #


Oui, c'est ça ! Si l=[1,2,3], f(*l) c'est f(1,2,3) (par opposition à f(l) qui est f([1,2,3])).

Le moins unaire tu peux le noter comme tu veux, "--" par exemple, ça n'a pas beaucoup d'importance.

Euh oui, c'est des produit et pas des atomes. Tu suis toi !
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 15:58 | #


J'essaye o/ ^^'

Du coup j'ai ce code :

def sum(self):
        atomes = [self.product()]

        while self.token_ahead.type in ("PLUS", "MINUS"):
            operator = self.expect()
            atome_after = self.product()
            atomes.append((atome_after, Node("Operation", "--", atome_after))[operator.type == "MINUS"])

        return Node("Operation", "+", *atomes)


et ce résultat :

>>> compylateur("a-b+c-d-7")
--- Tokens ---
('VAR', 'a')
('MINUS', '-')
('VAR', 'b')
('PLUS', '+')
('VAR', 'c')
('MINUS', '-')
('VAR', 'd')
('MINUS', '-')
('NUM', '7')


--- AST ---
Operation : +
  Variable : a
  Operation : --
    Variable : b
  Variable : c
  Operation : --
    Variable : d
  Operation : --
    Number : 7


Et quand ce n'est pas un moins unaire, juste a-2 j'ai une décomposition comme ça : a + (-2)

>>> compylateur("a-2")
--- Tokens ---
('VAR', 'a')
('MINUS', '-')
('NUM', '2')


--- AST ---
Operation : +
  Variable : a
  Operation : --
    Number : 2


Ajouté le 06/06/2020 à 17:30 :
Je pense voir ça demain, mais j'ai des erreurs lors de calculs avec des nombres négatifs, typiquement la syntaxe (atome) n'est pas comprise…

J'ai trouvé quelques cas : a* -2 ne marche pas, de même pour a * (-2)
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 18:19 | #


Parfait ! C'est exactement là où je voulais arriver. Du coup, la grammaire correspondante s'écrit :

somme -> produit ((PLUS|MINUS) produit)*

Le * signifie "répété 0 ou plus de fois", donc selon la chaîne de la somme on applique le groupe "(PLUS|MINUS) produit" un nombre différent de fois. Tu peux faire pareil pour les produits !

Avec les nombres négatifs c'est normal parce que... tu n'as pas le moins unaire ! Tu n'as que le moins binaire comme dans "a-2" (que tu traduis en un moins unaire par facilité mais ça c'est un détail). Il faut modifier la règle atome. Je te laisse essayer...
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5504 Défis: 18 Message

Citer : Posté le 06/06/2020 18:26 | #


Du coup ma todo list :

1 - gérer la grammaire atome -> somme | (somme)
2 - gérer les nombres négatifs
"Ce n'est pas parce que les chose sont dures que nous ne les faisons pas, c'est parce que nous ne les faisons pas qu'elles sont dures." Sénèque

Lephenixnoir En ligne Administrateur Points: 24676 Défis: 170 Message

Citer : Posté le 06/06/2020 18:28 | #


Hmm cette règle pour atome est pas bonne. Oublie pas il y a VAR et NUM, et entre parenthèses tu peux autoriser n'importe quelle expr (même si l'expression complète ne contient aucun opérateur moins prioritaire que +, c'est mieux de mettre "(expr)" et "expr -> somme" pour être clair).
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Précédente 1, 2, 3 ··· 8, 9, 10, 11, 12, 13, 14 ··· 18, 19, 20 Suivante

LienAjouter une imageAjouter une vidéoAjouter un lien vers un profilAjouter du codeCiterAjouter un spoiler(texte affichable/masquable par un clic)Ajouter une barre de progressionItaliqueGrasSoulignéAfficher du texte barréCentréJustifiéPlus petitPlus grandPlus de smileys !
Cliquez pour épingler Cliquez pour détacher Cliquez pour fermer
Alignement de l'image: Redimensionnement de l'image (en pixel):
Afficher la liste des membres
:bow: :cool: :good: :love: ^^
:omg: :fusil: :aie: :argh: :mdr:
:boulet2: :thx: :champ: :whistle: :bounce:
valider
 :)  ;)  :D  :p
 :lol:  8)  :(  :@
 0_0  :oops:  :grr:  :E
 :O  :sry:  :mmm:  :waza:
 :'(  :here:  ^^  >:)

Σ π θ ± α β γ δ Δ σ λ
Veuillez donner la réponse en chiffre
Vous devez activer le Javascript dans votre navigateur pour pouvoir valider ce formulaire.

Si vous n'avez pas volontairement désactivé cette fonctionnalité de votre navigateur, il s'agit probablement d'un bug : contactez l'équipe de Planète Casio.

Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 127 connectés | Nous contacter | Qui sommes-nous ? | Licences et remerciements

Planète Casio est un site communautaire non affilié à Casio. Toute reproduction de Planète Casio, même partielle, est interdite.
Les programmes et autres publications présentes sur Planète Casio restent la propriété de leurs auteurs et peuvent être soumis à des licences ou copyrights.
CASIO est une marque déposée par CASIO Computer Co., Ltd