Une fonction par règle de grammaire : la grammaire devient du code, et l'arbre apparaît tout seul.
⏱️ Durée : environ 90 minutes · 🎓 Niveau : intermédiaire · 🏅 Badge : Grammairien du code
🎬 L'histoire
Le lexer de Kodi produit des jetons. Maintenant il faut comprendre 2 + 3 * 4. Kodi essaie avec une boucle qui lit de gauche à droite : résultat 20 au lieu de 14.
« Tu ignores la grammaire, dit Sam. La structure du texte est un arbre. Chaque règle de grammaire devient une fonction, et les priorités sortent naturellement de l'imbrication des appels. »
Tu écris le parser de HashScript par descente récursive.
🎯 Ta mission
À la fin, je serai capable de :
- transformer une grammaire en fonctions récursives
- encoder priorités et associativité dans la structure des règles
- construire un arbre syntaxique pendant l'analyse
- signaler les erreurs de syntaxe avec un message utile
- évaluer un arbre d'expression
🧩 Défi d'échauffement (5 XP)
Calcule à la main 2 + 3 * 4 - 1. Dans quel ordre as-tu fait les opérations ? Dessine l'arbre des calculs (un nœud par opération). Maintenant, suppose que tu veuilles écrire un programme qui lit 2 + 3 * 4 - 1 de gauche à droite : à quel moment sait-il qu'il doit faire la multiplication avant l'addition ?
💡 Le concept
L'idée
Une grammaire devient un programme : on écrit une fonction par non-terminal. Chaque fonction lit les jetons qui correspondent à sa règle et appelle d'autres fonctions pour les sous-règles. C'est l'analyse par descente récursive (recursive descent).
Grammaire des expressions (EBNF) :
expression → terme (("+" | "-") terme)*
terme → facteur (("*" | "/") facteur)*
facteur → NOMBRE | "(" expression ")" | "-" facteur
Priorités par l'imbrication
expression appelle terme, qui appelle facteur. Les opérateurs les plus prioritaires (*, /) sont donc traités plus profondément dans l'arbre, donc calculés en premier. Ajouter un niveau de priorité = ajouter une règle (et une fonction) entre deux niveaux.
Associativité par la boucle
La boucle ( … )* construit l'arbre vers la gauche :
1 - 2 - 3 : g = 1
g = (1 - 2)
g = ((1 - 2) - 3)
C'est l'associativité à gauche. Pour un opérateur associatif à droite (comme la puissance ^), la règle s'écrit récursivement : puissance → facteur ("^" puissance)?.
Le parser en Python
import re
def lexer(texte):
return re.findall(r"\d+(?:\.\d+)?|[-+*/()]", texte)
class Parseur:
def __init__(self, jetons):
self.jetons, self.i = jetons, 0
def courant(self):
return self.jetons[self.i] if self.i < len(self.jetons) else None
def prendre(self):
jeton = self.courant()
self.i += 1
return jeton
def expression(self): # expression → terme (("+" | "-") terme)*
gauche = self.terme()
while self.courant() in ("+", "-"):
op = self.prendre()
gauche = ("bin", op, gauche, self.terme())
return gauche
():
gauche = .facteur()
.courant() (, ):
op = .prendre()
gauche = (, op, gauche, .facteur())
gauche
():
jeton = .prendre()
jeton :
SyntaxError()
jeton == :
e = .expression()
.prendre() != :
SyntaxError()
e
jeton == :
(, .facteur())
re.fullmatch(, jeton):
(, (jeton) jeton (jeton))
SyntaxError()
():
p = Parseur(lexer(texte))
arbre = p.expression()
p.courant() :
SyntaxError()
arbre
Évaluer l'arbre
OPS = {"+": lambda x, y: x + y, "-": lambda x, y: x - y, "*": lambda x, y: x * y, "/": lambda x, y: x / y}
def evaluer(a):
if a[0] == "num":
return a[1]
if a[0] == "neg":
return -evaluer(a[1])
_, op, g, d = a
return OPS[op](evaluer(g), evaluer(d))
Les erreurs de syntaxe
Un bon parser dit ce qu'il attendait et ce qu'il a trouvé : « attendu ), trouvé fin du programme ». Il vérifie aussi qu'il n'y a rien après l'expression complète.
Limites de la descente récursive
- Elle ne supporte pas la récursion à gauche (
expr → expr "+" termebouclerait indéfiniment) : on la transforme en boucle. - Pour de grandes grammaires, on utilise des générateurs de parseurs (ANTLR, Lark, PEG) ou des analyseurs LR (Yacc/Bison). Les principes restent les mêmes.
🧠 Astuce : écris d'abord la grammaire sur papier. Chaque ligne de grammaire devient une fonction. Si le code ne ressemble pas à la grammaire, quelque chose ne va pas.
🔍 Exemple pas à pas
Problème : analyser et évaluer des expressions, en vérifiant les priorités et les erreurs.
import re
def lexer(texte):
return re.findall(r"\d+(?:\.\d+)?|[-+*/()]", texte)
class Parseur:
def __init__(self, jetons):
self.jetons, self.i = jetons, 0
def courant(self):
return self.jetons[self.i] if self.i < len(self.jetons) else None
def prendre(self):
jeton = self.courant(); self.i += 1; return jeton
def expression(self):
gauche = self.terme()
while self.courant() in ("+", "-"):
op = self.prendre(); gauche = ("bin", op, gauche, self.terme())
return gauche
def terme():
gauche = .facteur()
.courant() (, ):
op = .prendre(); gauche = (, op, gauche, .facteur())
gauche
():
jeton = .prendre()
jeton :
SyntaxError()
jeton == :
e = .expression()
.prendre() != :
SyntaxError()
e
jeton == :
(, .facteur())
re.fullmatch(, jeton):
(, (jeton) jeton (jeton))
SyntaxError()
():
p = Parseur(lexer(texte))
arbre = p.expression()
p.courant() :
SyntaxError()
arbre
OPS = {: x, y: x + y, : x, y: x - y, : x, y: x * y, : x, y: x / y}
():
a[] == : a[]
a[] == : -evaluer(a[])
_, op, g, d = a
OPS[op](evaluer(g), evaluer(d))
(analyser())
texte (, , , , ):
attendu = (texte)
evaluer(analyser(texte)) == attendu, texte
()
mauvais (, , , ):
:
analyser(mauvais)
SyntaxError e:
()
Lecture :
- l'arbre de
2 + 3 * 4place3 * 4sous l'addition : le résultat est 14, pas 20 ; 10 - 4 - 3donne 3 (associativité à gauche) et non 9 ;- on compare chaque résultat à
evalde Python uniquement dans les tests pour vérifier le parser (jamaisevalsur une entrée utilisateur : danger !) ; - les quatre entrées invalides produisent chacune un message précis.
✍️ À toi, avec aide (10 XP)
Ajoute au parseur de l'exemple les comparaisons : <, >, <=, >=, ==, !=, avec une priorité plus basse que l'addition (donc 1 + 2 < 4 se lit (1 + 2) < 4) et un résultat booléen.
- Écris la nouvelle grammaire.
- Modifie le lexer (les opérateurs à deux caractères) et le parseur.
- Étends
evaluer. - Teste :
1 + 2 < 4→ True,2 * 3 == 6→ True,5 != 5→ False.
💡 Indice 1
Nouvelle règle : comparaison → expression (OP_COMP expression)? placée au-dessus de expression.
💡 Indice 2
Le lexer doit reconnaître <=|>=|==|!=|[<>] avant les opérateurs simples.
💡 Indice 3
Appelle comparaison depuis analyser à la place de expression, et depuis les parenthèses dans facteur.
✅ Réponse
import re
def lexer(texte):
return re.findall(r"\d+(?:\.\d+)?|<=|>=|==|!=|[<>]|[-+*/()]", texte)
class Parseur:
def __init__(self, jetons):
self.jetons, self.i = jetons, 0
def courant(self):
return self.jetons[self.i] if self.i < len(self.jetons) else None
def prendre(self):
jeton = self.courant(); self.i += 1; return jeton
def comparaison(self): # comparaison → expression (OP_COMP expression)?
gauche = self.expression()
if self.courant() in ("<", ">", "<=", ">=", , ):
op = .prendre()
(, op, gauche, .expression())
gauche
():
gauche = .terme()
.courant() (, ):
op = .prendre(); gauche = (, op, gauche, .terme())
gauche
():
gauche = .facteur()
.courant() (, ):
op = .prendre(); gauche = (, op, gauche, .facteur())
gauche
():
jeton = .prendre()
jeton :
SyntaxError()
jeton == :
e = .comparaison()
.prendre() != :
SyntaxError()
e
jeton == :
(, .facteur())
re.fullmatch(, jeton):
(, (jeton) jeton (jeton))
SyntaxError()
():
p = Parseur(lexer(texte))
arbre = p.comparaison()
p.courant() :
SyntaxError()
arbre
OPS = {: x, y: x + y, : x, y: x - y, : x, y: x * y, : x, y: x / y,
: x, y: x < y, : x, y: x > y, : x, y: x <= y, : x, y: x >= y,
: x, y: x == y, : x, y: x != y}
():
a[] == : a[]
a[] == : -evaluer(a[])
_, op, g, d = a
OPS[op](evaluer(g), evaluer(d))
evaluer(analyser())
evaluer(analyser())
evaluer(analyser())
evaluer(analyser())
()
🚀 À toi, en solo (20 XP)
La puissance. Ajoute l'opérateur ^ (puissance), qui doit être :
- plus prioritaire que
*et/; - associatif à droite :
2 ^ 3 ^ 2=2 ^ (3 ^ 2)= 512 ; - plus prioritaire que le moins unaire dans la convention mathématique :
-2 ^ 2=-(2 ^ 2)= -4.
Écris la nouvelle grammaire, modifie lexer et parseur, et teste : 2 ^ 3 ^ 2, -2 ^ 2, (2 ^ 3) ^ 2, 2 * 3 ^ 2, 2 ^ -1.
✅ Pistes de correction
terme → unaire (("*" | "/") unaire)*
unaire → "-" unaire | puissance
puissance → atome ("^" unaire)? # associatif à droite, l'exposant peut être négatif
atome → NOMBRE | "(" expression ")"
import re
def lexer(texte):
return re.findall(r"\d+(?:\.\d+)?|[-+*/^()]", texte)
class Parseur:
def __init__(self, jetons):
self.jetons, self.i = jetons, 0
def courant(self):
return self.jetons[self.i] if self.i < len(self.jetons) else None
def prendre(self):
jeton = self.courant(); self.i += 1; return jeton
def expression(self):
g = self.terme()
while self.courant() (, ):
op = .prendre(); g = (, op, g, .terme())
g
():
g = .unaire()
.courant() (, ):
op = .prendre(); g = (, op, g, .unaire())
g
():
.courant() == :
.prendre()
(, .unaire())
.puissance()
():
base = .atome()
.courant() == :
.prendre()
(, , base, .unaire())
base
():
jeton = .prendre()
jeton :
SyntaxError()
jeton == :
e = .expression()
.prendre() != :
SyntaxError()
e
re.fullmatch(, jeton):
(, (jeton) jeton (jeton))
SyntaxError()
():
p = Parseur(lexer(texte))
a = p.expression()
p.courant() :
SyntaxError()
a
OPS = {: x, y: x + y, : x, y: x - y, : x, y: x * y, : x, y: x / y, : x, y: x ** y}
():
a[] == : a[]
a[] == : -evaluer(a[])
_, op, g, d = a
OPS[op](evaluer(g), evaluer(d))
texte, attendu ((, ), (, -), (, ), (, ), (, )):
evaluer(analyser(texte)) == attendu, texte
()
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Lire de gauche à droite sans structure | 2 + 3 * 4 donne 20 | Une fonction par niveau de priorité |
| Récursion à gauche | expression → expression + terme boucle à l'infini | La transformer en boucle (...)* |
| Oublier de vérifier la fin de l'entrée | 1 2 est accepté | Contrôler qu'il ne reste aucun jeton |
| Messages d'erreur vagues | L'utilisateur ne sait pas quoi corriger | Dire ce qui était attendu et ce qui a été trouvé |
🐉 Mini-boss (40 XP)
Parseur de HashScript (expressions et appels). Étends le parseur d'expressions pour obtenir la grammaire :
expression → comparaison
comparaison → somme (OP_COMP somme)?
somme → produit (("+" | "-") produit)*
produit → unaire (("*" | "/") unaire)*
unaire → "-" unaire | appel
appel → primaire ("(" arguments? ")")*
primaire → NOMBRE | IDENTIFIANT | "true" | "false" | "(" expression ")"
- Le parseur doit produire des nœuds
("appel", fonction, [arguments])et("var", nom). - Écris
afficher(arbre)qui imprime l'expression complètement parenthésée (pour vérifier les priorités). - Teste au moins 15 expressions, dont
f(1)(2),-f(x) * 2,a < b == c. - Les messages d'erreur doivent indiquer le jeton attendu et le jeton trouvé.
- Teste aussi que 200 expressions aléatoires, générées par une fonction qui parenthèse complètement, sont analysées à l'identique de leur version avec parenthèses minimales.
✅ Pistes de correction
Un bon travail : appel boucle tant que ( suit, ce qui permet f(1)(2); afficher produit ((a < b) == c) pour montrer l'associativité de la comparaison; primaire renvoie ("var", nom) pour les identifiants et ("bool", True) pour true; les erreurs disent « attendu ), trouvé fin de l'entrée »; le test aléatoire génère un arbre d'expressions, l'imprime avec parenthèses complètes puis avec parenthèses minimales (en utilisant les priorités), et vérifie que afficher(analyser(texte_min)) == afficher(analyser(texte_complet)).
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Dans la descente récursive, on écrit :
- A. un seul gros
if - B. une fonction par règle de grammaire
- C. une expression régulière
2. Les priorités entre opérateurs sont encodées par :
- A. l'ordre des jetons dans le fichier
- B. une table triée au hasard
- C. l'imbrication des règles (qui appelle qui)
3. La boucle ( … )* dans une règle produit :
- A. une associativité à gauche
- B. une associativité à droite
- C. aucune associativité
4. 🔁 Révision mission 01 : Un terminal d'une grammaire est :
- A. une catégorie à développer
- B. un symbole réel du langage (jeton)
- C. un type de compilateur
5. 🔁 Révision mission 02 : Un jeton est :
- A. une instruction du processeur
- B. un type de variable
- C. une unité lexicale avec genre, texte et position
✅ Réponses
- B.
- C.
- A.
- B.
- C.
🪞 Je réfléchis (10 XP)
- Dans ta vie, où appliques-tu des priorités implicites (ordre des opérations, ordre des tâches) sans les écrire ?
- Qu'est-ce qui rend la descente récursive attrayante pour un débutant par rapport à d'autres techniques ?
🎒 À retenir
- Une fonction par non-terminal.
- Priorités = niveaux de règles imbriqués.
- Boucle = associativité à gauche ; récursion = à droite.
- Toujours vérifier qu'il ne reste rien après l'expression.
- Messages : attendu / trouvé.
flowchart LR
T(["Le parsing par descente récursive"])
T --> R1["1. Une fonction par non-terminal."]
T --> R2["2. Priorités = niveaux de règles imbriqués."]
T --> R3["3. Boucle = associativité à gauche ; récursion = à droite."]
T --> R4["4. Toujours vérifier qu'il ne reste rien après l'expression."]
T --> R5["5. Messages : attendu / trouvé."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Grammairien du code
← Mission 02 — Les jetons et l'analyse lexicale · Mission 04 — L'arbre syntaxique abstrait (AST) →
HEF-090 — Compilateurs et langages

