Ho il seguente grammatica, che mi hanno detto è LR (1), ma non SLR (1):Com'è questa grammatica LR (1) ma non SLR (1)?
S :: = a A | b A c | d c | b d un
A :: = d
Non capisco perché questo è. Come lo dimostreresti?
Un modo per capirlo sarebbe cercare di costruire parser LR (1) e SLR (1) per la grammatica. Se nel corso del processo riscontriamo un cambiamento/riduzione o riduzione/riduzione dei conflitti, possiamo dimostrare che la grammatica non deve appartenere a una di queste classi di lingue.
Iniziamo con il parser SLR (1). Per prima cosa, dobbiamo calcolare i set di configurazione LR (0) per la grammatica. Questi sono visti qui:
(1)
S -> .aA
S -> .bAc
S -> .dc
S -> .bda
(2)
S -> a.A
A -> .d
(3)
S -> aA.
(4)
A -> d.
(5)
S -> b.Ac
S -> b.da
A -> .d
(6)
S -> bA.c
(7)
S -> bAc.
(8)
S -> bd.a
A -> d.
(9)
S -> bda.
(10)
S -> d.c
(11)
S -> dc.
Quindi, abbiamo bisogno di ottenere i set seguire per tutti i simboli non terminali. Questo è mostrato qui:
FOLLOW(S) = { $ }
FOLLOW(A) = { $, c }
Detto questo, si può tornare indietro e aggiornare i LR set (0) configurando in SLR (1) set configurando:
(1)
S -> .aA [ $ ]
S -> .bAc [ $ ]
S -> .dc [ $ ]
S -> .bda [ $ ]
(2)
S -> a.A [ $ ]
A -> .d [ $, c ]
(3)
S -> aA. [ $ ]
(4)
A -> d. [ $, c ]
(5)
S -> b.Ac [ $ ]
S -> b.da [ $ ]
A -> .d [ $, c ]
(6)
S -> bA.c [ $ ]
(7)
S -> bAc. [ $ ]
(8)
S -> bd.a [ $ ]
A -> d. [ $, c ]
(9)
S -> bda. [ $ ]
(10)
S -> d.c [ $ ]
(11)
S -> dc. [ $ ]
È interessante notare che non vi siano conflitti Qui! L'unico possibile spostamento/riduzione del conflitto è in stato (8), ma non vi è alcun conflitto qui perché l'azione di spostamento è su a e la riduzione è su $. Di conseguenza, questa grammatica in realtà è SLR (1). Poiché qualsiasi grammatica SLR (1) è anche LR (1), ciò significa che la grammatica è sia SLR (1) che LR (1).
Spero che questo aiuti!
Basta notare che ogni grammatica SLR (1) è grammatica LR (1) ma non tutti LR (1) è SLR (1) –
Se stai cercando un esempio puoi utilizzare questa grammatica: '1) S -> XX 2) X -> aX 3) X -> b' –
@templatetypedef, se sarebbe stato BDA. [$] nello stato 8. Ci sarebbe una riduzione ridurre i conflitti? Perché abbiamo solo un simbolo che segue che è comune. – Zephyr
io non ho abbastanza karma di commentare la risposta di cui sopra, e sono un po 'in ritardo a questa domanda, ma ...
Ho visto questa grammatica come esempio altrove e l'OP in realtà ha fatto un errore di battitura. Dovrebbe essere:
S :: = A a | b A c | d c | b d un
A :: = d
cioè, la prima clausola di S è 'Un un', non 'un A'.
In questo caso il seguente set per una è {$, a, c} e v'è un conflitto reflex in stato 8.
Se avete intenzione di fare una carriera nel settore computer, è necessario imparare a leggere quando non sai qualcosa. Leggi attentamente Wikipedia sulle lingue LR e risolvilo.Se ci vuole del tempo per fissarlo e capire, così sia; questo è tipico http://en.wikipedia.org/wiki/LR_parser –
Grazie, sei stato molto utile! –
In un certo senso, sì: -} –