Hilfe mit Shift / Reduce Konflikt - Der Versuch, zu modellieren (X A) * (X B) *

Question

Im Versuch, den EBNF Ausdruck zu modellieren

("declare" "namespace" ";")* ("declare" "variable" ";")*

Ich habe die yacc (Im mit MPPG) Grammatik aufgebaut, die dies zu vertreten scheint, aber es funktioniert nicht meinen Testausdruck entspricht.

Der Testfall i bin versucht zu passen

declare variable;

Der Token Strom aus dem Lexer ist

KW_Declare
KW_Variable
Separator

Die Grammatik Parse sagt, es gebe eine "Shift / Reduce Konflikt, Zustand 6 auf KW_Declare". Ich habe versucht, dieses Problem zu lösen mit „% links PrologHeaderList PrologBodyList“, aber keine Lösung funktioniert.

Program                     : Prolog;
Prolog                      : PrologHeaderList PrologBodyList;

PrologHeaderList            : /*EMPTY*/
                            | PrologHeaderList PrologHeader;
PrologHeader                : KW_Declare KW_Namespace Separator;

PrologBodyList              : /*EMPTY*/
                            | PrologBodyList PrologBody;
PrologBody                  : KW_Declare KW_Variable Separator;

KW_Declare KW_Namespace KW_Variable Separator sind alle Token mit Werten "deklarieren", "naemsapce", "Variable", ";"

.

Answer 1

Es ist schon eine lange Zeit, da ich etwas yacc-like verwendet habe, aber hier ein paar Vorschläge, die nicht helfen können oder nicht.

Es scheint, dass Sie ein 2-Token Look-Ahead in dieser Situation brauchen. Der Parser wird auf den letzten PrologHeader , und es hat zu entscheiden, ob das nächste Konstrukt a PrologHeader oder PrologBody , und es kann nicht sagen, dass von der KW_Declare. Wenn es eine Richtlinie des Look-Ahead in dieser Situation zu erhöhen, wird es wahrscheinlich das Problem lösen.

Sie können auch Kontext in Ihre Aktionen vorstellen: anstatt definieren PrologHeaderList und PrologBodyList definieren PrologRuleList und haben die Aktionen werfen einen Fehler, wenn ein Header erscheint nach einem Körper. Hässlich, aber manchmal muss man es tun. Was in einer Grammatik einfach erscheint in der generierten Parser nicht einfach sein kann

Ein hackish Ansatz könnte sein, die Zeichen zu kombinieren: anstatt KW_Declare und KW_Variable , haben Sie Ihren Lexer den Raum erkennen und nutzen KW_Declare_Variable . Da beide sind Schlüsselwörter, sind Sie nicht in Namespace-Konflikt Probleme gehen laufen.

Answer 2

Die Grammatik an der Spitze ist regelmäßig so IIRC Sie es heraus als DFA (oder einem NDA und wandelt es in ein DFA) zeichnen und dann die DFA zu einer Grammatik umwandeln. Es ist Bohne eine Weile so werde ich die Arbeit als eine Übung für den Leser überlassen.