Ogni LR (0) la grammatica è SLR (1), ma viceversa non deve necessariamente essere vero, perché?

Question

Ogni LR (0) la grammatica è SLR (1), ma viceversa non deve necessariamente essere vero, perché?

Answer 1

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) :

1. S ? E
2. E ? 1 E
3. 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.