Gli alberi sintattici astratti sono strutture di dati ampiamente utilizzate nei compilatori per rappresentare la struttura del codice del programma. Un AST è di solito il risultato della fase di analisi della sintassi di un compilatore. Spesso serve come rappresentazione intermedia del programma attraverso diversi stadi che il compilatore richiede, e ha un forte impatto sull’output finale del compilatore.
MotivazioneModifica
Un AST ha diverse proprietà che aiutano le fasi successive del processo di compilazione:
- Un AST può essere modificato e migliorato con informazioni quali proprietà e annotazioni per ogni elemento che contiene. Tale modifica e annotazione è impossibile con il codice sorgente di un programma, poiché implicherebbe cambiarlo.
- Rispetto al codice sorgente, un AST non include punteggiatura inessenziale e delimitatori (parentesi graffe, punti e virgola, parentesi, ecc.).
- Un AST di solito contiene informazioni extra sul programma, dovute alle fasi consecutive di analisi da parte del compilatore. Per esempio, può memorizzare la posizione di ogni elemento nel codice sorgente, permettendo al compilatore di stampare utili messaggi di errore.
Gli AST sono necessari a causa della natura intrinseca dei linguaggi di programmazione e della loro documentazione. I linguaggi sono spesso ambigui per natura. Per evitare questa ambiguità, i linguaggi di programmazione sono spesso specificati come una grammatica senza contesto (CFG). Tuttavia, ci sono spesso aspetti dei linguaggi di programmazione che una CFG non può esprimere, ma sono parte del linguaggio e sono documentati nella sua specifica. Questi sono dettagli che richiedono un contesto per determinare la loro validità e il loro comportamento. Per esempio, se un linguaggio permette di dichiarare nuovi tipi, un CFG non può prevedere i nomi di tali tipi né il modo in cui dovrebbero essere usati. Anche se un linguaggio ha un insieme predefinito di tipi, far rispettare l’uso corretto di solito richiede un certo contesto. Un altro esempio è la tipizzazione delle anatre, dove il tipo di un elemento può cambiare a seconda del contesto. Il sovraccarico degli operatori è ancora un altro caso in cui l’uso corretto e la funzione finale sono determinati in base al contesto. Java fornisce un eccellente esempio, dove l’operatore ‘+’ è sia aggiunta numerica che concatenazione di stringhe.
Anche se ci sono altre strutture dati coinvolte nel funzionamento interno di un compilatore, l’AST svolge una funzione unica. Durante il primo stadio, lo stadio di analisi della sintassi, un compilatore produce un albero di analisi. Questo albero di parse può essere usato per eseguire quasi tutte le funzioni di un compilatore per mezzo della traduzione diretta alla sintassi. Anche se questo metodo può portare ad un compilatore più efficiente, va contro i principi dell’ingegneria del software di scrivere e mantenere programmi. Un altro vantaggio che l’AST ha rispetto ad un albero di parsing è la dimensione, in particolare la minore altezza dell’AST e il minor numero di elementi.
DesignEdit
Il design di un AST è spesso strettamente legato al design di un compilatore e alle sue caratteristiche previste.
I requisiti fondamentali includono i seguenti:
- I tipi di variabile devono essere preservati, così come la posizione di ogni dichiarazione nel codice sorgente.
- L’ordine delle dichiarazioni eseguibili deve essere esplicitamente rappresentato e ben definito.
- Le componenti sinistra e destra delle operazioni binarie devono essere memorizzate e correttamente identificate.
- Gli identificatori e i loro valori assegnati devono essere memorizzati per le dichiarazioni di assegnazione.
Questi requisiti possono essere usati per progettare la struttura dei dati per l’AST.
Alcune operazioni richiedono sempre due elementi, come i due termini per l’addizione. Tuttavia, alcuni costrutti del linguaggio richiedono un numero arbitrariamente grande di figli, come gli elenchi di argomenti passati ai programmi dalla shell di comando. Di conseguenza, un AST usato per rappresentare il codice scritto in un tale linguaggio deve anche essere abbastanza flessibile da permettere la rapida aggiunta di una quantità sconosciuta di figli.
Per supportare la verifica del compilatore dovrebbe essere possibile decodificare un AST in forma di codice sorgente. Il codice sorgente prodotto dovrebbe essere sufficientemente simile all’originale nell’aspetto e identico nell’esecuzione, dopo la ricompilazione.
UsageEdit
L’AST è usato intensamente durante l’analisi semantica, dove il compilatore controlla il corretto uso degli elementi del programma e del linguaggio. Il compilatore genera anche tabelle di simboli basate sull’AST durante l’analisi semantica. Una traversata completa dell’albero permette la verifica della correttezza del programma.
Dopo la verifica della correttezza, l’AST serve come base per la generazione del codice. L’AST è spesso usato per generare una rappresentazione intermedia (IR), a volte chiamata linguaggio intermedio, per la generazione del codice.
Si tratta di una rappresentazione intermedia.