L4) Qu’est-ce qu’un AST ?

Pourquoi les compilateurs ne travaillent-ils pas directement sur votre code source ? Parce qu’un arbre vaut mieux qu’une chaîne de caractères.

Où se situe cet article ?

Cet article fait partie de la série Langages formels (L). Il présente l’arbre syntaxique abstrait, produit par l’analyse des grammaires context-free (L2) décrites en EBNF (L3). L’AST est la représentation centrale du pipeline (chaîne de traitement) BP2SC.

Pourquoi c’est important ?

Vous avez écrit du code. Le compilateur doit le comprendre, le vérifier, peut-être l’optimiser, puis le traduire. Mais votre code est une simple suite de caractères — des lettres, des chiffres, des symboles. Comment le manipuler intelligemment ?

L’AST (Abstract Syntax Tree, arbre syntaxique abstrait) est la réponse. C’est une représentation structurée de votre code qui capture son sens sans s’encombrer des détails de sa forme. Parenthèses, espaces, points-virgules — tout ça disparaît. Il ne reste que la structure logique.

Pour le transpileur (traducteur de code source à code source) BP2SC (BP3-to-SuperCollider, voir I2 et I3), l’AST est le cœur du système. Chaque fichier BP3 (le langage de grammaires musicales du Bol Processor, voir I2) est d’abord parsé (parsed, analysé syntaxiquement) en un arbre de 12 types de nœuds différents, puis cet arbre est parcouru pour générer le code SuperCollider (environnement de synthèse sonore, voir I3) équivalent.

L’idée en une phrase

Un AST est une représentation arborescente du code source qui conserve sa structure logique tout en éliminant les détails syntaxiques non essentiels.

Expliquons pas à pas

Parse tree vs AST : la différence cruciale

Quand un parseur (analyseur syntaxique) analyse du code, il produit d’abord un parse tree (arbre de dérivation, aussi appelé arbre syntaxique concret) qui reflète exactement les règles de la grammaire. Cet arbre contient tout, y compris les éléments purement syntaxiques.

Analogie : le script vs le scénario

Imaginez une pièce de théâtre :

Le script complet inclut toutes les didascalies, les numéros de page, les indications techniques (« lumières à 50% »). C’est le parse tree.

Le scénario épuré ne garde que les dialogues et les actions essentielles. C’est l’AST.

Les deux représentent la même pièce, mais l’un est fidèle à la forme, l’autre au fond.

Exemple avec 2 + 3 :

Parse tree (arbre de dérivation) :

        Expr
       / | \
    Expr "+" Terme
      |        |
   Terme    Facteur
      |        |
  Facteur     "3"
      |
     "2"

Cet arbre contient les nœuds Expr, Terme, Facteur qui correspondent aux règles de la grammaire. C’est fidèle, mais verbeux.

AST (arbre abstrait) :

    Add
   /   \
  2     3

L’AST ne garde que l’essentiel : une opération d’addition avec deux opérandes. Les niveaux intermédiaires ont disparu.

Pourquoi cette simplification ?

Manipulation plus simple : moins de nœuds à parcourir
Indépendance de la grammaire : on peut changer la syntaxe sans modifier l’AST
Focus sur la sémantique : l’arbre représente ce que le code fait, pas comment il est écrit

Exemple 1 : l’expression `2 + 3 * 4`

Construisons l’AST de cette expression étape par étape.

Le code source : 2 + 3 * 4

L’AST résultant :

Observations importantes :

La priorité est encodée : Mul est un enfant de Add, donc la multiplication sera évaluée d’abord
Pas de parenthèses : elles ne sont pas dans l’arbre, mais leur effet y est
Les nombres sont des feuilles : ce sont des valeurs terminales

Évaluation de l’AST (parcours post-ordre) :

Qu’est-ce qu’un parcours post-ordre ?

Un parcours (ou traversée) est une façon systématique de visiter tous les nœuds d’un arbre. Le post-ordre signifie : « d’abord les enfants, ensuite le parent ».

Pourquoi post-ordre pour évaluer ? Parce qu’on doit connaître le résultat des sous-expressions avant de pouvoir calculer l’expression parente. On ne peut pas calculer 2 + (3*4) sans d’abord calculer 3*4.

1. Visiter le nœud Add
2.   Visiter enfant gauche → 2
3.   Visiter enfant droit (Mul)
4.     Visiter enfant gauche → 3
5.     Visiter enfant droit → 4
6.     Évaluer Mul(3, 4) → 12    <-- enfants évalués d'abord
7.   Évaluer Add(2, 12) → 14     <-- parent évalué après

Structure d’un nœud AST

En pratique, un nœud AST est souvent une classe ou une structure de données :

from dataclasses import dataclass
from typing import Union

@dataclass
class Number:
    value: int

@dataclass
class BinOp:
    op: str          # "+", "-", "*", "/"
    left: 'Expr'
    right: 'Expr'

Expr = Union[Number, BinOp]

L’AST de 2 + 3 * 4 en Python :

ast = BinOp(
    op="+",
    left=Number(2),
    right=BinOp(
        op="*",
        left=Number(3),
        right=Number(4)
    )
)

Exemple 2 : l’AST de BP3

Le transpileur BP2SC définit 12 types de nœuds pour représenter tous les éléments d’un fichier BP3 :

Nœud	Représente	Exemple BP3
`BPFile`	Fichier complet	(racine)
`GrammarBlock`	Section de grammaire	`ORD[1]`
`Rule`	Règle de production	`S --> A B`
`Weight`	Poids d’une règle (voir B4)	`<50>`, `<50-12>`
`Flag`	Condition ou opération (voir B4)	`/Ideas/`, `/Ideas-1/`
`Note`	Note musicale	`do4`, `C#5`
`Rest`	Silence	`-`
`NonTerminal`	Symbole à développer	`S`, `Phrase`
`Variable`	Variable entre pipes	`\\|x\\|`
`Polymetric`	Expression polymétrique (voir B5)	`{2, A B C}`
`SpecialFn`	Fonction spéciale	`_transpose(3)`
`HomoApply`	Homomorphisme (voir B6)	`(= \\|x\\|)`

Exemple concret — la règle BP3 :

<50> /Ideas/ S --> A _transpose(2) do4 {2, B C}

Son AST :

Rule
├── weight: Weight(value=50, decrement=None)
├── flags: [Flag(name="Ideas", op="condition")]
├── lhs: [NonTerminal("S")]
└── rhs:
    ├── NonTerminal("A")
    ├── SpecialFn(name="transpose", args=[2])
    ├── Note(name="do", octave=4, accidental=None)
    └── Polymetric(ratio=2, elements=[
        NonTerminal("B"),
        NonTerminal("C")
    ])

Chaque élément du code source correspond à un nœud typé dans l’arbre.

Traversée d’un AST

Pour exploiter un AST, on le parcourt (ou traverse) : on visite systématiquement chaque nœud pour effectuer une opération. Il existe plusieurs stratégies, chacune adaptée à un usage :

Les trois ordres de parcours en profondeur

Imaginez visiter une maison à plusieurs étages :

Pré-ordre : noter chaque pièce en entrant, avant d’explorer ses sous-pièces

Post-ordre : noter chaque pièce en sortant, après avoir exploré ses sous-pièces

In-ordre : pour les arbres binaires, alterner gauche-centre-droite

Parcours en profondeur (depth-first) :

Stratégie	Ordre de visite	Cas d’usage
Pré-ordre	Nœud, puis enfants	Copier l’arbre, sérialiser
Post-ordre	Enfants, puis nœud	Évaluer, calculer des propriétés
In-ordre	Gauche, nœud, droite	Afficher expressions infixes

Parcours en largeur (breadth-first) :

Visiter niveau par niveau, de haut en bas
Utile pour les analyses qui dépendent de la « profondeur » dans l’arbre

Le pattern Visitor :

Qu’est-ce qu’un « pattern » de conception ?

Un design pattern (patron de conception) est une solution réutilisable à un problème récurrent en programmation. Ce sont des « recettes » éprouvées.

Le pattern Visitor résout ce problème : « Comment ajouter de nouvelles opérations sur un AST sans modifier les classes de nœuds à chaque fois ? »

Analogie : Imaginez un musée (l’AST) avec des œuvres (les nœuds). Plutôt que de modifier chaque œuvre pour ajouter une nouvelle fonctionnalité (audio-guide, description en braille…), on crée un « visiteur » spécialisé qui sait interagir avec chaque type d’œuvre.

En programmation orientée objet, le pattern Visitor permet d’ajouter des opérations sans modifier les classes de nœuds :

class ASTVisitor:
    def visit(self, node):
        method_name = f'visit_{type(node).__name__}'
        visitor = getattr(self, method_name, self.generic_visit)
        return visitor(node)

    def generic_visit(self, node):
        raise NotImplementedError(f"No visitor for {type(node)}")

class Evaluator(ASTVisitor):
    def visit_Number(self, node):
        return node.value

    def visit_BinOp(self, node):
        left = self.visit(node.left)
        right = self.visit(node.right)
        if node.op == '+': return left + right
        if node.op == '*': return left * right
        # ... autres opérations

# Utilisation
evaluator = Evaluator()
result = evaluator.visit(ast)  # → 14

De l’AST au code cible

Le transpileur BP2SC (voir B7) utilise l’AST pour générer du code SuperCollider. Chaque type de nœud a une règle de traduction :

Nœud BP3	Code SuperCollider
`Rule(lhs=S, rhs=[A,B])`	`Pdef(\S, Pseq([Pdef(\A), Pdef(\B)]))`
`Note(do, 4)`	`Pbind(\midinote, 60, \dur, 0.25)`
`Rest`	`Event.silent(0.25)`
`Polymetric(2, [A,B,C])`	`Pbindf(Pseq([...]), \stretch, 2/3)`
`SpecialFn(transpose, 3)`	`Pbindf(..., \mtranspose, 3)`

Exemple de traduction :

// BP3
S --> do4 re4 mi4

// AST
Rule(lhs=[NonTerminal("S")], rhs=[Note("do",4), Note("re",4), Note("mi",4)])

// SuperCollider
Pdef(\S, Pseq([
    Pbind(\midinote, 60, \dur, 0.25),
    Pbind(\midinote, 62, \dur, 0.25),
    Pbind(\midinote, 64, \dur, 0.25)
], 1))

Pourquoi l’AST est central

L’AST est le pivot de tout compilateur ou transpileur :

Code source → [Lexer] → Tokens → [Parser] → AST → [Emitter] → Code cible
                                                 ^
                                                 |
                                          Point central

Les étapes du pipeline de compilation

Étape Rôle Entrée Sortie

Lexer Découper le texte en unités "2 + 3" [NUM:2, PLUS, NUM:3]

Parser Construire la structure Liste de tokens AST

Emitter Générer le code cible AST Code exécutable

>
Lexer (ou tokenizer) : transforme une chaîne de caractères en tokens (jetons), les unités significatives du langage. Exemple : 123 devient un token NUMBER, if devient un token KEYWORD.

Tokens : unités lexicales du langage (nombres, opérateurs, mots-clés, identifiants). Ce sont les « mots » reconnus par le lexer avant l’analyse syntaxique.

Étape	Rôle	Entrée	Sortie
Lexer	Découper le texte en unités	`"2 + 3"`	`[NUM:2, PLUS, NUM:3]`
Parser	Construire la structure	Liste de tokens	AST
Emitter	Générer le code cible	AST	Code exécutable

Avantages de cette architecture :

Séparation des responsabilités : le parser s’occupe de la syntaxe, l’emitter de la génération
Analyses intermédiaires : on peut vérifier, optimiser, transformer l’AST avant émission
Multi-cibles : un même AST peut générer du code pour différentes plateformes
Testabilité : on peut tester le parser et l’emitter indépendamment

Ce qu’il faut retenir

Un AST est une représentation arborescente du code source, épurée des détails syntaxiques non essentiels.
Parse tree vs AST : le parse tree est fidèle à la grammaire, l’AST est fidèle au sens.
Les nœuds sont typés : chaque construction du langage a son type de nœud (Note, Rule, BinOp…).
La traversée permet l’exploitation : évaluation, génération de code, analyse statique.
L’AST est le point central de tout compilateur : il découple l’analyse syntaxique de la génération de code.
BP2SC utilise 12 types de nœuds pour représenter l’intégralité de la notation BP3.

Pour aller plus loin

Module Python ast : https://docs.python.org/3/library/ast.html (pour explorer les AST Python)
AST Explorer : https://astexplorer.net/ (visualisation interactive d’AST pour de nombreux langages)
Dragon Book, chapitre 5 : Syntax-Directed Translation
Pattern Visitor : https://refactoring.guru/design-patterns/visitor

Glossaire

Terme	Définition
AST	Abstract Syntax Tree (arbre syntaxique abstrait). Représentation arborescente du code source qui conserve la structure logique en éliminant les détails syntaxiques non essentiels (parenthèses, virgules de décoration, etc.).
Design pattern	Solution réutilisable à un problème récurrent en conception logicielle. Le pattern Visitor est un exemple classique pour les AST.
Emitter	Composant d’un compilateur qui génère le code cible (ou code objet) à partir de l’AST. Aussi appelé « générateur de code ».
Feuille	Nœud terminal de l’arbre, sans enfants. Représente les valeurs atomiques : nombres, identifiants, chaînes de caractères.
Lexer	Première étape d’un compilateur. Découpe le code source en tokens (unités lexicales). Aussi appelé « tokenizer » ou « analyseur lexical ».
Nœud	Élément de l’arbre représentant une construction du langage. Chaque nœud a un type (BinOp, Note, Rule…) et zéro ou plusieurs enfants.
Parse tree	Arbre de dérivation fidèle aux règles de la grammaire. Plus détaillé que l’AST, il inclut tous les éléments syntaxiques. Aussi appelé « arbre syntaxique concret ».
Parcours	Visite systématique de tous les nœuds d’un arbre selon une stratégie définie (pré-ordre, post-ordre, in-ordre, ou en largeur).
Post-ordre	Stratégie de parcours où l’on visite d’abord tous les enfants d’un nœud, puis le nœud lui-même. Idéal pour l’évaluation d’expressions.
Pré-ordre	Stratégie de parcours où l’on visite d’abord le nœud, puis ses enfants. Idéal pour copier ou sérialiser un arbre.
Token	Unité lexicale du langage, produite par le lexer. Exemples : nombre, opérateur, mot-clé, identifiant. Un token a un type et une valeur.
Traversée	Synonyme de parcours. Action de visiter systématiquement tous les nœuds de l’arbre.
Visitor	Pattern de conception permettant d’ajouter des opérations sur l’AST sans modifier les classes de nœuds. Chaque type d’opération est un « visiteur » distinct.

Prérequis : L2 — Grammaires context-free, L3 — EBNF
Temps de lecture : 9 min
Tags : #ast #compilation #parsing #arbres #transpilation

Article suivant : L5 — Les trois sémantiques : donner du sens aux langages formels