LR Parser

Giuseppe Morelli

• 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

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

• 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 ????

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-> .

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.

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

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.

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

Algoritmo

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.

β }

Calcolo della collezione canonica LR(0)

QuickTime™ e undecompressore

sono necessari per visualizzare quest'immagine.

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.

F

Classificazione di item

• Kernel items: – S’->.S– A->α.Bβ con α != ε

• Non Kernel items:– A-> .β con β != S

Algoritmo di Parsing

ACTION GOTO

PROGRAMMA DI PARSING LR

OUTPUT

INPUT a1

… ai

an

$

STACK

sn

Xn

.

.

.

X1

s1

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

• 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

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

• 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

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).

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]

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$

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

Stringa “bbba”

Goto (4,C)