Entscheiden, ob die Grammatik LR(0) ist oder nicht

Question

Ich bin neu im Thema Kompilierung und habe gerade mit einer Übung zum Bottom-up-Parsing begonnen.

Ich bin bei folgendem Problem hängengeblieben.

Erstellen Sie eine LR(0)-Parsing-Tabelle für die folgende Grammatik:

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

auf E wäre der nächste Staat im DFA:

 I1:

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

Handelt es sich nach dem, was ich bisher gelernt habe, nicht um einen S-R-Konflikt?Weil der Parser nicht wissen würde, ob er reduziert oder verändert werden soll, da er keine Variable aussieht?Das sollte also keine LR(0)-Grammatik sein?

aber das PDF, das ich lese, hat die LR(0)-Tabelle erstellt.Liegt also ein Fehler im PDF vor, oder habe ich beim Verständnis des Konzepts einen Fehler gemacht?

Answer 1

Dies ist in der Tat ein Umschalt- / Reduzierkonflikt.Diese Grammatik ist nicht lr (0).Sie können dies auch sehen, weil es nicht prefix-free ist;Die Grammatik enthält mehrere Zeichenfolgen, die einander Präfixe sind, sodass er nicht lr (0) sein kann.

Das heißt, Sie können immer noch alle LR (0) -Einstellungssätze erstellen und den LR (0) Automaton herstellen.Es wird einfach nicht wegen des Umschalt- / Reduzierungskonflikts deterministisch sein.Es ist daher möglich, dass Sie richtig sind und die Handout richtig ist.

hoffe das hilft!

Answer 2

Sie haben die Grammatik um erweitert E' -> E.Normalerweise würden Sie mit einer Produktion wie ergänzen E' -> E $, wobei $ ein (Terminal-)Symbol ist, das sonst in der Grammatik nicht vorkommt und das Ende der Eingabe bezeichnet.

Also I1 wäre es tatsächlich

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

und es gibt keinen Konflikt.(Und ich glaube der Grammatik Ist LR(0).)