Bison shift/reduce conflict with balanced parentheses grammar

Question

I'm doing an exercise with the grammar of the balanced parentheses:

S -> (S)

S -> SS

S -> ()

The compiler returns a shift/reduce conflict. This is my bison grammar:

%%
prog:
  srule
;

srule 
    : ( srule )
    | srule srule 
    | ( )
;
%%

Can anyone explain to me the reason and how can I solve it without changing the grammar?

You can't solve it without changing the grammar, unless using %prec or %assoc isn't considered as changing the grammar. Are you sure you transcribed it correctly? — user207421
Changing the grammar is quite simple, such as with this grammar it works: S -> (S)S | ε. I would like to know the reason for the shift/reduce and how to use the precedence operators in this case. Thank you again. — Valerio Coretti

rici rici · Accepted Answer · 2020-05-31T22:15:56

Your grammar is ambiguous, and ambiguous grammars always produce conflicts. That's because the ambiguity means that there will come a point at which two different parses are possible, which means that two different parsing actions are possible. Which is the definition of a parsing conflict.

The ambiguity is pretty obvious. S: S S says that the concatenation of two S is a valid S. But () and ()() are both valid S. So you could make a new S by concatenating () with ()(), or you could make a new S by concatenating ()() with (). Unfortunately, those would both be the same new S, and the grammar does not specify which decomposition is to be used.

Fixing the grammar is one way to do this, and the fix is pretty simple. We just need to specify that when concatenating two balanced sentences, the first one cannot itself be a concatenation. That means that ()•()() is a valid composition, but ()()•() is not.

As you note in a comment, it's simple to modify the grammar with this requirement, by replacing the concatenation rule with S: ( S ) S. The two literal parentheses in that rule match, which means that the part of the rule before the first S cannot be a concatenation.

But we can use the normal yacc/bison mechanism for dealing with ambiguous grammars instead. All we need to do is to require that the parser always resolve a conflict in favour of the reduction action. (This is not a general solution, but it will work here.)

In order for a yacc/bison precedence rule to take effect, the right-hand side which might be reduced must have higher precedence than the lookahead character which might be shifted. The precedence of a right-hand side is specified as the precedence of the first token in the right-hand side, but unfortunately the right-hand side we are interested in -- the concatenation rule -- doesn't have any tokens at all. So we need to mark it with a %prec marker. Since we know that the lookahead symbol will always be a ( (there is no ambiguity with ), since the parser must reduce until the ) can be shifted), we can just mark the production as having the precedence of ( and then declare that ( is right-associative, meaning that reduction is preferred to shift:

%right '('
%%
%%
srule: '(' srule ')'
     | '(' ')'
     | srule srule %prec '('

In fact, the use of %right above is completely arbitrary. Had we started with the unambiguous grammar S → S ( S ) | ε instead of S → ( S ) S | ε, we would have created a left-associative composition in which ()()() must be decomposed as ()()•() rather than ()•()(). That would be implemented by changing %right in the above Bison snippet to %left, which would lead to a more efficient use of the parser stack in the generated parser.

Bison shift/reduce conflict with balanced parentheses grammar

1 Answers