Analizzare le espressioni
Costruisca un albero di analisi sintattica.
Analizzare le espressioni è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 2 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.
Dai token all'albero
Il parsing trasforma un flusso piatto di token in un Albero sintattico astratto (AST) strutturato. L'albero codifica precedenza e raggruppamento, che i token grezzi implicano soltanto.
Per 3 + 4 * 2, l'AST annida la moltiplicazione sotto l'addizione, quindi il risultato è 11, non 14.
Struttura dei nodi AST
Ogni nodo è una foglia numerica oppure un'operazione binaria con due figli. Una struct con tag e union mantiene ridotto l'uso della memoria.
Il carattere dell'operatore distingue +, -, * e / durante l'esecuzione.
typedef struct Node {
enum { N_NUM, N_BINOP } kind;
union {
int value; /* N_NUM */
struct { /* N_BINOP */
char op;
struct Node *left, *right;
} bin;
};
} Node;Allocare i nodi
Due piccoli costruttori allocano i nodi nell'heap. Costruire l'albero dal basso verso l'alto significa creare prima le foglie e poi racchiuderle nei nodi degli operatori.
In un interprete di produzione sarebbe necessario tenere traccia di queste allocazioni per liberarle in seguito.
#include <stdlib.h>
static Node *num(int v) {
Node *n = malloc(sizeof *n);
n->kind = N_NUM; n->value = v;
return n;
}
static Node *binop(char op, Node *l, Node *r) {
Node *n = malloc(sizeof *n);
n->kind = N_BINOP;
n->bin.op = op; n->bin.left = l; n->bin.right = r;
return n;
}La grammatica
Utilizziamo una grammatica classica basata sulla precedenza. expr gestisce + e -, term gestisce * e /, mentre factor gestisce numeri e parentesi.
Poiché le regole con precedenza maggiore si trovano più in profondità, la moltiplicazione ha automaticamente una precedenza maggiore rispetto all'addizione.
/* Grammar (EBNF):
expr = term { ('+' | '-') term } ;
term = factor { ('*' | '/') factor } ;
factor = NUMBER | '(' expr ')' ; */Corrispondenza dei token
Un helper expect consuma un token del tipo richiesto oppure interrompe l'esecuzione. È il contratto tra il parser e il lexer.
Riutilizziamo gli helper di lookahead cur e bump della lezione sul tokenizer.
#include <stdio.h>
#include <stdlib.h>
static void expect(TokKind k) {
if (cur().kind != k) {
fprintf(stderr, "parse error: unexpected token\n");
exit(1);
}
bump();
}Analisi di un fattore
Un fattore è l'elemento atomico della grammatica: può essere un numero letterale oppure una sottoespressione tra parentesi. Le parentesi richiamano ricorsivamente parse_expr.
È questa ricorsione a dare il nome ai parser a discesa ricorsiva.
static Node *parse_expr(void);
static Node *parse_factor(void) {
if (cur().kind == TOK_NUM) {
int v = cur().value; bump();
return num(v);
}
expect(TOK_LPAREN);
Node *e = parse_expr();
expect(TOK_RPAREN);
return e;
}Analisi di un termine
Un termine analizza un fattore, poi continua in un ciclo finché incontra * o /, incorporando ciascun operatore in un nodo binop associativo a sinistra.
L'associatività a sinistra significa che 8 / 4 / 2 viene analizzato come (8 / 4) / 2 = 1.
static Node *parse_term(void) {
Node *left = parse_factor();
while (cur().kind == TOK_STAR || cur().kind == TOK_SLASH) {
char op = (cur().kind == TOK_STAR) ? '*' : '/';
bump();
left = binop(op, left, parse_factor());
}
return left;
}Analisi di un'espressione
La regola principale rispecchia parse_term, ma gestisce + e -. Ogni livello richiama la regola con precedenza immediatamente superiore, quindi l'albero risulta annidato correttamente.
Questa struttura a tre funzioni è il cuore del parser.
static Node *parse_expr(void) {
Node *left = parse_term();
while (cur().kind == TOK_PLUS || cur().kind == TOK_MINUS) {
char op = (cur().kind == TOK_PLUS) ? '+' : '-';
bump();
left = binop(op, left, parse_term());
}
return left;
}Esame dell'albero
Questo programma analizza un'espressione e la ristampa in una forma completamente racchiusa tra parentesi, mostrando come è stata risolta la precedenza.
Il pretty-printer visita ricorsivamente la stessa struttura di nodi costruita dal parser.
#include <stdio.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 void show(Node *n){
if (n->is_num){ printf("%d", n->value); return; }
printf("("); show(n->l); printf(" %c ", n->op); show(n->r); printf(")");
}
int main(void){
/* 3 + 4 * 2 -> (3 + (4 * 2)) */
Node *ast = B('+', N(3), B('*', N(4), N(2)));
show(ast); printf("\n");
return 0;
}Evitare la ricorsione a sinistra
Una grammatica ingenua come expr = expr '+' term farebbe sì che parse_expr richiami se stessa all'infinito. La discesa ricorsiva non è in grado di gestire la ricorsione a sinistra diretta.
Riscrivere la regola come un ciclo while su { '+' term } evita completamente la ricorsione infinita.
Perché un AST?
L'AST separa la sintassi dall'esecuzione. Lo stesso albero può essere valutato, ottimizzato o compilato in bytecode senza dover eseguire nuovamente il parsing.
Ora percorreremo questo albero per calcolarne il valore.
Verifica rapida
Consideri in che modo i livelli della grammatica impongono la precedenza.
Riepilogo
Ha scritto un parser a discesa ricorsiva: strutture per i nodi dell'AST, costruttori e le funzioni expr/term/factor che codificano la precedenza e l'associatività a sinistra.
L'albero risultante è pronto per la valutazione.
Domande Frequenti
La lezione «Analizzare le espressioni» è gratuita?
Sì — il testo completo di «Analizzare le espressioni» è 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 «Analizzare le espressioni»?
Costruisca un albero di analisi sintattica. 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 2 di 4.
Quanto tempo richiede la lezione «Analizzare le espressioni»?
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