Search code examples
parsinggrammarlr-grammarlalr

Is it possible that going from LR(1) to LALR(1) introduces shift/reduce conflicts?

I am studying for a final in Language Theory and one question asks the following:

If you have a parsing table T in LR(1) and a parsing table T' in LALR(1) for the same grammar. Is it possible that T' introduces new shift/reduce conflicts that were not part of T?

My understanding is that LR(1) is "smarter" than LALR(1), so my gut is telling me the answer is "No". However, I'd like to know the correct answer and a proper justification.

Thank you in advance.

Solution

  • LR(1) is "smarter", so LALR(1) may have conflicts where LR(1) does not.

    Given a conflict-free LR(1) grammar, though, LALR(1) will only introduce reduce/reduce conflicts, not shift/reduce conflicts.