LR Parser
II Parte
Giuseppe Morelli
Parser LR(1)
• Con il metodo SLR la tabella indica di effettuare
una riduzione attraverso una produzione A-> α,
se accade che per un certo item Ii :
– [A->α. Є Ii]
– Per ogni a Є FOLLOW(A)
• In certi casi può succedere che se βα è il
contenuto dello stack, βAα non può essere
prefisso di una forma sentenziale destra e pur
essendo a Є FOLLOW(A) la riduzione A-> α non
si può applicare
In I2 esiste un
conflitto ShiftReduce
Ovvero non esiste
una forma
sentenziale
destra che
inizia per R
• E’ possibile mantenere informazioni riguardanti i
caratteri che possono essere presenti dopo una
variabile in un dato contesto.
• Data una produzione A->α, l’idea è di includere
negli items di uno stato i simboli terminali che
possono seguire un handle α per cui è possibile
una riduzione ad A.
• La forma generale di un item, LR(1) diventa
[A->α.β,a ]
• Il significato di “a” in [A->α.,a ] è: viene
applicata la riduzione A-> α solo se il simbolo di
lookahead è a.
Insieme di item LR(1)
• Il metodo è essenzialmente lo stesso usato per
la costruzione della collezione canonica LR(0)
• Ovvero:
• Si costruisce la grammatica aumentata G’
• Si definiscono e applicano le operazioni di
– CHIUSURA
– GOTO
• La discriminante è proprio la definizione delle
due procedure.
Es.
Costruzione della tabella LR(1)
• Data G si costruisce la grammatica aumentata
G’ quindi:
– Si costruisce la collezione di insiemi di Items LR(1) C’
= {I0, I1, …. ,In} per G’
– Lo stato i è costruito da Ii. L’azione per lo stato i è
determinata come segue:
• Se [A-> α.aβ,b] è in Ii e GOTO(Ii,a) = Ij allora
ACTION[i,a] = “shift j” . a deve essere un terminale
• Se [A-> α., a] è in Ii (A<>S’ ) allora ACTION[i,a] = “reduce
A-> α.”
• Se [S’ -> S.,$] è in Ii allora ACTION[i, $] = “accept”
– GOTO deve essere costruita per tutti i non terminali
Secondo la regola se GOTO(Ii,A)=Ij allora GOTO(i,A)
=j
– Errore se vi sono entry non definite da 2 e 3
– Lo stato iniziale è quello ottenuto dall’insieme di Item
contenente [S’->.S, $]
Parser LALR
• È caratterizzato dal fatto che la tabella di
parsing ottenuta per una data grammatica è
considerabilmente più piccola della
corrispondente LR.
• L’idea di base di questo metodo è quella di
costruire la tabella di parsing a partire dagli
insieme di items LR(1) ed apportando delle
semplificazioni.
• L’algoritmo si costruzione si rifà ad alcune
definizioni e strategie già viste (kernel items,
closure etc..)
• In generale la tecnica prevede di fare il merge
in un unico insieme gli insiemi di item LR(1) che
hanno lo stesso core(primo item dell’insieme).
• L’unione si ripercuote anche sugli insiemi
GOTO(I,X) degli item I coinvolti nella “fusione”;
poiché GOTO(I,X) dipende dal core di I si può
fare il merge anche delle funzioni GOTO degli
stati merged.
• Poiché in una grammatica LR(1) non sono
presenti errori di parsing si può dimostrare che
anche nell’insieme di stati ottenuti attraverso
fusione non sono presenti errori
Tabella di parsing LALR
• Data G si costruisce la grammatica aumentata
G’ quindi:
– Si costruisce la collezione di insiemi di Items LR(1) C
= {I0, I1, …. ,In} per G’
– Trovare per ogni core di item in C, gli item con lo
stesso core e rimpiazzarli con la loro unione.
– Sia C’ = = {J0, J1, …. ,Jn} l’insieme di items
risultante. La funzione ACTIONE delle tabelle di
parsing dello stato i è costruita attraverso Ji come
fatto per la tabella LR(1).
– La funzione GOTO deve essere costruita
considerando che se J = I1 U I2 U … U Im allora i
cores di di GOTO(Ii,X) sono gli stessi dei
corrispondenti Ii (i=1...m); sia K l’unione di
GOTO(Ii,X) aventi lo stesso core allora GOTO(J,X)=K
QuickTime™ and a
decompressor
are needed to see this picture.
• La tabella derivante dall’algoritmo prima visto è
chiamata LALR parsing table e se non esistono
confilitti nella fase di parsing la grammatica
restitutia è detta LALR
• L’insieme di Item derivanti dalla fusione e dalla
nuova definzione della funzione GOTO è detto
LALR.
• La costruzione della tabella di parsing LALR
implica la costruzione dell’intera collezione
LR(1) che può richiedere troppo spazio e tempo
per essere utilizzata nella pratica.
• Servono degli espedienti per migliorare allora il
processo di costruzione
Costruzione efficiente
• Anziché considerare tutti gli insieme di Item si
considerano quelli kernel ([S’->.S,$] e con il .
non all’inizio del corpo della produzione); si
potrebbero considerare anche gli item LR(0)
senza cioè il carattere di lookahead.
• Si costruiscono gli item LALR(1) kernel
attraverso un processo di propagazione e
generazione spontanea di caratteri di lookahead
(see later)
• Da LALR(1) kernel si genera la tabella di parsing
applicando l’operazione di chiusura (CLOUSURE)
e applicando l’algoritmo adottato per la
costruzione della tabella LR(1) (def. ACTION e
GOTO)
Determinazione dei caratteri lookahead