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 157 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 02/06/2020 08:41 | #
Aha c'est ça que j'ai pas
Pour l'AST, j'ai effectivement confondu les Nodes et les Branchs, je corrige ça en même temps que je supprime l'objet inutile !
Du coup je ré-essaye de repartir sur un truc plus académique avec token_ahead et expect
Ajouté le 02/06/2020 à 09:07 :
J'ai compris le problème de token_ahead et expect… je vais essayer d'expliquer, mais je promet rien xD
En gros mes tokens c'est ça :
+-----+ +-----+ +-----+
X | VAR | | + | | VAR |
+-----+ +-----+ +-----+
Avec X le token_ahead au tout début, avant le parser.
- Initialisation du parser, token_ahead regarde VAR et renvoie rien.
- atome_1 = parser.atome() là on a un problème token_ahead regarde + et renvoie une erreur syntaxe car il attend VAR.
- Arrêt de l'exécution
Si je n'initialise par token_ahead :
- atome_1 = parser.atome() : token_ahead passe sur VAR, tout va bien c'est ce que l'on attend, mais cela renvoie le token précédent, soit un magnifique… None.
- la valeur de atome_1 ne veut plus rien dire, et même si je n'ai pas d'erreurs par la suite, c'est complètement inexploitable…
Citer : Posté le 02/06/2020 11:35 | #
Tu n'as pas tout à fait compris le mécanisme du lookahead. Le lookahead est testé par expect avant d'être avancé.
Dans VAR + VAR, tu initialises le lookahead et donc tu as lookahead=VAR, suivi de + VAR.
Donc là tu lances atome(), qui appelle expect([VAR]). On a bien lookahead=VAR, donc ça passe, et on renvoie le token VAR. En même temps on avance le lexer, et maintenant lookahead=+, suivi de VAR.
Donc là tu as un atome, et ensuite somme() va prendre le relais pour lire le +. Et ainsi de suite.
Citer : Posté le 02/06/2020 11:36 | #
Donc dans expect, j'ai inversé l'ordre des opération en fait ?
Citer : Posté le 02/06/2020 12:20 | #
Yup. Pour rappel :
t = lookahead
lookahead = get_next_token()
if valid_tokens != [] && t[0] not in valid_tokens:
raise SyntaxError("expected one of " + ", ".join(valid_tokens))
return t
Citer : Posté le 02/06/2020 13:13 | #
Ah c'est t que l'on teste !! C'est ça que j'avais pas x) Merci !
Ajouté le 03/06/2020 à 08:27 :
Maintenant que la règle de grammaire pour la somme est codée (de manière non récursive), je vais étendre la fonction à toutes les opération mathématiques : divisions, soustractions, multiplication, puissance. et après rendre tout ça récursif.
Citer : Posté le 03/06/2020 08:34 | #
Parfait ! Hésite pas à me montrer ta grammaire et ton code une fois que t'auras fait ça
Citer : Posté le 03/06/2020 08:38 | #
Ouaip !
Ajouté le 03/06/2020 à 08:52 :
Le code pour la règle de grammaire (non récursive pour le moment) :
expr_backward.append(parser.atome())
expr_backward.append(parser.expect(["OPTR"]))
expr_backward.append(parser.atome())
return Node("Operation", expr_backward[1].value, Node(("Variable", "Number")[expr_backward[0].value.isdigit()], expr_backward[0].value), Node(("Variable", "Number")[expr_backward[2].value.isdigit()], expr_backward[2].value))
Et le code complet est là : https://gitea.planet-casio.com/Shadow/Compylateur/src/branch/master/Compylateur.py
Citer : Posté le 03/06/2020 09:13 | #
Wow. Il y a deux-trois choses à modifier là-dedans. xD
D'abord, tu t'y prends pas dans le bon ordre. Tu dois *d'abord* écrire la grammaire et *ensuite* écrire la fonction qui l'implémente. Ici, la grammaire que tu as codée c'est ça :
ce qui est intéressant mais pas trop (et c'est pas une règle qu'il y aura dans ta grammaire finale). N'aies pas peur de la récursion, elle va apparaître toute seule et tu n'auras rien à faire. Par exemple une fois que tu as défini expr tu peux redéfinir atome pour rajouter les parenthèses :
et pouf ça devient récursif (une expr peut contenir un atome qui peut contenir une expr entre parenthèses). Ça change rien à la façon d'écrire les fonctions.
Ensuite, expr est un symbole de ta grammaire donc la fonction expr() doit être une méthode de ton parser. Je sais pas ce que t'es parti inventer... et je vois pas du tout ce que tu fais avec une variable expr_backward, c'est hyper étrange. C'est simple : tous les symboles de ta grammaire ont une méthode associée dans la classe Parser qui lit une instance du symbole dans le flux de tokens.
Enfin, dans la façon dont tu construis ton Node final, il y a plusieurs problèmes. D'abord toutes les méthodes grammaticales doivent renvoyer des noeuds d'AST, donc il est temps de modifier atome() pour qu'il renvoie un Node qui va bien. Tu ne dois surtout pas créer dans expr() le noeud correspondant à atome() parce que seul atome() est capable de décider ce que ça doit être.
Donc là ton code il devrait plutôt ressembler à ça :
(...)
def atome(self):
t = self.expect(["VAR", "NUM"])
if t.type == "NUM": # ou [if t.value.isdigit()] mais c'est douteux
return Node("Num", t.numerical_value)
elif t.type == "VAR":
return Node("Var", t.variable_name)
def expr(self):
atome1 = self.atome()
optr = self.expect(["OPTR"])
atome2 = self.atome()
return Node("Operation", optr.value, atome1, atome2)
La méthode est hyper systématique, y'a aucune déviation possible.
1. Tu écris la grammaire d'abord.
2. Pour chaque symbole, tu écris une méthode grammaticale. La méthode grammaticale est une méthode du parser qui ne prend aucun paramètre d'entrée, qui lit une instance du symbole dans le flux de tokens et qui la renvoie sous forme d'AST.
→ Donc là tu devrais renvoyer un AST dans atome() et plus un token (c'était ok tant que tu testais mais plus maintenant).
→ Et ensuite expr() doit être une méthode de la classe Parser.
3. La méthode applique les règles de production à la lettre en lisant dans l'ordre les tokens et/ou symboles et en choisissant les règles à appliquer selon la valeur du lookahead.
Je sais que j'ai l'air chiant comme ça mais y'a quasiment qu'une seule façon de faire ! Une fois que t'as saisi le schéma ça va beaucoup mieux.
Citer : Posté le 03/06/2020 09:45 | #
J'ai retouché le code !
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"])
return Node(("Variable", "Number")[atm.type == "NUM"], atm.value)
def expr(self):
atome_1 = parser.atome()
operator = self.expect(["OPTR"])
atome_2 = parser.atome()
return Node("Operation", operator.value, atome_1, atome_2)
Du coup le parser est entièrement dans sa classe.
En fait j'ai du mal à écrire la grammaire, et ensuite à la coder… par exemple dans le cas des opérations operation -> atome OPTR atome la règle devient : operation -> atome | operation OPTR atome avec récursion ?
Après là atome gère juste variable / nombre. L'idéal serait qu'il gère les parenthèses en même temps ? Du coup on aurai une grammaire : atome -> VAR | NUM | PRTH atome PRTH ?
Le problème c'est pas que ce soit chiant, c'est que j'arrive pas à le conceptualiser
Citer : Posté le 03/06/2020 10:28 | #
Il y a plein de façons d'avoir de la récursion. En fait, avec une gramaire, la flèche signifie que tu peux "construire" ou "remplacer". Donc par exemple avec la grammaire suivante qui représente des expressions arithmétiques avec parenthésage explicite :
atome -> INT | ( expr )
Tu peux écrire la "chaîne de production" expr -> atome OPTR atome -> INT OPTR atome [utilisation de atome -> INT] -> INT OPTR ( expr ) [utilisation de atome -> ( expr )]. Et là comme tu as expr à la fois à gauche et à droite, c'est récursif.
Évidemment si tu as une règle expr -> atome OPTR expr c'est récursif aussi et ça se voit tout de suite !
La question n'est pas tellement "comment est-ce que je rends récursif" ? La question est plus simple que ça, il suffit de se demander "qu'est-ce qu'une expression arithmétique ?". Je vais commencer par plus simple avec "qu'est-ce qu'une produit" ? C'est quand on multiplie ou divise plusieurs facteurs ensemble. L'idée derrière c'est de gérer les priorités opératoires, donc je veux pouvoir reconnaître des trucs du genre a*b/c*4 comme un seul produit.
Donc j'ai des atomes séparés par des * et des /. On sait pas trop combien il y en a à l'avance, mais on peut au moins commencer par prendre un atome et ensuite voir s'il se fait multiplier ou diviser. Ça nous donne :
atome -> VAR | NUM
La raison pour laquelle tu as "produit" derrière le FOIS et le DIVISION c'est que pour gérer les cas comme a*b/c*4. En effet, regarde la "chaîne de production" que je peux obtenir :
-> VAR(a) FOIS produit
-> VAR(a) FOIS atome FOIS produit
-> VAR(a) FOIS VAR(b) FOIS produit
-> VAR(a) FOIS VAR(b) FOIS atome DIVISION produit
-> VAR(a) FOIS VAR(b) FOIS VAR(c) DIVISION produit
-> VAR(a) FOIS VAR(b) FOIS VAR(c) DIVISION atome
-> VAR(a) FOIS VAR(b) FOIS VAR(c) DIVISION INT(4)
Comme tu peux le voir, à chaque ligne j'ai appliqué une règle de la grammaire pour remplacer un symbole par une des façons de le créer. Le produit qui reste quand on étend "produit -> atome FOIS produit" ou "produit -> atome DIVISION produit" permet de continuer à rajouter des facteurs jusqu'à ce qu'on en ait assez et qu'on termine avec "produit -> atome" !
Oui ! Mais mieux encore ! Dans des parenthèses tu peux mettre n'importe quoi, n'est-ce pas ? Là tu n'autorises que des atomes dedans, donc tu es coincé avec (a) ou (4) ou ((((b)))). Tu ne peux pas écrire (a + b) parce que l'atome entre les parenthèses ne peut pas être a+b.
En fait entre les parenthèses, tu peux mettre n'importe quelle expression ! Donc ta règle ce serait (et je distingue les parenthèses ouvrantes et fermantes, ça peut être utile) :
Et tu peux voir que la récursion apparaît de nouveau parce qu'on a la "chaîne de production"
Et c'est bien normal ! La récursion c'est ce qui fait la puissance des grammaires et c'est ce qui fait qu'on peut mettre des sommes dans des parenthèses dans des sommes et des if dans des while dans des if.
Citer : Posté le 03/06/2020 13:12 | #
Ah ok… je commence à comprendre, mais je prend un temps de fou a digérer toute ces infos
Dans l'idée, il faut que atome gère les parenthèses. Donc j'ai :
atome -> VAR | NUM | PRTH expr PRTH
expr -> atome OPTR atome
et comme atome peut être PRTH expr PRTH j'ai bien un truc récursif…
Citer : Posté le 03/06/2020 13:25 | #
Voilà très bien (pourvu que tu acceptes pas deux parenthèses ouvrantes autour de l'expression) ! C'est l'idée. Après tu rajoutes des couches, les atomes forment des puissances, qui forment des produits, qui forment des sommes, qui forment des expressions. C'est la façon "manuelle" de faire les priorités opératoires.
Citer : Posté le 03/06/2020 18:27 | #
Le coup des parenthèse, j'ai le type de token PRTH qui prend parenthèses, crochets, accolades, après, faut voir la valeur pour être sûr
Citer : Posté le 03/06/2020 19:15 | #
C'est pas très pratique parce que du coup la fonction atome() va devoir décider si oui ou non il y a une erreur de syntaxe selon si le type de parenthèse est correct, alors que c'est plus facile de distinguer les tokens et de laisser expect() émettre une erreur si ça matche pas. Mais pas de pression, tu fais comme tu préfères.
Citer : Posté le 03/06/2020 19:55 | #
Je ne voyais pas comment intégrer la gestion des parenthèses dans le lexer… Et faire une multitude de règles grammaticales pour les parenthèses me rebute un peu… ^^' Mais c'est pas très dur de vérifier la valeur, à la limite, on ne peut même vérifier que ça… si la parenthèse est dans du texte, elle ne sera pas seule, il y aura au moins les guillemets avec…
Citer : Posté le 03/06/2020 20:57 | #
Il n'y a aucune différence entre une multitude de règles grammaticales et une multitude de valeurs... normalement les valeurs ne sont utilisées que dans les cas où il y a une infinité de possibilités, eg. pour les entiers, les noms de variables, ou les chaînes de caractères. Même le symbole OPTR c'est un problème parce que tu ne peux pas distinguer plus/moins de fois/division, alors que tu en as besoin dans tes règles.
En gros une règle simple est la suivante : si tu as une règle de grammaire qui utilise un token T mais n'accepte qu'une partie des tokens de type T, alors tu as un problème, et il vaut mieux séparer T pour que la règle dispose d'un token T' qui représente tout ce qu'elle accepte et uniquement ce qu'elle accepte.
Comme tu le dis c'est "pas dur" de vérifier la valeur... sauf qu'en fait si, c'est inutilement dur. Regarde la différence entre les deux versions de atome() selon les parenthèses. Voici la version où tu ne distingues pas les parenthèses :
t = self.expect(["VAR", "NUM", "PRTH"])
if t.type == "VAR":
return Var(t.variable_name)
elif t.type == "NUM":
return Num(t.numerical_value)
elif t.type == "PRTH":
if t.parenthesis != "(":
raise SyntaxError("expected VAR, NUM or (")
e = self.expr()
t = self.expect("PRTH")
if t.parenthesis != ")":
raise SyntaxError("expected )")
return e
On peut même imaginer un cas un peu plus tordu où la parenthèse fermante est optionnelle et dans ce cas tu peux même pas écrire t = self.expect("PRTH") parce que si le token n'est pas celui que tu attends, mais quand même valide vu que la parenthèse est optionnelle, et faut utiliser directement le lookahead.
Alors que si tu notes différemment les parenthèses, ça donne ça :
t = self.expect(["VAR", "NUM", "LPAR"])
if t.type == "VAR":
return Var(t.variable_name)
elif t.type == "NUM":
return Num(t.numerical_value)
elif t.type == "LPAR":
e = self.expr()
self.expect("RPAR")
return e
Crois-moi dupliquer les messages d'erreur partout ça va être vraiment chiant dans le temps !
Si la parenthèse est dans une chaîne de caractère par exemple a="hey(maybe)", alors tu auras que le token de la chaîne de caractères du type STRING et de valeur "hey(maybe)", il n'y a aucune parenthèse du tout.
De façon générale t'as rien à gagner à mélanger les parenthèses/crochets/accolades parce que tu peux jamais en remplacer un par un autre. Séparer coûte zéro sur le lexer et simplifie le parser. Avoir une poignée de noms de tokens en plus on s'en fout complètement aussi en général.
Citer : Posté le 04/06/2020 08:18 | #
Ah oui, ok, je vois le problème…
Mais alors c'est mon lexer qui est mal fai : j'ai un ensemble par token… x) Parce que si je dois séparer ( et ) dans tes tokens différents je vais avoir ça dans le code :
RPAR = {")"}
Il doit y avoir un autre moyen de penser le lexer pour qu'il soit plus souple ?
Citer : Posté le 04/06/2020 09:23 | #
Traditionnellement un lexer utilise des regex pour représenter les chaînes de caractères qui constituent chaque token. Tu peux pas faire la liste de tous les entiers ou noms de variables de toute façon. Ce qui ne t'empêche pas d'avoir des cas triviaux comme les symboles de ponctuation qui n'ont qu'une forme possible d'un seul caractère.
Citer : Posté le 04/06/2020 10:16 | #
Des regex… ?
Là mon lexer c'est ça :
# Lexer
# ==================================================
# --- Main function --- #
def lexer(prgm_src):
var_type = {"des réels", "un réel", "des entiers", "un entiers", "un entier naturel", "des entiers naturels", "un entier relatif", "des entiers relatifs", "une liste", "des listes", "un flottant", "des flottants", "une chaîne de caractères", "des chaînes de caractères"}
cmnd = {"fin", "finsi", "fin si", "fintantque", "fin tantque", "fin tant que", "finpour", "fin pour", "afficher", "si", "alors", "sinon", "tant que", "tantque", "pour"}
optr = {"+", "-", "/", "*", "^"}
sptr = {"et", "\n", "à", "entre", "de", ",", ";", "faire", "(", ")", "[", "]", "{", "}"}
comp = {"=", "<", "<=", ">", ">=", "est supérieur à", "est supérieur ou égal à", "est inférieur à", "est inférieur ou égal à", "est différent de", "est égal à"}
user = {"saisir", "saisir la valeur de", "saisir les valeurs de", "demander la valeur de", "demander à l'utilisateur la valeur de"}
logi = {"et que", "ou que"}
assi = {"prend la valeur", "sont", "est"}
rang = {"allant", "variant"}
for i in {"=", "<", "<=", ">", ">=", "+", "-", "/", "*", "^", "(", ")", "[", "]", "{", "}", '"', "\n", ",", ";"}:
prgm_src = prgm_src.replace(i, " " + i + " ")
word = [i for i in prgm_src.lower().split(" ") if i != ""]
l_token = TokenList()
index, undef = 0, bool()
token = (var_type, cmnd, optr, comp, user, logi, assi, sptr, rang)
name = ("TYPE", "CMND", "OPTR", "COMP", "USER", "LOGI", "ASSI", "SPTR", "RANG")
while True:
undef = True
for j in range(len(token)):
for k in token[j]:
target = k.split(" ")
if index >= len(word): return l_token
if word[index] in target and lexer_detect(word, index, target):
l_token.add(Token(name[j], k))
undef = False
index += len(target)
if undef and word[index] == "\"":
l_token, index = text_detecter(word, index, l_token)
elif undef:
l_token.add(Token(("VAR", "NUM")[word[index].isdigit()], word[index]))
index += 1
# --- Secondary functions --- #
def lexer_detect(word, index, target):
try:
return not 0 in [target[i] == word[i + index] for i in range(len(target))]
except:
return 0
def text_detecter(word, index, l_token):
txt = word[index]
index += 1
while word[index] != '"':
txt = txt + " " + word[index]
index += 1
l_token.add(Token("TEXT", txt + ' "'))
return l_token, index + 1
Citer : Posté le 04/06/2020 15:11 | #
Et comment tu détectes les entiers là-dedans ? ^^"
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]))