How to resolve a shift/reduce conflict forcing a shift or a reduce?

Question

When there is a shift/reduce conflict in Yacc/Bison, is it possible to force the conflict to be solved exactly as you want? In other words: is it possible explicitly force it to prioritize the shift or the reduce?

For what I have read, if you are happy with the default resolution you can tell the generator to not complain about it. I really don't like this because it is obfuscating your rational choice.

Another option is to rewrite the grammar to fix the issue. I don't know if this is always possible and often this makes it much harder to understand.

Finally, I have read the precedence rules can fix this. I clueless tried that in many ways and I couldn't make it work. Is it possible to use the precedence rule for that? How?

Though my ambiguous grammar is very different, I can use the classical if-then-else from the Bison manual to give a concrete example:

 %token IF THEN ELSE variable
 %%
 stmt:
   expr
 | if_stmt
 ;

 if_stmt:
   IF expr THEN stmt
 | IF expr THEN stmt ELSE stmt
 ;

 expr:
   variable
 ;

alecov alecov · Accepted Answer · 2012-08-27T20:36:37

As far as I can tell, it is not possible to direct the parser to resolve a S/R conflict by choosing to reduce. Though I might be wrong, it is probably ill-advised to proceed this way anyway. Therefore, the only possibilities are either rewriting the grammar, or solving the conflict by shifting.

The following usage of right predecence for THEN and ELSE describes the desired behavior for the if-then-else statement (that is, associating else with the innermost if statement).

%token IF THEN ELSE variable
%right THEN ELSE

%%

stmt
    : expr
    | if_stmt
    ;

if_stmt
    : IF expr THEN stmt
    | IF expr THEN stmt ELSE stmt
    ;

expr
    : variable
    ;

By choosing right association for the above tokens, the following sequence:

IF expr1 THEN IF expr2 THEN IF expr3 THEN x ELSE y

is parsed as:

IF expr1 THEN (IF expr2 THEN (IF expr3 THEN (x ELSE (y))))

and Bison does not complain about the case any longer.

Remember that you can always run bison file.y -r all and inspect file.output in order to see if the generated parser state machine is correct.

How to resolve a shift/reduce conflict forcing a shift or a reduce?

2 Answers