Albero sintattico astratto

In informatica, un albero sintattico astratto (AST) o semplicemente albero sintattico è una rappresentazione ad albero della struttura sintattica astratta del testo (spesso codice sorgente) scritto in un linguaggio formale. Ogni nodo dell'albero denota un costrutto che si verifica nel testo.

La sintassi è "astratta" nel senso che non rappresenta ogni dettaglio presente nella sintassi reale, ma solo quelli strutturali o relativi al contenuto. Ad esempio, le parentesi di raggruppamento sono implicite nella struttura ad albero quindi non devono essere rappresentate da nodi separati. Similmente, un costrutto solitamente sintattico come l'istruzione se-condizione-allora può essere denotato per mezzo di un singolo nodo con tre rami.

Questo distingue gli alberi sintattici astratti da quelli concreti, tradizionalmente designati come alberi di analisi che sono tipicamente costruiti da un parser durante la traduzione del codice sorgente e il processo di compilazione. Una volta costruiti, ulteriori informazioni vengono aggiunte all'AST mediante elaborazioni successive come le analisi contestuali.

Gli alberi sintattici astratti vengono utilizzati anche nell'analisi del programma e nei sistemi di trasformazione del programma.

Applicazione nei compilatori

Gli alberi sintattici astratti sono strutture dati ampiamente utilizzate dai compilatori per rappresentare la struttura del codice sorgente. Un AST è in genere il risultato della fase di analisi sintattica del compilatore. Spesso funge da rappresentazione intermedia del programma attraverso le diverse fasi di compilazione e ha un forte impatto sul risultato finale.

Motivazioni

Un AST ha diverse proprietà che aiutano nelle varie fasi del processo di compilazione:

Può essere modificato e migliorato con informazioni quali proprietà e annotazioni per ogni elemento che contiene, impossibile da fare con il codice sorgente di un programma, poiché implicherebbe cambiarlo.
Rispetto al codice sorgente, un AST non include punteggiatura e delimitatori non essenziali (parentesi, punto e virgola, ecc.).
Di solito contiene informazioni extra sul programma, a causa delle varie fasi di analisi da parte del compilatore. Ad esempio, può memorizzare la posizione di ciascun elemento nel codice sorgente, consentendo al compilatore di stampare utili messaggi di errore.

Gli AST sono necessari a causa della natura intrinseca dei linguaggi di programmazione e della relativa documentazione. Le lingue sono spesso ambigue per natura. Per evitare questa ambiguità, i linguaggi di programmazione sono spesso specificati come grammatica libera dal contesto (CFG). Tuttavia, ci sono spesso aspetti dei linguaggi di programmazione che una CFG non può esprimere, ma fanno parte del linguaggio e sono documentati nelle sue specifiche. Questi sono dettagli che richiedono un contesto per determinarne la validità e il comportamento. Ad esempio, se un linguaggio consente la dichiarazione di nuovi tipi, una CFG non può prevedere i nomi di tali tipi né il modo in cui debbano essere utilizzati. Anche se un linguaggio ha un insieme predefinito di tipi, il modo corretto di utilizzarli di norma richiede un contesto. Un altro esempio è il duck typing, in cui il tipo di un elemento può cambiare a seconda del contesto. L'overloading degli operatori è un altro caso in cui l'utilizzo corretto e la funzione finale dipendono dal contesto.

Design

La progettazione di un AST è spesso strettamente collegata alla progettazione di un compilatore e alle sue caratteristiche.

I requisiti fondamentali includono quanto segue:

I tipi di variabile devono essere preservati, così come la posizione di ogni dichiarazione nel codice sorgente.
L'ordine delle istruzioni eseguibili deve essere rappresentato in modo esplicito e ben definito.
I componenti sinistro e destro delle operazioni binarie devono essere memorizzati e identificati correttamente.
Gli identificatori e i relativi valori devono essere memorizzati per le istruzioni di assegnazione.

Questi requisiti possono essere usati per progettare la struttura dati per l'AST.

Alcune operazioni richiedono sempre due elementi, come i due termini per l'addizione. Tuttavia, alcuni costrutti di linguaggio richiedono un numero arbitrariamente elevato di elementi figlio, come l'elenco di argomenti passati ai programmi dalla shell. Di conseguenza, un AST utilizzato per rappresentare il codice scritto in tale linguaggio deve anche essere sufficientemente flessibile da consentire l'aggiunta rapida di una quantità sconosciuta di figli.

Per supportare la verifica del compilatore, dovrebbe essere possibile riconvertire l'AST in un codice sorgente sufficientemente simile all'originale nell'aspetto e identico nell'esecuzione dopo la ricompilazione.

Utilizzo

L'AST viene utilizzato intensamente durante l'analisi semantica, dove il compilatore verifica il corretto utilizzo degli elementi del programma e del linguaggio. Il compilatore genera anche la tabella dei simboli in base all'AST durante l'analisi semantica. Un attraversamento completo dell'albero permette di verificare la correttezza del programma.

Dopo aver verificato la correttezza, l'AST funge da base per la generazione del codice la quale spesso avviene per mezzo di una rappresentazione intermedia (IR) talvolta detta linguaggio intermedio.

Voci correlate

Document Object Model (DOM)
Lisp, famiglia di linguaggi basati su alberi (chiamati liste) e macro per la loro manipolazione
Albero sintattico, detto anche albero sintattico concreto