5.1-Definizioni orientate alla sintassi - principio del compilatore (2023)

UNdefinizione diretta dalla sintassi(SDD) è una grammatica libera dal contesto insieme aattributiEregole. Gli attributi sono associati ai simboli grammaticali e le regole sono associate alle produzioni. SeXè un simbolo eUNè uno dei suoi attributi, quindi scriviamoX.aper indicare il valore diUNin un particolare nodo dell'albero di analisi etichettatoX. Se implementiamo i nodi dell'albero di analisi per record o oggetti, allora il fileattributiDiXpuò essere implementato dai campi dati nei record che rappresentano i nodi perX. Gli attributi possono essere di qualsiasi tipo: numeri, tipi, riferimenti a tabelle o stringhe, ad esempio. Le stringhe possono anche essere lunghe sequenze di codice, diciamo codice nel linguaggio intermedio usato da un compilatore.

NOTA: SDD è composto da due elementi: attributo e regola, quindi SDD viene utilizzato in futuro, devi essere chiaro che significa attributo e regola.

5.1.1 Attributi ereditati e sintetizzati

Ci occuperemo di due tipi di attributi pernon terminali:

1. UNattributo sintetizzatoper unnon terminale UNin un nodo dell'albero di analisiNè definito da aregola semanticaassociato alla produzione aN. Si noti che la produzione deve avereUNcome suoTesta. UNattributo sintetizzatoal nodoNè definito solo in termini di valori di attributo ai figli diNe aNsi.
2. UNattributo ereditatoper unnon terminale Bin un nodo dell'albero di analisiNè definito da aregola semanticaassociato alla produzione presso la casa madre diN. Si noti che la produzione deve avereBcome simbolo nel suo corpo. UNattributo ereditatoal nodoNè definito solo in termini di valori di attributo atNil genitore,Nstesso, eNfratelli.

NOTA: Il metodo di classificazione di cui sopra si basa su come calcolare il valore dell'attributo. È ovvio che la direzione del calcolo diattributo sintetizzatoè in contrasto conattributo ereditato'S. Più precisamente,attributo sintetizzatoè adatto aanalisi dal basso verso l'altoMentreattributo ereditatoè adatto aanalisi dall'alto verso il basso. L'Esempio 5.2 mostra comeattributo sintetizzatoviene calcolato mentre l'esempio 5.3 mostra comeattributo ereditatoviene calcolato. Il calcolo dell'attributo sarà discusso nel capitolo successivo.

NOTA: Un SDD può avere contemporaneamente attributo ereditato e attributo ereditato, introdotto nel capitolo 5.1.2.

Mentre non permettiamo unattributo ereditatoal nodoNda definire in termini di valori di attributo ai figli di nodeN, consentiamo un attributo sintetizzato in nodeNda definire in termini diattributo ereditatovalori al nodoNsi.

NOTA:Attributo ereditato, il nome ha implicato che l'attributo è ereditato da parent, quindi è naturale cheattributo ereditatoal nodoNnon può essere definito in termini di valori di attributo albambinidi nodoNo sarà autocontraddittorio.

I terminali possono avereattributi sintetizzati, ma noattributi ereditati. Gli attributi per i terminali hanno valori lessicali forniti dall'analizzatore lessicale; non ci sono regole semantiche nello stesso SDD per calcolare il valore di un attributo per un terminale.

NOTA: che ne dici di un simbolo di inizio? È ovvio che un simbolo di inizio non può avere un attributo ereditato perché è l'antenato e non ha un genitore.

Esempio 5.1: saltato

Un SDD che coinvolge soloattributi sintetizzatiè chiamatoS-attribuito; l'SDD in Fig. 5.1 ha questa proprietà. In unSDD attribuito a S, ogni regola calcola un attributo per il non terminale all'inizio di una produzione dagli attributi presi dal corpo della produzione.

Per semplicità, gli esempi in questa sezione hanno regole semantiche senza effetti collaterali. In pratica, è conveniente consentire agli SDD di avere effetti collaterali limitati, come la stampa del risultato calcolato da una calcolatrice da tavolo o l'interazione con una tabella dei simboli. Una volta discusso l'ordine di valutazione degli attributi nella Sezione 5.2, consentiremo alle regole semantiche di calcolare funzioni arbitrarie, possibilmente con effetti collaterali.

Un SDD attribuito a S può essere implementato naturalmente insieme a unanalizzatore LR.

Un SDD senza effetti collaterali è talvolta chiamato angrammatica degli attributi. Le regole in una grammatica degli attributi definiscono il valore di un attributo esclusivamente in termini di valori di altri attributi e costanti.

5.1.2 Valutazione di un SDD nei nodi di un albero di analisi

Per visualizzare la traduzione specificata da un SDD, è utile lavorare con gli alberi di analisi, anche se un traduttore non ha bisogno di creare effettivamente un albero di analisi. Immagina quindi che le regole di un SDD vengano applicate costruendo prima un albero di analisi e quindi utilizzando le regole per valutare tutti gli attributi in ciascuno dei nodi delalbero di analisi. UNalbero di analisi, che mostra il/i valore/i dei suoi attributi è chiamato analbero di analisi annotato.

Come costruiamo unalbero di analisi annotato? In quale ordine valutiamo gli attributi? Prima di poter valutare un attributo in un nodo di un albero di analisi, dobbiamo valutare tutti gli attributi da cui dipende il suo valore. Ad esempio, se tutti gli attributi sonosintetizzato, come nell'Esempio 5.1, allora dobbiamo valutare thevalattributi a tutti i figli di un nodo prima di poter valutare ilvalattributo al nodo stesso.

Conattributi sintetizzati, possiamo valutare gli attributi in qualsiasi ordine dal basso verso l'alto, come quello di un attraversamento post-ordine dell'albero di analisi; la valutazione delle definizioni S-attribuite è discussa nella Sezione 5.2.3.

Per gli SDD con attributi sia ereditati che sintetizzati, non vi è alcuna garanzia che esista un solo ordine in cui valutare gli attributi nei nodi. Ad esempio, considera i non terminaliUNEB, con attributi sintetizzati ed ereditatiCOMEEBi, rispettivamente, insieme alla produzione e alle regole

Queste regole sono circolari; è impossibile valutare entrambiCOMEad un nodoNOBial figlio diNsenza prima valutare l'altro. ILdipendenza circolareDiCOMEEBiin qualche coppia di nodi in un albero di analisi è suggerito dalla Fig. 5.2.

È computazionalmente difficile determinare se ne esistano o menocircolaritàin uno qualsiasi degli alberi di analisi che un dato SDD potrebbe dover tradurre. Fortunatamente esistono utili sottoclassi di SDD sufficienti a garantire l'esistenza di un ordine di valutazione, come vedremo nella Sezione 5.2.

NOTA: Di seguito è riportata la spiegazione del perché determinarne l'esistenza o menocircolaritàin uno qualsiasi degli alberi di analisi di un dato SDD è computazionalmente difficile:

Senza entrare nei dettagli, mentre il problema è decidibile, non può essere risolto da un algoritmo tempo-polinomiale, anche se P = NP , poiché ha complessità temporale esponenziale.

In realtà, questo è un problema di algoritmotrova il ciclo nel grafico.

Esempio 5.2: saltato

Esempio 5.3 :L'SDD in Fig. 5.4 calcola termini come3 * 5E3 * 5 * 7. ILdall'alto al bassoanalisi dell'input3 * 5inizia con la produzioneT \to F T'. Qui,Fgenera la cifra 3, ma l'operatore*è generato daT'. Pertanto, l'operando di sinistra 3 appare in un diverso sottoalbero dell'albero di analisi da*. UNattributo ereditatoverrà quindi utilizzato per passare l'operando all'operatore. La grammatica in questo esempio è un estratto da una versione non ricorsiva a sinistra della familiare grammatica delle espressioni; abbiamo usato una grammatica di questo tipo come esempio per illustrare l'analisi dall'alto verso il basso nella Sezione 4.4.

Figura 5.4: Un SDD basato su una grammatica adatta per l'analisi top-down

Ciascuno dei non terminaliTEFha unattributo sintetizzato val; la cifra terminale ha aattributo sintetizzato lexval. Il non terminaleT'ha due attributi: anattributo ereditato inhe unattributo sintetizzato sin.

Le regole semantiche si basano sull'idea che l'operando sinistro dell'operatore*è ereditato. Più precisamente, la testaT'della produzioneT' \to * F T_1'eredita l'operando sinistro di*nel corpo di produzione. Dato un terminex * y * z, la radice del sottoalbero per* e * zereditaX. Quindi, la radice del sottoalbero for*zeredita il valore di* x * a, e così via, se ci sono più fattori nel termine. Una volta che tutti i fattori sono stati accumulati, il risultato viene ritrasmesso all'albero utilizzandoattributi sintetizzati.

Per vedere come vengono utilizzate le regole semantiche, si consideri l'albero di analisi annotato for3 * 5nella figura 5.5. La foglia più a sinistra nell'albero di analisi, etichettatacifra, ha un valore di attributolexval = 3, dove il3è fornito dalanalizzatore lessicale. Il suo genitore è per la produzione 4,F \a cifra. L'unica regola semantica associata a questa produzione definisceF.val = digit.lexval, che è uguale a 3.

Al secondo figlio della radice, l'attributo ereditatoPuroè definito dalla regola semanticaT'.inh = F.valassociato alla produzione 1. Pertanto, l'operando sinistro, 3, per il*L'operatore viene passato da sinistra a destra attraverso i figli della radice.

La produzione al nodo perT'ÈT' \to * F T_1'. (Conserviamo il pedice 1 nell'albero di analisi annotato per distinguere tra i due nodi perT'.) L'attributo ereditato $T_1'.inh $ è definito dalla regola semanticaT_1'.inh = T'.inh * F.valassociato alla produzione 2.

ConT'.in = 3EF.val = 5, noi abbiamoT_1'.inh = 15. Al nodo inferiore perT_1', la produzione èT' \to \epsilon. La regola semanticaT'.syn = T'.inhdefinisceT_1'.syn = 15. ILsinattributi ai nodi perT'passare il valore 15 sull'albero al nodo forT, DoveT.val = 15.