Hilfe mit Shift/Konflikt reduzieren - Der Versuch, Modell (XA) * (XB) * ​​

Question

Im Versuch, die EBNF Ausdruck

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

ich die yacc aufgebaut haben zu modellieren Grammatik (Im MPPG verwenden), die scheint um dies darzustellen, aber es stimmt nicht mit meinem Testausdruck überein.

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, dies mit "% left PrologHeaderList PrologBodyList" zu lösen, 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 eine lange Zeit her, seit ich irgendetwas YACC-like verwendet habe, aber hier sind ein paar Vorschläge, die helfen können oder nicht.

Es scheint, dass Sie in dieser Situation ein 2-Token-Lookahead benötigen. Der Parser wird zum letzten PrologHeader, und es hat zu entscheiden, ob das nächste Konstrukt ist ein PrologHeader oder ein PrologBody, und es kann nicht sagen vom KW_Declare. Wenn es eine Anweisung gibt, in dieser Situation das Lookahead zu erhöhen, wird es wahrscheinlich das Problem lösen.

Sie könnten auch Kontext in Ihre Aktionen vorstellen: anstatt definieren PrologHeaderList und PrologBodyList definieren PrologRuleList und haben die Aktionen einen Fehler aus, wenn ein Header nach einem Körper erscheint. Hässlich, aber manchmal müssen Sie es tun: Was in einer Grammatik einfach erscheint, ist im generierten Parser möglicherweise nicht einfach.

könnte ein hackish Ansatz sein, um die Token zu kombinieren: anstatt KW_Declare und KW_Variable, haben Ihre Lexer den Raum erkennen und KW_Declare_Variable verwenden. Da beide Schlüsselwörter sind, werden Sie keine Namespace-Kollisionsprobleme haben.

Answer 2

Die Grammatik an der Spitze ist regelmäßig, so IIRC können Sie es als DFA (oder eine NDA und konvertieren Sie es in eine DFA) und konvertieren Sie dann die DFA in eine Grammatik. Es ist eine Weile, also werde ich die Arbeit als Übung für den Leser verlassen.