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
F
• CLOSURE(I) ={
[E’->.E], [E->.E+T], [E->.T],
[T->.T*F],[T->.F],
[F->.(E)], [F->.id]
}
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 un
decompressore
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
INPUT
a1
…
ai
an
$
STACK
sn
Xn
.
.
.
PROGRAMMA DI PARSING
LR
X1
s1
ACTION
GOTO
OUTPUT
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:
a) Se [A-> α.aβ] è in Ii e GOTO(Ii,a) = Ij allora
ACTION[i,a] = “shift j”
b) Se [A-> α.] è in Ii allora ACTION[i,a] = “reduce A-> α” per
ogni a Є FOLLOW(A)
c) 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 3
5. Lo stato iniziale è quello ottenuto dall’insieme di Item
contenente [S’->S]
Esempio
• Consideriamo la grammatica aumentata S’=I
I->S
S->B
S->Caa
B->bC
C->bbCa
C->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$
I0
I->°S
S->°B
S->°Caa
B->°bC
C->°bbCa
C->e°
S
I1
I->S°
B
I2
a
S->B°
C
I3
S->C°aa
I5
S->Ca°a
a
I6
B->bC°
C
b
I4
B->b°C
C->b°bCa
C->°bbCa
C->e°
I8
S->Caa°
b
I7
C->bb°Ca
C->b°bCa
C->°bbCa
C->e°
C
I9
C->bbC°a
a
I10
C->bbCa°
Stringa “bbba”
Goto (4,C)