Parser LR

Nell'informatica, un parser LR è un parser di tipo Bottom-up per grammatiche libere da contesto, usate molto di frequente nei compilatori dei linguaggi di programmazione (e degli altri strumenti associati). Un Parser LR legge il proprio input partendo da sinistra (Left) verso destra, producendo una derivazione destra (Rightmost Derivation). A volte questo parser viene anche indicato col nome "Parser LR(k) dove k si riferisce al numero di simboli letti (ma non "consumati") utilizzati per prendere le decisioni di parsing. Tipicamente k ha valore 1 ed è spesso omesso. Una grammatica libera da contesto è chiamata LR(k) se esiste un parser LR(k) adatto ad essa.

Nell'uso tipico, quando ci si riferisce a un parser LR significa che si sta parlando di un particolare parser in grado di riconoscere un linguaggio specifico in una grammatica libera da contesto. Non è tuttavia insolito che ci si riferisca a un parser LR intendendo un programma che, fornita una tabella "ad hoc", sia in grado di produrre un ampio numero di LR distinti.

Il parsing LR ha parecchi benefici:

• Parecchi linguaggi di programmazione possono essere parsificati usando varianti del parser LR. Notevoli eccezioni sono C++ e Perl.
• Il parser LR può esser implementato in modo estremamente efficiente.
• Tra tutti i tipi di parser che scandiscono il loro input da sinistra verso destra, il parser LR è quello in grado di identificare gli errori sintattici (ovvero quando l'input non è conforme alla grammatica) più rapidamente.

Creare un parser LR a mano è parecchio difficile; solitamente essi sono creati usando dei generatori di parser. In base a come la tabella di parsing viene generata, questi parser possono essere anche parser SLR o LALR. Con questi tipi di parser si ha a che fare con un'ampia varietà di grammatiche aumentate; il parser LALR ad esempio è in grado di riconoscere un numero maggiore di grammatiche rispetto ad un SLR. Il famoso Yacc produce parser di tipo LALR.

Architettura di un parser LR

Il parser è composto da:

• Un input buffer, che permette di leggere il prossimo simbolo dallo standard input;
• Una pila, che permette di memorizzare quali simboli sono stati letti;
• Una tabella, suddivisa in Action Table (che permette di determinare quale azione bisogna intraprendere) e GoTo Table (che determina in quale nuovo stato spostarsi o quale regola della grammatica adottare);

Cercando di spiegare il funzionamento con un esempio; si consideri la seguente grammatica:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

La Tabella di Action e Goto

Le due tabelle di parsing LR(0) per questa grammatica sono:

	action						goto
state	*	+	0	1	$		E	B
0			s1	s2			3	4
1	r4	r4	r4	r4	r4
2	r5	r5	r5	r5	r5
3	s5	s6			acc
4	r3	r3	r3	r3	r3
5			s1	s2				7
6			s1	s2				8
7	r1	r1	r1	r1	r1
8	r2	r2	r2	r2	r2

Nell'Action Table i contenuti delle celle sono determinati dallo stato del parser e di un simbolo terminale (incluso il simbolo terminale speciale $ che indica la fine dell'input) e può contenere tre tipi di azioni:

• shift, scritto in forma 'sn' indica che bisogna spostare un simbolo e che il prossimo stato è n
• reduce, scritto in forma 'rm' indica che si deve effettuare una riduzione applicando la regola m
• accept, scritto in forma 'acc' e indica che tutti i simboli sono stati letti e la stringa è conforme alla grammatica definita

Nella GoTo Table invece i valori delle celle sono determinati dallo stato del parser e dai simboli non-terminali; il contenuto determina quale sarà il prossimo stato del parser se è stato riconosciuto un non-terminale.

L'Algoritmo di Parsing

L'Algoritmo di Parsing LR lavora nel seguente modo:

1. Il contenuto della pila viene posto a [0]. Lo stato corrente dovrà essere sempre lo stato in cima alla pila.
2. Dato lo stato corrente e il terminale corrente nell'input stream si esegue l'azione presente nell'action table. Vi sono quattro possibili casi:
   • uno shift sn:
     • il terminale corrente viene rimosso dall'input stream
     • lo stato n viene inserito nella pila e diviene lo stato corrente,
   • una riduzione rm:
     • il numero m viene scritto nell'output stream,
     • per ogni simbolo a destra della regola m uno stato viene rimosso dalla pila e
     • definito con $S$ lo stato successivo sulla cima della pila, e NT il carattere non terminale che si trova nel lato sinistro della regola numero m; si chiami poi $S_{1}$ lo stato che si trova nella goto table in corrispondenza dello stato $S$ (indice di riga) e del non-terminale NT (indice di colonna). A questo punto si inserisce lo stato $S_{1}$ in cima alla pila.
   • un accept: la stringa è accettata
   • nessun'azione: viene segnalato un errore di sintassi
3. Il passo precedente viene ripetuto finché la stringa non viene accettata o un errore di sintassi viene segnalato

Si può esprimere meglio l'algoritmo con una stringa d'esempio: 1 + 1. La tabella sottostante illustra ogni passo effettuato dal processo, lo stato di riferimento è l'elemento in cima alla pila (ovvero quello più a destra) e l'azione da intraprendere sarà quella determinata dall'action table definita prima. Notare inoltre che il simbolo $ è inserito in fondo alla stringa per segnalare la fine dell'input.

State	Input Stream	Output Stream	Stack	Next Action
0	1+1$		[0]	Shift 2
2	+1$		[0,2]	Reduce 5
4	+1$	5	[0,4]	Reduce 3
3	+1$	5,3	[0,3]	Shift 6
6	1$	5,3	[0,3,6]	Shift 2
2	$	5,3	[0,3,6,2]	Reduce 5
8	$	5,3,5	[0,3,6,8]	Reduce 2
3	$	5,3,5,2	[0 3]	Accept

Quando il parsing inizia esso si troverà allo stato iniziale 0 e con la seguente pila:

[0]

Il primo terminale che il parser riconosce è '1' e in accordo all'action table si può andare nello stato 2 con la Pila che si trova nel seguente modo:

[0 '1' 2]

La testa della pila è la parte più a destra (per comodità si mostra anche il simbolo, terminale o non terminale, per esempio '1' o B, che ha "causato" la transizione allo stato successivo, anche se tale simbolo non appartiene realmente alla pila).

Nello stato 2 l'action table dice che per qualunque terminale si trovi nell'input dovremmo effettuare una riduzione con la regola grammaticale 5. Se la tabella è stata creata correttamente questo significa che il parser ha riconosciuto correttamente il lato destro della regola 5, che è appunto il nostro caso. Si può scrivere così scrivere '5' nello stream in output, fare il 'pop' dello stato sulla pila e poi un 'push' sulla pila dello stato indicato dalla goto table con 0 e B, ovvero 4. La pila risultante sarà:

[0 B 4]

Tuttavia lo stato 4 dell'action table indica che dovremmo fare una riduzione con la regola n° 3. Si scrive quindi 3 nell'output stream, si fa un'ulteriore 'pop' sulla pila e si trova il nuovo stato nella goto table, indicato da 0 e E, ovvero 3. Di conseguenza:

[0 E 3]

Il terminale successivo che il parser riconosce è il '+' e seguendo l'action table, si dovrà andare allo stato 6:

[0 E 3 '+' 6]

Si può notare come la pila sino a qui costruita può essere vista come la storia di un Automa a stati finiti che ha appena letto un non-terminale E seguito da un terminale '+'. La tabella di transizione di questa automazione è definita dalle azioni di 'shift' dell'action table e le azioni si spostamento nella gogo table.

Il terminale successivo è ora '1' e significa che deve esser effettuato uno "shift and go" allo stato 2:

[0 E 3 '+' 6 '1' 2]

Come appena fatto il simbolo '1' viene ridotto a B con pila formata nel seguente modo:

[0 E 3 '+' 6 B 8]

Si può notare ancora come la pila ora corrisponda a una lista di stati di un automa a stati finiti che ha letto un non-terminale E, seguito poi da un '+' e un non-terminale B. Nello stato 8 si effettuerà sempre una riduzione con la regola 2. Notare che ora i 3 stati della pila corrispondono ai 3 simboli nel lato destro della regola 2.

[0 E 3]

Finalmente si trova in lettura il simbolo '$' che, seguendo le regole dell'action table (il cui stato corrente è il 3º), il parser accetta la stringa in input. I numeri delle regole che sono stati scritti negli output stream saranno [5, 3, 5, 2] che è effettivamente un derivazione destrorsa della stringa "1+1" al rovescio.

Costruzione di una tabella di parsing LR(0)

Item

La costruzione di queste tabelle di parsing si basa sulla notazione di LR(0) item che sono regole grammaticali con un punto speciale aggiunto in posizioni precise nel lato destro. Per esempio, la regola E → E + B ha i quattro seguenti oggetti corrispondenti:

E → • E + B

E → E • + B

E → E + • B

E → E + B •

Le regole nella forma A → ε hanno un singolo item A → •. Queste regole saranno usate per denotare lo stato del parser. L'item E → E • + B, ad esempio, indica che il parser ha riconosciuto una stringa corrispondente ad E nell'input stream e ora si aspetta di leggere un '+' seguito da un'altra stringa, corrispondente a B.

Item sets

Solitamente non è possibile caratterizzare lo stato del parser con un singolo item in quanto non si può sapere in anticipo quali regole verranno usate per la riduzione. Per esempio, se è già presente una regola nella forma E → E * B, allora gli item E → E • + B e E → E • * B verranno entrambi applicati dopo che la stringa corrispondente ad E è stata letta. Di conseguenza si dovranno caratterizzare gli stati del parser tramite un set di item, nel nostro caso il set sarà formato da { E → E • + B, E → E • * B }.

Closure of item sets

Un item con un punto davanti a un non-terminale, come ad esempio E → E + • B, indica che il parser si aspetta poi di ricevere un non-terminale B. Per assicurarsi che l'insieme di oggetti contenga tutte le possibili regole nelle quali il parser potrebbe trovarsi durante l'esecuzione del suo lavoro, deve includere tutti i termini che descrivano come B stesso debba essere parsato. Questo significa che se c'è una regola come B → 1 e B → 0 allora il set di item dovrà anche includere gli item B → • 1 and B → • 0. In generale questo può essere formulato come segue:

Se c'è un item nella forma A → v•Bw in un set di item e nella grammatica c'è una regola nella forma B → w' allora l'item B → • w' dovrà essere anch'esso nel set di item.

Ogni set di item può essere esteso in modo che soddisfi la seguente regola: Continua semplicemente ad aggiungere gli item appropriati sino a quanto tutti i non-terminali preceduti da punti sono stati presi in considerazione. L'estensione minima viene chiamata closure di un set di item ed è scritta clos(I) dove I è un set di item. È questo set di closed item che verranno presi come stati del parser, anche se soltanto quelli che sono realmente raggiungibili dallo stato iniziale saranno inclusi nella tabella.

La grammatica aumentata

Prima di cominciare a determinare le transizioni tra gli stati differenti, la grammatica viene sempre aumentata con la seguente regola extra:

(0) S → E

dove S è un nuovo simbolo di partenza e E quello vecchio. Il parser userà questa regola per ridurre esattamente quando ha accettato la stringa in input.

Si prenda come esempio la grammatica vista prima:

(0) S → E

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

È tramite questa grammatica aumentata che si determineranno il set di item e le transizioni tra loro.

Trovare i set di item raggiungibili e le transizioni tra loro

Il primo passo nella costruzione delle tabelle consiste nel determinare le transizioni tra i set di item closed.. Queste transizioni saranno determinate come se noi stessimo considerando un automa a stati finiti che può leggere sia terminali che non-terminali. L'inizio dello stato di questo automa è sempre la closure del primo item della regola aggiunta, ovvero S → • E:

Item set 0

S → • E

+ E → • E * B

+ E → • E + B

+ E → • B

+ B → • 0

+ B → • 1

Il '+' in testa all'item indica che gli item che sono stati aggiunti alla closure. Gli item originali senza un '+' davanti, vengono chiamati kernel del set di item.

Partendo dallo stato iniziale (S0) si determinano ora tutti gli stati che possono essere raggiunti da questo stato. Le possibili transizioni per un set di item possono essere trovate guardando i simboli (sia terminali che non) presenti a destra del punto; nel caso di set di item 0 questi sono terminali '0' e '1' e non-terminali E e B. Per trovare il set di item a cui conduce un simbolo 'x' dallo stato corrente si segue questa procedura:

1. Prendi il set S di tutti gli item nel corrente set dove c'è un punto davanti a un qualche simbolo x.
2. Per ogni item in S, si muove il punto alla destra di x.
3. Si chiude il risultante set di item.

Per il terminale '0' questo risulta in:

Item set 1

B → 0 •

e per il terminale '1' in:

Item set 2

B → 1 •

e per il non-terminale E in:

Item set 3

S → E •

E → E • * B

E → E • + B

e per il non-terminale B in:

Item set 4

E → B •

Notare che in tutti la closure non aggiunge nessun nuovo item. Si continua così il processo finché nessun nuovo item nel set viene trovato. Per il set di item 1, 2 e 4 non ci sarà nessuna transizione finché il punto non sarà davanti a nessun simbolo. Per il set di item 3 si noti che il punto è davanti ai terminali '*' e '+'. Per '*' la transizione va in:

Item set 5

E → E * • B

+ B → • 0

+ B → • 1

e per '+' la transizione va in:

Item set 6

E → E + • B

+ B → • 0

+ B → • 1

Per gli item del set 5 si devono considerare i terminali '0' e '1' e il non-terminale B. Per i terminali si nota che la risultante closure del set di item sono uguali a quelli già trovati prima: rispettivamente il set 1 e 2. Per il non-terminale B invece la transizione sarà:

Item set 7

E → E * B •

Per il set di item 6 bisogna inoltre considerare il terminale '0' e '1' e il non-terminale B. Come prima, il set di item risultante è eguale al set 1 e 2. Per il non-terminale B la transizione va in:

Item set 8

E → E + B •

Si è arrivati all'ultimo set di item che non ha più alcun simbolo dopo il punto e di conseguenza nessun nuovo item viene aggiunto e il lavoro è concluso. La tabella di transizione per l'automa ora sarà la seguente:

Item Set	*	+	0	1	E	B
0			1	2	3	4
1
2
3	5	6
4
5			1	2		7
6			1	2		8
7
8

Costruzione della tabella di action e di goto

Da questa tabella e dal set di item appena ricavato, si possono costruire le tabelle nel modo seguente:

1. Le colonne dei non-terminali sono copiate nella goto table
2. Le colonne dei terminali sono copiate nell'action table come le azioni di shift
3. Una colonna extra per il simbolo $ (fine dell'input) è aggiunta nell'action table che contiene acc per ogni set di item che contengono S → E •.
4. Se un set di item i contiene un item nella forma A → w • e A → w è la regola m con m > 0 allora la riga per lo stato i nell'action table viene riempita completamente con l'azione indicante la riduzione rm.

Versioni più potenti del parsing LR

Notare che solo lo step 4 delle procedure descritte sopra produce un'azione di riduzione, e quindi tutte le azioni di riduzione devono occupare un'intera riga della tabella. Questo perché un parser LR(0) non guarda al token successivo per decidere quale riduzione bisogna effettuare. Una grammatica che necessita di guardare oltre per risolvere le disambiguità sulle riduzioni richiede che la tabella indichi diverse azioni a seconda dei token successivi in input.

Miglioramenti della procedura per la costruzione di una tabella LR(0) (come ad esempio i parser SLR e LALR) sono in grado di creare le azioni di riduzione che non occupino l'intera riga. Di conseguenza riescono ad effettuare il parsing di più grammatiche rispetto ai parser LR(0).

Conflitti nelle tabelle costruite

Può succedere tuttavia che, quando un'azione di riduzione viene aggiunta all'action table, la cella relativa sia già occupata da un'azione. Quando questo accade, significa semplicemente che non si tratta di una grammatica LR(0). Se il contenuto precedente della cella è uno shift si parla di conflitto shift-reduce; se è una differente azioni di riduzione si parla di conflitto reduce-reduce.

Un esempio di una grammatica non LR(0) con conflitto shift-reduce è:

(1) E → 1 E

(2) E → 1

Un set di item che si trova è:

Item set 1

E → 1 • E

E → 1 •

+ E → • 1 E

+ E → • 1

C'è un conflitto shift-reduce in questo set di item perché nella cella dell'action table per questo set di item e il terminale '1' c'è sia un'azione di shift allo stato 1 sia un'azione di riduzione con regola 2.

Un altro esempio di grammatica non-LR(0) con conflitto reduce-reduce è:

(1) E → A 1

(2) E → B 2

(3) A → 1

(4) B → 1

In questo caso si ottiene il seguente set di item

Item set 1

A → 1 •

B → 1 •

C'è un conflitto di tipo reduce-reduce in questo set di item poiché le celle dell'action table per questo set di item saranno sia per la regola 3 che per la regola 4.

Entrambi gli esempi sopra possono essere risolti lasciando usare al parser il seguente set (vedi LL parser) di un non-terminale A per decidere se è il caso di usare una regola di A per una riduzione; verrà usata la regola A → w per una riduzione se il simbolo successivo nell'input stream è nel set seguente di A. Questa soluzione è detta Simple LR parser.

Alcuni esempi con LR(0)

   E->E+T/T
   T->T*F/F
   F->id

   S->AA
   A->aA/b

Bibliografia

• Compilers: Principles, Techniques, and Tools, Aho, Sethi, Ullman, Addison-Wesley, 1986. ISBN 0-201-10088-6
• Internals of an LALR(1) parser generated by GNU Bison, su cs.uic.edu. URL consultato il 22 dicembre 2006 (archiviato dall'url originale il 26 novembre 2006).

Voci correlate

• Grammatica formale
• Grammatica libera dal contesto
• Linguaggio formale
• Parser SLR

Collegamenti esterni

• Parsing Simulator Questo simulatore è concepito per aiutare lo studente a comprendere in tutta semplicità i vari passaggi per la costruzione delle tabelle di Parsing LR. Utile per chi vuole esercitarsi sull'argomento