Posté le 08/05/2020 14:00
)… J'aimerais faire de ce projet un 'vrai' compilateur 
(on reste sur du Python ). Et j'ai quelques questions : 
En fait l'analyse lexicale est mélangée à la phase d'analyse syntaxique.
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…
Planète Casio v4.3 © créé par Neuronix et Muelsaco 2004 - 2024 | Il y a 43 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
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).
Citer : Posté le 06/06/2020 18:30 | #
Okay… dans tous les cas, il faut juste modifier atome ?
Citer : Posté le 06/06/2020 18:40 | #
Euh... à vue de nez oui. Tu verras à l'usage si les priorités opératoires marchent bien, mais je pense que oui, ça suffit.
Citer : Posté le 07/06/2020 19:11 | #
J'ai un peu réfléchis, du coup coup pour atome ma grammaire est plutôt :
atome -> VAR | NUM | somme | (atome) ?
Citer : Posté le 07/06/2020 19:15 | #
Hmm, malheureusement non. D'abord atome -> somme est un gros problème. Un atome peut être : une variable, une constante numérique, une expression entre parenthèses, mais une somme ?! Non, une somme est composée d'atomes. D'ailleurs tu vois que si tu fais ça tu as un gros problème car tu as une dérivation :
et tu boucles à l'infini.
Donc, une idée que tu peux retenir : quand un symbole représentant un "petit" objet (comme atome) utilise un symbole représentant un "grand" objet (comme somme) il doit y avoir un marquage explicite (comme des parenthèses). Une règle que tu dois avoir est
ou, si tu veux vraiment pas définir expr comme somme,
Maintenant il reste le fait que tu gères pas encore le moins unaire
Citer : Posté le 07/06/2020 19:51 | #
Pour l'instant mon atome ressemble à ça :
atm = self.expect(["VAR", "NUM", "LPAR"])
if atm.type in ("VAR", "NUM"):
return Node(("Variable", "Number")[atm.type == "NUM"], atm.value)
else:
e = self.sum()
self.expect("RPAR")
return e
Ouaip, je saisis le problème du bouclage à l'infini… x)
J'ai par contre plus de mal avec le concept d'expression…
somme c'est un abus de langage vu que je prend produit comme atome que produit a pour atome exposant… somme détecte toutes les opérations mathématiques…
Citer : Posté le 07/06/2020 20:18 | #
Ton atome actuel implémente la grammaire atome -> VAR | NUM | ( somme ), ce qui est très bien !
Une "expression" ça veut dire n'importe quelle expression (ici, arithmétique). Ça peut être 2**3, 8+a, ou 5*(3^8-c). Compte tenu de ta grammaire ça se traduit par le symbole d'expression avec la priorité la plus faible, donc somme.
Citer : Posté le 08/06/2020 08:39 | #
Okay ! Du coup il ne reste que le moins unaire comme tu disais… ?
J'avais dans l'idée de rajouter "MINUS" dans les tokens accepté par atome, puis renvoyer la valeur numérique du token suivant avec le signe - devant
Citer : Posté le 08/06/2020 08:52 | #
J'avais dans l'idée de rajouter "MINUS" dans les tokens accepté par atome, puis renvoyer la valeur numérique du token suivant avec le signe - devant
Exactement ! Tu peux l'écrire comme ça :
Où ? signifie "optionnel". Regarde dans ton code comment tu détectes ça
Citer : Posté le 08/06/2020 10:08 | #
J'ai trouvé un truc qui marche…
atm = self.expect(["VAR", "NUM", "LPAR", "MINUS"])
if atm.type == "MINUS": return self.atome(True)
elif atm.type == "VAR":
return Node("Variable", atm.value)
elif atm.type == "NUM":
return Node("Number", (atm.value, "-" + atm.value)[minus])
else:
e = self.sum()
self.expect("RPAR")
return e
Avec le défaut que le compilateur recherche une somme à tout prix même si il n'y en a pas… par exemple :
--- Tokens ---
('VAR', 'a')
('MULTI', '*')
('MINUS', '-')
('NUM', '2')
--- AST ---
Operation : +
Operation : *
Variable : a
Number : -2
Citer : Posté le 08/06/2020 23:22 | #
if atm.type == "MINUS": return self.atome(True)
Très bien, c'est correct ! Moi j'aurais mis une variable locale, visiblement toi tu vas plus loin encore avec posément un appel récursif et un paramètre optionnel !
return Node("Variable", atm.value)
Hey attention ! Tu ignores le moins devant la variable quand il y en a un. Ça devrait ressembler à :
if minus:
return Node("Operation", "--", Node("Variable", atm.value))
else:
return Node("Variable", atm.value)
Dans le code suivant :
Il n'y a pas de problème fondamental, mais tu ne devrais pas stocker les valeurs numériques sous forme de texte. Ton deuxième paramètre devrait vraiment être un entier ou un flottant, et ce dès le token. Dans cette situation le deuxième cas devrait être -atm.value.
e = self.sum()
self.expect("RPAR")
return e
Pareil que pour VAR, tu ignores le moins quand il y en a un ! Si minus==True, tu devrais renvoyer Node("Operation","--",e) et non pas e.
Deux indications supplémentaires :
• Si tu trouves un MINUS, tu devrais en fait faire un appel récursif avec not minus plutôt que True. Réfléchis à ce qui se passe si tu écris --2 !
• Pour être tout à fait complet, tu pourrais aussi supporter le plus unaire, auquel cas tu ferais juste un appel récursif sans inverser la valeur de minus.
Bravo !
Citer : Posté le 09/06/2020 08:30 | #
Merci !
Le coup du paramètre optionnel c'est propre ? Ou il faut que je change ?
Pour le coup de ne pas gérer le moins sur les autres tokens j'avais oublié…
Au niveau du stockage des nombres sous forme de str le problème remonte directement à l'AST : Node ne prends que des chaînes de caractères en argument…
J'ai des problèmes au niveau de sum le moins qui devrait être appliqué à une variable est gérer comme l'opérateur de soustraction… De même quand j'ai des codes sans additions, j'ai un AST qui me met des additions là où il n'y en a pas…
--- Tokens ---
('NUM', '2')
('MULTI', '*')
('VAR', 'a')
--- AST ---
Operation : +
Operation : *
Number : 2
Variable : a
J'ai commencé à revoir le code, j'ai ça du coup
atm = self.expect(["VAR", "NUM", "LPAR", "MINUS"])
if atm.type == "MINUS": return self.atome(True)
elif atm.type == "VAR":
return (Node("Variable", atm.value), Node("Operation", "--", Node("Variable", atm.value)))[minus]
elif atm.type == "NUM":
return Node("Number", (atm.value, "-" + atm.value)[minus])
else:
e = self.sum()
self.expect("RPAR")
return (e, Node("Operation", "--", e))[minus]
Citer : Posté le 09/06/2020 08:55 | #
Ça relève de tes préférences. Moi j'y vois pas de problème, tu peux le laisser comme ça.
Tu comprends que chaque - inverse le signe de la constante, donc --2 = +2, n'est-ce-pas ? Or, avec ton système actuel, voici ce qui se passe :
• Tu appelles atome() sur --2 avec minus=False (c'est juste)
• Tu lis un -, tu appelles atome() sur -2 avec minus=True (c'est juste)
• Tu lis le second -, tu appelles atome() sur 2 avec minus=True (horreur !!)
• Tu renvoies -2 !
Comme tu peux le voir, un deuxième moins vient annuler le premier ! Et ça marche aussi avc 3, 4, 5, etc moins. Pour modéliser proprement ça, tu dois faire ça :
Par contre la valeur par défaut doit bien être False, je pense que tu auras compris que s'il n'y a pas de moins devant l'atome il n'y a pas de raison de rendre la donnée négative !
Tu fais du Python, tu te rappelles ? Ce genre de contraintes de types n'existe pas. Tu peux passer ce que tu veux à Node.
Et c'est normal, si tu écris 1-a le résultat de ce sera bien la soustraction de 1 et de a. Et c'est le cas parce que sum() va lire l'atome 1 et va rester avec -a, puis va gober le - au moment où il fait self.expect(["PLUS", "MINUS"]) !
Je pense que tu comprends que sum() n'a pas le choix ici, il lui faut un opérateur et aucun autre n'est disponible ! En plus, si tu mets le - dans le a, tu te retrouves avec deux atomes à la suite (1 et -a), et tu n'as aucune règle de grammaire qui accepte deux atomes à la suite qui ne sont pas séparés par un opérateur. Ce serait donc une erreur de syntaxe !
Et... c'est normal aussi ! (Mais on peut l'éviter.) Regarde bien ta grammaire, qui ressemble à ça :
produit -> exp ((FOIS | DIV) exp)*
exp -> atome | atome EXP atome
atome -> MINUS? (VAR | NUM | LPAR somme RPAR)
Lorsque tu veux analyser une expression arithmétique, tu appelles somme(). Pourquoi ? Parce que c'est l'expression la plus générale, les sommes couvrent tout. Ce que tu dois penser quand tu appelles somme(), c'est "je vais aller lire une expression et je m'autorise à utiliser tous les opérateurs de priorité au moins aussi forte que + et -". Ça inclut aussi les produits, exposants et atomes.
Donc c'est normal que 2*a soit compris comme la somme d'un seul élément, gros produit entre 2 et a. Le parser passe par somme() avant d'arriver dans produit() et c'est tout à fait normal car tu ne sais pas à l'avance que c'est un produit (au début tu ne vois que le 2 !) donc tu pares à tous les possibilités en appelant la méthode grammaticale la plus générale pour les expressions.
Maintenant, c'est sûr que somme() pourrait se rendre compte qua s'il n'y a qu'un objet dans la somme ça ne sert à rien de créer le noeud. Tout comme dans la règle atome -> LPAR somme RPAR on ne perd pas de temps à créer de noeud et on renvoie directement celui de somme(), ici on peut faire pareil.
produits = [self.produit()]
while self.token_ahead.type in ("PLUS", "MINUS"):
t = self.expect()
p = self.produit()
if t.type == "MINUS":
p = Node("Operation", "--", at)
produits.append(p)
if len(produits) == 1:
return produits[0]
else:
return Node("Operation", "+", *produits)
Citer : Posté le 09/06/2020 09:08 | #
Ouaip, je comprend, mais le moins en tant qu'opérateur à la priorité sur le moins unaire… par exemple :
--- Tokens ---
('NUM', 2)
('MULTI', '*')
('LPAR', '(')
('VAR', 'a')
('MINUS', '-')
('NUM', 9)
('RPAR', ')')
--- AST ---
Operation : *
Number : 2
Operation : +
Variable : a
Operation : -
Number : 9
Au niveau de l'AST, je me serais attendu à avoir un truc plutôt comme ça :
Variable : a
Number : -9
Ajouté le 09/06/2020 à 09:12 :
Je peux forcer le moins unaire en renversant l'expression :
--- Tokens ---
('MINUS', '-')
('NUM', 2)
('PLUS', '+')
('VAR', 'a')
--- AST ---
Operation : +
Number : -2
Variable : a
En fait la vraie question c'est : Est-ce que le fait d'avoir un nœud Operation avec un seul enfant ça ne va pas me poser des problèmes ?
Citer : Posté le 09/06/2020 09:54 | #
Ce n'est pas vraiment une question de priorité. La chose importante c'est que la seule façon de lire a-2 avex ta grammaire c'est de mettre le - dans la règle de somme. Il n'y a aucune "chaîne de dérivation" (si tu te souviens de cette notion) qui parte de somme et arrive à a-2 et qui traite le moins comme un moins unaire.
Tu peux avoir ça, mais faut pas essayer de le faire dans le parser. Pour ton information, l'arbre en sortie du parser s'appelle en fait un CST (Concrete Syntax Tree) et l'AST (Asbtract Syntax Tree) est souvent obtenu en simplifiant le CST.
Si tu veux, je peux te montrer comment programmer une fonction qui fait ce genre de simplifications dans l'AST. C'est un exemple simple de comment on utilise un AST et ça ouvre sur des sujets passionnants sur la transformation de programmes !
Morale de l'histoire : tant que ton parser produit des choses justes, t'embête pas à vouloir faire des simplifications élaborées tout de suite, tu pourras le faire après.
Non, ça te posera aucun problème. Regarde en Python, tu fais sum([2]) ça fait 2. Aucun problème.
Si tu veux, tu peux éliminer les noeuds à une opération dans l'étape de simplification après le parser. Ici, tu peux même l'éliminer directement dans le parser de la façon que j'ai décrite tout à l'heure en testant si len(produits) == 1. Mais dans tous les cas, garder des noeuds de taille 1 n'est absolument pas un problème.
Citer : Posté le 09/06/2020 09:56 | #
Okay !
Bah du coup j'ai un code pour le parser qui ressemble à ça :
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, minus = False):
atm = self.expect(["VAR", "NUM", "LPAR", "MINUS"])
if atm.type == "MINUS": return self.atome(not minus)
elif atm.type == "VAR":
return (Node("Variable", atm.value), Node("Operation", "--", Node("Variable", atm.value)))[minus]
elif atm.type == "NUM":
return Node("Number", (atm.value, -atm.value)[minus])
else:
e = self.sum()
self.expect("RPAR")
return (e, Node("Operation", "--", e))[minus]
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), atomes[0])[len(atomes) == 1]
def product(self):
atome_1 = self.exp()
if self.token_ahead.type not in ("MULTI", "DIVI"):
return atome_1
op = self.expect()
product_1 = self.product()
return Node("Operation", op.value, atome_1, product_1)
def exp(self):
atome_1 = self.atome()
if self.token_ahead.type != "EXP":
return atome_1
op = self.expect()
atome_2 = self.atome()
return Node("Operation", op.value, atome_1, atome_2)
Citer : Posté le 09/06/2020 11:47 | #
Pas mal ! Abuse pas de (x,y)[condition] par contre, c'est vraiment pas lisible et ça t'oblige à calculer les deux valeurs alors que tu vas en utiliser qu'une.
À la limite, y if condition else x fait pareil.
Il faut encore modifier product() pour faire comme somme() histoire que a/b/c passe correctement, en introduisant un réciproque (l'opération 1/x) comme on a introduit le moins unaire (l'opération 0-x).
Citer : Posté le 09/06/2020 11:52 | #
Ok, je retouche le coup des conditions
J'ai pas trop compris pourquoi a/b/c ne passerait pas… ? Le coup du moins unaire c'est pour la confusion entre les nombres négatifs et l'opérateur de soustraction ?
Citer : Posté le 09/06/2020 11:59 | #
Non, le moins unaire c'est parce que la forme récursive de somme() produit des parenthèses à droite : a+b+c+d est lu comme a+(b+(c+d)). Ce n'est pas un problème pour plus, mais c'est un problème pour moins : a-b-c-d n'est *pas* a-(b-(c-d)) !
Introduire le moins unaire permet de développer somme() sous forme de boucle et donc d'éliminer ce petit problème.
De la même façon a*b*c*d est actuellement lu a*(b*(c*d)) ce qui est est acceptable, mais a/b/c/d est lu a/(b/(c/d)), et ça c'est faux ! Il faut donc développer produit() sous forme de boucle, et on utilisera un opérateur 1/x ("division unaire") là où on avait utilisé le moins unaire dans somme().
Citer : Posté le 09/06/2020 12:00 | #
Okay, je vois le problème
Ajouté le 09/06/2020 à 14:20 :
J'ai essayé des trucs, j'ai ça en sortie :
--- Tokens ---
('VAR', 'a')
('DIVI', '/')
('VAR', 'b')
('DIVI', '/')
('VAR', 'c')
--- AST ---
Operation : /
Variable : a
Operation : /
Variable : b
Variable : c
Citer : Posté le 09/06/2020 14:21 | #
Ah mais ça c'est faux !