Right way to fix shift/reduce conflict?

Question

I see 1 shift/reduce conflict for following bison grammar:

%token EQUAL "=" NUM "NUM" WORD "WORD" ; %% %start line; VALUES: NUM | VALUES NUM ; PARAM: NUM | WORD EQUAL VALUES ; PARAM_LIST: PARAM | PARAM_LIST PARAM ; line: WORD PARAM_LIST ; %%

I understand that bison sees ambiguity when meets NUM while having in stack: WORD EQUAL NUM (either shift NUM and reduce NUM NUM to VALUES or reduce NUM to VALUES and then reduce WORD EQUAL VALUES to PARAM). Default shift action perfectly matches my expectation and %expect 1 hides warning. But is there are any better practice to fix such grammar to force bison using shift action without complaining (e.g. %prec, %left, %right)?

Chris Dodd · Accepted Answer · 2025-11-09 10:58:39Z

The conflict comes from the grammar being ambiguous. If you have a PARAM_LIST that is

WORD = NUM NUM

is that one PARAM (a WORD = VALUES with 2 NUMs) or two (a WORD = VALUES with one NUM followed by a bare NUM param?

The default "prefer shift" resolution will treat it as the former -- basically any VALUES will absorb as many NUM tokens as it can, leaving none to be stand-alone params. If that is the preferred resolution, then you can just leave it as that, but if you really want to shut up the "warning" message, you can either:

Add precedence rules to shut it up: You want shifting a NUM to have higher precedence that the rule PARAM: WORD EQUAL VALUES. The latter will get the precedence of the EQUAL token, so that needs to have higher precedence than NUM. The main danger in using the precedence rules is in overspecifying them and having them trigger when you don't expect. This might hide a conflict if you have any other rules that use the tokens NUM or EQUAL

Refactor the grammar to make the ambiguity go away. Something like

 NUM_PARAMS: NUM | NUM_PARAMS NUM ; WORD_PARAM: WORD EQUAL VALUES ; WORD_PARAMS: WORD_PARAM | WORD_PARAMS WORD_PARAM ; PARAM_LIST: NUM_PARAMS WORD_PARAMS | NUM_PARAMS | WORD_PARAMS ;

This makes it clear that when you have both params that are bare NUMs and params that are WORD = VALUES all the bare NUMs must come first.

If, on the other hand, you would rather have the ambiguity resolved the other way (so that the trailing NUM is a separate param), the easiest fix is probably just to change the WORD EQUAL VALUES to WORD EQUALS NUM.

Thank you for the hints! With simple solution %right NUM bison still reports conflict. But refactoring did help, I've stopped at following grammar: %token EQUAL "=" NUM "NUM" WORD "WORD" ; %% %start line; VALUES: NUM | VALUES NUM; UNNAMED_PARAM: NUM ; NAMMED_PARAM: WORD EQUAL VALUES; UNNAMED_PARAMS: UNNAMED_PARAM | UNNAMED_PARAMS UNNAMED_PARAM; NAMMED_PARAMS: NAMMED_PARAM | NAMMED_PARAMS NAMMED_PARAM; PARAM_LIST: UNNAMED_PARAMS NAMMED_PARAMS | UNNAMED_PARAMS; line: WORD PARAM_LIST ; %%

Collectives™ on Stack Overflow

Right way to fix shift/reduce conflict?

1 Answer 1

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Related