Parser SLR
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.
Esempio
modificaLa 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 follow 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 |
Algoritmo
modifica1 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
Collegamenti esterni
modifica- Parsing Simulator Questo simulatore è concepito per aiutare lo studente a comprendere in tutta semplicità i vari passaggi per la costruzione delle tabelle di Parsing SLR. Utile per chi vuole esercitarsi sull'argomento