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

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

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

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 SLR. Utile per chi vuole esercitarsi sull'argomento