Inside Out & Back Again

Parsing LR(k)
Vedremo il parsing LR
L = scorre l’input da sinistra a destra
R = segue una derivazione a destra al contrario
k = numero di simboli in input da guardare per
prendere una decisione
LR = LR(1): legge anticipatamente 1 simbolo in
input per capire cosa fare
SLR: LR semplice
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
29 of 55
Qualit`a del parsing LR
Molto generale: funziona per quasi tutti i
costrutti che possono essere descritti da
grammatiche libere da contesto
Non fa backtracking, pu`o essere implementato
efficientemente
Trova errori sintattici appena possibile in una
singola passata da sinistra a destra dell’input
Pu`o essere applicato ad un soprainsieme delle
grammatiche LL
Grammatiche LR(k): dobbiamo poter riconoscere la
parte destra di una produzione in una forma
sentenziale destra, leggendo k simboli di input futuri
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
30 of 55
Prefissi validi
Non `e ovvio come trovare le maniglie
Ad ogni passo il parser vede solo la pila, non
l’intero input
↵ `e un prefisso ammissibile se ! `e tale che ↵|! `e
uno stato di un parser shift-reduce
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
31 of 55
Cosa significa ?
Un prefisso ammissibile non va oltre la fine
destra di una maniglia
E un prefisso ammissibile perch´e `e un prefisso
della maniglia
Finch´e ci sono prefissi validi sulla pila, non sono
stati visti errori di parsing
Per ogni grammatica, l’insieme dei prefissi validi `e
un linguaggio regolare
Mostreremo come costruire automi a stati finiti che
accettano prefissi validi
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
32 of 55
Item
Un item `e una produzione con un “.” nella sua
parte destra
Esempio: gli item per T ! (E ) sono
T
T
T
T
! .(E )
! (.E )
! (E .)
! (E ).
L’unico item per X ! ✏ `e X ! .
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
33 of 55
Item
Spesso chiamati “item LR(0)”
Intuizione: un item indica quanto abbiamo visto
di una produzione finora
l’item A ! .XYZ indica che speriamo di vedere
nell’input una stringa derivabile da XYZ
l’item A ! X .YZ indica che abbiamo gi`a visto una
stringa derivabile da X e che speriamo di vedere
nell’input una stringa derivabile da YZ
l’item A ! XYZ . indica che abbiamo gi`a visto una
stringa derivabile da XYZ e che potrebbe essere il
momento di ridurre XYZ ad A
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
34 of 55
Dagli item ad un automa a stati finiti
Alcuni item sono usati per costruire un automa
a stati finiti deterministico che viene usato per
prendere decisioni durante il parsing (automa
LR(0))
Ogni stato dell’automa LR(0) rappresenta un
insieme di item canonici LR(0)
Data una grammatica e due funzioni CLOSURE
e GOTO, costruiamo gli item canonici LR(0)
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
35 of 55
Funzione CLOSURE
Grammatica aumentata: aggiungiamo S 0 ! S
Serve a dire al parser quando fermarsi
(quando riduce tramite questa produzione)
CLOSURE(I), dove I `e un insieme di item per
una grammatica:
I `e un sottoinsieme di CLOSURE(I)
Se A ! ↵.B `e in CLOSURE(I) e B ! `e
una produzione, aggiungiamo B ! . in
CLOSURE(I). Applichiamo questa regola
finch´e non si pu`o aggiungere pi`u niente a
CLOSURE(I)
Usato per definire gli stati dell’automa
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
36 of 55
Idea di CLOSURE
A ! ↵.B `e in CLOSURE(I) se pensiamo di
poter vedere in futuro una sottostringa
derivabile da B come input
Questa sottostringa avr`a un prefisso derivabile
da B
Quindi aggiungiamo l’item B ! . per tutte le
produzioni B !
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
37 of 55
Intuizione
Il problema nel riconoscere prefissi validi consiste
nel fatto che la pila contiene solo alcune parti
della parte destra di una produzione
Se avesse una parte destra completa,
potremmo ridurre
Queste parti sono sempre prefissi della parte
destra di una produzione
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
38 of 55
Esempio
Consideriamo la stringa in input (int)
Allora (E |) `e uno stato in un parsing shift-reduce
(E `e un prefisso della parte destra di T ! (E )
sar`a ridotto dopo il prossimo shift
L’item T ! (E .) dice che finora abbiamo visto
(E di questa produzione e speriamo di vedere )
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
39 of 55
Esempio
Grammatica
E0
E
T
F
!E
! E + T |T
! T ⇤ F |F
! (E )|id
I = {E 0 ! .E }
CLOSURE (I ) = {E 0 ! .E , E ! .E + T , E ! .T ,
T ! .T ⇤ F , T ! .F , F ! .(E ), F ! .id}
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
40 of 55
Generalizzazione
La pila pu`o avere molti prefissi di parti destre di
produzioni
Prefix1 Prefix2 . . . Prefixn 1 Prefixn
Sia Prefixi un prefisso della parte destra di
Xi ! ↵i
Prefixi prima o poi verr`a ridotto a Xi
la parte mancante di ↵i 1 inizia con Xi
esiste un Xi 1 ! Prefixi 1 Xi per qualche
|
{z
}
↵i
1
Ricorsivamente, Prefixk+1 . . . Prefixn prima o
poi verr`a ridotto alla parte mancante di ↵k
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
41 of 55
Esempio
Consideriamo la stringa in input (int ⇤ int)
(int ⇤ |int) `e uno stato in un parsing shift-reduce
( `e un prefisso della parte destra di T ! (E )
✏ `e un prefisso della parte destra di E ! T
int⇤ `e un prefisso della parte destra di
T ! int ⇤ T
(
✏
int⇤
Prefix1
Prefix2
Prefix3
T ! (E ) E ! ✏T T ! int⇤T
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
42 of 55
Esempio
La “pila di item”
T ! (.E )
E ! .T
T ! int ⇤ .T
Dice:
Abbiamo visto ( di T ! (E )
Abbiamo visto ✏ di E ! T
Abbiamo visto int⇤ di T ! int ⇤ T
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
43 of 55
Funzione GOTO
GOTO(I , X ), dove I `e un insieme di item e X `e
un simbolo della grammatica:
CLOSURE dell’insieme di item A ! ↵X .
tale che A ! ↵.X `e in I
Usata per definire le transizioni dell’automa
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
44 of 55
Esempio
Grammatica
E0
E
T
F
!E
! E + T |T
! T ⇤ F |F
! (E )|id
I = {E 0 ! E ., E ! E . + T }
GOTO(I , +) = {E ! E + .T , T ! .T ⇤ F ,
T ! .F , F ! .(E ), F ! .id}
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
45 of 55
Collezione canonica di insiemi di item LR(0)
Data una grammatica G , aggiungere una
produzione S 0 ! S a G
C = CLOSURE ({S 0 ! .S})
Per ogni insieme di item in C
Per ogni simbolo X di G
Se GOTO(I , X ) non `e vuoto e non in C ,
aggiungi GOTO(I , X ) a C
Finch´e non `e pi`u possibile aggiungere qualcosa
aC
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
46 of 55
Automa DFA
Stati: insiemi di item dalla collezione canonica
Transizioni: funzione GOTO
Stato iniziale: CLOSURE ({S 0 ! .S})
Altri stati: ottenuti applicando GOTO e poi
facendo la chiusura
Tutti gli stati sono finali
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
47 of 55
Esempio
Grammatica
E ! T + E |T
T ! int ⇤ T |int|(E )
Produzione aggiunta S 0 ! .E
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
48 of 55
Esempio
E→T+.E
Automa DFA
E → .T
T
E
T → .int * T
E → T. + E
T
T → int. * T
S’ → . E
int
E→.T
*
T → .(E)
T → int * .T
T → .int * T
T → .(E)
T → .int
T → .int * T
T → .int
(
T → .int
int
T
int
T → int.
int
E → .T + E
E → T + E.
T → .(E)
+
E → T.
S’ → E .
E
E → .T + E
T → int * T.
T
T → (. E)
(
E → .T
E → .T + E
E
T → .int * T
T → .int
T → (E.)
T → (E).
T → .(E)
)
(
63
(
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
49 of 55
Nota
Ogni stato corrisponde ad un simbolo della
grammatica: quello delle transizioni che
portano a lui
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
50 of 55
Per riconoscere i prefissi ammissibili
Dobbiamo:
riconoscere una sequenza di parti destre
parziali, dove
ogni sequenza pu`o eventualmente essere
ridotta (reduce) a parte del suffisso
mancante del suo predecessore
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
51 of 55
Come usare l’automa nel parsing shift-reduce?
Inseriamo gli stati raggiunti in una pila (ultimo stato in
cima)
Supponiamo che la stringa di simboli della grammatica
porti l’automa dallo stato iniziale ad uno stato j
Allora:
Shift sul prossimo simbolo in input a se c’`e una
transizione da j etichettata a, e aggiungo prossimo
stato sulla pila
Altrimenti, riduciamo:
Gli item nello stato j ci diranno quale produzione
usare: A ! ↵
Eliminiamo tanti stati dalla pila quanti sono i
simboli di ↵
Seguiamo una transizione etichettata A
Inseriamo il nuovo stato sulla pila
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
52 of 55
Perch´e l’automa LR(0) `e utile ? Item validi!
L’item X ! . `e valido per un prefisso ammissibile ↵ se
⇤
S 0 ) ↵X ! ) ↵
rm
rm
!
Gli item validi per ↵ aiutano a decidere quale azione
intraprendere se sulla cima della pila compare ↵ :
se 6= ✏ significa che non abbiamo ancora una
maniglia sulla cima della pila e quindi dobbiamo
e↵ettuare uno shift
se = ✏ significa che sulla cima abbiamo una
maniglia e possiamo ridurre utilizzando la produzione
X !
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
53 of 55
Item validi
Un item pu`o essere valido per prefissi ammissibili diversi
Ad esempio: l’item T ! (.E ) `e valido per i prefissi
(
((
(((
((((
...
Esiste un teorema che a↵erma
l’insieme di item validi per un prefisso ammissibile `e
esattamente l’insieme di item raggiungibili dall’automa
LR(0) della grammatica a partire dallo stato iniziale lungo
un percorso etichettato con
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
54 of 55
Verificare per prefisso (((
E→T+.E
Automa DFA
E → .T
T
E
T → .int * T
E → T. + E
T
T → int. * T
S’ → . E
int
E→.T
*
T → .(E)
T → int * .T
T → .int * T
T → .(E)
T → .int
T → .int * T
T → .int
(
T → .int
int
T
int
T → int.
int
E → .T + E
E → T + E.
T → .(E)
+
E → T.
S’ → E .
E
E → .T + E
T → int * T.
T
T → (. E)
(
E → .T
E → .T + E
E
T → .int * T
T → .int
T → (E.)
T → (E).
T → .(E)
)
(
63
(
Automi e Linguaggi Formali – A.A 2014-2015
Docente: Alessandro Sperduti
55 of 55

Download Report