Linguaggi formali e compilazione -...

LFC

Analisi semanticae generazione delcodice intermedioSymbol table e regole diambiente

Rappresentazioniintermedie

Dall’AST alla generazionedel three-address code

Traduzione guidata dallasintassi

Linguaggi formali e compilazioneCorso di Laurea in Informatica

A.A. 2014/2015

LFC





Linguaggi formali e compilazione

Cenni alle regole di ambiente e generazione del codice intermedioSymbol table e regole di ambienteRappresentazioni intermedieDall’AST alla generazione del three-address codeTraduzione guidata dalla sintassi

LFC





Static scoping

◮ Abbiamo già osservato come le informazionicontenute nella symbol table consentano dicontrollare il soddisfacimento di alcuni requisiti dicorrettezza del programma che sarebbe complicato“forzare” nella sintassi

◮ Esempi riguardano:1. il fatto che una variabile sia stata definita prima di

venire usata2. la concordanza dei tipi3. la concordanza sul numero di parametri formali e

argomenti di una funzione

◮ Ora vedremo brevemente come un’accuratarealizzazione della symbol table consenta anche diimplementare le regole statiche di ambiente o divisibilità dei simboli (in inglese static scoping rule).

LFC





Ambiente

◮ Lo scope (ambiente) della dichiarazione di unavariabile è la porzione di programma in cui talevariabile è visibile (e dunque utilizzabile).

◮ Lo stesso identificatore può essere definito più voltein un programma, ma ad esso saranno associatiambienti diversi.

◮ Nei moderni linguaggi di programmazione l’ambientedi una variabile è “quasi sempre” determinabile inmodo statico, cioè guardando il testo del programma.

◮ In particolare, la visibilità è determinata dallastruttura di annidamento dei blocchi di programma.

◮ In questo caso si parla di static (o lexical) scoping.

LFC





Esempio (in Pascal)

Program P;

var i:integer;

c:char;

x:real;

function f(x:integer);

var i:integer;

procedure z;

var x:integer;

begin

(1)end

begin

(2)end

begin

(3)end

LFC





Static scoping

◮ L’implementazione della nozione di ambiente puòessere realizzata nel compilatore mediante unastruttura a stack della symbol table.

◮ Più precisamente, si utilizzano più tabelleconcatenate e la symbol table nel suo insieme è unalista di tabelle.

◮ Quando incontra l’inizio di un blocco di programma, ilcompilatore inizializza una tabella e la inserisce intesta alla lista.

◮ Quando incontra la fine di un blocco rimuove latabella in testa alla lista.

LFC





Static scoping (2)

◮ L’inserimento di un simbolo avviene sempre nellatabella di testa.

◮ Il look up della symbol table avviene dapprima nellatabella di testa.

◮ In caso di search hit, il look up termina, altrimentiprocede nella successiva tabella.

◮ Se il simbolo non viene trovato in alcuna tabella si hauna search miss (con eventuale generazione di unmessaggio di errore).

LFC





Esempio

◮ Si consideri, come esempio, il seguente sempliceframmento di programma C++:

1. { int i,j;

2. cin » i » j;

3. { int i; float x;

4. i=1;

5. x=2.0*j;

6. cout « i « “: ” « x;

7. }8. cout « i « “: ” « j;

9. }

LFC





Esempio (continua)

◮ All’ingresso del blocco più esterno viene creata unatabella S1 (essenzialmente un dizionario) che divienela testa della symbol table.

◮ Gli identificatori i e j di riga 1 vengono inseriti in S1.

i, int

j, int

S1

ST

LFC





Esempio (continua)

◮ All’ingresso del blocco interno (riga 3) viene creata(e inserita in testa alla symbol table) una secondatabella, S2, nella quale vengono poi inseriti gliidentificatori i e x di riga 3 (col loro tipo).

i , int

j, int

S1

i , int

x, f loat

S2

ST

◮ Il riferimento alla variabile i di riga 4 viene risolto conun lookup alla tabella di testa (S2), che contieneun’entry con chiave i.

LFC





Esempio (continua)

◮ Il riferimento alla variabile j di riga 5 viene risolto conun lookup alla tabella S1, dopo aver cercato“inutilmente” in S2 un’entry con chiave j.

◮ Si noti come la definizione della variabile i di riga 3,unitamente al processo di lookup, renda invisibile,nel blocco interno, la variabile i definita a riga 1.

◮ All’uscita del blocco interno, il puntatore alla testadella symbol table viene fatto avanzare, con l’effettodi rendere inaccessibile la tabella di testa (S2).

◮ Il riferimento alla variabile i di riga 8 verrà quindinuovamente risolto con un lookup a S1.

LFC





Altri usi della symbol table

◮ Oltre all’implementazione delle regole d’ambiente e averifiche di correttezza semantica, le informazionicontenute nella symbol table sono fondamentali insede di generazione del codice

◮ Ad esempio, la entry per un identificatore contiene:◮ la sequenza di caratteri che ne costituisce il lessema

(che può essere usata come chiave per l’accessoalle tabelle);

◮ il tipo della variabile;◮ l’indirizzo (relativo) di memoria della variabile.

◮ Fra gli altri usi, il tipo è importante per stabilirel’occupazione di memoria mentre l’indirizzo serve pergenerare gli operandi nelle istruzioni macchina.

LFC





Le due parti del compilatore

◮ Il passaggio dal codice sorgente ad un codicemacchina efficiente viene tipicamente spezzato indue parti.

◮ La prima parte, gestita dal front-end del compilatore,termina con la generazione di un opportuno codiceintermedio ed è chiaramente dominata dallecaratteristiche del linguaggio sorgente.

◮ La seconda parte, gestita dal back-end, è invecespecializzata ad ottenere un codice macchinaefficiente in funzione della particolare architettura.

◮ La suddivisione netta del progetto di un compilatorein front-end e back-end (la prima indipendentedall’architettura e la seconda indipendente dallinguaggio) ha, fra le altre proprietà, un notevoleimpatto in termini di economicità di progetto.

◮ Le rappresentazioni intermedie più importanti sono isyntax tree e il cosiddetto three-address code.

LFC





Three address code

◮ Il codice a tre indirizzi è una rappresentazioneintermedia lineare del programma sorgenteindipendente da ogni specifica architettura.

◮ Più precisamente, il three address code è il codiceper una architettura astratta di calcolatore.

◮ Tale modello descrive abbastanza fedelmente lastruttura di ogni macchina reale, evitando tuttavia ditrattare tutti i complessi dettagli delle moderneachitetture.

LFC





Il modello di calcolo per il three address code

◮ Il calcolatore astratto è in grado di eseguire sempliciistruzioni caratterizzate da un codice operativo e daal più tre indirizzi per gli operandi (da qui il nome).

◮ Fra le istruzioni disponibili in tale modello dicalcolatore, troviamo le operazioni logico/aritmetichebinarie e unarie, le istruzioni di salto (condizionato oincondizionato), il semplice assegnamento, lachiamata di procedura e la gestione di array lineari.

◮ Ogni istruzione può essere preceduta da una o piùetichette (stringhe letterali), utilizzate nelle istruzionidi salto.

LFC





Esempio (cfr: Compilatori: Principi, tecnichee strumenti)

◮ L’istruzione condizionale

potrebbe essere tradotta nel seguente frammento dithree address code:

◮ Come si vede dall’esempio, il codice èsufficientemente vicino ad un ragionevole codicemacchina, pur essendo indipendente da ogniparticolare architettura.

LFC





Three address code (2)

◮ I moderni compilatori generano codice intermediolineare (come il three address code, del qualetorneremo ad occuparci più avanti) in manieradiretta.

◮ In queste note (per ragioni didattiche) supporremoinvece che il three address code sia il risultato finaledi una serie di passaggi “più fini”.

◮ Tali ulteriori passaggi intermedi trasformano ilprogramma sorgente in rappresentazioni ad allberoequivalenti.

◮ Queste rappresentazioni sono lo stesso parse tree e,soprattutto, l’abstract syntax tree.

◮ Peraltro, la generazione esplicita del parse tree è(quasi sempre) evitabile.

LFC





Abstract syntax tree

◮ Un abstract syntax tree (AST) per un linguaggio L èun albero in cui:

◮ i nodi interni rappresentano costrutti di L;◮ i figli di un nodo che rappresenta un costrutto C

rappresentano a loro volta le “componentisignificative” di C;

◮ le foglie sono “costrutti elementari” (nonulteriormente decomponibili) caratterizzati da unvalore lessicale (tipicamente un numero o unpuntatore alla symbol table).

◮ Le diapositive seguenti illustrano la nozione diabstract syntax tree.

LFC





Esempio

◮ Un abstract syntax tree per la frase id + id× id è+

×

〈id,ptr〉〈id,ptr〉

〈id,ptr〉

◮ Abstract syntax tree e parse tree sono oggetti diversi.E

T

F

id

×T

F

id

+E

T

F

id

LFC





Esempio◮ Un AST per l’assegnamento a=b*(-c)+b*(-c):

◮ Un AST per il comandodo i=i+1 while (a[i]>v)

LFC





Abstract syntax tree (2)

◮ L’utilità degli AST è riassumibile nelle seguentiaffermazioni.

◮ Partendo da un AST la generazione del threeaddress code è un esercizio sufficientementesemplice (anche se l’intero processo è menoefficiente della generazione diretta di codiceintermedio).

◮ Nella realizzazione di semplici linguaggi intepretati (ocomunque di applicazioni dove l’efficienza non sia ilprincipale requisito) gli AST possono rappresentare ilrisultato ultimo della compilazione.

◮ Risulta infatti molto semplice (in generale, e inrapporto alla complessità di realizzare uncompilatore completo) implementare un software perinterpretare gli AST.

LFC





Un semplice interprete per le espressioniaritmetiche

◮ La diapositiva seguente presenta lo pseudocodiceper un semplice interprete di AST che rappresentanoespressioni aritmetiche.

◮ Ogni nodo dell’albero tre campi:◮ un campo etichetta (label) che, se il nodo è interno,

contiene un codice di operatore (come, ad esempio,PLUS, TIMES, MINUS, UNARY_MINUS, ...),se invece il nodo è una foglia contiene un puntatorealla symbol table;

◮ un campo puntatore al primo operando (left);◮ un campo puntatore all’eventuale secondo operando.

◮ Lo pseudocodice usa una routine (apply) cherestituisce il valore dell’applicazione di un operatorebinario a due operandi passati come parametri.

LFC





Un semplice interprete per le espressioniaritmetiche

EVAL(NODE v )1: if left(v) 6= nil then

2: x ← eval(left(u))3: if label(v) = UNARY_MINUS then

4: return −x

5: y ← eval(right(u))6: return apply(label(v), x , y)7: else

8: return symlookup(label(v))

LFC





Assunzioni

◮ Presentiamo ora alcuni semplici esempi digenerazione di codice intermedio.

◮ Non intendiamo presentare una descrizionecompleta, sia per ragioni di tempo sia perché (anostro avviso) questa attività è molto menointeressante dal punto di vista delle idee sottostanti.

◮ Gli esempi hanno dunque il solo scopo di illustrarel’approccio base per la generazione di codiceintermedio, ignorando quegli aspetti cherichiederebbero un ragionamento più approfondito.

◮ Faremo inoltre tre ipotesi molto forti, e precisamente:(1) di disporre dell’abstract syntax tree delle stringheda tradurre; (2) che il risultato debba esserepresentato sotto forma di file alfanumerico, (3) cheesista un unico tipo di dato nei programmi sorgenti(ad esempio, numeri interi).

LFC





Istruzioni specifiche del three-address code

◮ Allo scopo di presentare gli esempi, considereremosolo le seguenti istruzioni, il cui significato dovrebberisultare chiaro:

◮ A← B op C, dove op ∈ {+,−,×, /} e A,B e C sonoidentificatori definiti dall’utente nel programmasorgente oppure temporanee generate dal parser;

◮ A← B, dove A e B sono definiti come al puntoprecedente;

◮ A← op B, dove op è un operatore unario;◮ goto L, dove L è un’etichetta generata dal parser;◮ if A goto L, dove A è un identificatore definito

dall’utente oppure una temporanea generata dalparser ed L è un’etichetta generata dal parser;

◮ ifFalse A goto L, dove A ed L sono definiti comeal punto precedente.

LFC





Ulteriori assunzioni◮ Ipotizzeremo che il parser possa invocare una

funzione per generare identificatori univoci, comepure una funzione per generare etichette univoche.

◮ Assumeremo inoltre la disponibilità di una funzione,che chiameremo emit(), che stampa la stringapassata come parametro (che rappresenta unaporzione del programma in three-address code) suun opportuno supporto di output.

◮ Assumeremo infine che il generico nodo dell’abstractsyntax tree abbia la seguente struttura:

◮ un campo label che caratterizza il tipo di nodo(assegnamento, operatore, comando if, ...);

◮ se significativo (ad esempio nel caso di identificatoreo operatore), un puntatore alla symbol table per ilcorrispondente valore lessicale, accessibie mediantela funzione lexval;

◮ uno o più puntatori ai nodi che rappresentano icomponenti del costrutto, accessibili mediante icampi c1, c2, ...

LFC





La struttura generale del traduttore

◮ Con le ipotesi fatte, il traduttore (da syntax tree athree-address code) può essere organizzato comeprocedura ricorsiva il cui corpo è costituitoessenzialmente da una “grossa” istruzione case (o,se si preferisce, switch), che analizza il nodo p

passato come parametro e, a seconda del tipo,esegue operazioni diverse.

◮ Data la struttura del parse tree, la generazione delcodice per un dato nodo implicherà poi una o piùchiamate ricorsive per la generazione del codiceassociato ai nodi figli.

◮ La procedura, che chiameremo gencode, riceve unulteriore parametro (RES) che è una stringa(eventualmente vuota) alla quale (vista come nomedi variabile) deve essere assegnato il risultatocalcolato dal codice generato per il nodo p.

LFC





Procedura gencode

LFC





Procedure 1 gencode(string RES,AST ∗ p)

tag← (p→ label)case tag of

id : . . .number : . . .assignment : . . .comparison : . . .binaryop : . . .unaryminus : . . .seq : . . .if : . . .ifElse : . . .while : . . .

. . .default : error()

end

LFC





Il caso degli identificatori

◮ Si tratta del caso più semplice da trattare.◮ Infatti, se un nodo è etichettato come identificatore,

tutto ciò che bisogna fare è semplicemente emettereuna stringa che ne rappresenta il valore lessicale.

◮ Al riguardo, utilizziamo una funzione toString (esisteanche in Java), che, nel caso il valore lessicaledell’identificatore sia già internamente rappresentatocome stringa, equivale ad un no-op.

◮ Per altri tipi di nodo, toString svolge effettivamenteuna funzione: ad esempio, se il nodo è un operatorebinario, la chiamata toString(lexval(p)) ne fornisce laconsueta rappresentazione matematica (+,-, ecc).

LFC





Il caso degli identificatori (continua)

◮ Il codice relativo a questo caso è dunque:

id : string name← toString(lexval(p))if not empty(RES) then

emit(RES+“←”+name)else

emit(name)

dove l’operatore + applicato a stringhe denotaconcatenazione.

◮ Si noti anche il controllo (che sarà ricorrente anchenei seguenti esempi) sulla stringa RES.

◮ Se RES non è la stringa vuota, il codice da generaredeve infatti prevedere un assegnamento al nome daessa rappresentato.

LFC





Costanti numeriche

◮ Il caso delle costanti numeriche è identico a quellodegli identificatori.

◮ C’è solo un maggior lavoro (nascosto) da parte dellaprocedura toString, che deve ri-trasformare insequenza ASCII un numero rappresentatointernamente in virgola fissa o virgola mobile.

id : string const← toString(lexval(p))if not empty(RES) then

emit(RES+“←”+const)else

emit(const)

LFC





Assegnamento

◮ Un nodo etichettato come assignment ha due figli, ilprimo dei quali deve necessariamente essere un id .

◮ Il codice da generare prevede la chiamata ricorsivaal secondo figlio, in modo che lasci il valore nellavariabile il cui nome è il valore lessicale del primofiglio.

◮ In altre parole:

assignment : string name← lexval(p→ c1)if not empty(RES) then

gencode(name,p→ c2)emit(RES+“←”+name)

else

gencode(name,p→ c2)

LFC





Gli operatori (aritmetici) binari

◮ Se l’etichetta del nodo è un operatore binariobisogna:

◮ generare ricorsivamente il codice per il figlio disinistra, in modo che lasci il risultato in una variabileil cui nome univoco è generato dal parser stesso(supporremo che tali nomi abbiano la forma TEMPn,con n progressivo);

◮ generare (analogamente) il codice per figlio di destra,in modo che lasci il risultato in una seconda variabile;

◮ generare la stringa per un’istruzione a tre o dueindirizzi (a seconda del valore del parametro RES)che esegue l’operazione indicata dal particolareoperatore binario sui dati memorizzati nelletemporanee.

LFC





Gli operatori (aritmetici) binari (continua)

◮ Il codice corrispondente è:

binaryop :string t1← new temporary()string t2← new temporary()gencode(t1,p→ c1)gencode(t2,p→ c2)string op← toString(lexval(p))if not empty(RES) then

emit(RES+“←”+t1+ op+ t2)else

emit(t1+ op+ t2)

LFC





Esempio

◮ Per l’abstract syntax tree del comando C/C++x = a+ b× c (rappresentato in modo da evidenziaredirettamente il valore lessicale degli operatori e degliidentificatori)

=

+

×

cb

a

x

viene generato il seguente codice a tre indirizzitemp1← a

temp3← b

temp4← c

temp2← temp3× temp4

x← temp1+ temp2

LFC





L’operatore “meno” unario

◮ È semplicissimo da realizzare.◮ Si tratta dapprima di generare il codice per

l’espressione che costituisce l’unico figlio, lasciandoil risultato il una temporanea.

◮ Al risultato si applica poi l’operatore meno unariouminus.

◮ Il codice è:

unaryminus :string t← new temporary()gencode(t,p→ c1)if not empty(RES) then

emit(RES+“← uminus”+t)else

emit(“uminus + t′′)

LFC





Sequenza◮ Una sequenza di comandi, definita dalle produzioni

L → L;S | S,

produce alberi sintattici con la struttura indicata diseguito (in cui ogni singolo statement può, a suavolta, essere un syntax tree)

seq

statementseq

statementseq

statementstatements

◮ Il codice corrispondente consiste semplicemente didue chiamate ricorsive:

seq :gencode(“”,p→ c1)gencode(“”,p→ c2)

LFC





Comando “If then”

◮ È rappresentato da alberi sintattici del tipoif

statementexpression

◮ I passi per effettuare la traduzione sono i seguenti:◮ si genera ricorsivamente il codice per calcolare

l’espressione, lasciando il risultato in unatemporanea;

◮ si genera un’etichetta e si emette un’istruzione disalto a tale etichetta, condizionato al valore falsodella temporanea;

◮ si genera quindi ricorsivamente il codice per ilcomando (che verrà dunque eseguito se il valoredella temporanea è vero);

◮ infine si emette l’etichetta generata (che andrà adetichettare la prossima istruzione a tre indirizzi, nonemessa dal trattamento del condizionale).

LFC





Comando “If then” (2)

◮ Il codice corrispondente è:

if :string t← new temporary()gencode(t,p→ c1)string l← new label()emit(“ifFalse ”+t+“ goto ”+l)gencode(“”,p→ c2)emit(l+“: ”)

LFC





Comando “If then else”

◮ È solo leggermente più complicato del casoprecedente, per cui presentiamo direttamente ilcodice

ifElse :string t← new temporary()gencode(t,p→ c1)string l1← new label()emit(“ifFalse ”+t+“ goto ”+l1)gencode(“”,p→ c2)string l2← new label()emit(“goto ”+l2)emit(l1+ “ :′′)gencode(“”,p→ c3)emit(l2+“: ”)

LFC





Esempio

◮ Alla frase C/C++

if a >= 0 then x = a else x = −a

corrisponde il seguente abstract syntax treeifElse

=

-

a

x

=

ax

≥

0a

(si ricordi che abbiamo scelto di evidenziaredirettamente il valore lessicale degli operatori e degliidentificatori anziché inserire simboli astratti eriferimenti alla symbol table).

LFC





Esempio (continua)

◮ Il codice a tre indirizzi corrispondente è:

temp2← a

temp3← 0temp1← temp2 ≥ temp3

ifFalse temp1 goto label1

x← a

goto label2

label1 : temp4← a

x← −temp4label2 :

LFC





Comando “while”

◮ Come ultimo caso, consideriamo la traduzione diabstract syntax tree corrispondenti al costrutto while.

◮ Il costrutto ha due componenti, la condizione e lostatement da ripetere finché la condizione è vera.

◮ La strategia di traduzione consiste quindi nelgenerare il codice per la condizione, emettereun’istruzione di salto condizionato (ifFalse),generare il codice per il comando ed emettereun’istruzione di salto incondizionato al codicegenerato per la condizione.

◮ Lo pseudocodice dettagliato è riportato nellasuccessiva trasparenza.

LFC





Comando “while” (2)

while :string t← new temporary()string l1← new label()emit(l1+“: ”)gencode(t,p→ c1)string l2← new label()emit(“ifFalse ”+t+“ goto ”+l2)gencode(“”,p→ c2)emit(“goto ”+l1)emit(l2+“: ”)

LFC





Traduzione guidata dalla sintassi

◮ La generazione dell’abstract syntax tree, il nostroobiettivo attuale, può essere eseguita mediantel’applicazione di una tecnica nota come Traduzione

guidata dalla sintassi (in inglese Syntax-Directed

Translation).◮ L’output desiderato (un abstract syntax tree) viene

cioè generato mediante un processo che è guidatodalla stessa grammatica e, in particolare, dalle sueproduzioni.

◮ La tecnica è simile a quella utilizzata da Yacc perassociare azioni alle produzioni.

◮ Nel caso di Yacc le azioni potevano essere di naturaqualsiasi, mentre qui ci interesseranno solo azioni dicostruzione dell’abstract syntax tree.

LFC





Traduzione guidata dalla sintassi (2)

◮ Tipicamente, quando viene effettuata una riduzione(nel parsing bottom-up, come per Yacc), viene ancheeseguita una qualche azione (ad esempio, lacreazione di nodi e il loro “aggancio” all’albero incostruzione).

◮ Nel caso di parsing top-down l’azione viene eseguitain fase di applicazione di una produzione.

◮ La modalità specifica che vedremo per larealizzazione del processo di costruzione dell’AST èquella degli schemi di traduzione (syntax-directed

translation scheme).

LFC





Syntax-directed translation scheme

◮ Uno schema di traduzione prevede la specifica diframmenti di codice, che vengono associati alleproduzioni della grammatica (esattamente comeavviene in Yacc)

◮ L’insieme dei frammenti non costituisce però unprogramma

◮ Al riguardo, e sempre ponendo a mente il caso diYacc, ci sono due fondamentali domande cuidobbiamo rispondere

1. Quali sono e dove sono memorizzati i dati manipolatidai frammenti di codice?

2. Chi e come “forza” un ordine di esecuzione deiframmenti in modo che costituiscano un programmaorganico e corretto?

LFC





Attributi

◮ Nel caso degli schemi di traduzione, i dati manipolatisono attributi associati ai simboli della grammatica.

◮ Se X è un simbolo della grammatica e a è il nome diun suo attributo, useremo la scrittura X .a perindicare il valore dell’attributo a di X .

◮ Come già osservato a proposito di Yacc, la scritturaX .a si applica non tanto al “generico” simbolo X

bensì ad una sua occorrenza nella derivazione (o,equivalentemente, nel parse tree).

◮ Il valore di un attributo può essere di qualunquenatura: stringa, numero, puntatore, tipo di dato, ecc.

LFC





Attributi (2)

◮ Nel nostro caso, i valori degli attributi sarannopuntatori al “costruendo” syntax tree.

◮ Per questa ragione, associato ad ogni non terminaledella grammatica si troverà sempre un attributo dinome node.

◮ In alcuni casi ci potranno essere anche ulterioriattributi

◮ Siamo ora in grado di presentare il nostro primoesempio di schema di traduzione, relativo alla piùsemplice grammatica per le espressioni aritmetiche.

LFC





Esempio

E → E1 + T {E .node← new node(′+′,E1.node,T .node)}

E → T {E .node← T .node}T → T1 × F {T .node← new node(′×′,T1.node,

F .node)}T → F {T .node← F .node}F → (E) {F .node← E .node}F → id {F .node← new leaf(id, id.lexval)}

◮ Si noti che:◮ ai non terminali è associato il solo attributo node;◮ ai terminali è associato l’attributo lexval (tipicamente,

un puntatore alla entry della symbol table).◮ l’aggiunta dell’indice ai non terminali E e T , nella

parte destra delle produzioni E → E + T eT → T × F , serve unicamente a disambiguare iriferimenti nelle corrispondenti azioni.

LFC





Calcolabilità degli schemi

◮ Come possiamo acquisire la capacità di scrivereschemi di traduzione corretti?

◮ In parole ancora più semplici: come possiamoimparare a mettere le “azioni giuste” a fianco delleproduzioni per poter creare effettivamente il syntaxtree della frase in input?

◮ Per raggiungere questo obiettivo, bisogna averechiaro come il parser mette assieme le singole azionispecificate in un processo di calcolo completo.

◮ Al riguardo è utile immaginare che il parsercostruisca effettivamente il parse tree.

LFC





Calcolabilità degli schemi (2)

◮ L’utilità del parse tree è che esso rende più facilevisualizzare istanze diverse di uno stesso simbolodella grammatica.

◮ Ad esempio, se il non terminale E viene usato duevolte in una derivazione, questo appare in modoevidente nel parse tree.

◮ Ci saranno infatti due nodi etichettati con il simboloE .

◮ Se riferita al parse tree, un’azione come{T .node← F .node} “dice” che il parser dovracopiare il valore di un attributo (node) da un nodo adun altro dell’albero.

LFC






◮ Utilizzando il parse tree, inoltre, l’ordine diesecuzione delle azioni di uno schema è determinatoda da un processo (ideale) di attraversamento delparse tree.

◮ L’ordine di visita (e dunque di esecuzione delleistruzioni previste nello schema) deve essere taleche il valore calcolato ad un dato nodo dipenda soloda valori che sono già stati calcolati (dunque in nodigià visitati).

LFC





Calcolabilità degli schemi (4)◮ Riconsideriamo lo schema relativo alla semplice

grammatica le espressioni:




e il parse tree relativo alla frase id + id× id:

N

+

E

T

FT

F id

id

E

T

F

id

M

LFC






◮ Nel parse tree soffermiamoci su due nodi N ed M

(padre e figlio) etichettati rispettivamente con i nonterminali T ed F .

◮ In corrispondenza della produzione T → F èpresente la regola {T .node← F .node}.

◮ Questo richiede che M sia visitato prima di N.◮ In generale le azioni eseguita dal parser saranno

quantomeno coerenti se inserite in una visitadell’albero che soddisfa la seguente proprietà

fondamentale:

se un attributo X .a presente in un nodo N

(con etichetta X ) dipende da un attributoY .b presente in un nodo M, allora M viene(almeno parzialmente) visitato prima di N.

LFC





Tipi di attributi

◮ Definiamo le due diverse tipologie di attributiutilizzate nelle applicazioni reali: gli attributisintetizzati e gli attributi ereditati.

◮ Consideriamo una generica produzione

A→ X1 . . .Xi−1Xi . . .Xk

◮ un attributo di A si dice sintetizzato se il suo valoredipende solo dal valore degli attributi dei simboli Xi

nella parte destra della produzione e(eventualmente) di altri attributi di A stesso.

◮ In termini di parse tree, è sintetizzato un attributo nelnodo A che dipenda solo dagli attributi in A o nei nodifigli X1 . . .Xi−1Xi . . .Xk .

LFC





Tipi di attributi (2)

◮ I simboli terminali della grammatica avranno soloattributi sintetizzati.

◮ Uno schema in cui tutti gli attributi siano sintetizzati èdetto S-attributed.

◮ Lo schema:




è chiaramente S-attributed.

LFC





Esempio◮ Esaminando la seguente figura, si comprende come

l’attraversamento in ordine posticipato del parse treeper id + id × id porti alla costruzione dell’AST.

E

T

F

id

+

E

T

FT

F id

id

E.node

E.node

T.node

T.node

F.node

T.node

F.node

F.node

<id,id.lexval> <id,id.lexval>

<id,id.lexval>

< , >

< , >

+

E

T

FT

F id

id

E

T

F

id

◮ Si tenga presente che la visita di un nodo consistenel calcolo dei suoi attributi (secondo lo schema).

LFC






◮ Consideriamo ancora la generica produzione

A→ X1 . . .Xi−1Xi . . .Xk

◮ Un attributo per Xi si dice ereditato se il suo valoredipende (eventualmente) dal valore di attributiereditati di A e di attributi (ereditati o sintetizzati) diX1, . . . ,Xi−1.

◮ In termini di parse tree, un attributo a un nodo èereditato se il suo valore dipende dal valore diattributi ereditati al nodo genitore o attributi (diqualunque tipo) ai nodi che sono “fratelli maggiori”.

◮ Questa definizione non è la più generale ma, di fatto,è quella operativa.

LFC





Tipi di attributi (4)◮ Schemi di traduzione in cui vi sia (oltre ad eventuali

attributi sintetizzati) almeno un attributo ereditatosecondo questa definizione vengono dettiL-attributed.

◮ Lo schema di traduzione:

E → TE ′ {E ′.inh← T .node;E .node← E ′.node}E ′ → +TE ′

1 {E ′

1.inh← new node(′+′,E ′.inh,T .node);E ′.node← E ′

1.node}E ′ → ǫ {E ′.node← E ′.inh}T → FT ′ {T ′.inh← F .node;T .node← T ′.node}T ′ → ×FT ′

1 {T ′

1.inh← new node(′×′,T ′.inh,F .node);T ′.node← T ′

1.node}T ′ → ǫ {T ′.node← T ′.inh}F → (E) {F .node← E .node}F → id {F .node← new leaf(id, id.lexval)}

relativo alla grammatica per le espressioni adatta altop-down parsing è L-attributed.

LFC






◮ Gli attributi ereditati possono essere calcolatinell’ambito di una visita in ordine anticipato del parsetree.

◮ Infatti, nel momento in cui viene calcolato il valore diun attributo ereditato ad un nodo X :

◮ i nodi che sono “fratelli maggiori” di X sono stati giàvisitati e i loro attributi (siano essi sintetizzati oereditati) già calcolati;

◮ gli attributi sintetizzati al nodo genitore non sono staticalcolati ma (con ragionamento ricorsivo) quelliereditati sì.

◮ La slide successiva illustra graficamente la validitàdelle precedenti osservazioni.

LFC






X

◮ Ai nodi colorati di rosso tutti gli attributi sono staticalcolati.

◮ Ai nodi colorati di giallo sono stati calcolati solo gliattributi ereditati.

◮ Al nodo colorato di verde (il “nostro” nodo X ) gliattributi non sono ancora stati calcolati.

LFC






◮ In uno schema L-attributed che abbia anche attributisintetizzati, il calcolo deve essere effettuato sia infase di discesa nel parse tree, sia in fase di risalita.

◮ Più precisamente, ad ogni dato nodo X gli attributiereditati vengono calcolati prima di visitare i figli di X

mentre gli attributi sintetizzati vengono calcolatidopo.

◮ Ad esempio, se il processo è realizzato medianteuna procedura ricorsiva, il calcolo degli attributiereditati avviene prima delle chiamate ricorsive suinodi figli, mentre quello degli attributi sintetizzatiavviene al ritorno di tali chiamate.

LFC





Esempio

◮ Per illustrare il processo generale ci aiutiamo con ilsemplice esempio di parsing della frase id1 + id2:

E

E ′

E’

ǫ

T

T ′

ǫ

F

id2

+

T

T ′

ǫ

F

id1

◮ Come già per gli schemi S-attributed, le dipendenzefunzionali fra gli attributi (e dunque il flusso di datinecessario affinché il calcolo proceda in modocorretto) possono essere evidenziati utilizzando unparse tree “annotato”.

LFC





Esempio (continua)

◮ Per descrivere il flusso di informazione utilizziamo,nella figura usiamo le seguenti convenzioni:

◮ una freccia indica un arco del parse tree(queste frecce sono sempre orientate verso il basso);

◮ una freccia (orientata verso l’alto) indica chel’attributo sintetizzato al nodo di partenza è usato percalcolare l’attributo sintetizzato al nodo di arrivo;

◮ una freccia (orientata verso il basso) indicache l’attributo ereditato al nodo di partenza è usatoper calcolare l’attributo ereditato al nodo di arrivo;

◮ infine, una freccia (orientata verso destra)indica che l’attributo sintetizzato al nodo di partenzaè usato per calcolare l’attributo ereditato al nodo diarrivo.

LFC





Esempio (continua)

◮ Riportiamo nuovamente lo schema di traduzione:

E → TE ′ {E ′.inh← T .node;E .node← E ′.node}E ′ → +TE ′

1 {E ′

1.inh← new node(′+′,E ′.inh,T .node);E ′.node← E ′

1.node}E ′ → ǫ {E ′.node← E ′.inh}T → FT ′ {T ′.inh← F .node;T .node← T ′.node}T ′ → ×FT ′

1 {T ′

1.inh← new node(′×′,T ′.inh,F .node);T ′.node← T ′

1.node}T ′ → ǫ {T ′.node← T ′.inh}F → (E) {F .node← E .node}F → id {F .node← new leaf(id, id.lexval)}

e, nella slide successiva, il parse tree annotato

LFC





Esempio (continua)

◮ Il parse tree annotato:

E

T E’

F T’ +

F T’

E’

id1

id2 ε

εε

T

LFC





Schemi e tipo di parsing

◮ In un parser reale il parse tree non vieneesplicitamente generato.

◮ Il soddisfacimento delle dipendenze fra attributi (equindi la possibilità di avere un ordine di esecuzione“corretto” delle azioni previste nello schema) puòcomunque essere ottenuto almeno nei seguenti duecasi:

◮ la grammatica considerata ammette parsing di tipoLR e lo schema utilizzato è S-attributed, oppure

◮ la grammatica ammette parsing di tipo LL e loschema è L-attributed.

LFC





Parsing LR◮ La validità della prima combinazione, di grammatica

analizzabile con parser LR unitamente a schemaS-attributed, è più semplice da dimostrare.

◮ Consideriamo infatti l’esecuzione di una riduzione inun parser LR, ad esempio A→ XYZ .

◮ Dimostriamo per induzione che (le occorrenze de) gliattributi dei simboli non terminali sono calcolaticorrettamente.

◮ È evidente che se tutti i simboli nella parte destradella produzione sono terminali (base), allora ilcalcolo degli eventuali attributi di A può essereeseguito correttamente.

◮ Se invece a destra vi è un simbolo non terminale, esupponiamo che Y lo sia, allora il parser ha giàeseguito una riduzione Y → α e dunque, per ipotesiinduttiva, gli attributi di Y sono stati calcolaticorrettamente.

LFC





Esempio

◮ Riconsideriamo in dettaglio l’esempio relativo alparsing della stringa id + id× id, secondo lo schema(S-attributed) introdotto.

◮ Le seguenti trasparenze illustrano come procede lacomputazione.

◮ Nelle illustrazioni il parse tree è mostrato solo alloscopo di evidenziare quali attributi sono utilizzati neivari stadi della computazione.

◮ I nodi del parse tree, infatti, fornisce un “luogo” dovememorizzare tali attributi.

◮ In effetti, uno dei problemi che dovremo risolvere inassenza del parse tree è proprio capire “dove”memorizzare gli attributi.

LFC





Esempio (continua)

F

id

E.node

F.node

T.node

F.node


E

T

F

id

Dopo F−>id

F.node

<id,id.lexval>

F

id

F.node

T.node

<id,id.lexval>

T

F

id

E.node

F.node

T.node

<id,id.lexval>

E

T

F

idDopo la riduzione F−>id Dopo T−>F Dopo E−>T

T

F

id

E.node

T.node

F.node

T.node

F.node


E

T

F

id

Dopo T−>F

LFC





Esempio (continua)

FT

F id

id

E.node

T.node

F.node

T.node

F.node

F.node


<id,id.lexval>

E

T

F

id

Dopo F−>id

< , >T

FT

F id

id

E.node T.node

T.node

F.node

T.node

F.node

F.node


<id,id.lexval>

E

T

F

idDopo T−>T*F

< , >

< , >

+

E

T

FT

F id

id

E.node

E.node

T.node

T.node

F.node

T.node

F.node

F.node


<id,id.lexval>

E

T

F

idDopo E−>E+T

LFC





Aspetti implementativi

◮ Nel caso di parsing LR e schema S-attributed èrelativamente semplice mostrare come lacostruzione esplicita del parse tree non sia richiesta.

◮ Osserviamo infatti che, non appena un nodo N vienecollegato al padre P nel parse tree (a seguito di unariduzione), gli attributi definiti in N, e quindi anche N

stesso, non servono più.◮ È dunque sufficiente modificare lo stack utilizzato dal

parser LR, in modo che esso memorizzi non solostati ma anche gli attributi associati al simbolo checorrisponde a quello stato.

◮ A quest’ultimo riguardo, ricordiamo come ogni statos dell’automa sia associato ad un simbolo dellagrammatica (precisamente quel simbolo cheetichetta le transizioni entranti in s).

LFC





Aspetti implementativi (2)◮ Si può verificare la validità dell’ultima affermazione

nel caso dell’automa LR(0) della grammatica LR(0)per le espressioni aritmetiche:

I0

I1

I3

I2

I6

I4

I5 I8

I7

I11

I9

I10

accept

$

EF

F

(

+

F

(T

T(

id

id

(

id

+

)

×

×

F

T

id

F

LFC





Schema di traduzione modificato

◮ Presentiamo di seguito lo schema di traduzione perla grammatica delle espressioni, modificato in mododa utilizzare lo stack per memorizzare gli attributi.

◮ Lo stack memorizza ora coppie 〈s,p〉, dove s è unostato (un numero compreso fra 0 e 11), mentre p è ilvalore dell’attributo node (in pratica, un puntatore adun nodo dell’abstract syntax tree in costruzione) delsimbolo associato ad s.

◮ Poiché gli attributi non vengono più indicatiesplicitamente nelle azioni dello schema, non è piùnecessario distinguere le differenti occorrenze dellostesso simbolo.

LFC





Schema di traduzione modificato

E → E + T {p2 ← pop().p; pop(); p1 ← pop().p;s ← GOTO(top().s,E);push(〈s,new node(′+′,p1,p2)〉)}

E → T {p ← pop().p; s ← GOTO(top().s,E);push(〈s,p〉)}

T → T × F {p2 ← pop().p; pop(); p1 ← pop().p;s ← GOTO(top().s,T );push(〈s,new node(′×′,p1,p2)〉)}

T → F {p ← pop().p; s ← GOTO(top().s,T );push(〈s,p〉)}

F → (E) {pop(); p ← pop().p; pop();s ← GOTO(top().s,F ); push(〈s,p〉)}

F → id {p ← pop().p; s ← GOTO(top().s,F );push(〈s,p〉)

LFC





Parsing LL

◮ Passiamo ora ad analizzare il secondo caso dicalcolabiltà efficiente degli schemi di traduzione, eprecisamente quello relativo a schemi L-attributedunitamente a grammatiche di tipo LL.

◮ Anche in questo caso, l’esempio che ci guiderà saràquello relativo alla grammatica per le espressionimodificata con l’eliminazione della ricorsione asinistra.

◮ Abbiamo già visto come lo schema sia L-attributed.◮ Abbiamo anche visto (astrattamente) come sia

possibile eseguire correttamente lo schema nel casosi costruisca prima il parse tree, cioè eseguendo unopportuno attraversamento dell’albero stesso.

◮ Vogliamo ora in concreto vedere come modificare laprocedura generale di parsing LL vista a suo tempoallo scopo di produre in output l’abstract syntax tree.

LFC





Organizzazione concreta del calcolo◮ Nel caso di implementazione del parser LL mediante

procedure ricorsive, un’implementazione delloschema di traduzione che rispetti le dipendenzefunzionali è alquanto semplice (come in realtà giàosservato).

◮ Sia A→ X1 . . .Xi−1Xi . . .Xk una generica produzioneusata dal parser.

◮ Nel momento in cui, all’interno della procedura (per)A, viene chiamata la procedura Xi le procedureX1, . . . ,Xi−1 sono già state chiamate e dunqueeventuali valori da esse prodotti possono esserepassati in input a Xi .

◮ Ciò consente di implementare il flusso dati richiestodalla definizione di attributo ereditato, nel senso che,qualora Xi abbia attributi ereditati, questi dipendonoda valori associati a (e calcolati dalle procedure) A

e/o X1, . . . ,Xi−1.

LFC





Organizzazione concreta del calcolo (2)

◮ In realtà, è proprio la struttura delle procedurericorsive di un parser LL ad aver suggerito ladefinizione di attributo ereditato.

◮ Tornando alla nostra grammatica per le espressioni,consideriamo, ad esempio, la procedura per E (unicaproduzione E → TE ′) e le corrispondenti azioni delloschema:

E ′.inh← T .node e E .node← E ′.node.

◮ La procedura invocherà dapprima la routine T (chenon necessita di “informazione ereditata”).

◮ Il valore restituito da quest’ultima (T .node) saràpassato in input a E ′ come valore ereditato.

◮ Il valore restituito dalla chiamata ad E ′ sarà poianche il valore restituito da E .

LFC






◮ Si noti quindi che le procedure corrispondenti ai nonterminali sono più utilmente realizzate mediantefunzioni.

◮ La funzione per E può quindi essere sinteticamenteespressa nel modo seguente:

1: Tnode ← T ()2: return E ′(Tnode)

◮ Consideriamo, come altro esempio, la routine per E ′

(produzioni E ′ → +TE ′ e E ′ → ǫ).◮ Abbiamo appena visto che essa riceve in input un

argomento (attributo ereditato) che supporremovenga assegnato al parametro formale inh.

LFC






◮ Il corpo della funzione può essere espresso nelmodo seguente:

1: if t ← get_next_token() =′ +′ then

2: Tnode ← T ()3: inh1 ← new node(′+′, inh,Tnode)4: return E ′(inh1)5: else if t =′ )′ or t =′ $′ then

6: return inh

7: else

8: error()◮ Nel caso di implementazione ricorsiva del parser,

non è dunque necessario che vengapreliminarmente costruito il parse tree.

Linguaggi formali e compilazione -...

Documents

Transcript of Linguaggi formali e compilazione -...