lr parser giuseppe morelli. la maggior parte dei parser bottom-up è costituita dai cosiddetti...
TRANSCRIPT
![Page 1: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/1.jpg)
LR Parser
Giuseppe Morelli
![Page 2: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/2.jpg)
• La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove:
• L indica il verso dell’analisi della stringa di input (letf-to-right)
• R indica che per la costruzione dell’albero di parse si usa una derivazione destra inversa
• K indica il numero di simboli di lookahead utilizzati per le decidere come fare evolvere il procedimento di parsing.
• Per k<=1 indichiamo tali parser con LR• I parser LR sono table-driven
![Page 3: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/3.jpg)
Vantaggi e svantaggi dei parser LR(k)
• Generalità: praticamente tutti i linguaggi di programmazione possono essere riconosciuti con parser LR.
• Efficienza: è il metodo shift-reduce bottom-up senza backtracking più generale ed efficiente
• Potenza: la classe LR(k) estende la classe LL(k)• Capacità di rilevare errori: un errore viene
riconosciuto immediatamente al suo verificarsi.Svantaggi:• Complessità: necessitano appositi tools per la
generazione automatica
![Page 4: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/4.jpg)
• Un parser Bottom-up , shift-reduce, deve continuamente scegliere se effettuare una operazione di SHIFT o una di REDUCE:
Es: Shift * oppure Reduce T con E -> T ????
![Page 5: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/5.jpg)
Stati ed items
• La scelta è fatta mantenendo ed utilizzando gli stati, che permettono di tenere traccia circa la “posizione” della situazione di parse.
• Gli stati sono insiemi di “items”• Item (item LR(0))di una grammatica G è una
produzione di G con un “punto” in una posizione del corpo della stessa.
• Es. A ->XYZ
• Mentre A -> ε ha item A-> .
![Page 6: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/6.jpg)
Canonical LR(0) collection
• Un item indica lo stato di avanzamento nell’utilizzo di una produzione in un qualsiasi passo del processo di parsing.
• Es. A -> X.YZ indica che è stato già provato che una parte della stringa di input è derivabile da X e si spera il resto sia derivabile da YZ. Mentre A->XYZ. indica che è giunto il momento di ridurre la stringa derivata da XYZ con A.
• Una collezione di insiemi di item (stati) (LR(0) Canonical collection) fornisce le basi per la costruzione di un automa a stati finiti deterministico (Automa LR(0)) usato per le decisioni del parser. Ogni stato dell’automa è un insieme di items.
![Page 7: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/7.jpg)
Grammatica Aumentata
• Per la costruzione della collezione LR(0) canonica di una data grammatica si definisce una grammatica aumentata (argumented grammar) e due funzioni CLOSURE e GOTO.
• Se G è una grammatica la grammatica aumentata G’ è una grammatica con:– Tutte le produzioni di G– La nuova produzione S’ -> S con (S simbolo iniziale di
G)– S’ simbolo iniziale (G’)
• Una stringa è accettata se si applica la produzione S’ -> S
![Page 8: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/8.jpg)
CLOSURE (chiusura di insiemi di Item)
• Se I è un insieme di Item per la grammatica G allora CLOSURE(I) è costruito seguendo 2 regole:
1. In CLOSURE (I) vengono aggiunti tutti gli Item già presenti in I
2. Se A -> α.Bβ è in CLOSURE(I) e B -> γ è una produzione allora si aggiunge a CLOSURE (I) anche l’item B ->.γ ( se non c’è ancora). Tale regola si applica finchè si possono aggiungere elementi.
![Page 9: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/9.jpg)
Esempio
• Supponiamo sia I ={[E’->.E]} un insieme di items della grammatica aumentata seguente
• CLOSURE(I) ={
[E’->.E], [E->.E+T], [E->.T], [T->.T*F],[T->.F],[F->.(E)], [F->.id]
}
F
![Page 10: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/10.jpg)
Algoritmo
![Page 11: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/11.jpg)
GOTO
• La funzione GOTO permette di definire le transizioni nell’automa LR(0) canonico di una grammatica; GOTO(I,X) con I insieme di items, X un simbolo della grammatica è definito come:GOTO(I,X) = CLOSURE {A -> αX.β : A -> α.Xβ Є I }
• Esempio:– Se I = E’ -> .E allora GOTO(I, E) = {[E’->E.], E’->E.
β }
![Page 12: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/12.jpg)
Calcolo della collezione canonica LR(0)
QuickTime™ e undecompressore
sono necessari per visualizzare quest'immagine.
![Page 13: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/13.jpg)
SLR
• Concetto chiave la costruzione dell’ LR(0) automa.
• Gli stati dell’automa sono gli insiemi di Item della collezione canonica LR(0) e le transizioni sono determinate dalla funzione GOTO
• Lo stato iniziale coincide con CLOSURE({[S’->.S]})
• La scelta di SHIFT o REDUCE è fatta come segue:– Se la stringa γ porta l’automa LR(0) dallo stato 0 allo
stato j; se lo stato j ha una transizione etichettata con il successivo simbolo di input a, allora si sceglierà di shiftare a, altrimenti si riduce con la produzione indicata allo stato j.
![Page 14: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/14.jpg)
F
![Page 15: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/15.jpg)
Classificazione di item
• Kernel items: – S’->.S– A->α.Bβ con α != ε
• Non Kernel items:– A-> .β con β != S
![Page 16: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/16.jpg)
Algoritmo di Parsing
ACTION GOTO
PROGRAMMA DI PARSING LR
OUTPUT
INPUT a1
… ai
an
$
STACK
sn
Xn
.
.
.
X1
s1
![Page 17: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/17.jpg)
Alcune note
• Come mostra la figura un parser LR consiste di un input, un output, un programma di controllo, uno stack ed infine una tabella di parsing che ha due parti (ACTION e GOTO)
• Il programma di controllo è lo stesso per tutti i parser LR
• La differenza tra parser LR è determinata dalla tabella di parsing
![Page 18: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/18.jpg)
• Lo stack contiene una sequenza di stati che nel caso di SLR parser corrispondono a quelli dell’automa LR(0).
• Per costruzione ogni stato coincide con un insieme di items ovvero Ij = GOTO(Ii,X) rappresenta una transizione dallo stato i allo stato j.
• Ad ogni stato eccetto che a quello iniziale è possibile associare un solo simbolo della grammatica
![Page 19: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/19.jpg)
Struttura della tabella di parsing LR
• Tale tabella consiste di:– ACTION: Una funzione per le azioni del parser che
prende come argomenti uno stato i ed un simbolo terminale a e restituisce ACTION[i,a] come segue:
• = Shift j (con j uno stato): in effetti è il simbolo che deve essere shiftato ma come visto in precedenza c’è una corrispondenza tra simbolo e stato.
• = Reduce A->β: viene sostituito β (top dello stack) con la testa della produzione A
• = Accept: il processo di parsing finisce accettando l’input• = Error: l’input non è riconosciuto ed il parser genera errore.
– GOTO:Viene estesa agli stati i e j la funzione GOTO[Ii, A] = Ij applicata e definita per gli insiemi di Item
![Page 20: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/20.jpg)
• Input: stringa w e tabella di Parsing LR per G• Output: riduzione al simbolo iniziale a partire da
w se w appartiene a L(G) altrimenti errore
![Page 21: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/21.jpg)
Definizione dell’insieme FOLLOW
• Dato un simbolo non terminale A si definisce FOLLOW(A) l’insieme di simboli terminali che appaiono immediatamente alla destra di A in una forma proposizionale. Ovvero l’insieme di simboli terminali a per i quali esiste una derivazione della forma S =>αAaβ per qualche α e β.
• Il calcolo di FOLLOW avviene:– Si posizione $ nel FOLLOW(S) S= simbolo iniziale– Se esiste una produzione del tipo A->αBβ allora gli
elementi di FIRST(β) si aggiungono in FOLLOW(B) escludendo ε
– Se esiste una produzione A->αB o una produzione A->αBβ con ε Є FIRST(β) allora FOLLOW(B) conterrà tutto FOLLOW(A).
![Page 22: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/22.jpg)
Costruzione della tabella SLR• Data G si costruisce la grammatica aumentata
G’ quindi:1. Si costruisce la collezione canonica LR(0) (insiemi di
Items) c = {I0, I1, …. ,In}2. Lo stato i è costruito da Ii. L’azione per lo stato i è
determinata come segue:1. Se [A-> α.aβ] è in Ii e GOTO(Ii,a) = Ij allora
ACTION[i,a] = “shift j”2. Se [A-> α.] è in Ii allora ACTION[i,a] = “reduce A-> α” per
ogni a Є FOLLOW(A) 3. Se [S’ -> S.] è in Ii allora ACTION[i, $] = “accept”
3. GOTO deve essere costruita per tutti i non termiali Secondo la regola se GOTO(Ii,a)=Ij allora GOTO(i,a) = j
4. Errore se vi sono entry non definit da 2 e 35. Lo stato iniziale è quello ottenuto dall’insieme di Item
contenente [S’->S]
![Page 23: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/23.jpg)
Esempio
• Consideriamo la grammatica aumentata S’=II->SS->BS->CaaB->bCC->bbCaC->e Per costruire la tabella SLR Calcoliamo FOLLOW dei Non
terminali e l’insieme di items LR(0)Follow(I): $Follow(S): $Follow(B): $Follow(C): a$
![Page 24: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/24.jpg)
I0I->°SS->°BS->°CaaB->°bCC->°bbCaC->e°
I1I->S°
I2 S->B°
I3 S->C°aa
I4B->b°CC->b°bCaC->°bbCaC->e°
I5S->Ca°a
I6B->bC°
I7C->bb°CaC->b°bCaC->°bbCaC->e°
I8S->Caa°
I10 C->bbCa°
I9 C->bbC°a
S
B
C
b
a
C
b
a
C
a
![Page 25: LR Parser Giuseppe Morelli. La maggior parte dei parser Bottom-Up è costituita dai cosiddetti parser LR(k) dove: L indica il verso dellanalisi della stringa](https://reader035.vdocumenti.com/reader035/viewer/2022062307/5542eb4b497959361e8b8c31/html5/thumbnails/25.jpg)
Stringa “bbba”
Goto (4,C)