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: 5503 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 ··· 7, 8, 9, 10, 11, 12, 13 ··· 18, 19, 20 Suivante
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

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


Si rien n'a été trouvé et que le mot regardé est un nombre…
ici : l_token.add(Token(("VAR", "NUM")[word[index].isdigit()], word[index]))
"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: 24508 Défis: 170 Message

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


C'est un peu fragile mais pourquoi pas. Je vois pas de raison de ne pas utiliser LPAR = {"("} et RPAR = {")"} pour l'instant, c'est pas comme si ça changeait grand-chose.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

Citer : Posté le 04/06/2020 15:18 | #


Justement ça ajoute encore plus au bordel général… Fin, j'ai codé ça, mais sans vraiment savoir comment ça allait fonctionner et je comprends pas comment les lexers "normaux" fonctionnent…
"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: 24508 Défis: 170 Message

Citer : Posté le 04/06/2020 15:21 | #


Un lexer normal c'est un automate fini... en gros tu donne une regex pour chaque type de token et ensuite tu construis (automatiquement) un automate combiné qui applique toutes les regex en même temps chaque fois qu'il lit un caractère. C'est très pété parce c'est super rapide (plus que ce que tu ferais à la main) et les regex c'est super pratique. C'est pour ça que personne n'écrit des lexers à la main en général.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

Citer : Posté le 04/06/2020 15:22 | #


Ah… et dans mon cas, je peux espérer avoir un truc moins bancal ? ^^' Ou ce que j'ai peut suffir ?
"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: 24508 Défis: 170 Message

Citer : Posté le 04/06/2020 15:23 | #


Tant que tu le codes à la main, t'auras rien de fondamentalement meilleur que ce que t'as déjà. Donc t'embête pas pour l'instant.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

Citer : Posté le 04/06/2020 15:23 | #


Okay, merci !

Ajouté le 06/06/2020 à 12:55 :
Donc, j'ai rajouté une gestion des parenthèses…

# --- Parser --- #

class Parser():
    def __init__(self, l_token):
        self.l_token = l_token
        self.token_ahead = l_token.list[0]

    def expect(self, target = []):
        last = self.token_ahead
        self.token_ahead = self.l_token.next()
        if target != [] and last.type not in target:
            raise SyntaxError("This operand was not expected : '{0}' (for dev : {1})".format(last.value, target))
        return last

    def atome(self):
        atm = self.expect(["VAR", "NUM", "LPAR"])
        if atm.type in ("VAR", "NUM"):
            return Node(("Variable", "Number")[atm.type == "NUM"], atm.value)
        else:
            e = self.expr()
            self.expect("RPAR")
            return e

    def expr(self):
        atome_1 = self.atome()
        operator = self.expect(["OPTR"])
        atome_2 = self.atome()
        return Node("Operation", operator.value, atome_1, atome_2)


Du coup je pense qu'on peut passer au point suivant ! (avec mon lot de questions…)

- À un moment tu avais soulevé le point que j'ai toute mes opérations mathématiques dans la même méthode… Est-ce que c'est pertinent comme choix ? Quels problèmes ça va me poser par la suite ?

- Pour la suite du parser, je pensais me tourner vers les comparaisons et les conditions, j'ai donc commencé à faire une petite grammaire :
comparaison -> expr COMP expr
condition -> comparaison | comparaison LOGI comparaison

Du coup est-ce que partir dans ce sens est une bonne idée, et si oui, est-ce que ma grammaire tiens la route ?

Merci d'avance !
"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: 24508 Défis: 170 Message

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


- À un moment tu avais soulevé le point que j'ai toute mes opérations mathématiques dans la même méthode… Est-ce que c'est pertinent comme choix ? Quels problèmes ça va me poser par la suite ?

Ça va mal se passer exactement pour la même raison que les parenthèses. Quand tu vas vouloir faire les sommes et produits, tu vas vouloir tester PLUS et MOINS d'un côté, FOIS et DIVISION de l'autre, mais tu n'auras pas la finesse nécessaire pour faire ça parce que tu n'as que OPTR. Tu auras besoin de séparer pour faire marcher les règles sans devoir dupliquer partout la logique de test et les messages d'erreur.

- Pour la suite du parser, je pensais me tourner vers les comparaisons et les conditions, j'ai donc commencé à faire une petite grammaire :

C'est "trop tôt" ! Tu n'as pas encore l'arithmétique. Mais c'est le bon schéma. C'est exactement pareil que pour les sommes produits sauf que comme tu ne peux pas écrire x ≤ y ≤ z tu n'as pas besoin de la récursivité de la même façon que quand tu écris x + y + z (associativité gauche-à-droite si tu veux tout savoir).

Les comparaisons feront a priori partie de tes expressions et tu as certainement besoin d'établir des priorités opératoires parce que là tu peux même pas écrire de comparaisons "composées" avec des ET/OU puisque tu n'as pas de parenthèses.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

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


Quand je fait OPTR c'est la valeur que je stocke, soit l'opérande de l'opération je sais quelle opération est faite… 'Fin, je ne comprends la trop la différence, à la fin que je regarde séparément somme et produit ou que je traite les deux par la même méthode, l'AST est identique, non ?

J'ai pas compris :
puisque tu n'as pas de parenthèses.

Les parenthèses sont gérées avec les atomes et les expressions… Du coup je peux faire des comparaisons (a+3) est inférieur à b le début (a+3) c'est géré… Et de là à rajouter des ET/OU entre les comparaisons… je crois que je ne saisis pas le problème…
"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: 24508 Défis: 170 Message

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


Quand je fait OPTR c'est la valeur que je stocke, soit l'opérande de l'opération je sais quelle opération est faite…

On a eu exactement la même discussion avec les parenthèses. Il ne suffit pas que toi (la méthode grammaticale) puisse faire la distinction, il faut que expect() puisse faire la distinction pour lever l'erreur de syntaxe qui convient. Et expect() ne lit que le type de tokens.

Tu as des parenthèses avec les expressions arithmétiques, oui. Mais tu n'as pas de parenthèses avec les expressions booléennes, tu ne peux pas écrire "a supérieur à 3 et (b supérieur à 5 ou c plus grand que 7)".

Au passage tes expressions arithmétiques ne sont pas du tout finies car il te manque des opérateurs et surtout les priorités opératoires ! Les grandes idées sont les mêmes pour les expressions arithmétiques et booléennes, donc si tu veux en regarder une avant l'autre pas de problème, mais n'oublie pas que tu as encore du travail à faire sur les deux.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

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


Nan, on va faire ça dans l'ordre je suis juste un peu paumé x) faut que je fasse un token PLUS = {"+"} et de même pour chaque opération… ? Et que je gère les sommes et les produits séparément ?

Pour en revenir à expect, que ce soit une multiplication, une addition, ou une puissance c'est toujours la même forme A opérateur B ? Il n'y a pas d'erreurs de syntaxe quelque soit cet opérateur… ?
"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: 24508 Défis: 170 Message

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


faut que je fasse un token PLUS = {"+"} et de même pour chaque opération… ?

Oui c'est ça !

Pour en revenir à expect, que ce soit une multiplication, une addition, ou une puissance c'est toujours la même forme A opérateur B ? Il n'y a pas d'erreurs de syntaxe quelque soit cet opérateur… ?

Si parce qu'en fait comme tu vas le voir bientôt, la méthode pour gérer les priorités opératoires consiste à créer une règle différente par niveau de priorité, par exemple comme ceci avec les puissances, multiplications et additions :

atome -> VAR | NUM | LPAR expr RPAR
facteur -> atome | atome PUISSANCE atome
produit -> facteur | facteur FOIS produit
somme -> produit | produit PLUS somme

Pour les soustractions et divisions c'est un peu plus compliqué : en fait ici je lis a+b+c comme a+(b+c) [associativité gauche-à-droite], mais si on fait pareil avec moins, on va lire a-b-c comme a-(b-c) = a-b+c, ce qui est faux ! Il faut le lire (a-b)-c [associativité droite-à-gauche]. On verra après comment faire ça.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Zezombye Hors ligne Rédacteur Points: 1756 Défis: 13 Message

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


Heu, a+b+c doit être lu en tant que (a+b)+c non ?
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Lephenixnoir En ligne Administrateur Points: 24508 Défis: 170 Message

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


On s'en fout, l'addition est associative. En général on le lit bien (a+b)+c, mais le problème c'est que la règle de grammaire correspondante c'est somme -> produit | somme PLUS produit donc elle est récursive à gauche, et ça tu ne peux pas le coder directement dans un parser à descente récursive (la première action de somme() serait d'appeler somme(), ce qui ferait une boucle infinie).
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

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


Okay… donc la séparation des opérateurs en tokens permet de définir les priorités de calculs…

Mon lexer commence à me faire peur… xDD j'essaye de faire ça du coup
"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 13:42 | #


Ben, comment tu fais pour la soustraction alors et techniquement l'addition n'est pas associative dans le cas des under/overflow mais vu qu'on parse un langage "mathématique" on peut ignorer ça.

On peut prendre exemple sur la grammaire du python :


expr: xor_expr ('|' xor_expr)*
xor_expr: and_expr ('^' and_expr)*
and_expr: shift_expr ('&' shift_expr)*
shift_expr: arith_expr (('<<'|'>>') arith_expr)*
arith_expr: term (('+'|'-') term)*
term: factor (('*'|'@'|'/'|'%'|'//') factor)*
factor: ('+'|'-'|'~') factor | power
power: atom_expr ['**' factor]
atom_expr: [AWAIT] atom trailer*
atom: ('(' [yield_expr|testlist_comp] ')' |
       '[' [testlist_comp] ']' |
       '{' [dictorsetmaker] '}' |
       NAME | NUMBER | STRING+ | '...' | 'None' | 'True' | 'False')

Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Lephenixnoir En ligne Administrateur Points: 24508 Défis: 170 Message

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


Doucement Zezombye. On gère la soustraction en modifiant la règle pour utiliser une répétition au lieu d'une récursion, ça change un appel récursif en un while dans la méthode grammaticale.

Et c'est exactement ce que la grammaire de Python fait si tu lis ça un peu attentivement.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Zezombye Hors ligne Rédacteur Points: 1756 Défis: 13 Message

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


Et donc, pourquoi on ne peut pas utiliser ça pour l'addition ?
Divers jeux : Puissance 4 - Chariot Wars - Sokoban
Ecrivez vos programmes basic sur PC avec BIDE
Lephenixnoir En ligne Administrateur Points: 24508 Défis: 170 Message

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


On peut et c'est ce que j'ai l'intention de présenter à Shadow, mais pas besoin de se presser. Pour l'instant le côté récursif de t1+...+tn est déjà pas clair, donc on verra après.
Mon graphe (11 Avril): ((Rogue Life || HH2) ; PythonExtra ; serial gint ; Boson X ; passe gint 3 ; ...) || (shoutbox v5 ; v5)
Shadow15510 Hors ligne Administrateur Points: 5503 Défis: 18 Message

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


J'ai essayé de faire un truc récursif pour la somme… j'ai modifié le lexer avec un token par opérateur.

Ça me donne ça :
def somme():
        atome_1 = self.atome()
        operator = self.expect(["PLUS", "MINUS"])
        atome_2 = self.atome()
        if self.token_ahead.type not in ("PLUS", "MINUS"):
            return Node("Opération", operator.value, atome_1, atome_2)
        else:
            return Node("Operation", opérator.value, atome_1, atome_2, self.somme())

"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: 24508 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)
Précédente 1, 2, 3 ··· 7, 8, 9, 10, 11, 12, 13 ··· 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 79 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