Shift/reduce conflict in yacc grammar

Question

I've written a grammar that as rules as follows:

A : B '?'  
  | B
  | A '+' A
  ;

B : "a"
  | "c" A "t" A
  ;

And this gives me a shift/reduce conflict on

A : B . '?'  (96)
A : B .  (98)

I've tried multiple ways to change the grammar but I seem to create even more conflicts when I try to change things. How can I remove this conflict?

Thank you in advance, any help will be appreciated.

How would you expect the parser to parse cata?? Which A gets the trailing ?? — Scott Hunter
The "c" and the other chars are meant to represent tokens, sorry I wasnt clear on that — Frank Wright
That doesn't answer my question: you can get to cata? by starting with A->B? or A->B, meaning the grammar is inherently ambiguous. — Scott Hunter
Oh I understand it now, I cant really do anything about it the grammar itself is ambigous. Thank you! — Frank Wright

Erez Erez · Accepted Answer · 2018-04-26T10:17:00

LALR(1) parsers resolve their conflicts using a single-character lookahead. When the lookahead can't disambiguate between the different actions, the conflict is then shown to the user.

In the following state, a "?" lookahead means the parser can shift.

A : B . '?'
A : B .

But what if it reduces A? It could possible reduce into the following state:

B: "c" A "t" A .

Which, by reducing B, could lead right back into:

A : B . '?'
A : B .

Therefore, "?" is also a valid lookahead to reduce.

So how can you solve this?

You have two options:

1) Try to rewrite the grammar with left-recursion instead of right-recursion. It might help, but that's not guaranteed.

2) Tell YACC which one to choose whenever it has this conflict (For example, using %left or %right).

Or, perhaps, use a smarter parser. For example elkhound or antlr.

Shift/reduce conflict in yacc grammar

1 Answers