Parser LR

Da Wikipedia, l'enciclopedia libera.

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 riferiamo a un parser LR significa che stiamo parlando di un particolare parser in grado di riconoscere un linguaggio specifico in una grammatica libera da contesto. Non è tuttavia insolito che ci riferisca a un parser LR intendendo un programma che, fornendogli 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 parserizzati usando varianti del parser LR. Notevoli eccezioni sono C++ e Perl.
• Il parser LR puo' esser implementato in modo estremamente efficiente.
• Di tutti i parser che scandiscono il loro input da sinistra verso destra, il parser LR è in grado di identificare gli errori sintattici (ovvero quando l'input non è conforme alla grammatica) 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 una ampia varietà di grammatiche aumentate; il parser LALR ad esempio è in grado di riconoscere un numero maggiore di grammatiche rispetto un SLR. Il famoso Yacc produce parser di tipo LALR.

Indice 1 Architettura di un parser LR 1.1 La Tabella di Action e Goto 1.2 L' Algoritmo di Parsing 2 Intestazione 2.1 Costruzione di una tabella di parsing LR(0) 2.1.1 Items 2.1.2 Item sets 2.1.3 Closure of item sets 2.1.4 La grammatica aumentata 2.1.5 Trovare i set di item raggiungibili e le transizioni tra loro 2.1.6 Costruzione della tabella di action e di goto 2.1.6.1 Versioni più potenti del parsing LR 2.1.7 Conflitti nelle tabelle costruite 3 Alcuni esempi con LR(0) 4 Bibliografia

[modifica] 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);

Cerchiamo di spiegare il funzionamento con un esempio; consideriamo la seguente grammatica:

(1) E → E * B

(2) E → E + B

(3) E → B

(4) B → 0

(5) B → 1

[modifica] 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

Nella 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 di m passi
• 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.

[modifica] 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 nella 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
     • dato lo stato successivo sulla cima della pila e la regola sinistra di m un nuovo stato viene visitato nella goto table e inserito un nuovo stato corrente in cima alla pila.
   • un accept: la stringa è accettata
   • nessuna 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

Cerchiamo di 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 dalla 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 alla action table si può andare nello stato 2 con la Pila che si trovare nel seguente modo:

[0 '1' 2]

La testa della pila è la parte più a destra. (or the sake of our explanation we also show the symbol (e.g., '1', B) that caused the transition to the next state although strictly speaking it is not part of the stack.)

Nello stato 2 la action table diche che per qualunque terminale troviamo 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. Possiamo 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 della action table indica che dovremmo fare una riduzione con la regola n° 3. Scriviamo quindi 3 nell'ouput stream, facciamo un'ulteriore 'pop' sulla pila e troviamo 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 la action table, si dovrà andare allo stato 6:

[0 E 3 '+' 6]

Possiamo 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à della 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]

Possiamo 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 effettueremo 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 troviamo in lettura il simbolo '$' che, seguendo le regole della 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 sranno [5, 3, 5, 2] che è effettivamente un derivazione destrorsa della stringa "1+1" al rovescio.

[modifica] Intestazione

[modifica] Costruzione di una tabella di parsing LR(0)

[modifica] Items

La costruzione di queste tabelle di parsing si basa sulla notazione di LR(0) items che sono regole grammaticale con un punto speciale aggiunto in punti precisi 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.

[modifica] Item sets

Solitamente non è possibile caratterizzare lo stato del parser con un singolo item in quanto non possiamo 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 dovremo caratterizzare gli stati del parser tramite un set di items, nel nostro caso il set sarà formato da { E → E • + B, E → E • * B }.

[modifica] 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 items 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 items può essere esteso in modo che soddisfi la seguente regola: Continua semplicemente ad aggiungere gli items appropriati sino a quanto tutti i non-terminali preceduti da punti sono stati aggregati 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.

[modifica] La grammatica aumentata

Prima di cominiciare 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.

Prendiamo 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 determineremo il set di items e le transizioni tra loro.

[modifica] 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 è sammpre 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 items che sono stati aggiunti alla closure. Gli items originali senza un '+' davatni, vengono chiamati kernel del set di item.

Partendo dallo stato iniziale (S0) determineremo ora tutti gli stati che possono essere raggiunti da questo stato. La possibile transizione per un set di item può essere trovata 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 TO BE CORRECTED

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

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. Continuiamo 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 vediamo 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 dobbiamo considerare i terminali '0' e '1' e il non-terminale B. Per i terminali notiamo 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 •

Siamo 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

[modifica] Costruzione della tabella di action e di goto

Da questa tabella e dal set di items appena ricavato, possiamo costruire le tabelle nel modo seguente:

1. Le colonne dei non-terminali sono copiate nella goto table
2. Le colonne dei terminali sono copiate nella action table come le azioni di shift
3. Un colonna extra per il dimbolo $ (fine dell'input) è aggiunta nella 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 nella action table viene riempita completamente con la azione indicante la riduzione rm.

[modifica] Versioni più potenti del parsing LR

Notare che solo lo step 4 delle procedure descritte sopra produce una azione di riduzione, e quindi tutte le azioni di riduzione devono occupare una 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).

[modifica] Conflitti nelle tabelle costruite

Può succedere tuttavia che, quando una azione di riduzione viene aggiunta alla action table, la cella relativa sia già occupata da una 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 items che troviamo è:

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 nella cella della action table per questo det di item e il terminale '1' c'è sia una azione di shift allo stato 1 che una 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 otteniamo 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 della action table x 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.

[modifica] Alcuni esempi con LR(0)

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

   S->AA
   A->aA/b

[modifica] Bibliografia

• 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