Search code examples
parsinggrammaryacclalr

Shift/reduce conflict in yacc grammar

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.

Solution

  • 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.