Ogni LR (0) la grammatica è SLR (1), ma viceversa non deve necessariamente essere vero, perché?
-
09-10-2019 - |
Domanda
Ogni LR (0) la grammatica è SLR (1), ma viceversa non deve necessariamente essere vero, perché?
Soluzione
In sostanza, una reflex (1) grammatica può risolvere i conflitti spostamento-ridurre che esistono in una corrispondente LR (0) grammatica. Prendiamo l'esempio di grammatica href="http://en.wikipedia.org/wiki/Simple_LR_parser" rel="nofollow"> reflex parser pagina di Wikipedia (che spiega questo a un livello più rigoroso inferiore) :
- S ? E
- E ? 1 E
- E ? 1
Quando un LR (0) parser sta analizzando un E e un "1" è il simbolo di ingresso successivo, potrebbe riconoscere E e ridurre (regola 3) o potrebbe spostare per analizzare un seguito E (regola 2). Perché non può guardare avanti, un LR (0) non è in grado di determinare che fare. Questo diventa più evidente se guardiamo il LR (0) potrebbe essere l'elaborazione se incontra un "1" (il simbolo di fine stringa è stata aggiunta):
- E ? 1 • E $
- E ? 1 • $
Il primo richiederebbe uno spostamento, il secondo richiede un ridurre.
Con la grammatica di cui sopra, una reflex (1) la grammatica può guardare avanti un simbolo e determinare quale azione intraprendere. E può essere seguito solo da $, in modo da ridurre un atto è valido solo alla fine della stringa. Ciò corrisponde alla seconda voce, dove si può vedere il simbolo successivo è un "$".
Per un altro esempio di grammatica che è SLR (1) e non LR (0), vedi Fegaras' note per CSE 5317/4305 presso l'Università del Texas.