Decidere se la grammatica è lr (0) o no

Question

Sono nuovo all'argomento della compilazione e ho appena iniziato un esercizio per il fanale di fondo.

Ho bloccato il problema seguente.

Build A LR (0) Tabella antigas per la seguente grammatica:

1) E –> E + T
2) E –> T
3) T –> (E)
4) T –> id


I0 :

   E' –> .E
   E –> .E + T
   E –> .T
   T –> .(E)
   T –> .id

.

On e lo stato successivo nel DFA sarebbe:

 I1:

    E' -> E.
    E  -> E. + T

.

Da quello che ho imparato finora non è questo un conflitto S-R? perché il parser non saprebbe se ridurre o spostare come non ha la variabile di ricerca? Quindi questo non dovrebbe essere LR (0) Grammatica?

Ma il PDF che sto leggendo ha costruito la tabella LR (0). Quindi c'è un errore nel PDF o ho sbagliato un po 'dove capire il concetto?

Answer 1

Questo è davvero un conflitto Shift / Riduce.Questa grammatica non è LR (0).Puoi anche vederlo perché non è prefisso-libero ;La grammatica contiene più stringhe che sono prefissi l'uno dell'altro, quindi non può essere LR (0).

Detto ciò, è comunque possibile costruire tutti i set di configurazione del LR (0) e rendere il LR (0) Automaton.Semplicemente non sarà deterministico a causa del conflitto Shift / Riduci.È possibile, quindi, che hai ragione e il dispensa è giusto.

Spero che questo aiuti!

Answer 2

Hai aumentato la grammatica con E' -> E.Normalmente, aumenteresti con una produzione come E' -> E $, dove $ è un simbolo (terminale) che non si verifica altrimenti nella grammatica e denota la fine dell'ingresso.

Allora I1 sarebbe effettivamente

E' -> E. $
E  -> E. + T

.

E non c'è un conflitto.(E credo che la grammatica sia lr (0).)