#AST (arbre syntaxique abstrait)Copier le lien

Objectifs d'apprentissage

• Définir un jeu de nœuds AST minimal et stable pour le langage Expr.
• Évaluer un AST avec un environnement (variables) et des erreurs propres.
• Écrire une transformation d'arbre (desucaring, folding) sans muter l'original.

Prérequis: page Parsing (l'AST de ('program', stmts)), récursion sur des structures arborescentes.

#Le familier: 2*(3+4)-5Copier le lien

Le fil conducteur du module continue. Pour cette expression, le parseur produit:

1ast = ('-',2       ('*',3         ('num', 2),4         ('+', ('num', 3), ('num', 4))),5       ('num', 5))

Trois formes de nœuds apparaissent déjà: 'num' (littéral), 'var' (variable), et les opérateurs binaires ('+', gauche, droite). La page précédente y a ajouté 'neg' (moins unaire), 'let'/'assign' (déclarations) et 'program'/'expr' (instructions). Un AST complet mais minuscule: sept formes pour tout le langage.

#Évaluation: récursion structurelleCopier le lien

Évaluer, c'est poursuivre la récursion du parsing: chaque nœud se calcule à partir de ses enfants. La fonction fait moins de vingt lignes et sert de spécification exécutable du langage: tout compilateur ultérieur devra produire un code qui calcule la même chose.

Remarquez trois décisions de conception visibles dans le code: l'évaluation de l'expression se fait avant l'affectation (l'argument droite est calculé avec l'ancien environnement), la variable non définie lève NameError avec le nom fautif, et la division reprend le // de Python: le langage Expr travaille en entiers.

#Deux environnements, deux sémantiquesCopier le lien

L'objet env passé en paramètre mérite attention. Deux choix existent, et ils changent le langage:

• Environnement global: toutes les fonctions partagent le même dictionnaire, comme ci-dessus. Simple, mais chaque run sur le même env laisse des traces.
• Environnement fonctionnel: run renvoie un nouvel environnement (copie), l'original reste intact. C'est ce que feront le codegen WASM avec ses variables locales, et c'est le seul choix sûr pour du parallélisme.

Piège Python visible: le code utilise un env passé explicitement plutôt qu'un paramètre par défaut env={}, qui serait partagé entre tous les appels (un dictionnaire par défaut est créé une fois pour toutes à la définition).

#Transformations d'arbreCopier le lien

Un compilateur ne s'arrête pas à l'évaluation: il réécrit l'arbre. La transformation la plus rentable est le constant folding: calculer à la compilation ce qui ne dépend d'aucune variable.

1def constant_fold(node):2    tag = node[0]3    if tag == 'num':4        return node5    if tag == 'neg':6        sub = constant_fold(node[1])7        return ('num', -sub[1]) if sub[0] == 'num' else ('neg', sub)8    if tag in ('+', '-', '*', '/'):9        left, right = constant_fold(node[1]), constant_fold(node[2])10        if left[0] == right[0] == 'num':11            return ('num', run((tag, left, right), {}))   # calcule maintenant12        return (tag, left, right)13    # var, let, assign, expr, program: reconstruire avec les enfants pliés14    if tag in ('let', 'assign'):

La fonction ne mute jamais ses entrées: elle construit de nouveaux nœuds en sortie. Cette discipline (fonctions pures d'arbre vers arbre) rend les passes chaînables et testables: parse → fold → codegen se compose sans effet de bord caché. C'est exactement l'architecture des vrais compilateurs, où chaque passe est un programme séparé.

#Quiz du fil conducteurCopier le lien

#Exercice : vérifier avant d'évaluerCopier le lien

Un interpréteur détecte y = x + 1 (x non définie) seulement au moment de l'évaluer. Pour un compilateur, c'est trop tard.

#InstructionsCopier le lien

1. Écrivez check(node, declared) qui parcourt l'AST et collecte les noms utilisés mais jamais déclarés par un let antérieur (portée séquentielle, comme dans le run ci-dessus).
2. La fonction renvoie la liste des couples (nom, position approximative), ou liste vide si tout est défini.
3. Testez sur ('program', [('assign','y',('+',('var','x'),('num',1)))]) puis sur le programme valide du playground.

#CorrectionCopier le lien

1def check(node, declared=None):2    declared = declared or set()3    tag = node[0]4    if tag == 'var':5        return [] if node[1] in declared else [node[1]]6    if tag in ('let', 'assign'):7        errs = check(node[2], declared)8        declared.add(node[1])            # visible pour la suite du programme9        return errs10    if tag in ('+', '-', '*', '/'):11        return check(node[1], declared) + check(node[2], declared)12    if tag == 'neg' or tag == 'expr':13        return check(node[1], declared)14    if tag == 'program':

L'ordre compte: dans let x = x_prev + 1, la déclaration ne prend effet qu'après son expression droite, ce que reflète l'ajout à declared après le parcours de node[2]. Cette passe est l'embryon d'analyse sémantique que tout compilateur réel exécute avant de générer du code.