Issue resolving a shift-reduce conflict in my grammar

6
votes

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.

4
parsinggrammarshift-reduce-conflictirony
Heh, come to think of it, I'm starting to remember this pattern from my days at the University. :D – Vilx-

4 Answers

3
votes

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

1
votes

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.

0
votes

Shift reduce conflicts are one of the harder things to get your brain around when it comes to parsers. The easiest way to illustrate the conflict is in this pseudo code:

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

The else statement could bind to the first or second if. In the case of ambiguous grammars, you usually define a value to indicate the number of expected shift-reduce warnings in your grammar.

Alternatively, you can use a LL(k) or LL(*) parser. These types of parsers don't have the shift/reduce ambiguity. Depending on your application they may be easier or harder than the LALR(1) parser.

0
votes

grammar is ambiguous in LL(1) or LALR(1) since asd token can be substituted in ExpressionTerm and also LogicalExpression flatten the grammar rules to resolve shift/reduce conflicts