Problem Lösung eines shift-reduce-Konflikt in meiner Grammatik

Question

Ich versuche, einen kleinen Parser mit Irony zu schreiben. Leider bekomme ich einen „shift-reduce-Konflikt“. Grammatiken sind nicht meine Stärke, und ich brauche nur dieses ein kleines Ding zu erledigen. Hier ist die reduzierte Grammatik, die den Fehler erzeugt:

ExpressionTerm := "asd"
LogicalExpression :=
    ExpressionTerm |
    LogicalExpression "AND" LogicalExpression |
    LogicalExpression "OR" LogicalExpression

Was bedeutet die „shift-reduce-Konflikt“ und wie kann ich sie lösen? Ich nehme an, dass es bedeutet, dass meine Grammatik nicht eindeutig ist, aber ich kann meine Logik nicht ausreichend drehen, um zu sehen, wie.

am: Um zu klären - "asd" ist einfach eine Zeichenkette "asd". Also ich würde erwarten, dass die folgenden Ausdrücke, die von dieser Grammatik analysiert werden:

asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd

hinzugefügt. 2: vergessen die Wurzel der Grammatik zu sagen, ist LogicalExpression

Added 3: Ahh, ich habe es! Die Mehrdeutigkeit ist, weil ein Ausdruck wie

asd AND asd OR asd

konnte auf zwei verschiedene Arten interpretiert werden:

(asd AND asd) OR asd
asd AND (asd OR asd)

Aber wie kann ich dieses Problem lösen? OK, kann ich einen von AND oder OR setze die andere, stärker zu sein als (I den bestimmungsgemäßen hatte sowieso). Aber jetzt sehe ich, dass der Fehler angezeigt wird, auch wenn es nur ein Operator ist. Mit anderen Worten, erzeugt dies auch den gleichen Fehler:

LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression

In diesem Fall mag ich:

asd OR asd OR asd

, um diese analysiert werden:

(asd OR asd) OR asd

Was ist die nicht-mehrdeutige Art und Weise, dies zu tun?

Hinzugefügt 4: Verstanden

LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"

Dieses parst alle Booleschen Ausdrücken, mit Operatorpräzedenz als NOT-> und-> OR. „Asd“ kann mit dem Ausdruck ersetzt werden, die für Ihre Bedingungen.

Answer 1

Ihre Grammatik ist mehrdeutig, wenn Sie nur einen einzigen Look-Ahead verwenden. Zur Veranschaulichung, was „asd“? Ist es ein ExpressionTerm oder eine längerfristige. Das heißt shift-reduce-Konflikt. Ich vermute, dass eine Verringerung-reduce-Konflikt auch hier.

Die meisten LL (1) / LALR (1) Generatoren wird eine Möglichkeit zu schaffen, mit shift-reduce-Konflikt über Vorrang Betreiber zu beschäftigen. Die meisten werden auch in Gegenwart eines shift-reduce-Konflikt auf die längste Sequenz Verzug, so dass mehr als oft können diese (nach einer gewissen Kontrolle) ignoriert. (In diesem Fall müssen Sie vielleicht den einzigen Begriff nach unten zu bewegen, um sie richtig zu verhalten).

Answer 2

shift-reduce Konflikt bedeutet, dass Ihre Grammatik mehrdeutig ist. Mit Ihrer rekursive Regel könnte ein Token „asd“ als Teil entweder von ExpressionTerm oder LogicalExpression interpretiert werden und der Parser kann nicht entscheiden, welche. Benötigen Sie eine zusätzliche Regel die Krawatte zu brechen.

Answer 3

Umschalt reduzieren Konflikte sind eine der schwierigeren Dinge, die Ihr Gehirn um zu bekommen, wenn es um Parser kommt. Der einfachste Weg, um den Konflikt ist in diesem Pseudo-Code zu veranschaulichen:

if (a) then
   if (b) then
     printf('a + b');
   else
     print('this could be a + !b or !a');

Die else-Anweisung an den ersten binden könnte oder Sekunde, wenn. Im Fall von mehrdeutigen Grammatiken, Sie in der Regel einen Wert definieren die Anzahl der um anzuzeigen, erwartete shift-reduce Warnungen in Ihrer Grammatik.

Alternativ können Sie auch eine LL (k) oder LL (*) Parser verwenden. Diese Arten von Parsern haben nicht die Verschiebung / Mehrdeutigkeit reduzieren. Je nach Anwendung können sie leichter oder schwerer sein als die LALR (1) Parser.

Answer 4

Grammatik ist mehrdeutig in LL(1) oder LALR(1) da asd Token in ExpressionTerm ersetzt werden kann und LogicalExpression auch die Grammatikregeln abflachen Verschiebung zu lösen / reduzieren Konflikte