Après le parsing, le programme n'est plus un texte : c'est un arbre qu'on peut parcourir, transformer et optimiser.
⏱️ Durée : environ 85 minutes · 🎓 Niveau : intermédiaire · 🏅 Badge : Jardinier d'arbres
🎬 L'histoire
Kodi dispose maintenant d'un parser. Maya demande : « Peux-tu m'afficher la liste de toutes les variables utilisées dans un programme HashScript ? Et simplifier 2 * 3 + x en 6 + x automatiquement ? » Kodi cherche à le faire sur le texte et se perd dans les cas particuliers.
« Le texte est une représentation pour les humains, dit Sam. Pour les machines, l'arbre est la bonne structure : on le parcourt, on le transforme, on l'optimise. »
Tu apprends à représenter, parcourir et transformer un AST.
🎯 Ta mission
À la fin, je serai capable de :
- expliquer la différence entre arbre syntaxique concret et AST
- lire et construire un AST avec des nœuds typés (dataclasses)
- écrire un parcours récursif (visiteur) sur un AST
- implémenter une transformation : le pliage de constantes
- produire une représentation de l'arbre (S-expression, Mermaid)
🧩 Défi d'échauffement (5 XP)
Voici l'expression (2 + 3) * x. Dessine l'arbre qui la représente en gardant seulement ce qui compte pour le calcul (opérateurs, nombres, variables), sans les parenthèses ni les virgules. Que deviennent les parenthèses ? Peux-tu retrouver le texte à partir de l'arbre ?
💡 Le concept
Arbre concret et AST
- L'arbre syntaxique concret (de dérivation) contient tous les détails de la grammaire (règles intermédiaires, parenthèses, séparateurs).
- L'AST (Abstract Syntax Tree) garde l'essentiel : la structure du programme, sans le « bruit » syntaxique.
Les parenthèses de (2 + 3) * x disparaissent de l'AST : leur effet est déjà dans la forme de l'arbre.
flowchart TD
M["Bin *"] --> P["Bin +"]
M --> X["Var x"]
P --> N2["Num 2"]
P --> N3["Num 3"]
Description du schéma : la racine est une multiplication. Son enfant gauche est l'addition de 2 et 3 ; son enfant droit est la variable x.
Des nœuds typés
En Python, on représente un AST avec des classes (souvent des @dataclass) :
from dataclasses import dataclass
@dataclass
class Num: valeur: float
@dataclass
class Var: nom: str
@dataclass
class Bin: op: str; gauche: object; droite: object
@dataclass
class Neg: expr: object
Avantages par rapport à des tuples : noms de champs explicites, vérification des types, affichage lisible, positions de code (ligne, colonne) ajoutables.
Parcourir un arbre : le visiteur
Presque tout traitement est un parcours récursif : on regarde le type du nœud, on traite, on descend dans les enfants.
def afficher(n):
if isinstance(n, Num): return str(n.valeur)
if isinstance(n, Var): return n.nom
if isinstance(n, Neg): return f"(- {afficher(n.expr)})"
if isinstance(n, Bin): return f"({n.op} {afficher(n.gauche)} {afficher(n.droite)})"
Le même squelette sert à : évaluer, vérifier les types, compter, optimiser, compiler.
Le patron visiteur formalise cela : une fonction par type de nœud, et un mécanisme de dispatch. Python moderne propose aussi la correspondance de motifs (match/case).
Les transformations
Une transformation construit un nouvel arbre à partir de l'ancien. Exemple essentiel : le pliage de constantes (constant folding) :
| Avant | Après |
|---|---|
2 * 3 + x | 6 + x |
x * 1 | x |
x + 0 | x |
0 * f(x) | à ne pas simplifier (si f a des effets de bord) |
Une optimisation doit préserver le sens du programme. Attention à 0 * f(x) ou à la division par zéro 1 / 0 que l'on ne doit pas évaluer à la compilation.
Représentations de l'arbre
- S-expression :
(+ 2 (* 3 4)): compacte, facile à comparer dans les tests. - Mermaid/DOT : pour dessiner.
- JSON : pour échanger avec d'autres outils.
Pourquoi un AST plutôt que d'interpréter directement le texte ?
- on sépare la structure de son traitement (plusieurs traitements sur le même arbre) ;
- on peut optimiser avant d'exécuter ;
- on peut produire des messages précis avec les positions ;
- les outils de qualité (analyseurs, formateurs, refactoring automatique) travaillent sur l'AST.
🧠 Astuce : Python expose le sien :
ast.parse("1 + 2"). Explore-le avecast.dumppour voir un AST industriel.
🔍 Exemple pas à pas
Problème : utiliser l'AST de HashScript pour (1) afficher en S-expression, (2) lister les variables, (3) plier les constantes.
On utilise le lexer et le parseur de référence (fournis dans 01-Course/code/hashscript.py, construits dans les missions 2 et 3 puis étendus).
from hashscript import parser, Num, Var, Bin, Neg, Let, Print
def sexpr(n):
if isinstance(n, Num):
return str(n.valeur)
if isinstance(n, Var):
return n.nom
if isinstance(n, Neg):
return f"(- {sexpr(n.expr)})"
if isinstance(n, Bin):
return f"({n.op} {sexpr(n.gauche)} {sexpr(n.droite)})"
raise TypeError(type(n).__name__)
def variables(n):
if isinstance(n, Var):
return {n.nom}
if isinstance(n, Neg):
return variables(n.expr)
if isinstance(n, Bin):
return variables(n.gauche) | variables(n.droite)
return set()
programme = parser("let r = 2 * 3 + x * (4 - 4 + y);")
expression = programme[0].expr
print(sexpr(expression)) # (+ (* 2 3) (* x (+ (- 4 4) y)))
print(sorted(variables(expression)))
Le pliage de constantes : on reconstruit l'arbre en évaluant tout ce qui est constant.
import operator
from hashscript import parser, Num, Var, Bin, Neg
OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}
def plier(n):
if isinstance(n, Neg):
e = plier(n.expr)
return Num(-e.valeur) if isinstance(e, Num) else Neg(e)
if not isinstance(n, Bin):
return n
g, d = plier(n.gauche), plier(n.droite)
if n.op in OPS and isinstance(g, Num) and isinstance(d, Num):
if n.op == "/" and d.valeur == 0:
return Bin(n.op, g, d, n.ligne, n.col) # on ne simplifie pas : l'erreur doit rester à l'exécution
return Num(OPS[n.op](g.valeur, d.valeur))
if n.op == "*" and isinstance(g, Num) and g.valeur == 1: return d
if n.op == "*" and isinstance(d, Num) and d.valeur == 1: return g
n.op == (g, Num) g.valeur == : d
n.op == (d, Num) d.valeur == : g
Bin(n.op, g, d, n.ligne, n.col)
():
(n, Num): (n.valeur)
(n, Var): n.nom
(n, Neg):
source (, , , ):
arbre = parser(source)[]
()
Lecture : 2 * 3 + x devient (+ 6 x) ; x * 1 + 0 devient x ; 1 / 0 n'est pas évalué à la compilation (on laisse l'erreur au moment de l'exécution, avec sa position). Chaque règle de simplification préserve le sens du programme.
✍️ À toi, avec aide (10 XP)
Écris profondeur(n) qui renvoie la hauteur d'un AST d'expression (un Num ou Var seul a la hauteur 1) et compter(n) qui renvoie le nombre de nœuds. Calcule les deux pour 1 + 2 * (3 - x).
Dessine ensuite l'arbre en Mermaid avec une fonction vers_mermaid(n) qui produit le texte d'un flowchart TD.
💡 Indice 1
profondeur d'un Bin = 1 + max(gauche, droite).
💡 Indice 2
Numérote les nœuds avec un compteur pour créer des identifiants uniques.
💡 Indice 3
Chaque Bin produit une arête vers ses deux fils.
✅ Réponse
from hashscript import parser, Num, Var, Bin, Neg
def profondeur(n):
if isinstance(n, Bin):
return 1 + max(profondeur(n.gauche), profondeur(n.droite))
if isinstance(n, Neg):
return 1 + profondeur(n.expr)
return 1
def compter(n):
if isinstance(n, Bin):
return 1 + compter(n.gauche) + compter(n.droite)
if isinstance(n, Neg):
return 1 + compter(n.expr)
return 1
def vers_mermaid(racine):
lignes, compteur = ["flowchart TD"], [0]
def visiter(n):
compteur[0] += 1
ident = f"n{compteur[0]}"
if isinstance(n, Bin):
lignes.append(f' {ident}[""]')
fils (n.gauche, n.droite):
f_id = visiter(fils)
lignes.append()
(n, Neg):
lignes.append()
lignes.append()
(n, Num):
lignes.append()
:
lignes.append()
ident
visiter(racine)
.join(lignes)
arbre = parser()[]
(profondeur(arbre), compter(arbre))
(vers_mermaid(arbre))
🚀 À toi, en solo (20 XP)
Simplifications algébriques. Étends le pliage de constantes avec :
x - x→0(même variable des deux côtés) ;x * 0→0seulement sixne contient que des constantes et des variables (pas d'appel de fonction) ;-(-x)→x;x / 1→x.
Écris les tests : chaque simplification doit conserver le résultat de l'évaluation. Vérifie-le avec un petit évaluateur, sur 300 expressions aléatoires dans lesquelles les variables prennent des valeurs aléatoires.
✅ Pistes de correction
import operator, random
from hashscript import Num, Var, Bin, Neg
OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv}
def meme(a, b):
return type(a) is type(b) and ((isinstance(a, Var) and a.nom == b.nom) or (isinstance(a, Num) and a.valeur == b.valeur))
def pur(n): # sans appel : ici toutes nos expressions le sont
return True
def plier(n):
if isinstance(n, Neg):
e = plier(n.expr)
if isinstance(e, Num): return Num(-e.valeur)
if isinstance(e, Neg): return e.expr
return Neg(e)
if not isinstance(n, Bin):
return n
g, d = plier(n.gauche), plier(n.droite)
if n.op in OPS (g, Num) (d, Num):
n.op == d.valeur == :
Bin(n.op, g, d)
Num(OPS[n.op](g.valeur, d.valeur))
n.op == meme(g, d): Num()
n.op == (((g, Num) g.valeur == pur(d)) ((d, Num) d.valeur == pur(g))): Num()
n.op == (g, Num) g.valeur == : d
n.op == (d, Num) d.valeur == : g
n.op == (d, Num) d.valeur == : g
n.op == (g, Num) g.valeur == : d
n.op == (d, Num) d.valeur == : g
Bin(n.op, g, d)
():
(n, Num): n.valeur
(n, Var): env[n.nom]
(n, Neg): -evaluer(n.expr, env)
OPS[n.op](evaluer(n.gauche, env), evaluer(n.droite, env))
():
profondeur == rng.random() < :
Num(rng.choice([, , , ])) rng.random() < Var(rng.choice())
rng.random() < :
Neg(aleatoire(rng, profondeur - ))
Bin(rng.choice([, , , ]), aleatoire(rng, profondeur - ), aleatoire(rng, profondeur - ))
rng = random.Random()
verifies =
_ ():
arbre = aleatoire(rng)
env = {: rng.randint(, ), : rng.randint(, )}
:
attendu = evaluer(arbre, env)
ZeroDivisionError:
(evaluer(plier(arbre), env) - attendu) < , arbre
verifies +=
(verifies, )
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Optimiser en changeant le sens | 0 * f(x) supprime un effet de bord | Ne simplifier que ce qui est pur et sûr |
Évaluer 1 / 0 à la compilation | L'erreur change de moment ou disparaît | Laisser l'erreur à l'exécution |
| Garder le bruit syntaxique dans l'AST | Arbres lourds, traitements compliqués | Abstraire les parenthèses, virgules, séparateurs |
| Modifier l'arbre sur place | Effets de bord imprévus | Construire un nouvel arbre |
🐉 Mini-boss (40 XP)
Boîte à outils d'AST. À partir des programmes HashScript analysés avec parser, construis un module outils_ast.py avec :
- un visiteur générique
parcourir(noeud, fonction)qui appellefonctionsur chaque nœud (instructions et expressions, y comprisSi,TantQue,Fun) ; variables_lues(programme),variables_ecrites(programme)(déclarées ou affectées),fonctions_appelees(programme);statistiques(programme): nombre de nœuds par type, profondeur maximale ;- une transformation
renommer(programme, ancien, nouveau)qui renomme une variable en respectant les portées simples (ne touche pas une variable de même nom déclarée dans une fonction qui la masque) ; - un formateur qui reconstitue du texte HashScript lisible depuis l'AST (
vers_texte), et la propriété :parser(vers_texte(parser(s)))produit le même AST queparser(s)sur 20 programmes.
✅ Pistes de correction
Un bon travail : parcourir utilise dataclasses.fields pour descendre dans les enfants (listes ou nœuds) sans écrire un if par type; statistiques compte avec un Counter et max sur les profondeurs; renommer maintient une pile de noms masqués (dès qu'une Fun déclare un paramètre du même nom, on ne renomme pas dans son corps); vers_texte gère l'indentation des blocs et ajoute des parenthèses seulement quand la priorité l'exige. Le test de ronde (« aller-retour ») compare les AST avec l'égalité des dataclasses, en ignorant les champs de position (ligne/col).
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. L'AST garde :
- A. la structure essentielle, sans le bruit syntaxique
- B. tous les espaces et commentaires
- C. seulement les nombres
2. Le pliage de constantes consiste à :
- A. supprimer les variables
- B. évaluer à l'avance les calculs constants
- C. traduire en assembleur
3. Une optimisation doit toujours :
- A. réduire le nombre de lignes
- B. utiliser plus de mémoire
- C. préserver le sens du programme
4. 🔁 Révision mission 03 : Dans la descente récursive, on écrit :
- A. une fonction par règle de grammaire
- B. un seul gros
if - C. une expression régulière
5. 🔁 Révision mission 03 : La boucle ( … )* dans une règle produit :
- A. une associativité à droite
- B. une associativité à gauche
- C. aucune associativité
✅ Réponses
- A.
- B.
- C.
- A.
- B.
🪞 Je réfléchis (10 XP)
- Quel autre document ou outil de ta vie existe à la fois en « texte » et en « structure » (une recette, une formule, un plan) ?
- Pourquoi vaut-il mieux transformer un arbre en construisant un nouvel arbre qu'en le modifiant sur place ?
🎒 À retenir
- AST = structure essentielle du programme.
- Nœuds typés (dataclasses) + parcours récursif.
- Transformation = nouvel arbre, sens préservé.
- S-expression, Mermaid, JSON pour représenter.
- Un test aléatoire vérifie qu'une optimisation ne change pas le résultat.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Jardinier d'arbres
← Mission 03 — Le parsing par descente récursive · Mission 05 — L'analyse sémantique →
HEF-090 — Compilateurs et langages

