Évaluer l’arbre
Calculez le résultat.
Évaluer l’arbre est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 3 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.
Parcourir l'AST
L'évaluation est un parcours postfixé : calculez d'abord les enfants, puis combinez-les avec l'opérateur du nœud. Une feuille représentant un nombre renvoie simplement sa valeur.
Cet interpréteur qui parcourt l'arbre est le moteur d'exécution le plus simple qu'un interpréteur puisse avoir.
La signature de eval
Notre évaluateur reçoit un pointeur vers un nœud et renvoie un entier. Comme l'arbre est récursif, la fonction l'est également.
Pour les langages utilisant des nombres à virgule flottante, vous renverriez plutôt un double ou une valeur étiquetée.
int eval(Node *n); /* returns the integer value of the subtree */Évaluer une feuille
Le cas de base arrête la récursion. Lorsqu'un nœud représente un nombre, sa valeur est la réponse correspondant à ce sous-arbre.
Toute descente récursive doit atteindre un cas de base, sinon elle ne se terminerait jamais.
int eval(Node *n) {
if (n->kind == N_NUM) {
return n->value;
}
/* ... handle N_BINOP below ... */
return 0;
}Évaluer un BinOp
Pour un nœud opérateur, nous descendons récursivement dans les deux enfants, puis appliquons l'opérateur. Évaluer la partie gauche avant la partie droite donne l'ordre habituel de gauche à droite.
Un switch sur le caractère de l'opérateur rend la logique plus lisible.
int eval(Node *n) {
if (n->kind == N_NUM) return n->value;
int l = eval(n->bin.left);
int r = eval(n->bin.right);
switch (n->bin.op) {
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
}
return 0;
}Protéger la division par zéro
La division entière par zéro constitue un comportement indéfini en C et provoque généralement l'arrêt du processus. Un interpréteur sûr vérifie d'abord le diviseur.
Signaler une erreur d'exécution claire vaut mieux qu'un SIGFPE incontrôlé.
#include <stdio.h>
#include <stdlib.h>
static int safe_div(int a, int b) {
if (b == 0) {
fprintf(stderr, "runtime error: division by zero\n");
exit(1);
}
return a / b;
}Évaluation de bout en bout
Ici, un arbre construit manuellement pour (2 + 3) * 4 est évalué à 20. Le même eval pourrait exécuter n'importe quel arbre produit par l'analyseur syntaxique.
Exécutez-le pour vérifier que le parcours postfixé calcule le bon résultat.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int is_num; int value;
char op; struct Node *l, *r;
} Node;
static Node *N(int v){ Node*n=calloc(1,sizeof*n); n->is_num=1; n->value=v; return n; }
static Node *B(char o,Node*a,Node*b){ Node*n=calloc(1,sizeof*n); n->op=o; n->l=a; n->r=b; return n; }
static int eval(Node *n){
if (n->is_num) return n->value;
int l = eval(n->l), r = eval(n->r);
switch (n->op){
case '+': return l + r;
case '-': return l - r;
case '*': return l * r;
case '/': return l / r;
}
return 0;
}
int main(void){
Node *ast = B('*', B('+', N(2), N(3)), N(4));
printf("%d\n", eval(ast));
return 0;
}Profondeur de la pile
Chaque opérateur imbriqué ajoute une trame à la pile d'appels de C. Une expression profondément imbriquée, comme une expression contenant mille parenthèses, peut la faire déborder.
La plupart des expressions réelles sont peu profondes, mais un interpréteur robuste peut utiliser une pile explicite pour éviter ce problème.
Réduire les constantes
Comme l'évaluation et l'analyse syntaxique partagent le même arbre, vous pouvez l'optimiser. Si les deux enfants d'un nœud binop sont des nombres, vous pouvez calculer le résultat une fois et remplacer le nœud par une feuille.
Cette réduction des constantes est une optimisation classique des interpréteurs.
/* fold: collapse a binop of two literals into one literal */
Node *fold(Node *n) {
if (n->kind == N_BINOP) {
n->bin.left = fold(n->bin.left);
n->bin.right = fold(n->bin.right);
if (n->bin.left->kind == N_NUM &&
n->bin.right->kind == N_NUM)
return num(eval(n));
}
return n;
}Libérer l'arbre
Les nœuds alloués sur le tas doivent être libérés. Une libération postfixée parcourt les enfants avant le parent, comme lors de l'évaluation.
Oublier cette étape provoque une fuite de mémoire à chaque expression exécutée par l'interpréteur.
void free_tree(Node *n) {
if (n->kind == N_BINOP) {
free_tree(n->bin.left);
free_tree(n->bin.right);
}
free(n);
}Signe moins unaire
Il faut traiter la négation, comme dans -5. Une possibilité consiste à utiliser un nœud unaire ; une autre consiste à transformer -x en 0 - x lors de l'analyse syntaxique.
Dans les deux cas, l'évaluation reste un simple parcours récursif.
/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
bump();
return binop('-', num(0), parse_factor());
}Pourquoi parcourir l'arbre ?
Les interpréteurs qui parcourent l'arbre sont faciles à écrire et à déboguer, au prix d'une certaine perte de vitesse. Des langages comme les premières versions de Ruby utilisaient ce modèle avant de passer à des machines virtuelles à bytecode.
Nous allons ensuite ajouter des variables afin que l'interpréteur puisse mémoriser des valeurs.
Vérification rapide
Réfléchissez à l'ordre dans lequel eval visite les nœuds.
Récapitulatif
Vous avez implémenté un évaluateur récursif : un cas de base pour les feuilles, la récursion des nœuds binop, une protection contre la division par zéro, ainsi que la libération de l'arbre et la réduction des constantes.
L'interpréteur calcule maintenant n'importe quel AST arithmétique. L'ajout des variables est la prochaine étape.
Questions Fréquemment Posées
La leçon « Évaluer l’arbre » est-elle gratuite ?
Oui — le texte complet de « Évaluer l’arbre » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.
Qu'est-ce que j'apprendrai dans « Évaluer l’arbre » ?
Calculez le résultat. Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.
Dois-je avoir de l'expérience pour commencer C Academy ?
Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 3 sur 4.
Combien de temps prend la leçon « Évaluer l’arbre » ?
La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.
Peux-tu écrire et exécuter du code dans cette leçon C Academy ?
Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.