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

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

La Tabella di Action e Goto[modifica | modifica sorgente]

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

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
      • chiamiamo S lo stato successivo sulla cima della pila, e NT il carattere non terminale che si trova nel lato sinistro della regola numero m; chiamiamo 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 inseriamo lo stato S_1 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 trova nel seguente modo:

[0 '1' 2]

La testa della pila è la parte più a destra (per comodità mostreremo 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 la action table dice 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 saranno [5, 3, 5, 2] che è effettivamente un derivazione destrorsa della stringa "1+1" al rovescio.

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

Items[modifica | modifica sorgente]

La costruzione di queste tabelle di parsing si basa sulla notazione di LR(0) items 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[modifica | modifica sorgente]

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 }.

Closure of item sets[modifica | modifica sorgente]

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 AvBw in un set di item e nella grammatica c'è una regola nella forma Bw' 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.

La grammatica aumentata[modifica | modifica sorgente]

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.

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.

Trovare i set di item raggiungibili e le transizioni tra loro[modifica | modifica sorgente]

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

Partendo dallo stato iniziale (S0) determineremo 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

  1. Prendi il set 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

Costruzione della tabella di action e di goto[modifica | modifica sorgente]

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. Una colonna extra per il simbolo $ (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 Aw • e Aw è 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.

Versioni più potenti del parsing LR[modifica | modifica sorgente]

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).

Conflitti nelle tabelle costruite[modifica | modifica sorgente]

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 cella della action table per questo set 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 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 Aw 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)[modifica | modifica sorgente]

   E->E+T/T
   T->T*F/F
   F->id
   S->AA
   A->aA/b

Voci correlate[modifica | modifica sorgente]

Bibliografia[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

  • 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