Implementazione di Linguaggi 2 PARTE 4

11

Implementazione di Linguaggi 2Implementazione di Linguaggi 2PARTE 4PARTE 4

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

PARSER LRPARSER LR

33

Algoritmo di Algoritmo di Parsing LRParsing LR

Il parser usa uno stack su cui impila stringhe della Il parser usa uno stack su cui impila stringhe della forma:forma:

ss00XX11ss11XX22ss22…X…Xmmssm m con ssm m sul top sul topdove dove XXiiNN mentre mentre ssii rappresenta uno stato del parser. Il rappresenta uno stato del parser. Il

parser e’ di tipo parser e’ di tipo shift-reduceshift-reduce e il suo comportamento e il suo comportamento e’ deciso dall’input corrente e’ deciso dall’input corrente aai i e dall top dello stack e dall top dello stack ssmm. Le tavole del parser sono formate da due . Le tavole del parser sono formate da due funzioni dette action function funzioni dette action function ff e goto function e goto function gg. Il . Il parser consulta parser consulta [s[smm,a,aii]] che puo’ valere: che puo’ valere:

• shift shift • reduce by Areduce by A• acceptaccept• error error

44

Algoritmo di Algoritmo di Parsing LRParsing LR

La funzione goto La funzione goto gg mappa stati e simboli grammaticali in mappa stati e simboli grammaticali in stati stati g: Sg: SVVSS ed e’ la funzione di transizione di un ed e’ la funzione di transizione di un DFA che accetta DFA che accetta prefissi accessibiliprefissi accessibili (PrAc) della (PrAc) della grammatica G.grammatica G.

Un PrAc di una grammatica G e’ un prefisso di una Un PrAc di una grammatica G e’ un prefisso di una forma forma sentenziale canonica destrasentenziale canonica destra (FSCD) che puo’ (FSCD) che puo’ comparire sul top dello stack. Piu’ formalmente un comparire sul top dello stack. Piu’ formalmente un PrAc di G e’ una stringa PrAc di G e’ una stringa tale che:tale che:

SS**rmrmAwAwrmrmw w ee PREF(PREF() ) (*)(*)Una maniglia/chiave Una maniglia/chiave ((handlehandle) di una FSCD di) di una FSCD di G G e’ una e’ una

coppia formata da una produzione e una posizione coppia formata da una produzione e una posizione nella FSCD. Nell’ esempio (*) nella FSCD. Nell’ esempio (*) (A(A,,)) o o (A(A,n),n) dove dove n=|n=|+1|+1|. Lo handle esprime che la stringa. Lo handle esprime che la stringa

55

Algoritmo di Algoritmo di Parsing LR CanonicoParsing LR Canonico

alla posizione specificata dallo handle puo’ alla posizione specificata dallo handle puo’ essere sostituita da essere sostituita da AA per ottenere la FSCD per ottenere la FSCD precedente in una derivazione canonica destra.precedente in una derivazione canonica destra.

Il DFA ha come stato iniziale quello impilato dal Il DFA ha come stato iniziale quello impilato dal parser all’inizio.parser all’inizio.

Una configurazione del parser e’ una coppia formata Una configurazione del parser e’ una coppia formata da: da:

• il contenuto dello stackil contenuto dello stack• l’input non ancora lettol’input non ancora letto

(s(s00XX11ss11XX22ss33…X…Xmmssmm,a,ajjaaj+1j+1…a…ann))La mossa corrente del parser e’ determinata da La mossa corrente del parser e’ determinata da aajj, da , da

ssmm e dal valore di e dal valore di f[sf[smm,a,ajj] ] ((action[saction[smm,a,ajj]]) come ) come segue:segue:

66

Algoritmo di Algoritmo di Parsing LR CanonicoParsing LR Canonico

• Se Se f[sf[smm,a,ajj]=shift]=shift allora il parser esegue uno shift e allora il parser esegue uno shift e passa alla configurazionepassa alla configurazione

(s(s00XX11ss11XX22ss33…X…Xmmssmmaajjs,as,aj+1j+1…a…ann)) dove dove s=g[ss=g[smm,a,ajj]]..• se se f[sf[smm,a,ajj]=reduce A]=reduce A allora il parser esegue una allora il parser esegue una

azione reduce passando alla configurazione azione reduce passando alla configurazione (s(s00XX11ss11XX22ss33…X…Xm-rm-rssm-rm-rAs,aAs,ajjaaj+1j+1…a…ann)) dove dove s=g[ss=g[sm-rm-r,A],A] ed ed r=|r=|||. Cioe’ il parser spila . Cioe’ il parser spila 2r2r simboli dallo stack fino simboli dallo stack fino ad esporre sul top ad esporre sul top ssm-rm-r; quindi impila ; quindi impila AA seguito da seguito da s=g[ss=g[sm-rm-r,A],A]..

• Se Se f[sf[smm,a,ajj]=accept]=accept allora il parser termina l’analisi allora il parser termina l’analisi con successo.con successo.

• Se Se f[sf[smm,a,ajj]=error]=error allora attiva una routine di errore. allora attiva una routine di errore.

77

Struttura delle tavole di Struttura delle tavole di Parsing Parsing LRLR

Si consideri l’esempio Si consideri l’esempio (1) E(1) EE+T, (2) EE+T, (2) ET,(3) T,(3) TTT*F (4) TT*F (4) TF, (5) FF, (5) F(E), (6) F(E), (6) Fidid. La prima . La prima slide mostra le tavole canoniche. Il loro difetto slide mostra le tavole canoniche. Il loro difetto e’ di avere la tavola e’ di avere la tavola ff sparsa e sparsa e sspreca-spaziopreca-spazio. . Per questo la slide successiva sposta la parte Per questo la slide successiva sposta la parte delle azioni goto sui terminali nella tavola delle azioni goto sui terminali nella tavola ff. . Ad esempio se Ad esempio se f[s,a]=shiftf[s,a]=shift e e g[s,a]=ng[s,a]=n allora allora f[s,a]f[s,a] diviene diviene action[s,a]=shift naction[s,a]=shift n, mentre la , mentre la funzione funzione g(a)g(a) scompare restando solo scompare restando solo g(A)g(A)..

Di conseguenza il parser va ridescritto come Di conseguenza il parser va ridescritto come segue (le nuove funzioni segue (le nuove funzioni ff e e gg vengono vengono chiamate chiamate actionaction e e gotogoto): ):

88

Algoritmo di Algoritmo di Parsing LR libroParsing LR libro

• Se Se action[saction[smm,a,ajj]=shift s]=shift s allora il parser esegue uno allora il parser esegue uno shift e passa alla configurazioneshift e passa alla configurazione

(s(s00XX11ss11XX22ss33…X…Xmmssmmaajjs,as,aj+1j+1…a…ann))• se se action[saction[smm,a,ajj]=reduce A]=reduce A allora il parser allora il parser

esegue una azione reduce passando alla esegue una azione reduce passando alla configurazione configurazione (s(s00XX11ss11XX22ss33…X…Xm-rm-rssm-rm-rAs,aAs,ajjaaj+1j+1…a…ann)), , s=goto[ss=goto[sm-rm-r,A],A] e e r=|r=|||. Cioe’ il parser spila . Cioe’ il parser spila 2r2r simboli dallo stack fino ad esporre sul top simboli dallo stack fino ad esporre sul top ssm-rm-r; ; quindi impila quindi impila AA seguito da seguito da s=goto[ss=goto[sm-rm-r,A],A]..

• Se Se action[saction[smm,a,ajj]=accept]=accept allora il parser termina allora il parser termina l’analisi con successo.l’analisi con successo.

• Se Se action[saction[smm,a,ajj]=error]=error allora attiva una routine di allora attiva una routine di errore.errore.

99

Algoritmo di Algoritmo di Parsing LR Driver Parsing LR Driver RoutineRoutine

PROC ParserLR; PROC ParserLR; DODO /* s TOS state, a next input and ip pointer to it *//* s TOS state, a next input and ip pointer to it */

IF action[s,a]=shift s’ THENIF action[s,a]=shift s’ THENpush a; push s’; ip++push a; push s’; ip++

ELSIF action[s,a]=reduce AELSIF action[s,a]=reduce A THEN THENpop 2|pop 2|| symbols; /* s’ becomes TOS */| symbols; /* s’ becomes TOS */push A; push goto[s’,A]; out “Apush A; push goto[s’,A]; out “A””

ELSIF action[s,a]=accept THEN RETURNELSIF action[s,a]=accept THEN RETURNELSE Error()ELSE Error()FIFI

ODODEND.END.

1010

Esempio di Esempio di Parsing LRParsing LRStepStep stack stack input input action action outputoutput 11 0 0 id*id+id$ id*id+id$ shiftshift 22 0id5 0id5 *id+id$ *id+id$ reduce Freduce Fidid F Fidid 33 0F3 0F3 *id+id$ *id+id$ reduce Treduce TF F TTFF 44 0T2 0T2 *id+id$ *id+id$ shiftshift 55 0T2*7 0T2*7 id+id$ id+id$ shiftshift 66 0T2*7id5 0T2*7id5 +id$ +id$ reduce Freduce Fidid F Fidid 77 0T2*7F10 +id$ 0T2*7F10 +id$ reduce Treduce TT*FT*F T TT*FT*F 88 0T2 0T2 +id$ +id$ reduce Ereduce ETT E ETT 99 0E1 0E1 +id$ +id$ shiftshift1010 0E1+6 0E1+6 id$ id$ shiftshift1111 0E1+6id5 0E1+6id5 $ $ reduce Freduce Fid Fid Fid id

1111

Esempio di Esempio di Parsing LR cont.Parsing LR cont.

StepStep stack stack input input action action outputoutput

1212 0E1+6F3 $ 0E1+6F3 $ reduce Treduce TFF TTFF

13 0E1 +6E9 $ reduce E13 0E1 +6E9 $ reduce EE+T EE+T EE+TE+T14 0E1 $ accept14 0E1 $ accept

Da un punto di vista pratico sono state usate le Da un punto di vista pratico sono state usate le grammatiche LR(0) ed LR(1) ed alcune grammatiche LR(0) ed LR(1) ed alcune sottoclassi di queste uktime: SLR(1) e LALR(1) sottoclassi di queste uktime: SLR(1) e LALR(1) benche’ le potenzialita’ dei processori di oggi benche’ le potenzialita’ dei processori di oggi permetta di prendere in considerazione le LR(1) permetta di prendere in considerazione le LR(1) ed anche le LR(k) con k>1 senza grossi problemi.ed anche le LR(k) con k>1 senza grossi problemi.

1212

Tavole di Parsing CanonicheTavole di Parsing Canoniche

0

1

2

3

4

5

6

7

8

9

1011

Stato id + * ( ) $ E T F id + * ( ) $ s s

s

s

s s

s s

s s

s s

s

A

2 2 2

4 4 4 4

1 1 1

3 3 3 3

5 5 5 5

66 6 6

1 2 3

8 2 3

39

10

5 4

6

7

5

5 4

4

4

6 11

7

5

1313

Tavole di Parsing del LibroTavole di Parsing del Libro

0

1

2

3

4

5

6

7

8

9

1011

Stato id + * ( ) $ E T F s5 s4

s6

s7

s5 s4

s5 s4

s5 s4

s6 s11

s7

A

2 2 2

4 4 4 4

1 1 1

3 3 3 3

5 5 5 5

66 6 6

1 2 3

8 2 3

39

10

1414

Costruzione dell Tavole di Costruzione dell Tavole di Parsing LRParsing LR

Per questo vedremo in dettaglio le tavole LR(0), Per questo vedremo in dettaglio le tavole LR(0), SLR(1) ed LR(1) trattando le LALR(1) SLR(1) ed LR(1) trattando le LALR(1) marginalmente solo come meccanismo di marginalmente solo come meccanismo di semplificazione delle tavole LR.semplificazione delle tavole LR.

Item LR(0). Item LR(0). Un item LR(0) e’ una produzione con un Un item LR(0) e’ una produzione con un dotdot che ne marca una posizione nella parte che ne marca una posizione nella parte destra. La produzione destra. La produzione AAXYZ XYZ origina quattro origina quattro item:item:

AA.XYZ A.XYZ AX.YZ AX.YZ AXY.Z AXY.Z AXYZ.XYZ.;;Mentre Mentre AA genera il solo item genera il solo item AA. . ..L’idea centrale alla base del metodo consiste nel L’idea centrale alla base del metodo consiste nel

costruire dalla grammatica un automa finito che costruire dalla grammatica un automa finito che riconosca i PrAc della grammatica riconosca i PrAc della grammatica GG. Alla base . Alla base dei metodi piu’ semplici (SLR LALR) vi e’ la dei metodi piu’ semplici (SLR LALR) vi e’ la Collezione Canonica di Stati LR(0) (CCS0). Collezione Canonica di Stati LR(0) (CCS0).

1515

Tavole Tavole LR(0): funzione closureLR(0): funzione closure

Definizione.Definizione. Data Data G=(N,T,P,S)G=(N,T,P,S) definiamo grammatica definiamo grammatica estesa estesa G’=(NG’=(NS’S’,T,P,T,PS’S’SS,S’),S’) dove dove S’S’NN e’ e’ un nuovo simbolo iniziale. Scopo: determinare un nuovo simbolo iniziale. Scopo: determinare esattamente la terminazione del parser. esattamente la terminazione del parser.

Definizione.Definizione. Chiusura di un insieme di item Chiusura di un insieme di item II..• Inizialmente Inizialmente Closure(I)=IClosure(I)=I..• Se Se AA.B.BClosure(I) Closure(I) ee B B alllora aggiungere alllora aggiungere

BB.. a a closure(I)closure(I)..Il significato intuitivo di Closure e’ il seguente: se Il significato intuitivo di Closure e’ il seguente: se

AA.B.BClosure(I) Closure(I) allora durante il parsing e’ allora durante il parsing e’ possibile che si analizzi una sottostringa derivata possibile che si analizzi una sottostringa derivata da da BB. Se inoltre . Se inoltre BB allora e’ anche possibile allora e’ anche possibile analizzare una sottostringa derivabile da analizzare una sottostringa derivabile da ..

1616

Tavole Tavole LR(0): chiusuraLR(0): chiusura

Esempio di chiusura.Esempio di chiusura. Data la Data la grammatica estesa grammatica estesa G’ G’ (0)(0)E’E’EE; (1); (1)EEE+TE+T; (2); (2)EETT; ; (3)(3)TTT*FT*F; (4); (4)TTFF; (5); (5)FF(E)(E); (6); (6)FFidid. . Calcolo della chiusura di un insieme Calcolo della chiusura di un insieme di item di item II..

• Se inizialmente Se inizialmente I={E’ I={E’ .E} .E}• Allora Allora Closure(I)={E’Closure(I)={E’.E, E.E, E.E+T, .E+T,

EE.T, T.T, T.T*F, T.T*F, T.F, F.F, F.(E), F.(E), F.id}.id}..

1717

Tavole Tavole LR(0): routine di chiusuraLR(0): routine di chiusura

FUNC Closure(I: ItemSet);FUNC Closure(I: ItemSet);VAR J:ItemSet;VAR J:ItemSet;BEGINBEGIN

J:=I;J:=I;DO DO

FOR each itemFOR each item AA.B.BJ & each BJ & each B DODO

J:=JJ:=J{B{B..}}ODOD

UNTIL J unchanged; UNTIL J unchanged; RETURN JRETURN J

END.END.

1818

Tavole Tavole LR(0): kernel item e item LR(0): kernel item e item validivalidi

DefinizioneDefinizione: Un : Un kernel itemkernel item e’: e’:• S’S’.S .S • Un item con il dot cheUn item con il dot che nonnon precede precede la parte destra della la parte destra della

produzioneproduzione

Definizione Valid itemDefinizione Valid item. Un item . Un item AA11..22 e’ valido per per un e’ valido per per un PrAc PrAc 1 1 se esiste una derivazione se esiste una derivazione S’rm*Awrm*12w

Sapere che un item Sapere che un item AA11..22 e’ e’ validovalido per un PrAc per un PrAc 1 permette di decidere tra un’azione shift e reduce permette di decidere tra un’azione shift e reduce quando quando 1 e’ al top dello stack. In particolare se e’ al top dello stack. In particolare se 2 allora lo handle non si trova ancora sullo stack e l’azione e’ shift. Se invece 2= allora AA11 e’ lo handle e’ lo handle e l’azione sara’ reduce. E’ chiaro che due item validi e l’azione sara’ reduce. E’ chiaro che due item validi diversi possono suggerire due azioni contrastant per lo diversi possono suggerire due azioni contrastant per lo stesso PrAc.stesso PrAc.

1919






2020






2121

Tavole Tavole LR(0): funzione gotoLR(0): funzione goto

Definizione. Definizione. FunzioneFunzione goto(I,X) goto(I,X) definita su insiemi didefinita su insiemi di item item ee simboli grammaticali:simboli grammaticali:

goto(I,X)=Closure({ Agoto(I,X)=Closure({ AX.X.| A| A.X.XI}I}

Intuitivamente se I e’ l’insieme degli item validi per Intuitivamente se I e’ l’insieme degli item validi per un PrAc un PrAc allora allora goto(I,X) goto(I,X) e’ l’insieme degli item e’ l’insieme degli item validi per il PrAc validi per il PrAc XX..

Esempio:Esempio:

goto({E’goto({E’E.,EE.,EE.+T},E.+T},+)=Closure({E+)=Closure({EE+.T})=E+.T})=

{E{EE+.T, TE+.T, T.T*F, T.T*F, T.F, F.F, F.(E), F.(E), F.id}.id}

2222

Tavole Tavole LR(0): funzione goto cont.LR(0): funzione goto cont.

Per ogni G la funzionePer ogni G la funzione goto goto definisce un DFA che definisce un DFA che riconosce PrAc di G. Il DFA e’ costruibile riconosce PrAc di G. Il DFA e’ costruibile tramite un NFA che usa gli insiemi di item tramite un NFA che usa gli insiemi di item come stati e transizioni da come stati e transizioni da AA.X.X a a AAX.X. etichettate etichettate XX e da e da AA.B.B a a BB.. etichettate etichettate . . Ne segue che Closure(I) coincide con la Ne segue che Closure(I) coincide con la --closure closure di un insiemi di stati di un NFA come di un insiemi di stati di un NFA come visto a suo tempo. La funzione visto a suo tempo. La funzione goto(I,X)goto(I,X) realizza la transizione da da realizza la transizione da da II tramite l’input tramite l’input XX nel DFA ottenuto dal NFA tramite la nel DFA ottenuto dal NFA tramite la costruzione basata sui sottoinsiemi di stati costruzione basata sui sottoinsiemi di stati gia’ vista.gia’ vista.

2323

Insiemi di item canonici Insiemi di item canonici LR(0)LR(0)

Algoritmo: Algoritmo: Costruzione della Collezione Canonica degli Costruzione della Collezione Canonica degli item LR(0) per una grammatica (augmented) G’.item LR(0) per una grammatica (augmented) G’.PROC Items(G’);PROC Items(G’);BEGINBEGIN

C=Closure({s’C=Closure({s’.s});.s});DODO

FOR (FOR (I) II) IC & (C & (X) XX) XV: goto(I,X)V: goto(I,X)DO DO

C:=C C:=C goto(I,X)goto(I,X)UNTIL C unchangedUNTIL C unchanged

END;END;

2424

Insiemi di item canonici Insiemi di item canonici LR(0) di LR(0) di G’G’

G’: G’: (0)(0)E’E’EE;(1);(1)EEE+TE+T;(2);(2)EETT;(3);(3)TTT*FT*F;(4);(4)TTFF; (5); (5)FF(E)(E); ; (6)(6)FFidid..

II00: : E’E’.E .E II33:: T TF. TF. T.F .F II1111:: F F(E).(E). E E .E+T .E+T II44:: F F(.E) F(.E) F.(E) .(E) goto(Igoto(I00,E)=I,E)=I11

E E .T E.T E.E+T F.E+T F.id .id goto(Igoto(I00,T)=I,T)=I22

T T .T*F E.T*F E.T .T II77:: T TT*.F T*.F goto(Igoto(I00,F)=I,F)=I33

T T .F T.F T.T*F F.T*F F.(E) .(E) goto(Igoto(I00,()=I,()=I44

F F .(E) T.(E) T.F F.F F.id .id goto(Igoto(I00,id)=I,id)=I55

FF.id F.id F.(E) .(E) II88:: F F(E.) (E.) goto(Igoto(I11,+)=I,+)=I66

II11:: E’ E’ E. FE. F.id E .id E E.+T E.+T goto(Igoto(I22,*)=I,*)=I77

E E E.+T E.+T II55:: F Fid. id. II99:: E EE+T. E+T. goto(Igoto(I44,+)=I,+)=I88

II22:: E E T. T. II66:: E EE+.T TE+.T TT.*F T.*F goto(Igoto(I44,T)=I,T)=I22

T T T.*F TT.*F T.T*F .T*F II1010:: T TT*F. T*F. goto(Igoto(I44,F)=I,F)=I33

2525



II00: : E’E’.E .E II33:: T TF. TF. T.F .F II1111:: F F(E).(E). E E .E+T .E+T II44:: F F(.E) F(.E) F.(E) .(E) goto(Igoto(I44,()=I,()=I44

E E .T E.T E.E+T F.E+T F.id .id goto(Igoto(I44,id)=I,id)=I55

T T .T*F E.T*F E.T .T II77:: T TT*.F T*.F goto(Igoto(I66,T)=I,T)=I99

T T .F T.F T.T*F F.T*F F.(E) .(E) goto(Igoto(I66,F)=I,F)=I33

F F .(E) T.(E) T.F F.F F.id .id goto(Igoto(I66,()=I,()=I44

FF.id F.id F.(E) .(E) II88:: F F(E.) (E.) goto(Igoto(I66,id)=I,id)=I55

II11:: E’ E’ E. FE. F.id E .id E E.+T E.+T goto(Igoto(I77,F)=I,F)=I1010

E E E.+T E.+T II55:: F Fid. id. II99:: E EE+T. E+T. goto(Igoto(I77,()=I,()=I44

II22:: E E T. T. II66:: E EE+.T TE+.T TT.*F T.*F goto(Igoto(I77,id)=I,id)=I55

T T T.*F TT.*F T.T*F .T*F II1010:: T TT*F. T*F. goto(Igoto(I88,))=I,))=I1111

2626



II00: : E’E’.E .E II33:: T TF. TF. T.F .F II1111:: F F(E).(E). E E .E+T .E+T II44:: F F(.E) F(.E) F.(E) .(E) goto(Igoto(I88,+)=I,+)=I4646

E E .T E.T E.E+T F.E+T F.id .id goto(Igoto(I99,*)=I,*)=I77

T T .T*F E.T*F E.T .T II77:: T TT*.F T*.F T T .F T.F T.T*F F.T*F F.(E) .(E) F F .(E) T.(E) T.F F.F F.id .id FF.id F.id F.(E) .(E) II88:: F F(E.) (E.) II11:: E’ E’ E. FE. F.id E .id E E.+T E.+T E E E.+T E.+T II55:: F Fid. id. II99:: E EE+T. E+T. II22:: E E T. T. II66:: E EE+.T TE+.T TT.*F T.*F T T T.*F TT.*F T.T*F .T*F II1010:: T TT*F. T*F.

2727

Diagrammi LR(0) esempioDiagrammi LR(0) esempio

2828

Tavole di parsing STavole di parsing SLR(1)LR(1)Si costruisce a partire dalla collezione C di insiemi di Si costruisce a partire dalla collezione C di insiemi di

item LR(0) di item LR(0) di G’ G’ calcolando action e goto come calcolando action e goto come segue:segue:

1.1. Costruire C={ICostruire C={I00,I,I11,…I,…Inn} Collezione di insiemi di item } Collezione di insiemi di item LR(0) di G’LR(0) di G’

2.2. La tavola (stato) i deriva da ILa tavola (stato) i deriva da Iii con azioni: con azioni:

a)a) AA.a.aIIii & goto(I,a)=I & goto(I,a)=Ijj action[i,a]=“shift j” action[i,a]=“shift j”

b)b) AA..IIii aaFOLlOW(A) &AFOLlOW(A) &AS’ action[i,a]=“reduce S’ action[i,a]=“reduce AA””

c)c) S’S’SSIIii action[I,$]=“accept” action[I,$]=“accept”

Se le regole precedenti generano azioni in conflitto Se le regole precedenti generano azioni in conflitto allora G’ non e’ SLR(1).allora G’ non e’ SLR(1).

2929

Tavole di parsing SLR(1)Tavole di parsing SLR(1)3.3. AAN goto[IN goto[Iii,A]=I,A]=Ijj goto(i,A)=j goto(i,A)=j

4.4. Ogni entry non definita in 1. 2. 3. e’ posta a Ogni entry non definita in 1. 2. 3. e’ posta a errorerror

5.5. Lo stato iniziale del parser e’ costruito da Lo stato iniziale del parser e’ costruito da II00={S’={S’.S,…} .S,…}

Una grammatica che possieda una tavola di Una grammatica che possieda una tavola di parsing parsing SLR(1)SLR(1) e’ detta e’ detta SLR(1).SLR(1).

Ogni grammatica Ogni grammatica SLR(1)SLR(1) e’ non ambigua. e’ non ambigua. Esistono grammatiche non ambigue che non Esistono grammatiche non ambigue che non sono sono SLR(1),SLR(1), Es: Es: SSL=R SL=R SR LR L*R L*R Lid Rid RLL

3030

Tavole di ParsingTavole di Parsing

0

1

2

3

4

5

6

7

8

9

1011

Stato id + * ( ) $ E T F id + * ( ) $ s s

s

s

s s

s s

s s

s s

s

A

2 2 2

4 4 4 4

1 1 1

3 3 3 3

5 5 5 5

66 6 6

1 2 3

8 2 3

39

10

3131

Item Item LR(1)LR(1)Un item LR(1) e’ una coppia Un item LR(1) e’ una coppia [A[A..,a],a] con con aaTT{$}{$} e e

AA..Il secondo componente di un item e’ chiamato Il secondo componente di un item e’ chiamato stringa di stringa di

lookaheadlookahead. Essa non si usa quando . Essa non si usa quando β≠β≠. Se invece . Se invece ββ== la stringa di lookahead la stringa di lookahead a a specifica una riduzione specifica una riduzione AA solo quando il token in input è solo quando il token in input è aa. .

DefinizioneDefinizione. Un item LR(1) . Un item LR(1) [A[A..,a],a] è è validovalido per un PrAc per un PrAc a se esiste una derivazione canonica destra a se esiste una derivazione canonica destra S’rm*Awrm*w, con , con == e e w=aw’ w=aw’ oo w= w= & a=$ & a=$..

In relazione alle grammatiche SLR(1) va notato che l’ In relazione alle grammatiche SLR(1) va notato che l’ insieme insieme di stringhe di lookahead di stringhe di lookahead aa che formano gli che formano gli item LR(1) item LR(1) [A[A..,a],a] validi per un prefisso validi per un prefisso verifica verifica FOLLOW(A) FOLLOW(A) ma in generale ma in generale FOLLOW(a)FOLLOW(a)

3232

Tavole Tavole LR(1): funzione closureLR(1): funzione closureDefinizione.Definizione. Chiusura di un insieme di item Chiusura di un insieme di item II per per

una una G’G’ estesa: estesa:• Inizialmente Inizialmente Closure(I)=IClosure(I)=I..• Se Se [A[A.B.B,a],a]Closure(I) Closure(I) ee B B alllora alllora

aggiungere aggiungere [B[B..,b] ,b] a a closure(I)closure(I) per ogni per ogni bbFIRST(FIRST(a)a)

Il significato intuitivo di Closure e’ il seguente: se Il significato intuitivo di Closure e’ il seguente: se AA.B.BClosure(I) Closure(I) allora durante il parsing e’ allora durante il parsing e’ possibile che si analizzi una sottostringa possibile che si analizzi una sottostringa derivata da derivata da BB. Se inoltre . Se inoltre BB allora e’ anche allora e’ anche possibile analizzare una sottostringa derivabile possibile analizzare una sottostringa derivabile da da per tutti gli input per tutti gli input b b tali chetali che b bFIRST(FIRST(a)a)

3333

Tavole Tavole LR(1): routine di LR(1): routine di chiusurachiusura

FUNC Closure(I: ItemSet);FUNC Closure(I: ItemSet);VAR J:ItemSet;VAR J:ItemSet;BEGINBEGIN

J:=I;J:=I;DO DO

FOR each item [AFOR each item [A.B.B,a],a]J & each BJ & each B & & each each bbFIRST(FIRST(a)a)

DODOJ:=JJ:=J{[B{[B..,b]},b]}

ODODUNTIL J unchanged; UNTIL J unchanged; RETURN JRETURN J

END.END.

3434

Tavole Tavole LR(1): funzione gotoLR(1): funzione goto

Definizione. Definizione. FunzioneFunzione goto(I,X) goto(I,X) definita su definita su insiemi diinsiemi di item item ee simboli grammaticali:simboli grammaticali:

goto(I,X)=Closure({ [Agoto(I,X)=Closure({ [AX.X.,a]| ,a]| [A[A.X.X,a],a]I}I}

Ancora se Ancora se II e’ l’insieme degli item validi per e’ l’insieme degli item validi per un PrAc un PrAc allora allora goto(I,X) goto(I,X) e’ l’insieme e’ l’insieme degli item validi per il PrAc degli item validi per il PrAc XX..

3535

Insiemi di item canonici Insiemi di item canonici LR(1)LR(1)

Algoritmo: Algoritmo: Costruzione della Collezione Canonica degli Costruzione della Collezione Canonica degli item LR(1) per una grammatica (augmented) G’.item LR(1) per una grammatica (augmented) G’.PROC Items(G’);PROC Items(G’);BEGINBEGIN

C=Closure({[s’C=Closure({[s’.s,$]});.s,$]});DODO

FOR each IFOR each IC & each XC & each XV such that V such that goto(I,X)goto(I,X)

DO DO C:=C C:=C goto(I,X)goto(I,X) /* /*

INCL(C,goto(I,X)) */INCL(C,goto(I,X)) */UNTIL C unchangedUNTIL C unchanged

END;END;

3636

Insiemi di item canonici Insiemi di item canonici LR(1) di LR(1) di GG22’’

GG22’: ’: (0)(0)S’S’SS;(1);(1)SSCCCC;(2);(2)CCcCcC;(3);(3)CCdd;; II00: : [S’[S’.S,$] .S,$] II33: : [C[Cc.C,c] [Cc.C,c] [C.d,$] .d,$] goto(Igoto(I22,d)=I,d)=I77

[S[S.CC,$] [C.CC,$] [Cc.C,d] c.C,d] II77:: [C [Cd.,$] d.,$] goto(Igoto(I33,C)=I,C)=I88

[C[C.cC,c] [C.cC,c] [C.cC,c] .cC,c] II88:: [C [CcC.,c] cC.,c] goto(Igoto(I33,c)=I,c)=I88

[C[C.cC,d] [C.cC,d] [C.cC,d] [C.cC,d] [CcC.,d] cC.,d] goto(Igoto(I33,d)=I,d)=I44

[C[C.d,c] [C.d,c] [C.d,c] .d,c] II99:: [C [Cc.,$]c.,$] goto(Igoto(I66,C)=I,C)=I99

[C[C.d,d] [C.d,d] [C.d,d] .d,d] goto(Igoto(I00,S)=I,S)=I1 1 goto(Igoto(I66,c)=I,c)=I66

II11:: [S’ [S’S.,$] S.,$] II44:: [C [Cd.,c] d.,c] goto(Igoto(I00,C)=I,C)=I2 2 goto(Igoto(I66,d)=I,d)=I77

II22:: [S [SC.C,$] [CC.C,$] [Cd.,d] d.,d] goto(Igoto(I00,c)=I,c)=I33

[C[C.cC,$] .cC,$] II55:: [S [SCC.,$] CC.,$] goto(Igoto(I00,d)=I,d)=I44

[C [C .d,$] .d,$] II66:: [C [Cc.C,$] c.C,$] goto(Igoto(I22,C)=I,C)=I55

[C[C.cC,$] .cC,$] goto(Igoto(I22,c)=I,c)=I66

3737

Insiemi di Item LR(1): Insiemi di Item LR(1): diagrammadiagramma

3838

Costruzione delle Tavole Costruzione delle Tavole LR(1)LR(1)

Input:Input: una grammatica estesa una grammatica estesa G’G’..Output: Output: tavoletavole canoniche canoniche LR(1) di LR(1) di G’G’..

1.1. Costruire Costruire C={IC={I00,I,I11,...,I,...,Inn} } CCII LR(1)CCII LR(1)

2.2. La tavola La tavola i i deriva daderiva da I Ii i con con actionaction seguente: seguente:a)a) se se [A[A.a.a,b],b]IIii ee goto(I goto(Iii,a)=I,a)=Ijj alloraallora action[i,a]=shift j action[i,a]=shift j

b)b) se se [A[A.,a].,a]IIii e e A≠S A≠S alloraallora action[i,a]=reduce A action[i,a]=reduce Ac)c) se se [S’[S’S,$]S,$]IIii alloraallora action[i,$]= accept action[i,$]= accept

3.3. Se goto(ISe goto(Iii,A)=I,A)=Ijj allora goto[i,$]=j allora goto[i,$]=j4.4. Porre tutte le entry non definite in 1),2) e 3) a errorPorre tutte le entry non definite in 1),2) e 3) a error5.5. Lo stato iniziale del parser è quello contenente [S’Lo stato iniziale del parser è quello contenente [S’.S,.S,

$]$]Se le tavole non presentano conflitti shift-reduce o Se le tavole non presentano conflitti shift-reduce o

reduce-reduce allora la grammatica reduce-reduce allora la grammatica GG è LR(1). è LR(1).

3939

Tavole di Parsing LR(1) Tavole di Parsing LR(1) esempioesempio

0

1

2

3

4

5

6

7

8

9

Stato c d $ S C

s3

s4

1 2A

s6 s7 58

r3 r3r1

s3 s4

s6 s7 9

r3r2 r2

r2

G2’: G2’: (0)(0)S’S’SS;(1);(1)SSCCCC;(2);(2)CCcCcC;(3);(3)CCdd;;

4040


0

1

2

3

4

5

6

7

8

9

Stato c d $ S C

s3

s4

1 2A

s6 s7 58

r3 r3r1

s3 s4

s6 s7 9

r3r2 r2

r2

G2’: G2’: (0)(0)S’S’SS;(1);(1)SSCCCC;(2);(2)CCcCcC;(3);(3)CCdd;;

goto (I0,c)=I3goto(I0,d)=I4goto(I0,S)=I1goto(I0,C)=I2goto(I2,c)=I6goto(I2,d)=I7goto(I2,C)=I5goto(I3,c)=I3goto(I3,d)=I4goto(I3,C)=I8goto(I6,c)=I6goto(I6,d)=I7goto(I6,C)=I9

4141

Costruzione delle Tavole Costruzione delle Tavole LALALR(1)LR(1)

Definiamo Definiamo core(I)={[Acore(I)={[A..] | [A] | [A..,u],u]I}I} Poichè il core di Poichè il core di goto(I,X)goto(I,X) dipende dal core dipende dal core

di di II, ne segue che , ne segue che goto(goto(HHIIii)= )= HHgoto(Igoto(Iii)). . Quindi i goto di stati immersi sono a loro Quindi i goto di stati immersi sono a loro volta tra loro immergibili. Le tavole volta tra loro immergibili. Le tavole ottenute in questo modo, come ottenute in questo modo, come ottimizzazione della collezione di stati ottimizzazione della collezione di stati canonici LR(1) sono tuttavia anche canonici LR(1) sono tuttavia anche ottenibili a partire dalla collezione ottenibili a partire dalla collezione canonica di stati LR(0). Questo ne fa un canonica di stati LR(0). Questo ne fa un algoritmo molto efficiente.algoritmo molto efficiente.

4242

Costruzione delle Tavole Costruzione delle Tavole LALALR(1)LR(1)

Se nella collezione canonica di insiemi di item Se nella collezione canonica di insiemi di item LR(1) di LR(1) di GG22’’ uniamo gli stati I uniamo gli stati I44 e I e I77 in un in un nuovo stato Inuovo stato I4747 con 3 item con 3 item [C[Cd.,c/d/$] d.,c/d/$] allora allora il parser ha azione il parser ha azione reduce_Creduce_Cd d su ogni input, su ogni input, anche su quelli su cui l’originale dichiara anche su quelli su cui l’originale dichiara error (es. error (es. ccd cdcdcccd cdcdc) . La primo token in ) . La primo token in input errato. L’ottimizzazione consiste input errato. L’ottimizzazione consiste nell’ nell’ immergere gli stati con lo stesso coreimmergere gli stati con lo stesso core, cioè , cioè stati che differiscono solo per il token di stati che differiscono solo per il token di lookahead (idem per Ilookahead (idem per I33-I-I66 e I e I88-I-I99). ).

4343

Corrispondenti Item LALR(1)Corrispondenti Item LALR(1)

4444


4545

Corrispondenti Item LR(0)Corrispondenti Item LR(0)

4646

Insieme LALR(1) e LR(0)Insieme LALR(1) e LR(0)

4747


4848

Grammatiche LL ed LRGrammatiche LL ed LRTeorema (decidibilita’):Teorema (decidibilita’): date due grammatiche date due grammatiche

LL(k)LL(k), , GG11 e e GG22, il problema , il problema L(GL(G11)=L(G)=L(G22)) e’ e’ decidibile.decidibile.

La seguente grammatica: La seguente grammatica: SSA|B, AA|B, AaAb|0, aAb|0, BBaBbb|1aBbb|1 e’ e’ LR(0)LR(0) ma non ma non LL(k)LL(k) per ogni per ogni kk00..

Teorema. Teorema. Ogni grammatica Ogni grammatica LL(k) LL(k) e’ anche e’ anche LR(k)LR(k), , kk00..

DefinizioneDefinizione. Um linguaggio . Um linguaggio CFGCFG e’ e’ deterministico se esite un deterministico se esite un DPDADPDA (Det, (Det, PushDown Automaton) che lo accetta.PushDown Automaton) che lo accetta.

4949

Linguaggi LL ed LRLinguaggi LL ed LRDefinizioneDefinizione. Un linguaggio . Un linguaggio LL tale che nessuna tale che nessuna

wwLL e’ della forma e’ della forma w=xyw=xy con con xxL L e’ detto e’ detto avere la proprieta’ del prefisso (prefix-free).avere la proprieta’ del prefisso (prefix-free).

Teorema. Teorema.

LL linguaggio deterministico: linguaggio deterministico: GG LR(1): LR(1): L=L(G)L=L(G). .

Se inoltre Se inoltre LL e’ prefix-free allora: e’ prefix-free allora: GG LR(0): LR(0): L=L(G)L=L(G)..

Altrimenti detto Altrimenti detto LLT* T* CFG deterministico e CFG deterministico e T GG LR(0): LLR(0): L=L(G).

5050

Linguaggi LL ed LR cont.Linguaggi LL ed LR cont.Teorema.Teorema. Dato un linguaggio Dato un linguaggio LL per cui per cui

esiste una grammatica esiste una grammatica G, LL(k)G, LL(k) e priva e priva di di -produzioni-produzioni, tale che , tale che L=L(G)L=L(G) e e k>1k>1, , allora esiste una grammatica allora esiste una grammatica G’G’, , LL(k-1)LL(k-1) tale che tale che L=L(G’)L=L(G’)..

Teorema.Teorema. Per ogni Per ogni k k 00 la classe dei la classe dei linguaggi linguaggi LL(k)LL(k) e’ propriamente inclusa e’ propriamente inclusa in quella dei linguaggi in quella dei linguaggi LL(k+1)LL(k+1)..

5151

Rapporto tra grammatiche LL, Rapporto tra grammatiche LL, LR,... LR,...

5252

Rapporto tra linguaggi LL, Rapporto tra linguaggi LL, LR,... LR,...

5353

Seminari su grammatiche e Seminari su grammatiche e linguaggi LL, LR,... linguaggi LL, LR,...

1. Linguaggi e grammatiche LL, LR e deterministici.

2. Teoremi di inclusione tra tali linguaggi, eventuali controesempi

3. PDA non deterministici e non: linguaggi relativi.

5454

Seminari su rapporti tra XML e Seminari su rapporti tra XML e scanner, parser, grammatiche e scanner, parser, grammatiche e

linguaggi linguaggi

1. Confronto tra XML BNF EBNF come strumenti per descrivere linguaggi e grammatiche. Aspetti teorici associati per la costruzione automatica di parser.

2. Uso di XML e strumenti associati come standard di scambio dati tra parser scanner compiler ecc.

3. Problemi di parsing di documenti XML e strumenti associati applicazioni e teoria.

5555


0

1

2

3

4

5

6

7

8

9

1011

Stato id + * ( ) $ E T F id + * ( ) $

5656

Tavole di Parsing LR(1): Tavole di Parsing LR(1): esempioesempio

stato 0 1

2

Implementazione di Linguaggi 2 PARTE 4

Documents

Transcript of Implementazione di Linguaggi 2 PARTE 4