#Parsing (analyse syntaxique)Copier le lien

Objectifs d'apprentissage

• Écrire une grammaire non ambiguë en EBNF et coder la descente récursive correspondante.
• Encodrer précédence et associativité par niveaux de règles plutôt que par tables.
• Distinguer AST et CST, et conserver les positions source pour les diagnostics.

Prérequis: page Lexing (les tokens fournis par tokenize) et vocabulaire de grammaires hors contexte (dérivations, arbres).

#Grammaire du langage ExprCopier le lien

Une grammaire pour les expressions arithmétiques avec variables s'écrit en EBNF ({...} = zéro ou plus répétitions):

1program  = stmt { ";" stmt } [ ";" ] ;2stmt     = "let" ID "=" expr | ID "=" expr | expr ;3expr     = term { ("+" | "-") term } ;      (* niveau basse précédence *)4term     = factor { ("*" | "/") factor } ;  /* niveau haute précédence */5factor   = NUM | ID | "(" expr ")" | "-" factor ;

La structure en cascade expr → term → factor n'est pas décorative: elle est la précédence. Comme term apparaît sous + dans expr, toute multiplication se construit plus bas dans l'arbre, donc se compose avant l'addition lors de l'évaluation. L'associativité vient de la récursion à gauche: a-b-c se parse comme (a-b)-c.

#Descente récursive: une fonction par non-terminalCopier le lien

Chaque règle devient une méthode qui consomme des tokens. Le code suit la grammaire ligne à ligne; en cas d'écart, l'erreur signale le token attendu et le token trouvé.

Trois vérifications rapides à garder en tête:

• 2*(3+4) - 5 doit mettre la soustraction à la racine: la précédence est correcte.
• 10 - 3 - 2 doit imbriquer à gauche (vaut 5): l'associativité gauche est correcte.
• 2 +* 3 doit lever SyntaxError avec le token fautif nommé.

#Ambiguïté d'une grammaireCopier le lien

Une grammaire est ambiguë si un mot admet deux arbres de dérivation distincts. L'ambiguïté est une propriété de la grammaire, pas du langage: un langage peut être engendré par une grammaire ambiguë et par une autre qui ne l'est pas. Comme un parseur construit un arbre, une grammaire ambiguë rend la sémantique indéterminée — c'est un défaut à corriger, pas une curiosité théorique.

#L'exemple canoniqueCopier le lien

Soit $E \to E + E \mid D \mid N \times E \mid (E)$, où les $D$ sont des déplacements et les $N$ des nombres. Le mot H + B + G admet deux arbres:

1   E                E2  /|\              /|\3 E + E            E + E4/|\   |          |   /|\5H + B G          H  B + G

Le mot est le même, l'arbre diffère. La cause est structurelle: la règle $E \to E + E$ est récursivement double (à gauche et à droite), donc la position de l'opérateur racine n'est pas déterminée.

Dans ce cas précis, les deux arbres donnent le même résultat (l'addition des déplacements est associative), mais la grammaire reste ambiguë au sens syntaxique. C'est exactement la distinction à écrire sur une copie: la sémantique peut coïncider, la syntaxe est ambiguë quand même.

#Comment lever l'ambiguïté: stratifierCopier le lien

La méthode générale consiste à séparer les niveaux de priorité en non-terminaux distincts, un par niveau. Une grammaire non ambiguë pour le même langage:

$E \longrightarrow T + E \mid T \qquad T \longrightarrow N \times T \mid F \qquad F \longrightarrow H \mid B \mid G \mid D \mid (E)$

Trois arguments justifient la non-ambiguïté:

1. Un $E$ est une suite de $T$ séparés par des +, et un $T$ ne contient jamais de + au niveau supérieur. La décomposition de H + B + G en $T + E$ est donc unique: c'est le premier + non parenthésé.
2. La récursion à droite ($E \to T + E$ au lieu de $E \to E + T$) fixe l'associativité à droite, sans laisser de choix.
3. Un $T$ est soit un facteur, soit $N \times T$ avec $N$ maximal (la règle $N \to NC$ force à absorber tous les chiffres): le découpage est unique.

C'est exactement la cascade expr → term → factor de la grammaire du langage Expr plus haut. La stratification n'est pas un ornement: elle est la désambiguïsation.

#Reconnaître une grammaire ambiguëCopier le lien

Il n'existe pas d'algorithme général pour décider si une grammaire hors contexte est ambiguë (le problème est indécidable). En pratique, on repère quelques signatures:

• une règle récursive des deux côtés pour un opérateur associatif, comme $E \to E + E$;
• le dangling else: if a then if b then x else y, où le else peut appartenir au if interne ou externe;
• deux productions qui peuvent dériver le même mot par des chemins différents — le symptôme, mais pas la cause.

Le remède est toujours le même: introduire des niveaux, ou une règle de priorité explicite encodée dans la grammaire (jamais dans le code du parseur, où elle devient invisible).

#Conséquence sur le parseurCopier le lien

La descente récursive exige non seulement une grammaire non ambiguë, mais sans récursion gauche — ce qui tombe bien, puisque la stratification élimine les deux défauts d'un coup. Un parseur LL(1) a besoin en outre que chaque non-terminal se décide sur un seul token d'avance: c'est le cas ici, puisque E commence toujours par un T, et T par un facteur, dont la forme (H, B, G, D, (, ou un chiffre) est immédiatement visible.

#LL et LR: deux famillesCopier le lien

La descente récursive est LL(1) en pratique: elle Lit de gauche à droite, construit une dérivation Leftmost, en regardant 1 token d'avance. Simple à écrire et à déboguer, elle exige une grammaire sans récursion gauche directe (expr = expr "+" term bouclerait). Les parseurs LR (yacc, bison) lisent aussi de gauche à droite mais construisent la dérivation en remontant (Rightmost inverse): ils acceptent plus de grammaires, y compris récursives gauches, au prix d'une table générée et de conflits à interpréter. Règle pratique d'ingénierie: pour un mini-langage, la descente récursive suffit presque toujours et se lit comme la grammaire.

#Exercice : prédictions d'arbreCopier le lien

Avant d'exécuter le playground, prédisez l'AST (tuples Python) pour chacune de ces entrées, puis vérifiez:

1. 1 + 2 * 3
2. (1 + 2) * 3
3. -x + y
4. let a = 2; a * (a + 1)

Corrigé. 1: ('+', 1·…) plus précisément ('+', ('num',1), ('* ', ('num',2), ('num',3))): le * se construit dans term, sous le +. 2: les parenthèses forcent un passage par factor, donc le + se retrouve sous le *: ('*', ('+', 1, 2), 3). 3: le moins unaire s'attache au facteur le plus proche: ('+', ('neg', x), y). 4: un programme à deux instructions: ('program', [('let','a',2), ('expr', ('* ', var a, ('+', var a, 1)))]). Si vos prédictions diffèrent, rejouez la grammaire à la main sur papier: chaque token consommé correspond à un eat dans le code.

#Pièges classiquesCopier le lien

#Mini‑quizCopier le lien