Course contentsShow
← Computer Science
Lesson 1971 of 2,87244. Lexical Analysis and ParsingFree lesson

Conflict Resolution in LR Parsing

Identifying and resolving shift-reduce and reduce-reduce conflicts in parsing tables.

Conflict Resolution in LR Parsing

You'll learn how to identify and fix the conflicts that arise when building LR parsing tables.

The Core Problem

When constructing LR parsing tables (LR(0), SLR(1), LR(1), or LALR(1)), you sometimes encounter conflicts—situations where the parser doesn't know which action to take. Think of it like a GPS showing two equally valid routes: the parser sees multiple legal actions and doesn't know which to choose.

There are two types of conflicts:

Shift-Reduce Conflicts

A shift-reduce conflict occurs when the parser can either shift the next input token onto the stack OR reduce a completed handle. This typically happens with ambiguous grammars.

Example scenario: The classic "dangling else" problem. When parsing if (cond) if (cond2) stmt else stmt, should the parser shift the else (to attach it to the inner if) or reduce the inner if statement first?

Reduce-Reduce Conflicts

A reduce-reduce conflict happens when multiple grammar rules could be reduced using the same lookahead. The parser sees two different handles that both seem valid.

Example scenario: Two rules like A → x and B → x create ambiguity—which one should reduce when x is on the stack?

Resolution Strategies

  1. Rewrite the grammar to eliminate ambiguity (preferred)
  2. Use precedence and associativity rules (for operators in shift-reduce conflicts)
  3. Choose a default action (shift usually wins over reduce in many tools)
  4. Upgrade to a more powerful parser (LR(0) → SLR(1) → LR(1) → LALR(1))

Key Takeaway: Conflicts indicate ambiguity or insufficient lookahead; resolve them by refining the grammar, applying precedence rules, or using a stronger parsing method with more lookahead information.