Un arbre vérifié ne fait encore rien. L'interpréteur le parcourt et exécute chaque nœud.
⏱️ Durée : environ 90 minutes · 🎓 Niveau : intermédiaire · 🏅 Badge : Chef d'exécution
🎬 L'histoire
HashScript sait lire, comprendre et vérifier un programme. Reste à l'exécuter. Kodi a une intuition : « Il suffit de parcourir l'arbre et de faire ce qu'il dit. » Sam sourit : « C'est exactement ça. Chaque type de nœud sait comment s'exécuter. »
Tu écris l'interpréteur de HashScript : variables, calculs, conditions, boucles.
🎯 Ta mission
À la fin, je serai capable de :
- parcourir un AST pour l'exécuter (interpréteur « tree-walking »)
- gérer un environnement de variables avec des portées de blocs
- exécuter instructions, expressions, conditions et boucles
- signaler les erreurs d'exécution avec leur position
- protéger l'interpréteur contre les boucles infinies
🧩 Défi d'échauffement (5 XP)
Tu reçois une recette sous forme d'arbre (étapes imbriquées). Pour la réaliser, tu fais le tour de l'arbre : sur chaque étape, tu fais l'action correspondante, et tu descends dans ses sous-étapes. Comment sais-tu quand arrêter ? Que fais-tu quand une étape est une répétition (« recommence 3 fois ») ou une condition (« si la sauce a épaissi ») ?
💡 Le concept
Le principe d'un interpréteur d'arbre
Un interpréteur exécute un programme directement à partir de son AST. Il comporte deux fonctions principales :
evaluer(expression): calcule une valeur ;executer(instruction): fait quelque chose (affecter, afficher, répéter).
Le travail consiste à regarder le type de nœud et à appliquer la règle correspondante. On appelle cela l'évaluation récursive.
| Nœud | Règle d'exécution |
|---|---|
Num, Bool | renvoyer la valeur |
Var | lire la variable dans l'environnement |
Bin(op, g, d) | évaluer g, évaluer d, appliquer op |
Neg(e) | évaluer e, changer le signe |
Let(nom, e) | évaluer e, créer la variable |
Assign(nom, e) | évaluer e, la variable existante |
L'environnement et les portées
Les variables vivent dans un environnement : une pile de dictionnaires, un par bloc. Entrer dans un bloc ({ … }) empile un dictionnaire ; en sortir le dépile.
letcrée une variable dans la portée courante ;- lire ou modifier une variable cherche du plus interne au plus externe.
Valeurs et types à l'exécution
HashScript manipule des nombres (entiers/flottants Python) et des booléens. Les erreurs d'exécution typiques : division par zéro, variable inconnue, (plus tard) mauvais appel de fonction. On les signale avec la position du nœud fautif.
Les gardes-fous
Un interpréteur peut être piégé par while true { }. On borne donc le nombre de pas : au-delà d'une limite, on lève une erreur claire. De même, une récursion trop profonde doit être interceptée.
L'interpréteur en Python
import operator
from hashscript import parser, Let, Assign, Print, Si, TantQue, Num, Bool, Var, Bin, Neg, ErreurLangage
OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv,
"<": operator.lt, ">": operator.gt, "<=": operator.le, ">=": operator.ge,
"==": operator.eq, "!=": operator.ne}
class Interprete:
def __init__(self):
self.portees, self.sortie = [{}], []
def chercher(self, nom, noeud):
for portee in reversed(self.portees):
if nom in portee:
return portee
raise ErreurLangage(f"variable inconnue {nom!r}", noeud.ligne, noeud.col)
def evaluer(self, n):
if isinstance(n, (Num, Bool)):
return n.valeur
if isinstance(n, Var):
return self.chercher(n.nom, n)[n.nom]
if isinstance(n, Neg):
-.evaluer(n.expr)
(n, Bin):
a, b = .evaluer(n.gauche), .evaluer(n.droite)
n.op == b == :
ErreurLangage(, n.ligne, n.col)
OPS[n.op](a, b)
ErreurLangage(, , )
():
.portees.append({})
:
i instructions:
.executer(i)
:
.portees.pop()
():
(n, Let):
.portees[-][n.nom] = .evaluer(n.expr)
(n, Assign):
valeur = .evaluer(n.expr)
.chercher(n.nom, n)[n.nom] = valeur
(n, Print):
.sortie.append(.formater(.evaluer(n.expr)))
(n, Si):
.bloc(n.alors .evaluer(n.cond) n.sinon)
(n, TantQue):
.evaluer(n.cond):
.bloc(n.corps)
:
.evaluer(n)
():
v :
v :
(v, ) v == (v): ((v))
(v)
():
instruction parser(source):
.executer(instruction)
.sortie
🧠 Astuce :
isinstanceen cascade est la forme la plus simple. Dans un langage plus grand, on utilise le patron visiteur ou une tabletype de nœud → méthode.
🔍 Exemple pas à pas
Problème : exécuter des programmes HashScript avec l'interpréteur et vérifier le comportement.
import operator
from hashscript import parser, Let, Assign, Print, Si, TantQue, Num, Bool, Var, Bin, Neg, ErreurLangage
OPS = {"+": operator.add, "-": operator.sub, "*": operator.mul, "/": operator.truediv,
"<": operator.lt, ">": operator.gt, "<=": operator.le, ">=": operator.ge,
"==": operator.eq, "!=": operator.ne}
class Interprete:
def __init__(self):
self.portees, self.sortie = [{}], []
def chercher(self, nom, noeud):
for portee in reversed(self.portees):
if nom in portee:
return portee
raise ErreurLangage(f"variable inconnue {nom!r}", noeud.ligne, noeud.col)
def evaluer(self, n):
if isinstance(n, (Num, Bool)): return n.valeur
if isinstance(n, Var): return self.chercher(n.nom, n)[n.nom]
if isinstance(n, Neg): -.evaluer(n.expr)
(n, Bin):
a, b = .evaluer(n.gauche), .evaluer(n.droite)
n.op == b == :
ErreurLangage(, n.ligne, n.col)
OPS[n.op](a, b)
ErreurLangage(, , )
():
.portees.append({})
:
i instructions:
.executer(i)
:
.portees.pop()
():
(n, Let): .portees[-][n.nom] = .evaluer(n.expr)
(n, Assign):
valeur = .evaluer(n.expr)
.chercher(n.nom, n)[n.nom] = valeur
(n, Print): .sortie.append(.formater(.evaluer(n.expr)))
(n, Si): .bloc(n.alors .evaluer(n.cond) n.sinon)
(n, TantQue):
.evaluer(n.cond):
.bloc(n.corps)
: .evaluer(n)
():
v :
v :
(v, ) v == (v): ((v))
(v)
():
instruction parser(source):
.executer(instruction)
.sortie
programmes = {
: (, []),
: (, []),
: (, []),
: (, [, ]),
: (, [, ]),
}
nom, (source, attendu) programmes.items():
sortie = Interprete().lancer(source)
sortie == attendu, (nom, sortie)
()
source (, ):
:
Interprete().lancer(source)
ErreurLangage e:
()
Lecture :
- chaque programme s'exécute en parcourant l'AST ; le résultat est comparé à la valeur attendue ;
let x = 2dans le blocifmasque lexextérieur (portée de bloc) mais ne le modifie pas : le secondprint xaffiche 1 ;- les erreurs d'exécution portent la position du nœud fautif (colonne de l'opérateur
/, de la variable inconnue).
✍️ À toi, avec aide (10 XP)
Ajoute à l'interpréteur une limite de pas : Interprete(limite=10000) compte les instructions exécutées et lève ErreurLangage("trop d'instructions…") au-delà. Montre qu'elle arrête while true { }, et qu'un programme normal (somme de 1 à 100) passe avec une limite de 10 000.
Pense à ce que l'on compte dans une boucle dont le corps est vide.
💡 Indice 1
Incrémente un compteur dans executer et à chaque tour de TantQue.
💡 Indice 2
Une boucle while true { } n'exécute aucune instruction dans son corps : seul le comptage par tour l'arrête.
💡 Indice 3
Réinitialise le compteur dans lancer.
✅ Réponse
# (classe Interprete de l'exemple, étendue)
class InterpreteLimite(Interprete):
def __init__(self, limite=10000):
super().__init__()
self.limite, self.pas = limite, 0
def compter(self):
self.pas += 1
if self.pas > self.limite:
raise ErreurLangage("trop d'instructions exécutées (boucle infinie ?)", 0, 0)
def executer(self, n):
self.compter()
if isinstance(n, TantQue):
while self.evaluer(n.cond):
self.compter() # compte aussi les tours d'une boucle au corps vide
self.bloc(n.corps)
else:
super().executer(n)
assert InterpreteLimite(10000).lancer("let i = 1; let s = 0; while i <= 100 { s = s + i; i = i + 1; } print s;") == []
:
InterpreteLimite().lancer()
AssertionError()
ErreurLangage e:
(e.message)
🚀 À toi, en solo (20 XP)
Trace et profil d'exécution. Étends l'interpréteur pour produire :
- une trace : la liste des
(ligne, type de nœud)des instructions exécutées (affiche les 10 premières poursomme 1..5) ; - un profil : un
Counterdu nombre d'exécutions par type de nœud, y compris les expressions (Bin,Var,Num) ; - une option
pas_a_pasqui appelle une fonction de rappel avant chaque instruction (par exemple pour afficher l'état des variables).
Montre sur le programme « somme 1..10 » que Bin est le nœud le plus exécuté. Qu'en conclus-tu sur les optimisations possibles ?
✅ Pistes de correction
# (classe Interprete de l'exemple)
from collections import Counter
class InterpreteTrace(Interprete):
def __init__(self, rappel=None):
super().__init__()
self.trace, self.profil, self.rappel = [], Counter(), rappel
def evaluer(self, n):
self.profil[type(n).__name__] += 1
return super().evaluer(n)
def executer(self, n):
self.profil[type(n).__name__] += 1
self.trace.append((getattr(n, "ligne", 0), type(n).__name__))
if self.rappel:
self.rappel(n, self.portees)
super().executer(n)
interp = InterpreteTrace()
interp.lancer("let i = 1; let s = 0; while i <= 10 { s = s + i; i = i + 1; } print s;")
print(interp.trace[:10])
(interp.profil.most_common())
etats = []
InterpreteTrace(rappel= n, portees: etats.append((portees[-]))).lancer()
(etats)
⚠️ Pièges classiques
| Piège | Pourquoi c'est un problème | Comment l'éviter |
|---|---|---|
| Oublier de dépiler la portée en cas d'erreur | Les variables fuient dans le bloc suivant | try/finally autour du bloc |
| Évaluer deux fois une expression | Effets de bord dupliqués | Évaluer une fois, stocker le résultat |
| Pas de limite de pas | Un programme malveillant bloque la machine | Compteur de pas et de profondeur |
| Erreurs sans position | Impossible à localiser | Chaque nœud garde ligne et colonne |
🐉 Mini-boss (40 XP)
Fonctions natives (built-ins). Ajoute à l'interpréteur des fonctions fournies par le langage, appelables comme abs(-3) ou max(2, 7) : abs, max, min, racine (racine carrée), entier (partie entière), puissance(a, b).
- Le parseur sait déjà analyser les appels (
Appel(fonction=Var, args=[…])) ; l'interpréteur doit les évaluer. - Chaque fonction native a un nombre d'arguments attendu ; une erreur claire (avec position) est levée sinon.
racined'un nombre négatif doit lever une erreur d'exécution positionnée.- Une fonction native peut être utilisée dans une expression (
1 + max(2, 3) * 2). - Teste avec au moins 12 programmes, valides et invalides.
✅ Pistes de correction
import math
# (classe Interprete de l'exemple)
from hashscript import Appel
class InterpreteNatives(Interprete):
NATIVES = {
"abs": (1, abs), "max": (2, max), "min": (2, min),
"racine": (1, math.sqrt), "entier": (1, math.floor), "puissance": (2, pow),
}
def evaluer(self, n):
if isinstance(n, Appel) and isinstance(n.fonction, Var) and n.fonction.nom in self.NATIVES:
arite, f = self.NATIVES[n.fonction.nom]
if len(n.args) != arite:
raise ErreurLangage(f"{n.fonction.nom} attend {arite} argument(s), reçu {len(n.args)}", n.ligne, n.col)
valeurs = [self.evaluer(a) for a n.args]
n.fonction.nom == valeurs[] < :
ErreurLangage(, n.ligne, n.col)
f(*valeurs)
(n, Appel):
ErreurLangage(, n.ligne, n.col)
().evaluer(n)
():
InterpreteNatives().lancer(source)
lancer() == [, , ]
lancer() == []
lancer() == [, , ]
mauvais, msg ((, ), (, ), (, )):
:
lancer(mauvais)
AssertionError(mauvais)
ErreurLangage e:
msg e.message, e.message
()
⚡ Quiz éclair (15 XP si 4/5 ou plus)
1. Un interpréteur d'arbre exécute un programme en :
- A. le traduisant en code machine à l'avance
- B. parcourant l'AST et appliquant une règle par type de nœud
- C. relisant le texte caractère par caractère
2. Entrer dans un bloc { … } correspond à :
- A. supprimer les variables
- B. terminer le programme
- C. empiler une nouvelle portée
3. Une limite de pas protège contre :
- A. les boucles infinies
- B. les erreurs de syntaxe
- C. les variables inutilisées
4. 🔁 Révision mission 05 : L'analyse sémantique vérifie :
- A. uniquement les parenthèses
- B. noms, déclarations et types
- C. la vitesse d'exécution
5. 🔁 Révision mission 05 : Le typage statique vérifie les types :
- A. pendant l'exécution seulement
- B. jamais
- C. avant l'exécution
✅ Réponses
- B.
- C.
- A.
- B.
- C.
🪞 Je réfléchis (10 XP)
- Dans ta vie, où « exécutes-tu » une structure en la parcourant (une checklist, un organigramme, un arbre de décision) ?
- Pourquoi mettre des gardes-fous dans un interpréteur avant de l'ouvrir à d'autres utilisateurs ?
🎒 À retenir
- evaluer calcule, executer agit.
- Une règle par type de nœud.
- Environnement = pile de portées.
- Erreurs d'exécution positionnées.
- Limite de pas contre les boucles infinies.
flowchart LR
T(["L'interpréteur : faire vivre l'arbre"])
T --> R1["1. evaluer calcule, executer agit."]
T --> R2["2. Une règle par type de nœud."]
T --> R3["3. Environnement = pile de portées."]
T --> R4["4. Erreurs d'exécution positionnées."]
T --> R5["5. Limite de pas contre les boucles infinies."]
Description du schéma : la mission au centre, reliée aux cinq idées à retenir.
🏅 Récompenses
Total possible : 100 XP · 🏅 Badge Chef d'exécution
← Mission 05 — L'analyse sémantique · Mission 07 — Environnement, portée et fermetures →
HEF-090 — Compilateurs et langages

