Issue resolving a shift-reduce conflict in my grammar
-
05-09-2019 - |
Question
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).
OTHER TIPS
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.
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.
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