Valutare l'albero
Calcoli il risultato.
Valutare l'albero è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 3 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.
Percorrere l'AST
La valutazione è una visita post-order: prima si calcolano i figli, poi li si combina utilizzando l'operatore del nodo. Una foglia numerica restituisce semplicemente il proprio valore.
Questo interprete che percorre l'albero è il backend più semplice che un interprete possa avere.
La firma di eval
Il nostro valutatore riceve un puntatore a un nodo e restituisce un intero. Poiché l'albero è ricorsivo, lo è anche la funzione.
Nei linguaggi in virgola mobile si restituirebbe invece un double o un valore con tipo associato.
int eval(Node *n); /* returns the integer value of the subtree */Valutare una foglia
Il caso base interrompe la ricorsione. Quando un nodo contiene un numero, il suo valore è la risposta per quel sottoalbero.
Ogni discesa ricorsiva deve raggiungere un caso base, altrimenti non terminerebbe mai.
int eval(Node *n) {
if (n->kind == N_NUM) {
return n->value;
}
/* ... handle N_BINOP below ... */
return 0;
}Valutare un BinOp
Per un nodo operatore si visitano ricorsivamente entrambi i figli, quindi si applica l'operatore. Valutare prima il figlio sinistro e poi quello destro produce il consueto ordine da sinistra a destra.
Uno switch sul carattere dell'operatore mantiene leggibile la logica.
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;
}Gestire la divisione per zero
La divisione intera per zero produce un comportamento indefinito in C e in genere causa l'arresto del processo. Un interprete sicuro controlla prima il divisore.
Segnalare un errore di runtime chiaro è preferibile a un SIGFPE non gestito.
#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;
}Valutazione end-to-end
Qui un albero costruito manualmente per (2 + 3) * 4 viene valutato ottenendo 20. Lo stesso eval può eseguire qualsiasi albero prodotto dal parser.
Esegua il programma per verificare che la visita post-order calcoli il risultato corretto.
#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;
}Profondità dello stack
Ogni operatore annidato aggiunge un frame allo stack delle chiamate C. Un'espressione profondamente annidata, come una con mille parentesi, può causarne l'overflow.
La maggior parte delle espressioni reali è poco profonda, ma per sicurezza un interprete robusto può passare a uno stack esplicito.
Folding delle costanti
Poiché valutazione e parsing condividono l'albero, è possibile ottimizzarlo. Se entrambi i figli di un binop sono numeri, si può calcolare una volta il risultato e sostituire il nodo con una foglia.
Il constant folding è una classica ottimizzazione degli interpreti.
/* 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;
}Liberare l'albero
I nodi allocati nell'heap devono essere rilasciati. Una liberazione post-order visita i figli prima del padre, rispecchiando la valutazione.
Dimenticarsene causa una perdita di memoria per ogni espressione eseguita dall'interprete.
void free_tree(Node *n) {
if (n->kind == N_BINOP) {
free_tree(n->bin.left);
free_tree(n->bin.right);
}
free(n);
}Meno unario
È necessario gestire la negazione, ad esempio -5. Un'opzione consiste nell'utilizzare un nodo unario; un'altra nel trasformare -x in 0 - x durante il parsing.
In entrambi i casi, la valutazione rimane una semplice visita ricorsiva.
/* desugar approach: parse_factor returns binop('-', num(0), operand) */
if (cur().kind == TOK_MINUS) {
bump();
return binop('-', num(0), parse_factor());
}Perché visitare l'albero?
Gli interpreti che visitano l'albero sono facili da scrivere e correggere, anche se a costo di una certa velocità. Linguaggi come le prime versioni di Ruby utilizzavano questo modello prima di passare a VM bytecode.
Ora aggiungeremo le variabili, così l'interprete potrà ricordare i valori.
Verifica rapida
Ragioni sull'ordine in cui eval visita i nodi.
Riepilogo
Ha implementato un valutatore ricorsivo: il caso base per le foglie, la ricorsione sui binop, un controllo della divisione per zero, oltre alla liberazione dell'albero e al constant folding.
L'interprete ora calcola il valore di qualsiasi AST aritmetico. Il prossimo passo è aggiungere le variabili.
Domande Frequenti
La lezione «Valutare l'albero» è gratuita?
Sì — il testo completo di «Valutare l'albero» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.
Cosa imparerò in «Valutare l'albero»?
Calcoli il risultato. Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare C Academy?
Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 3 di 4.
Quanto tempo richiede la lezione «Valutare l'albero»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione C Academy?
Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Tokenizzare l'input
- Analizzare le espressioni
- Valutare l'albero
- Aggiungere variabili