How to resolve a shift/reduce conflict forcing a s

问题:

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
 ;

回答1:

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.

回答2:

Well, the default resolution for a shift/reduce conflict is to shift, so if that's what you want, you don't need to do anything (other than ignoring the warning).

If you want to resolve a shift/reduce conflict by reducing, you can use the precedence rules -- just make sure that the rule to be reduced is higher precedence than the token to be shifted. The tricky part comes if there are multiple shift/reduce conflicts involving the same rules and tokens, it may not be possible to find a globally consistent set of precedences for the rules and tokens which resolves things the way you want.