Parser SLR
Da Wikipedia, l'enciclopedia libera.
In informatica, un Parser SLR è un parser LR che riconosce tabelle di parsing generate come per un parser LR(0), ma che effettua una riduzione con la regola grammaticale A → w solo se il simbolo successivo in input è nel follow set. Questo parser può evitare alcuni conflitti di tipo shift-reduce e reduce-reduce e può quindi funzionare con un numero maggiore di grammatiche. Non è tuttavia in grado di analizzare tutte le grammatiche libere dal contesto, come può invece fare un parser LR(1). Una grammatica correttamente riconosciuta da un parser SLR viene detta grammatica SLR.
[modifica] Esempio
La seguente grammatica può esser riconosciuta da un parser SLR ma non da un parser LR(0)::
- (1) E → 1 E
- (2) E → 1
Costruire la action table e la goto table come per un parser LR(0) darebbe il seguente insieme di item e tabelle:
- Item set 0
- S → • E
- + E → • 1 E
- + E → • 1
- Item set 1
- E → 1 • E
- E → 1 •
- + E → • 1 E
- + E → • 1
- Item set 2
- S → E •
- Item set 3
- E → 1 E •
Le tabelle di action e goto:
| action | goto | ||
| state | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1/r2 | r2 | 3 |
| 2 | acc | ||
| 3 | r1 | r1 | |
Come si può notare c'è un conflitto di tipo shift-reduce per lo stato 1 e il terminale '1'. Tuttavia, l'insieme dei follo di E è { $ } così le azioni di reduce r1 e r2 sono valide solamente per la colonna $. Il risultato è la seguente tabella priva di conflitti:
| action | goto | ||
| state | 1 | $ | E |
| 0 | s1 | 2 | |
| 1 | s1 | r2 | 3 |
| 2 | acc | ||
| 3 | r1 | ||
[modifica] Algoritmo
1 Inizializzare la pila con S
2 Leggere il simbolo in input
3 While (true), do:
3.1 if Action(top(stack), input) = S
NS <- Goto(top(stack),input)
push NS
Leggi il prossimo simbolo
3.2 else if Action(top(stack), input) = Rk
output k
fai il pop |RHS| della produzione k dalla pila
NS <- Goto(top(stack), LHS_k)
push NS
3.3 else if Action(top(stack),input) = A
output corretto, return
else
output non valido, return
