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: Il contenuto della pila viene posto a . Lo stato corrente dovrà essere sempre lo stato in cima alla pila. 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 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 lo stato che si trova nella goto table in corrispondenza dello stato (indice di riga) e del non-terminale NT (indice di colonna). A questo punto si inserisce lo stato in cima alla pila. un accept: la stringa è accettata nessun'azione: viene segnalato un errore di sintassi 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.
StateInput StreamOutput StreamStackNext Action 0 1+1$ 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:
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.