Menu
I'm trying to write a small parser with Irony. Unfortunately I get a "shift-reduce conflict". Grammars are not my strong point, and I only need to get this one small thingy done. Here's the reduced grammar that produces the error:
ExpressionTerm := "asd"
LogicalExpression :=
ExpressionTerm |
LogicalExpression "AND" LogicalExpression |
LogicalExpression "OR" LogicalExpression
What does the "shift-reduce conflict" mean and how can I solve it? I gather that it means that my grammar is ambiguous, but I cannot twist my logic sufficiently to see how.
Added: To clarify - "asd" is simply a literal string "asd". So I would expect that the following expressions are parsed by this grammar:
asd
asd AND asd
asd AND asd OR asd
asd OR asd AND asd OR asd
Added 2: Forgot to say, the root of the grammar is LogicalExpression.
Added 3: Ahh, I got it! The ambiguity is because an expression like
asd AND asd OR asd
could be interpreted in two different ways:
(asd AND asd) OR asd
asd AND (asd OR asd)
But how can I solve this? OK, I can put one of AND or OR to be stronger than the other (I had inteded to anyway). But now I see that the error appears even if there is just one operator. In other words, this also produces the same error:
LogicalExpression := "asd" | LogicalExpression "OR" LogicalExpression
In this case I want this:
asd OR asd OR asd
to be parsed to this:
(asd OR asd) OR asd
What is the non-ambiguous way of doing this?
Added 4: Got it!
LogicalExpression1 := LogicalExpression1 "OR" LogicalExpression2 | LogicalExpression2
LogicalExpression2 := LogicalExpression2 "AND" LogicalExpression3 | LogicalExpression3
LogicalExpression3 := "NOT" LogicalExpression4 | LogicalExpression4
LogicalExpression4 := "asd" | "(" LogicalExpression1 ")"
This parses all boolean expressions, with operator precedence as NOT->AND->OR. "asd" can be replaced with the expression intended for your terms.
297
Rule 1. If there is a shift-reduce conflict in situations where no precedence rules have been created to resolve the conflict, the default action is to shift. The conflict is also reported in the yacc output so you can check that shifting is actually what you want.
Overview. The Shift-Reduce Conflict is the most common type of conflict found in grammars. It is caused when the grammar allows a rule to be reduced for particular token, but, at the same time, allowing another rule to be shifted for that same token.
In a shift-reduce conflict, the default is to shift. In a reduce-reduce conflict, the default is to reduce by the earlier grammar rule (in the yacc specification). Rule 1 implies that reductions are deferred in favor of shifts when there is a choice.
Your grammar is ambiguous, if you only use a single lookahead. To illustrate, what is "asd"? Is it an ExpressionTerm or a longer term. That is shift-reduce conflict. I suspect a reduce-reduce conflict here too.
Most LL(1) / LALR(1) generators will provide some way to deal with shift-reduce conflict via precedence operators. Most will also default to the longest sequence in the presence of a shift-reduce conflict, so more than often these can be ignored (after some scrutiny). (In this case maybe you need to move the single term to the bottom for it to behave correctly).
94
Shift-Reduce conflict means that your grammar is ambiguous. With your recursive rule a token "asd" could be interpreted as part of either ExpressionTerm or LogicalExpression and the parser can't decide which. Need an additional rule to break the tie.
35
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
