11

Implementazione di Linguaggi 2Implementazione di Linguaggi 2PARTE 5PARTE 5

Massimo AnconaMassimo AnconaDISI Università di GenovaDISI Università di Genova

Testo: A.V. Aho, R. Sethi, J.D.Ullman Compilers Testo: A.V. Aho, R. Sethi, J.D.Ullman Compilers Principles,Techniques and Tools, Addison WesleyPrinciples,Techniques and Tools, Addison Wesley

22

TRADUZIONE GUIDATA TRADUZIONE GUIDATA (DIRETTA) DALLA SINTASSI(DIRETTA) DALLA SINTASSI

Definizioni guidate dalla sintassi (DGS)Una definizione guidata dalla sintassi è una generalizzazione di una CFG in cui ogni simbolo grammaticale è associato un insieme di attributi, suddiviso in due sottoinsiemi chiamati rispettivamente insieme degli attributi ereditati e insieme degli attributi sintetizzati.

33

Attributi e loro gestioneAttributi e loro gestione

Se si pensa un nodo del parse tree associato ad un Se si pensa un nodo del parse tree associato ad un simbolo grammaticale come una struttura di simbolo grammaticale come una struttura di recordrecord con campi destinati a mantenere informazioni allora con campi destinati a mantenere informazioni allora un attributo corrisponde al nome di un campo.un attributo corrisponde al nome di un campo.

ll valore di un attributo in un nodo del parse tree è ll valore di un attributo in un nodo del parse tree è definito da una definito da una regola semanticaregola semantica associata alla associata alla produzione applicata in quel nodo. Il valore di un produzione applicata in quel nodo. Il valore di un attributo sintetizzato in un nodo è calcolato in attributo sintetizzato in un nodo è calcolato in funzione del valore degli attributi dei figli del nodo.funzione del valore degli attributi dei figli del nodo.

Il valore di un attributo ereditato in un nodo è calcolato in Il valore di un attributo ereditato in un nodo è calcolato in funzione del valore degli attributi dei fratelli e del funzione del valore degli attributi dei fratelli e del genitore del nodo.genitore del nodo.

Le regole semantiche introducono dipendenze tra gli Le regole semantiche introducono dipendenze tra gli attributi nei nodi. Queste vengono rappresentate da attributi nei nodi. Queste vengono rappresentate da un grafo orientato detto un grafo orientato detto grafo delle dpendenzegrafo delle dpendenze..

44

Parsing Tree Decorato e Attribute Parsing Tree Decorato e Attribute GrammarGrammar

Un parsing tree Un parsing tree decoratodecorato è un parsing tree che riportii valori degli è un parsing tree che riportii valori degli attributi di ogni nodo.attributi di ogni nodo.

Nelle DDS si associa ad ogni produzione Nelle DDS si associa ad ogni produzione AA un insieme di regole un insieme di regole semantiche della forma:semantiche della forma:

b:=f(cb:=f(c11,c,c22,...,c,...,ckk))In cui In cui ff è una e è una e bb verifica una dei due casi seguenti: verifica una dei due casi seguenti:1.1. bb è un attributo sintetizzato di è un attributo sintetizzato di A A e e cc11,c,c22,...,c,...,ckk sono attributi dei sono attributi dei

simboli nella parte destra della produzionesimboli nella parte destra della produzione2.2. bb è un attributo ereditato di uno dei simboli della parte destra è un attributo ereditato di uno dei simboli della parte destra

della produzione e della produzione e cc11,c,c22,...,c,...,ckk attributi di attributi di AA e di alcuni simboli e di alcuni simboli della parte destra di della parte destra di AA..

Una Una attribute grammar attribute grammar è una definizione guidata dalla sintassi in cui è una definizione guidata dalla sintassi in cui le funzioni le funzioni f f non generano side-effect. Quando si vogliono non generano side-effect. Quando si vogliono generare side-effect si usano procedure in luogo di funzioni. Le generare side-effect si usano procedure in luogo di funzioni. Le funzioni sono spesso espresse in forma da espressionifunzioni sono spesso espresse in forma da espressioni

55

Attributi SintrtizzatiAttributi Sintrtizzati

Esempio di un semplice calcolatore:Esempio di un semplice calcolatore:

LLEnEn print(E.val)print(E.val)

EEEE11+T+T E.val:=EE.val:=E11.val+T.val.val+T.val

EETT E.val:=T.valE.val:=T.val

TTTT11*F*F T.val:=TT.val:=T11.val.valF.valF.val

TTFF T.val:=F.valT.val:=F.val

FF(E)(E) F.val:=E.valF.val:=E.val

FFdigitdigit F.val:=digit.lexvalF.val:=digit.lexval

66

Attributi sintetizzati: Attributi sintetizzati: esempioesempio

77

Attributi EreditatiAttributi Ereditati

Dipendono dagli attributi di genitore e fratelli Dipendono dagli attributi di genitore e fratelli e sono utili per esprimere dipendenze dal e sono utili per esprimere dipendenze dal contesto del linguaggio. Esempio:contesto del linguaggio. Esempio:

DDTLTL L.in:=T.typeL.in:=T.type

TTintint T.type:=integerT.type:=integer

TTfloatfloat T.type:=realT.type:=real

LLLL11,id,id LL11.in:=L.in addtype(id.entry,L.in).in:=L.in addtype(id.entry,L.in)

LLLL11,id,id addtype(id.entry,L.in)addtype(id.entry,L.in)

88

Attributi ereditati: Attributi ereditati: esempioesempio

99

Ordine di valutazione degli Ordine di valutazione degli Attributi Attributi

1010

Ordine di valutazione-grafo di Ordine di valutazione-grafo di dipendenzadipendenza

Se l’attributo Se l’attributo bb nel nodo nel nodo nn dipende da dipende da cc nel nodo nel nodo mm allora la regola che valuta allora la regola che valuta bb in in nn deve essere deve essere valutata dopo quella che valuta valutata dopo quella che valuta cc in in mm. Le . Le interdipendenze di valutazione degli attributi in interdipendenze di valutazione degli attributi in un parse tree vengono descritte da un grafo un parse tree vengono descritte da un grafo diretto etichettato detto diretto etichettato detto grafo di dipendenza (o grafo di dipendenza (o delle dipendenze)delle dipendenze). Il grafo ha un nodo per ogni . Il grafo ha un nodo per ogni attributo e un arco dal nodo attributo e un arco dal nodo mm al nodo al nodo nn se se bb dipende da dipende da cc..

Ogni ordinamento topologico del grafo rappresenta Ogni ordinamento topologico del grafo rappresenta un ordine di valutazione possibile. un ordine di valutazione possibile.

1111

Ordine di valutazioneOrdine di valutazione

Qui consideriamo solo metodi che non Qui consideriamo solo metodi che non richiedono la costruzione del grafo di richiedono la costruzione del grafo di dipendenza (oblivious methods) ma dipendenza (oblivious methods) ma metodi che definiscono l’ordine in base metodi che definiscono l’ordine in base alla tecnica di parsing adottata. Questo alla tecnica di parsing adottata. Questo restringe la classe degli attributi restringe la classe degli attributi definibili ma è semplice da definibili ma è semplice da implementare ed estrememente implementare ed estrememente efficiente.efficiente.

1212

Attributi semantici: applicazioniAttributi semantici: applicazioni

Costruzione di syntax treeCostruzione di syntax tree. L’uso di alberi . L’uso di alberi sintattici come rappresentazione sintattici come rappresentazione intermedia consente di disaccoppiare il intermedia consente di disaccoppiare il processo di traduzione da quello di processo di traduzione da quello di analisi.analisi.

Un albero sintattico è una forma astratta e Un albero sintattico è una forma astratta e compatta di parsing tree dipendente compatta di parsing tree dipendente solo dal linguaggio e non dalla solo dal linguaggio e non dalla grammatica adottata per descriverlo.grammatica adottata per descriverlo.

1313

Esempi di Syntax TreeEsempi di Syntax Tree

1414

Costruzione del Syntax Tree di Costruzione del Syntax Tree di espressioniespressioni

Ogni nodo è rappresentato da un Ogni nodo è rappresentato da un record contrnrntr vari campi. Un record contrnrntr vari campi. Un nodo può rappresentare un operatore nodo può rappresentare un operatore o un operando. Nel primo caso deve o un operando. Nel primo caso deve anche contenere puntatori agli anche contenere puntatori agli operandi. Si usano tre funzioni. operandi. Si usano tre funzioni. Ciascuna restituisce un puntatore al Ciascuna restituisce un puntatore al nodo creato.nodo creato.

1515

Costruzione del Syntax Tree Costruzione del Syntax Tree funzioni primitivefunzioni primitive

1.1. mknode(op,left,right)mknode(op,left,right), crea nodo op , crea nodo op (operatore) op e operandi left right.(operatore) op e operandi left right.

2.2. mkleaf(id,entry)mkleaf(id,entry) crea nodo id crea nodo id (operando). entry è uno spix a (operando). entry è uno spix a symbol table.symbol table.

3.3. mkleaf(num,val)mkleaf(num,val) , crea un nodo di , crea un nodo di tipo valore: il campo val contiene il tipo valore: il campo val contiene il valore valore

1616

Costruzione del Syntax Tree Costruzione del Syntax Tree funzioni primitivefunzioni primitive

EEEE11+T +T E.np:=mknode(‘+’,EE.np:=mknode(‘+’,E11.np,T.np) .np,T.np)

EEEE11-T -T E.np:=mknode(‘-’,EE.np:=mknode(‘-’,E11.np,T.np).np,T.np)

EET T E.np:=T.npE.np:=T.np

TT(E) (E) T.np:=E.npT.np:=E.np

TTid id T.np:=mkleaf(id,id.entry)T.np:=mkleaf(id,id.entry)

TTnumnumT.np:=mkleaf(num,num.val)T.np:=mkleaf(num,num.val)

1717

Costruzione del Syntax Tree Costruzione del Syntax Tree esempioesempio

1818

Costruzione del Syntax Tree a Costruzione del Syntax Tree a DAG DAG

Si usa un grafo orientato aciclico per Si usa un grafo orientato aciclico per rappresentare sotto-espressioni comuni.rappresentare sotto-espressioni comuni.

Esempio: a+a*(b-c)+(b-c)*dEsempio: a+a*(b-c)+(b-c)*d

1.1. p1=mkleaf(id,a)p1=mkleaf(id,a)

2.2. p2:=mkleaf(id,a)p2:=mkleaf(id,a)

3.3. p3:=mkleaf(id,b)p3:=mkleaf(id,b)

4.4. p4:=mkleaf(id,c)p4:=mkleaf(id,c)

5.5. p5:=mknode(‘-’,p3,p4)p5:=mknode(‘-’,p3,p4)

1919

Costruzione del Syntax Tree a Costruzione del Syntax Tree a DAGDAG

Esempio: a+a*(b-c)+(b-c)*dEsempio: a+a*(b-c)+(b-c)*d

6.6. p6:=mknode(‘*’,p2,p5)p6:=mknode(‘*’,p2,p5)

7.7. p7:=mknode(‘+’,p1,p6)p7:=mknode(‘+’,p1,p6)

8.8. p8:=mkleaf(id,b)p8:=mkleaf(id,b)

9.9. p9:=mkleaf(id,c)p9:=mkleaf(id,c)

2020

Costruzione di un Syntax Tree Costruzione di un Syntax Tree a DAGa DAG

2121

Costruzione di un Syntax Tree Costruzione di un Syntax Tree a DAGa DAG

Algoritmo Algoritmo

I nodi del grafo sono memorizzati in un array I nodi del grafo sono memorizzati in un array ciascuno puntato da un cursore (indice). La ciascuno puntato da un cursore (indice). La segnatura di un nodo è formata da una segnatura di un nodo è formata da una tripla tripla <op,l,r><op,l,r>

Input: Input: op lop l ed ed rr

Output: nodo con segnatura Output: nodo con segnatura <op,l,r><op,l,r>

Metodo: scandire l’array fino a trovare nodo Metodo: scandire l’array fino a trovare nodo con etichetta con etichetta opop

2222

Costruzione di un Syntax Tree Costruzione di un Syntax Tree a DAGa DAG

Algoritmo Algoritmo

Metodo: scandire l’array fino a trovare Metodo: scandire l’array fino a trovare un nodo un nodo mm con etichetta con etichetta opop figlio figlio sinistro sinistro l l e destroe destro r r. Se esiste . Se esiste restituire restituire mm altrimenti creare un altrimenti creare un nuovo nodo nuovo nodo <op,l,r><op,l,r> alla posizione alla posizione lstlst e restituire e restituire lstlst. La ricerca può essere . La ricerca può essere ottimizzato con una tavola hash.ottimizzato con una tavola hash.

2323

Calcolo bottom-up di definizioni s-Calcolo bottom-up di definizioni s-attributedattributed

In questo caso gli attributi possono essere In questo caso gli attributi possono essere valutati bottom-up da un parser shift-valutati bottom-up da un parser shift-reduce o di altro tipo bottom-up che reduce o di altro tipo bottom-up che conservi i valori associati ai simboli conservi i valori associati ai simboli grammaticali sullo stack.grammaticali sullo stack.

Ad ogni azione reduce il parser valuta gli Ad ogni azione reduce il parser valuta gli attributi sintetizzati a partire dai valori attributi sintetizzati a partire dai valori sullo stack. Il metodo è applicabile anche sullo stack. Il metodo è applicabile anche a certi tipi di attributi ereditati (parser LR)a certi tipi di attributi ereditati (parser LR)

2424

Calcolo bottom-up di definizioni s-Calcolo bottom-up di definizioni s-attributedattributed

Ipotesi: stack composto da due array Ipotesi: stack composto da due array paralleli stato-valore. “stato” è uno paralleli stato-valore. “stato” è uno spix a parsing table (memorizzare spix a parsing table (memorizzare sullo stack anche il simbolo sullo stack anche il simbolo grammaticale non serve, ma per grammaticale non serve, ma per leggibilità identifichiamo lo stato con leggibilità identifichiamo lo stato con il simbolo grammaticale). il simbolo grammaticale).

2525

Calcolo bottom-up di definizioni s-Calcolo bottom-up di definizioni s-attributedattributed

2626

Calcolo bottom-up di definizioni s-Calcolo bottom-up di definizioni s-attributedattributed

Supponendo di valutare gli attributi prima della Supponendo di valutare gli attributi prima della riduzione e che riduzione e che A.a:=f(X.x,Y.y,Z.z)A.a:=f(X.x,Y.y,Z.z) sia sia associata a associata a AAXYZXYZ. Prima di ridurre . Prima di ridurre XYZXYZ ad ad AA i valori di i valori di Z.zZ.z, , Y.yY.y e e X.xX.x si trovano in si trovano in val[top]val[top], , val[top-1]val[top-1] e e val[top-2]val[top-2] rispettivamente. Dopo rispettivamente. Dopo la riduzione la riduzione top top viene decrementato di viene decrementato di 22 e lo e lo stato corrispondente ad stato corrispondente ad AA viene impilato in viene impilato in state[top]state[top] mentre il valore di mentre il valore di A.aA.a in in val[top]val[top] . .

2727

Definizioni L-attributed Definizioni L-attributed

Quando il processo di traduzione avviene Quando il processo di traduzione avviene durante il parsing un ordine di valutazione durante il parsing un ordine di valutazione ottimale dipende dall’ ordine di creazione dei ottimale dipende dall’ ordine di creazione dei nodi del parsing tree da parte del parser.nodi del parsing tree da parte del parser.

Un metodo compatibile con molti parser top-Un metodo compatibile con molti parser top-down e bottom-up si basa su una visita depth down e bottom-up si basa su una visita depth first dell’albero.first dell’albero.

2828

Visita depth-first e def. L-Visita depth-first e def. L-attributed attributed

PROC dfv(n: node);PROC dfv(n: node);

BEGINBEGIN

FOR EACH child m OF n FROM left TO rightFOR EACH child m OF n FROM left TO right

DODO

eval inherited attributes of m;eval inherited attributes of m;

dfv(m);dfv(m);

OD;OD;

eval syntetized attributes of neval syntetized attributes of n

END;END;

2929

Definizioni L-attributed Definizioni L-attributed

Una definizione è Una definizione è L-attributed L-attributed se ciascun se ciascun attributo di ogni regola semantica di attributo di ogni regola semantica di ogni produzione ogni produzione AAXX11XX22…X…Xnn è è

un attributo sintetizzatoun attributo sintetizzato un attributo ereditato di un attributo ereditato di Xj 1 Xj 1jn che

dipende solo da:1.1. Gli attributi di Gli attributi di XX11XX22…X…Xj-1j-1 a sinistra di a sinistra di X Xjj

2.2. Dagli attributi ereditati di Dagli attributi ereditati di AA;;

Ogni definizione Ogni definizione S-attributedS-attributed è è L-attributedL-attributed..

3030

Definizioni L-attributed Definizioni L-attributed esempioesempio

AALMLM L.in:=l(A.i)L.in:=l(A.i)

M.i:=m(L.s)M.i:=m(L.s)

A.s:=f(M.s)A.s:=f(M.s)

AAQR QR R.i:=r(A.i)R.i:=r(A.i)

Q.i:=q(R.s)Q.i:=q(R.s)

A.s:=f(Q.s)A.s:=f(Q.s)

3131

Schemi di traduzioneSchemi di traduzione

Uno schema di traduzione è una DGS in cui Uno schema di traduzione è una DGS in cui gli attributi sono associati ai simboli gli attributi sono associati ai simboli grammaticali e le azioni semantiche sono grammaticali e le azioni semantiche sono inserite tra graffe nella parte destra delle inserite tra graffe nella parte destra delle produzioni ad indicare l’ordine di produzioni ad indicare l’ordine di valutazione.valutazione.

Esempio:Esempio:

AATRTR

RRadop Tadop Tprint(adop.lexeme)print(adop.lexeme)RR11||

TTnum num print(num.val)print(num.val)

3232

Schemi di traduzioneSchemi di traduzione

3333

Schemi di traduzioneSchemi di traduzioneNel progetto di schemi di traduzione Nel progetto di schemi di traduzione

occorre rispettare vincoli per garantire la occorre rispettare vincoli per garantire la disponibilità del valore di un attributo al disponibilità del valore di un attributo al momento dell’ uso. Per questo si usano momento dell’ uso. Per questo si usano definizioni L-attributed o meglio s-definizioni L-attributed o meglio s-attributed. In questo caso le azioni attributed. In questo caso le azioni vengono inserite in coda alla vengono inserite in coda alla produzione, esempio:produzione, esempio:

TTTT11*F T.val:=T*F T.val:=T11.val.valF.valF.val

TTTT11*F *F T.val:=T1.valT.val:=T1.valF.val)F.val)

3434

Schemi di traduzione: regoleSchemi di traduzione: regole1.1. Un attributo ereditato di un simbolo nella Un attributo ereditato di un simbolo nella

parte destra di una produzione deve essere parte destra di una produzione deve essere calcolato un una azione che precede il calcolato un una azione che precede il simbolo,simbolo,

2.2. Un’azione non deve usare un attributo Un’azione non deve usare un attributo sintetizzati di un token a destra dell’azione sintetizzati di un token a destra dell’azione stessa,stessa,

3.3. Un attributo sintetizzato della parte sinistra Un attributo sintetizzato della parte sinistra di una prod. va calcolato solo dopo quelli a di una prod. va calcolato solo dopo quelli a cui fa riferimento (OK in coda alla cui fa riferimento (OK in coda alla produzione) produzione)

3535

Schemi di traduzione L-Schemi di traduzione L-attributedattributed

Una TGDS L-attributed è trasformabile in uno Una TGDS L-attributed è trasformabile in uno schema conforme alle tre regole schema conforme alle tre regole precedenti. Esempio (formattazione testo):precedenti. Esempio (formattazione testo):

SSB B B.ps:=10; S.ht:=B.htB.ps:=10; S.ht:=B.htBBBB11BB22 BB11.ps:=B.ps; B.ps:=B.ps; B22.ps:=B.ps.ps:=B.ps

B.ht:=max(BB.ht:=max(B11.ht,B.ht,B22.ht).ht)

BBBB1 1 subsub BB22 BB11.ps:=B.ps; B.ps:=B.ps; B22.ps:=shrink(B.ps).ps:=shrink(B.ps)

B.ht:=disp(BB.ht:=disp(B11.ht,B.ht,B22.ht).ht)

BBtext text B.ht:=text.hB.ht:=text.hB.ps;B.ps;

3636

Schemi di traduzione L-Schemi di traduzione L-attributedattributed

B sta per box, B sta per box, BBBB11BB22 indica giustap-indica giustap-posizione di testo, posizione di testo, BBBB1 1 subsub BB22 denota denota l’operazione pedice: B2 viene posto a l’operazione pedice: B2 viene posto a destra in basso di B1 ma in dimensione destra in basso di B1 ma in dimensione ridotta. ps è ereditato e indica l’altezza di ridotta. ps è ereditato e indica l’altezza di una formulauna formula

3737

Schemi di traduzione L-Schemi di traduzione L-attributedattributed

SSB.ps:=10B.ps:=10BBS.ht:=B.htS.ht:=B.htBBBB11.ps:=B.ps.ps:=B.psBB11BB22.ps:=B.ps.ps:=B.psBB2 2

B.ht:=max(BB.ht:=max(B11.ht,B.ht,B22.ht).ht)

BBBB11.ps:=B.ps.ps:=B.psBB1 1

subsubBB22.ps:=shrink(B.ps).ps:=shrink(B.ps)BB22

B.ht:=disp(BB.ht:=disp(B11.ht,B.ht,B22.ht).ht)

BBtext text B.ht:=text.hB.ht:=text.hB.ps;B.ps;

3838

Traduzioni topdown Traduzioni topdown

Implementazione di DGS L-attributed con Implementazione di DGS L-attributed con parser topdown:parser topdown:

EEEE11+T+TE.val:=EE.val:=E11.val+T.val.val+T.val

EEEE11-T-TE.val:=EE.val:=E11.val+T.val.val+T.val

EET T E.val:=T.valE.val:=T.valTT(E) (E) T.val:=E.valT.val:=E.valTTnumnumT.val:=num.valT.val:=num.val

3939

Traduzioni topdown Traduzioni topdown

Implementazione di DGS L-attributed con Implementazione di DGS L-attributed con parser topdown:parser topdown:

EETTR.i:=T.valR.i:=T.valR R E.val:=R.sE.val:=R.s RR+T +T RR11.i:=R.i+T.val.i:=R.i+T.val RR1 1 R.s:=RR.s:=R11.s.s

RR-T -T RR11.i:=R.i-T.val.i:=R.i-T.val RR1 1 R.s:=RR.s:=R11.s.s

RR R.s:=R.iR.s:=R.iTT(E) (E) T.val:=E.valT.val:=E.valTTnumnumT.val:=num.valT.val:=num.val

4040

Traduzioni topdown Traduzioni topdown

Si ricordi che un attributo ereditato di un token deve essere valutato in una azione che compare prima del token mentre un attributo sintetizzato della parte sinistra deve essere valutato dopo gli attributiDa cui ssso dipende.

4141

Traduzioni topdown Traduzioni topdown

AAAA11YYA.a:=g(AA.a:=g(A11.a,Y.y).a,Y.y)

AAX X A.a:=f(X.x)A.a:=f(X.x)AAXRXR

RRYR|YR|Con le azioni sementiche diviene:Con le azioni sementiche diviene:

AAXXR.i:=f(X.x)R.i:=f(X.x)R R A.a:=R.sA.a:=R.sRRY Y R.i:=g(R.i,Y.y)R.i:=g(R.i,Y.y) R R1 1 R.s:=RR.s:=R11.s.s

R R R.s:=R.iR.s:=R.i