Reduce/reduce conflict in grammar

1
votes

Let's imagine I want to be able to parse values like this (each line is a separate example):

x
(x)
((((x))))
x = x
(((x))) = x
(x) = ((x))

I've written this YACC grammar:

%%
Line: Binding | Expr
Binding: Pattern '=' Expr
Expr: Id | '(' Expr ')'
Pattern: Id | '(' Pattern ')'
Id: 'x'

But I get a reduce/reduce conflict:

$ bison example.y
example.y: warning: 1 reduce/reduce conflict [-Wconflicts-rr]

Any hint as to how to solve it? I am using GNU bison 3.0.2

2
parsinggrammarbisonyacc

2 Answers

2
votes

Reduce/reduce conflicts often mean there is a fundamental problem in the grammar.

The first step in resolving is to get the output file (bison -v example.y produces example.output). Bison 2.3 says (in part):

state 7

    4 Expr: Id .
    6 Pattern: Id .

    '='       reduce using rule 6 (Pattern)
    ')'       reduce using rule 4 (Expr)
    ')'       [reduce using rule 6 (Pattern)]
    $default  reduce using rule 4 (Expr)

The conflict is clear; after the grammar reads an x (and reduces that to an Id) and a ), it doesn't know whether to reduce the expression as an Expr or as a Pattern. That presents a problem.

I think you should rewrite the grammar without one of Expr and Pattern:

%%
Line: Binding | Expr
Binding: Expr '=' Expr
Expr: Id | '(' Expr ')'
Id: 'x'
1
votes

Your grammar is not LR(k) for any k. So you either need to fix the grammar or use a GLR parser.

Suppose the input starts with:

(((((((((((((x

Up to here, there is no problem, because every character has been shifted onto the parser stack.

But now what? At the next step, x must be reduced and the lookahead is ). If there is an = somewhere in the future, x is a Pattern. Otherwise, it is an Expr.

You can fix the grammar by:

  • getting rid of Pattern and changing Binding to Expr | Expr '=' Expr;

  • getting rid of all the definitions of Expr and replacing them with Expr: Pattern

The second alternative is probably better in the long run, because it is likely that in the full grammar which you are imagining (or developing), Pattern is a subset of Expr, rather than being identical to Expr. Factoring Expr into a unit production for Pattern and the non-Pattern alternatives will allow you to parse the grammar with an LALR(1) parser (if the rest of the grammar conforms).

Or you can use a GLR grammar, as noted above.