44
Capitolo 4
Rappresentazione
4.1 Albero della Sintassi Astratta (Abstract Syntax Tree)
E’ possibile realizzare un compilatore fondendo interamente la fase di analisi
semantica , quindi le azioni semantiche, con la fase di parsing (analisi sintattica).
Però, un compilatore così scritto risulta difficile da leggere e mantenere. Inoltre tale approccio costringe il compilatore ad analizzare il programma nell’esatto ordine in cui è stato parsato.
Per aggiungere modularità, sarebbe meglio separare la sintassi (parsing) dalla semantica (type-checking e traduzione in codice macchina).
Un modo per far questo consiste nel far generare al parser un parse tree, cioè una struttura dati che le fasi successive della compilazione possono attraversare. Un parse tree ha esattamente una foglia per ogni token dell’input ed un nodo interno per ogni
regola grammaticale ridotta durante l’analisi sintattica.
Però un parse tree, che in genere è chiamato concrete parse tree perché rappresenta la sintassi concreta del linguaggio, non è conveniente da usare direttamente. Infatti molta della sintassi (parentesi, punti, virgole,…) usata per l’input, non contiene informazioni interessanti da inserire nella struttura dell’albero. Questi dettagli potrebbero essere confinati nella fase di parsing e resi invisibili all’analisi semantica. La sintassi astratta (abstract syntax)[3][5], costituisce un ottimo collante tra il parsing e le fasi successive della compilazione. L’albero della sintassi astratta rappresenta la struttura delle frasi del programma sorgente, con l’intera fase di parsing già risolta, ma senza alcune interpretazioni semantiche.
I primi compilatori non usavano l’albero della sintassi astratta perché i primi computer non avevano sufficiente memoria per rappresentare l’intera struttura dati. I moderni linguaggi di programmazione (in primis Java) permettono di far
45
riferimento agli identificatori definiti magari più avanti nello stesso modulo; un albero della sintassi astratta rende la compilazione per questi linguaggi più facile. Riassumendo e concludendo: il parser usa la sintassi concreta per costruire un parse tree per la sintassi astratta. L’ analisi semantica lavora sull’albero della sintassi
astratta.
Nota
I compilatori hanno bisogno di rappresentare e manipolare l’albero della sintassi astratta come una struttura dati.
Definizione. Sintassi astratta
Essa non è altro che una rappresentazione dei dati indipendente dalla rappresentazione fisica dei dati stessi (sintassi concreta). Definisce infatti come ogni struttura sintattica è scomponibile nei suoi componenti. Questo è espresso mediante una relazione binaria (antisimmetrica) tra termini: relazione orientata dal termine stesso ai sottotermini componenti.
Vediamo un esempio. Consideriamo il termine g(f(y) , z) e costruiamo l’albero della sintassi concreta (a) e l’albero della sintassi astratta (b).
g ( f , z ) ( y ) (a) g f z y (b)
