tabelle slr costruzione di tabelle di parsing slr
TRANSCRIPT
Tabelle SLR
Costruzione di tabelle di Parsing SLR
Metodo simple LR
Metodo di costruzione di una tabella di parsing LR
Abbreviazione: SLR Parser SLR: parser LR che usa una
tabella di parsing SLR Grammatica SLR: grammatica per cui
esiste un parser SLR
Potenza del metodo
È il metodo di costruzione di tabelle LR più semplice
È il metodo meno potente: ha successo per meno grammatiche rispetto agli altri due che vedremo
È Il metodo più semplice da implementare
Item LR(0)
Un item LR(0) per una grammatica G è una produzione di G con un punto in qualche posizione della parte destra della produzione
Es: la produzione A XYZ può dar luogo a quattro item LR(0):
1. A • XYZ2. A X • YZ3. A XY • Z4. A XYZ •
Item LR(0)
La produzione A dà luogo ad un solo item LR(0), cioè A •
Un item può essere rappresentato efficacemente con due numeri interi: il numero della produzione e la posizione del punto
Un item indica quanto di una produzione è stato visto ad un certo punto del parsing
Es: A X • YZ indica che X è stato visto e ci si aspetta di vedere YZ
Idea Centrale del metodo SLR
Gli item sono gli stati di un NFA che riconosce i viable prefixes
Insiemi di item sono gli stati del DFA che si ottiene da questo NFA con la costruzione dei sottoinsiemi
Una collezione di insiemi di item LR(0) costituisce la base per costruire un parser SLR
Collezione canonica LR(0)
G grammatica con simbolo iniziale S G’ grammatica G aumentata con un
nuovo simbolo iniziale S’ e la produzione S’ S
Questo accorgimento serve ad indicare al parser la fine del parsing: il parsing ha successo se e solo se l’input è terminato e c’è una riduzione con la produzione S’ S
Operazione di closure
I insieme di item closure(I) è un insieme di item
costruito da I come segue:1. Inizialmente poni closure(I) uguale a I2. Se A • B è in closure(I) e B è
una produzione, allora aggiungi B • a closure(I), se non è già presente. Applica questa regola fino a quando nessun altro item può essere aggiunto a closure(I)
Operazione di closure
Intuizione: la presenza di A • B in closure(I) indica che, ad un certo punto del processo di parsing, ci aspettiamo di vedere nell’input una stringa derivabile da B
Se B è una produzione, allora è possibile che ci sia una stringa derivabile da , a questo punto dell’input
Per questa ragione aggiungiamo anche l’item B • a closure(I)
Esempio closure E’ E E E + T | T T T * F | F F (E) | id I = {E’ • E} closure(I) = {E’ •E} {E • E + T,
E • T } { T • T * F, T • F } {F • (E), F • id }
Kernel item
Si noti che se un item B • viene inserito in closure(I), allora anche tutte le produzioni di B vengono inserite con il punto nella posizione più a sinistra
In effetti basterebbe indicare solo B convenendo che rappresenta tutte le sue produzioni con il punto nella posizione più a sinistra
Kernel item
Kernel item: S’ • S oppure un item con il punto non nella posizione più a sinistra
Non-kernel item: tutti gli altri (quelli che hanno il punto nella posizione più a sinistra)
Ogni insieme di item può essere generato con una closure a partire da un certo insieme di kernel item
Questa proprietà è utile per minimizzare lo spazio necessario per memorizzare gli insiemi di item
Operazione goto
I insieme di item X simbolo della grammatica goto(I,X) = closure( { A X• |
A •X I} ) Se I è un insieme di item validi per un
qualche viable prefix , allora goto(I,X) è il set di item validi per il viable prefix X
Esempio goto
I = {E’ •E, E E • + T} goto(I,+) = closure({E E + • T}) = {
E E + • T,
T • T * F,
T • F,
F•(E),
F •id }
Collezione canonica LR(0)
procedure items(G’);begin
C := { closure({S’ •S}) } repeat
for each insieme di item I in C e simbolo X tale che goto(I,X) non è vuoto doaggiungi goto(I,X) a Cuntil non possono essere aggiunti nuovi insiemi di item a C
end;
Esempio
Costruiamo la collezione canonica LR(0) per la solita grammatica
E’ E E E + T | T T T * F | F F (E) | id
Esempio
Il primo insieme di item che inseriamo in C è I0 = closure({E’ •E})= {E’ •E,
E • E + T, E • T,
T • T * F, T • F, F • (E), F • id }
Iniziamo il ciclo. Vediamo subito che goto(I0,E) non è vuoto perché in I0 ci sono i due item E’ •E e E • E + T
Esempio
goto(I0,E)=closure({E’ E•, E E • + T}) =
{E’ E•, E E • + T}
Chiamiamo I1 questo nuovo insieme ed aggiungiamolo a C
Esempio Continuiamo con goto(I0,T)=
closure({E T•, T T• * F}) = {E T•,
T T• * F} Anche questo insieme non è presente in
C e quindi lo inseriamo con il nome I2
goto(I0,F) = closure({T F • }) = {T F • } = I3
Esempio (continuando)
goto(I0, ‘(‘)=closure({F (• E)}) = {F (• E),
E • E + T, E • T, T • T * F, T • F, F • (E), F • id }) = I4
Questa volta l’operazione di chiusura ha rigenerato tutti gli item di I0 dall’item F (• E)
Esempio (continuando)
I5 = {F id • } I6 = {E E + • T,
T • T * F, T • F, F • (E), F • id }
I7 = {T T * • F, F • (E), F • id }
I8 = {E E • + T, F (E • ) }
Esempio
I9 = {E E + T • , T T • * F}
I10 = {T T * F • }
I11 = {F (E ) • }
La funzione goto
I0I1 I6 I9
I2 I7 I10
I3
I4I8 I11
I5
E + T
T
F
(
id
* F
E )
I3
I4
I5
F (
id
I7
*
I4(
I5
id
(idI2T
F
I6+
La funzione goto
Si noti che il precedente è un DFA: non è un caso!
Se ogni stato di questo automa è uno stato finale e I0 è lo stato iniziale, allora l’automa riconosce tutti e soli i viable prefixes della grammatica aumentata
L’algoritmo aveva intenzione di costruire proprio un automa di questo genere
Item validi Un item A12 si dice valido per un
viable prefix 1 se e solo se esiste una derivazione:
S*rm Aw rm 12w
In generale un item sarà valido per più viable prefixes
L’informazione sul fatto che un certo A12 è valido per 1 ci aiuta molto nella decisione fra lo shift e il reduce
Item validi Se durante il parsing troviamo sullo
stack 1 allora:
– Se 2 è diversa da allora la è possibile che la handle non è ancora stata messa interamente sullo stack. Dovremmo procedere quindi a fare uno shift
– Se 2 è allora è possibile che A 1 sia la handle e quindi la mossa dovrebbe essere una riduzione con questa produzione
Item validi Tuttavia può succedere che due diversi item
validi per lo stesso viable prefix indichino mosse diverse
Alcuni di questi conflitti possono essere risolti guardando il simbolo di lookahead oppure applicando metodi più potenti
Come sappiamo, in generale, non tutti i conflitti possono essere risolti se il metodo LR scelto viene usato su una grammatica arbitraria
Item validi
Come trovare gli item validi per un certo viable prefix?
Teorema: L’insieme degli item validi per un viable prefix è esattamente l’insieme di item raggiunto dallo stato iniziale lungo un cammino etichettato del DFA rappresentato dalla funzione goto fra gli stati della collezione canonica LR(0)
Item validi: esempio
È facile convincersi che E + T * è un viable prefix per la nostra grammatica aumentata
“Eseguendo” questa stringa nell’automa che rappresenta la funzione goto si arriva nello stato I7
I7 = {T T * • F, F • (E), F • id }
Questi tre item sono esattamente gli item validi per E + T *
Item validi: esempio
Per convincerci che sono validi, consideriamo le seguenti derivazioni rightmost:
1. E’E E+T E+T*F (T T * • F valido)2. E’ E E+T E+T*F E+T*(E) (F • (E)
valido)3. E’ E E+T E+T*F E+T*id (F • id
valido) Non ci sono altri item validi per E + T *
Tabelle di parsing SLR
Ingredienti:– Grammatica aumentata G’– DFA che riconosce i viable prefixes di G’
(funzione goto)– FOLLOW(A) per ogni non terminale A di G’
Output: tabella di parsing LR (se è multidefinita in almeno un’entrata la grammatica non è analizzabile SLR(1))
Algoritmo
1. Costruisci C = {I0,I1,...,In }, la collezione canonica LR(0)
2. Lo stato i del parser LR è costruito a partire da Ii. Le azioni di parsing per lo stato i sono determinate come segue:
a) Se A a Ii e goto(Ii,a) = Ij, allora poni action[i,a]:= “shift j” (a è terminale!)
b) Se A Ii, allora poni action[i,a] := “reduce A ” per tutte le aFOLLOW(A) (A S’)
c) Se S’S Ii, allora poni action[i,$] := “accept”
Algoritmo
La tabella action+goto del parser LR così ottenuto è data dalla tabella action così costruita e dalla funzione goto calcolata durante la costruzione della collezione canonica LR(0)
Lo stato iniziale del parser LR così ottenuto è quello costruito dall’insieme di item che contiene S’ • S
Tutte le entrate non definite sono entrate “error”
Esempio
Calcoliamo la tabella SLR per la nostra solita grammatica aumentata
Abbiamo già calcolato la collezione canonica LR(0)
Esaminiamo tutti gli stati e seguiamo le istruzioni
Cominciamo con lo stato I0 che è quello iniziale
Esempio I0 = {E’ •E,
E • E + T, E • T,
T • T * F, T • F, F •
(E), F • id } L’item F • (E) indica di porre action[0,(]:=
“shift 4” (poiché goto(I0,()= I4) L’item F • id indica di porre action[0,id]:=
“shift 5” (poiché goto(I0,id)= I5) Gli altri item di I0 non suggeriscono azioni
Esempio
I1= {E’ E•, E E • + T}
L’item E’ E• suggerisce di porre action[1,$]= “accept”
L’item E E • + T suggerisce di porre action[1,+]= “shift 6” poiché goto(I1,+) = I6
Esempio
I2 ={E T•, T T• * F}
L’item E T• suggerisce di effettuare una reduce. Si ha che FOLLOW(E)={$,+,)} e quindi action[2,$] := action[2,+] := action[2,)] := “reduce E T”
L’item T T• * F suggerisce action[2,*]=“shift 7”
Esempio
Continuando in questo modo otteniamo la tabella di parsing LR che avevamo già visto per questa grammatica quando illustravamo il funzionamento di un parser LR
Siccome non ci sono entrate multidefinite concludiamo che la grammatica è SLR(1)
La tabella SLR(1)action goto
Stato id + * ( ) $ E T F
0 s5 s4 1 2 3
1 s6 acc
2 r2 s7 r2 r2
3 r4 r4 r4 r4
4 s5 s4 8 2 3
5 r6 r6 r6 r6
6 s5 s4 9 3
7 s5 s4 10
8 s6 s11
9 r1 s7 r1 r1
10 r3 r3 r3 r3
11 r5 r5 r5 r5
Grammatiche non SLR(1)
Sappiamo già che nessuna grammatica ambigua può essere LR, quindi tantomeno SLR
Ci sono grammatiche non ambigue che però non sono SLR. Ad esempio:
S L = R | R L * R | id R L
Esempio
Questa grammatica non è ambigua Genera gli assegnamenti fra
identificatori e puntatori oppure espressioni di locazioni o valori
Es: id = * id, * id = id, **id L sta per locazione, R è un valore che
può essere memorizzato in una locazione, * sta per “il contenuto di”
Collezione canonica LR(0)
I0 = {S’ S,
S L=R,
S R,
L *R,
L id,
R L}
I1= {S’ S}
I2 = {S L=R,
R L}I3= {S R}
I4= {L *R,
R L,
L *R,
L id}
I5 = { L id}
Esempio
I6 = {S L=R,
R L,
L *R,
L id}
I7= {L *R}
I8= { R L}
I9 = { S L=R}
Esempio
Consideriamo lo stato 2. L’item S L=R fa porre action[2,=] := “shift 6” L’item R L suggerisce una riduzione. Ma il
simbolo = appartiene a FOLLOW(R) e quindi si ha anche che action[2,=] := “reduce R L”
Un conflitto shift/reduce sul simbolo di input = nello stato 2.
Il metodo SLR non è abbastanza potente per decidere quale azione intraprendere avendo visto una stringa riducibile ad L e il segno =