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.