Search code examples
parsinggrammarshift-reduce-conflictirony

Issue resolving a shift-reduce conflict in my grammar

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.

Solution

  • 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).