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 64 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 18/05/2020 16:00 | #
Ah ok, merci !
Ajouté le 27/05/2020 à 13:42 :
J'ai bien avancé le lexer… il me reste la gestion des intervalles qui n'est pas du tout implémentée
Je ne met pas le code ici (trop gros) par contre il est dispo sur le git : https://gitea.planet-casio.com/Shadow/Compylateur/src/branch/master/Lexer.py
Un exemple de tokens générés : sur cette ligne Si a est égal à b ou que c est supérieur ou égal à a j'obtient :
('UNDEF', 'a')
('COMP', 'est égal à')
('UNDEF', 'b')
('LOGI', 'ou que')
('UNDEF', 'c')
('COMP', 'est supérieur ou égal à')
('UNDEF', 'a')
(là je met sur différentes lignes pour la lisibilité, en pratique c'est une liste
Citer : Posté le 27/05/2020 13:56 | #
Oh, pas mal du tout. Le "que" n'a pas grand-chose à faire dans ta phrase mais c'est stylé !
Citer : Posté le 27/05/2020 13:57 | #
C'est plus français en fait
Ajouté le 27/05/2020 à 16:31 :
Le coup du que dans le token ça permet des affectations multiples
Le code suivant : a et b sont des entiers naturels me renvoie :
('SPTR', 'et')
('UNDEF', 'b')
('ASSI', 'sont')
('TYPE', 'des entiers naturels')
Ajouté le 28/05/2020 à 08:12 :
Le parser est très loin d'être au point, mais je commence à y réfléchir
Pour l'arbre je partirai plutôt vers un truc récursif
Chaque branche fille a plusieurs caractéristique : Titre, Valeur et Branches filles (de type Branch)… et ainsi de suite
Ça c'était pour le modèle de l'AST retourné par le parser. Avec le nouveau lexer, il faut que je refasse une grammaire complète… du coup je vais commencer à l'attaquer !
Citer : Posté le 28/05/2020 08:56 | #
L'AST est forcément récursif, mais tu ne peux pas avoir que 2 niveaux (AST → Branche). Normalement chaque noeud de l'AST a un rôle (expression, boucle, assignment, etc) correspondant aux différents symboles de ta grammaire, et chaque noeud a des enfants qui sont aussi des noeuds d'AST.
Citer : Posté le 28/05/2020 09:02 | #
Ouaip j'était partit sur un modèle comme ça
J'ai essayé d'afficher l'AST avec des tabulations, sur un exemple simple j'ai ça :
value : while
title : condition
value : <
title : var
value : a
title : num
value : 5
title : assign
value : expr_to_var
title : var
value : a
title : expr
value : a - 1
Pour le code : while a < 5: a -= 1
Pour l'instant c'est théorique, j'ai rempli l'AST à la main
Citer : Posté le 28/05/2020 09:05 | #
Pas mal ! Il manque une seule chose : le while devrait avoir en arguments une condition et un "bloc" (ie une *liste*) d'instructions, une seule ne peut pas suffire. Ton expr_to_var devrait probablement s'appeler "assign" mais comme tu préfères. a-1 devrait être un noeud de soustraction avec a d'un côté et 1 de l'autre, ou une addition avec a et -1, selon tes goûts. Pareil, les opérandes de < devraient être des expressions, contenant pour a une variable, et pour 5 un noeud d'entier constant.
Citer : Posté le 28/05/2020 09:08 | #
Okay… donc je peux subdiviser encore l'AST
Pour l'instant c'est encore très théorique, je ne vois pas encore dans quel sens je vais le remplir
Citer : Posté le 28/05/2020 09:11 | #
quand je remplis à la main, je commence par la fin et j'ajoute les sous-branches aux branches avant de relier les branches à l'arbre…
Donc tu réfléchis comme un parser LR
Citer : Posté le 28/05/2020 09:13 | #
Ah… ? Et c'est comme ça qu'il faut faire ? Ou ma méthode est inapplicable en conditions réelles ?
Citer : Posté le 28/05/2020 09:18 | #
Eh bien... les parsers "bottom-up" comme les parsers LR appliquent les règles de grammaire de bas en haut : ils commencent par construire des petits groupes comme des variables ou des expressions, puis des choses plus grosses comme des boucles, et ainsi de suite jusqu'à avoir tout le programme.
Les parsers "top-down" comme les parsers LL font exactement le contraire, et décident dès qu'ils aperçoivent un token spécifique comme "Pour tout" qu'une boucle for doit avoir lieu, et s'intéressent ensuite seulement à trouver les expressions et les variables dedans.
Sans rentrer dans les détails, les deux ne permettent pas de parser les mêmes grammaires, mais la grammaire d'un langage de programmation comme le tien sera facile et tu pourras utiliser celui que tu veux.
Cependant, les parsers LR sont fait pour être générés automatiquement parce que c'est imbitable à écrire à la main, c'est des automates. Si tu veux écrire ton parser à la main, il est bien mieux de partir sur un parser LL.
Citer : Posté le 28/05/2020 09:21 | #
Okay, c'est vrai que le LL à l'air plus intuitif
Pour l'instant je viens de me rendre compte que j'ai un problème sur mon lexer…
Citer : Posté le 28/05/2020 09:24 | #
Yup, perso mon AST a une propriété "args" (un array d'AST) et "children" (un array d'AST aussi), les "children" sont les lignes appartenant à un AST (dans le cas d'un if, while, for, etc).
Ecrivez vos programmes basic sur PC avec BIDE
Citer : Posté le 29/05/2020 08:41 | #
Pour le lexer (encore et toujours
Pour ce code :
u prend la valeur 2
n prend la valeur 0
Tant que u<A
n prend la valeur n+1
u prend la valeur 3*n^2+2
Fin Tant que
Afficher n
J'ai la liste :
('UNDEF', 'a')
('SPTR', '\n')
('UNDEF', 'u')
('ASSI', 'prend la valeur')
('NUM', '2')
('SPTR', '\n')
('UNDEF', 'n')
('ASSI', 'prend la valeur')
('NUM', '0')
('SPTR', '\n')
('CMND', 'tant que')
('UNDEF', 'u')
('COMP', '<')
('UNDEF', 'a')
('SPTR', '\n')
('UNDEF', 'n')
('ASSI', 'prend la valeur')
('UNDEF', 'n')
('OPTR', '+')
('NUM', '1')
('SPTR', '\n')
('UNDEF', 'u')
('ASSI', 'prend la valeur')
('NUM', '3')
('OPTR', '*')
('UNDEF', 'n')
('OPTR', '^')
('NUM', '2')
('OPTR', '+')
('NUM', '2')
('SPTR', '\n')
('CMND', 'fin tant que')
('SPTR', '\n')
('CMND', 'afficher')
('UNDEF', 'n')
Ajouté le 29/05/2020 à 09:24 :
Pour la grammaire j'ai trouvé un système sous forme de dictionnaire :
Les clefs sont le type du token (CMND, COMP…) et les items sont les valeurs acceptées. Par exemple pour un test conditionnel, j'aurait CMND comme type de token avec 'si' en valeur : test = {"CMND":("si")}
Pour une comparaison : comparaison : {"UNDEF":(None), "COMP":("=", "<", "<=", ">", ">="), "UNDEF":(None)} c'est encore bancal, mais dans l'idéal None permettrait de tout accepter…
Après faut que j'y réfléchisse encore, mais je pense faire comme Zez a dit
{UNDEF | NUM}
Et du coup un truc dans le code un peu comme ça (là c'est incomplet
expr = {"UNDEF":(None), "OPTR":("+", "-", "/", "*", "^"), "UNDEF":(None)}
Citer : Posté le 29/05/2020 17:30 | #
Wow, euh ça ne se code pas comme ça une grammaire. Tu peux improviser, mais ton parser sera mauvais à la sortie, garanti (y'a qu'à regarder celui de ZZ <3).
Tu as deux options pas trop compliquées :
1. Utiliser un générateur de parser auquel tu donnes la grammaire sous forme quasi-formelle et qui génère le code ;
2. Écrire un parser top-down avec des fonctions récursives.
Je peux te montrer des exemples des deux, mais c'est des choses très codifiées que tu peux pas laisser au hasard.
Citer : Posté le 30/05/2020 13:12 | #
Je n'utilise que mon code sur ce projet
Pour le sens du haut vers le bas me semble le plus logique
Pour le côté récursif, autant au niveau du code de l'arbre c'était évident, autant là je vois moins bien comment ça marche…
Citer : Posté le 30/05/2020 14:17 | #
Je n'utilise que mon code sur ce projet
Pas de souci.
Les parsers courants lisent tous les tokens une seule fois du début à la fin, donc oui faut pas revenir en arrière.
En gros pour chaque symbole comme expr tu auras une fonction genre expr() qui va lire une expression dans le flux de tokens et renvoyer le résultat.
Par exemple, avec la grammaire classique pour l'arithmétique, qui ressemble à ça (on note traditionnellement les tokens en majuscules et les symboles de grammaire en minuscules) :
somme -> produit | produit PLUS somme
Tu auras deux fonctions récursives en plus de la fonction expect() qui est utilisée pour obtenir le token suivant et du lookahead dont j'ai parlé avant, qui est le token suivant (on s'autorise à regarder un peu devant pour prendre des décisions).
lookahead = get_next_token()
# Renvoie le prochain token en vérifiant qu'il est du bon type (le nom "expect" est classique)
# Si valid_tokens = [], on accepte tout (pour simplifier)
# Gère aussi le lookahed
def expect(valid_tokens = []):
# Récupère le lookahead (puisque c'est le prochain) et le remplacer
t = lookahead
lookahead = get_next_token()
# Vérifier le type
if valid_tokens != [] && t.type not in valid_tokens:
raise SyntaxError("expected one of " + ", ".join(valid_tokens))
# Et on renvoie
return t
# Lit une somme
def somme():
# D'abord on veut un INT
i1 = expect([INT])
# Ensuite si le lookahead est PLUS, on utilise somme -> INT PLUS somme
# Sinon, on utilise somme -> INT
if lookahead.type != PLUS:
return Somme(i1)
# On lit le plus
expect([PLUS])
# Et ensuite on lit une autre somme
s = somme()
return Somme(i1, s)
# Ici, c'est tout pareil, on gère deux règles : produit -> somme et produit -> somme FOIS somme
# On décide pas tout de suite laquelle on va appliquer
def produit():
# On récupère une somme
s1 = somme()
# Ensuite si le lookahead n'est pas FOIS, on laisse tomber
if lookahead.type != FOIS:
return Produit(s1)
# Si c'est FOIS, on le lit et on récupère un autre produit
expect([FOIS])
p = produit()
return Produit(s1, p)
Citer : Posté le 30/05/2020 14:28 | #
Donc ma grammaire va se présenter sous la forme d'une suite de fonction…
Ça met aussi en évidence que je dois faire un objet token ? avec type ?
J'ai très bien compris le coup de
somme -> produit | produit PLUS somme
Pour quoi INT | INT FOIS produit ? le premier INT correspond à quoi ? au résultat attendu… ?
Pourquoi faire des trucs récursifs… ? Pour somme à la fin tu va voir la prochaine somme… ? Mais entre les deux sommes il y a d'autres instructions… ? Ou alors c'est pour parer aux cas comme : a+2+b ?
Une subtilité en terme de connaissance Python : raise SyntaxError("expected one of " + ", ".join(valid_tokens)) le raise stop l'execution… ? (je connais pas du tout… )
Citer : Posté le 30/05/2020 14:54 | #
Ta grammaire ça reste le truc formel où tu écris chaque règle avec des flèches, mais le parser oui c'est des fonctions récursives.
Le premier c'est le A dans A×B. Un produit c'est deux opérandes. Dans A×B×C×D tu vas obtenir Produit(A,Produit(B,Produit(C,D))) par exemple.
Non, le somme() à la fin de ne va pas voir la "prochaine somme". N'oublie pas, on lit les tokens une fois chacun et dans l'ordre. Si je passe là c'est que je sais que derrière INT PLUS j'ai encore des éléments dans ma somme. C'est donc bien le cas de a+2+b+etc. Tu pourrais aussi faire une boucle mais on se précipite pas, pour l'instant on fait la grammaire exactement comme elle est écrite.
Ça balance une exception, comme quand tu interromps le programme au clavier, que tu accèdes en-dehors des bornes d'un tableau, que tu divises par zéro, etc. Si tu rattrapes pas exprès l'exception avec un try ailleurs ça arrête le programme.
Citer : Posté le 30/05/2020 15:05 | #
Je crois que j'ai toujours pas compris… xD Pourquoi on écrit pas tout simplement : produit -> INT FOIS INT ?
Je crois que j'ai pas d'autre questions pour l'instant… Merci beaucoup !!
Citer : Posté le 30/05/2020 15:36 | #
Parce que 2×3×4 est un produit !
Citer : Posté le 30/05/2020 16:12 | #
Ah je crois que je viens de comprendre… c'est produit = INT la première fois est après on prend le modèle récursif produit = INT FOIS produit ?
Du coup toute ma grammaire va être définie par : nom_pattern -> SIMPLE | RECURRENCE ?