CODEWITHSUNDEEP
parsinggrammaryacclalr
Frank Wright
Frank Wright

Reputation: 83

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.

Upvotes: 0

Views: 908

Answers (1)

Erez
Erez

Reputation: 1430

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.

Upvotes: 2

Related Questions