Coursify

Shift-Reduce Conflict in LR Parsing: Definition, Detection, and Resolution

Shift-Reduce Conflict in LR Parsing: Definition, Detection, and Resolution

Verified Sources
Sep 12, 2026

A shift-reduce conflict occurs in bottom-up LR parsing when, for the same parser state and lookahead token, the parsing table contains both:

  1. an instruction to shift (read the next input token and move to a new state), and
  2. an instruction to reduce (apply a grammar production and replace a handle on the parse stack with a nonterminal).

Conceptually, this means the parser cannot decide whether the “correct” next step is to extend the current handle (shift) or to finalize it (reduce), leading to ambiguity in the control action for that (state,lookahead)(state, lookahead) pair.2

Footnotes

  1. “LR parsing / action table / items” - Wikipedia. https://en.wikipedia.org/wiki/LR_parser - Explains LR parsing mechanics, items, and action decisions. ↩

  2. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

Shift/Reduce Conflicts (YACC/Bison) Explained

How LR(1)/LALR parsers decide between shift and reduce

LR parsers use an automaton over items (productions with a dot position) to build parsing tables. During parsing, they consult:

  • the current state (derived from the parse stack), and
  • the lookahead token (the next input symbol).

In an LR table, reduce actions are populated from completed items (dots at the end of a production), while shift actions are populated from transitions on terminals.
A shift-reduce conflict arises when, for the same lookahead, both a shift and a reduce are valid according to the table construction rules.2

Mermaid view of the conflict decision point:

Key learning terms:

  • LR parsing
  • parse table
  • lookahead
  • production rule
  • item (See references for how items and table entries relate.)2

Footnotes

  1. “LR parsing / action table / items” - Wikipedia. https://en.wikipedia.org/wiki/LR_parser - Explains LR parsing mechanics, items, and action decisions. ↩ ↩2 ↩3

  2. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

  3. “LALR parser” - Wikipedia. https://en.wikipedia.org/wiki/LALR_parser - Covers LALR lookahead approximation and how conflicts relate to parsing class. ↩

Why shift-reduce conflicts happen (common causes)

Shift-reduce conflicts generally indicate one of the following issues in the grammar or parsing strategy:

1) Grammar ambiguity or near-ambiguity

Even grammars that are intended to be “unambiguous” can produce conflicts if they allow multiple derivations that lead to the same viable prefix boundary. LR table construction then can legitimately produce multiple actions for the same (state,lookahead)(state, lookahead).2

2) Missing precedence/associativity declarations

Many parser generators (e.g., YACC/Bison-style tools) can resolve certain conflicts automatically when operator precedence and associativity rules are provided. Without them, grammars for expressions often yield shift-reduce conflicts like the classic ambiguous arithmetic patterns (e.g., chaining operators without precedence constraints).

3) Using a grammar that is not in the target class (not LR/LALR(1) compatible)

A grammar might be workable for some parsing approach but not fit cleanly into LR(1) or LALR(1) table construction. Conflicts are the symptom: the automaton/table doesn’t produce a deterministic action function.2

Footnotes

  1. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

  2. “LALR parser” - Wikipedia. https://en.wikipedia.org/wiki/LALR_parser - Covers LALR lookahead approximation and how conflicts relate to parsing class. ↩ ↩2

  3. “Yacc / Bison conflicts and precedence” - GNU Bison manual (conflict resolution and precedence). https://www.gnu.org/software/bison/manual/ - Documents how precedence/associativity resolve shift/reduce conflicts in typical expression grammars. ↩

  4. “LR parsing / action table / items” - Wikipedia. https://en.wikipedia.org/wiki/LR_parser - Explains LR parsing mechanics, items, and action decisions. ↩

Detecting and interpreting a shift-reduce conflict

  1. 1
    Step 1

    Use your parser generator to build the parsing tables. Tools typically report conflicts during construction (e.g., listing the number of shift/reduce conflicts).2

    Footnotes

    1. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

    2. “Yacc / Bison conflicts and precedence” - GNU Bison manual (conflict resolution and precedence). https://www.gnu.org/software/bison/manual/ - Documents how precedence/associativity resolve shift/reduce conflicts in typical expression grammars. ↩

  2. 2
    Step 2

    Many tools can print the conflicting state and show competing actions (shift vs reduce) for a particular lookahead token.2

    Footnotes

    1. “LR parsing / action table / items” - Wikipedia. https://en.wikipedia.org/wiki/LR_parser - Explains LR parsing mechanics, items, and action decisions. ↩

    2. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

  3. 3
    Step 3

    The conflict will list (explicitly or implicitly) which production the reduce corresponds to (a completed item like A→β•).

    Footnotes

    1. “LALR parser” - Wikipedia. https://en.wikipedia.org/wiki/LALR_parser - Covers LALR lookahead approximation and how conflicts relate to parsing class. ↩

  4. 4
    Step 4

    Look for patterns where a substring could reasonably be a completed handle (reduce) or an unfinished one that should grow (shift), often around operator expressions or optional constructs.2

    Footnotes

    1. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

    2. “LALR parser” - Wikipedia. https://en.wikipedia.org/wiki/LALR_parser - Covers LALR lookahead approximation and how conflicts relate to parsing class. ↩

  5. 5
    Step 5

    "Try precedence/associativity declarations, refactor the grammar (eliminate ambiguity), or change the parsing class if needed (e.g., move from LALR to LR(1) in some toolchains).2"

    Note: The general workflow above is tool-agnostic; exact flags and diagnostics vary by generator.2

    Footnotes

    1. “Yacc / Bison conflicts and precedence” - GNU Bison manual (conflict resolution and precedence). https://www.gnu.org/software/bison/manual/ - Documents how precedence/associativity resolve shift/reduce conflicts in typical expression grammars. ↩ ↩2

    2. “LALR parser” - Wikipedia. https://en.wikipedia.org/wiki/LALR_parser - Covers LALR lookahead approximation and how conflicts relate to parsing class. ↩

    3. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

Pro Tip: Use precedence/associativity for operator grammars

If your conflict comes from expression grammar (e.g., E → E op E style rules), adding precedence/associativity often removes classic shift-reduce conflicts by forcing deterministic action selection when both shift and reduce appear possible.

Footnotes

  1. “Yacc / Bison conflicts and precedence” - GNU Bison manual (conflict resolution and precedence). https://www.gnu.org/software/bison/manual/ - Documents how precedence/associativity resolve shift/reduce conflicts in typical expression grammars. ↩

Warning: Precedence does not fix true grammar ambiguity

If the grammar is genuinely ambiguous beyond what precedence/associativity can disambiguate, precedence declarations may not fully eliminate conflicts—or may “choose” an interpretation that isn’t semantically what you intended.2

Footnotes

  1. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

  2. “Yacc / Bison conflicts and precedence” - GNU Bison manual (conflict resolution and precedence). https://www.gnu.org/software/bison/manual/ - Documents how precedence/associativity resolve shift/reduce conflicts in typical expression grammars. ↩

Example: expression grammar and the shift/reduce conflict idea

A commonly problematic grammar shape for expressions is the recursive form that allows multiple grouping structures:

  • E→E op EE \rightarrow E\ \text{op}\ E
  • optionally, other forms like parentheses and literals

Without precedence/associativity constraints, the parser can face a decision where:

  • shifting continues building a longer expression, or
  • reducing commits to a smaller handle (e.g., reducing a left part before seeing the next operator).

Parser generators translate that into a shift/reduce conflict because both actions can be consistent with the LR item automaton at that point.2

Resolution approaches typically include:

  • introducing a precedence stratification (e.g., separate nonterminals for each precedence level),
  • rewriting the grammar to encode associativity in structure, or
  • using tool-specific precedence directives.

Footnotes

  1. “LR parsing / action table / items” - Wikipedia. https://en.wikipedia.org/wiki/LR_parser - Explains LR parsing mechanics, items, and action decisions. ↩

  2. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

  3. “Yacc / Bison conflicts and precedence” - GNU Bison manual (conflict resolution and precedence). https://www.gnu.org/software/bison/manual/ - Documents how precedence/associativity resolve shift/reduce conflicts in typical expression grammars. ↩

Comparison: shift-reduce vs reduce-reduce vs “no conflict”

In deterministic LR parsing, the action table is a function: each (state,lookahead)(state, lookahead) maps to exactly one action. Conflicts represent violations of this property.

SituationWhat the table contains for a given (state,lookahead)(state, lookahead)Parser behavior
No conflictExactly one action (shift or reduce or accept)Deterministic parsing
Shift-reduce conflictBoth shift and reduceGenerator reports conflict; ambiguity in next control step
Reduce-reduce conflictTwo different reducesAmbiguity in which production to apply

This table-level characterization is the core operational meaning of shift-reduce conflicts.3

Footnotes

  1. “LR parsing / action table / items” - Wikipedia. https://en.wikipedia.org/wiki/LR_parser - Explains LR parsing mechanics, items, and action decisions. ↩

  2. “Shift-reduce conflict” - Wikipedia. https://en.wikipedia.org/wiki/Shift-reduce_conflict - Defines shift-reduce conflicts as table non-determinism between shift and reduce actions. ↩

  3. “LALR parser” - Wikipedia. https://en.wikipedia.org/wiki/LALR_parser - Covers LALR lookahead approximation and how conflicts relate to parsing class. ↩

From grammar to conflict resolution

Define productions

1. Write grammar

Specify the language syntax rules (productions)."

Build action/goto tables

2. Generate LR tables

Construction may introduce multiple possible actions for some (state,lookahead)(state, lookahead)."

Interpret shift vs reduce

3. Diagnose conflicts

Pinpoint which token triggers the conflict and which reduce rule competes with shifting."

Refactor / add precedence

4. Resolve

Rewrite grammar or use precedence/associativity to restore determinism."

Confirm conflict-free tables

5. Rebuild and verify

Re-run generation and test parsing on representative inputs."

Common edge cases and FAQs

Determinism at a (state, lookahead) cell

A conflict is precisely when the action mapping is not unique.

Knowledge Check

Question 1 of 4
Q1Single choice

In an LR parsing table, a shift-reduce conflict means that for some (state, lookahead) pair, which two actions both appear possible?

Explore Related Topics

1

Hierarchy and Power of Bottom-Up Parsers: SLR, LALR, and CLR

Bottom‑up LR parsers form a strict hierarchy of power: LR(0) < SLR < LALR < CLR, with each level able to handle all grammars of the lower levels.

  • SLR uses LR(0) items and resolves conflicts with FOLLOW sets; it is the weakest but simplest LR parser.
  • LALR builds full LR(1) items then merges states that share the same core, keeping the same number of states as SLR while adding look‑ahead precision.
  • CLR (canonical LR) retains all LR(1) states and look‑aheads, giving it the highest grammar coverage at the cost of many more states.
  • Merging CLR states to form LALR can introduce reduce‑reduce conflicts (never shift‑reduce), making LALR strictly less powerful than CLR.
  • In practice, tools like Yacc/Bison prefer LALR because it balances power with manageable memory usage.
2

Syntax-Directed Translation: Infix to Prefix Notation

The module shows how a syntax‑directed translation scheme using only synthesized attributes can convert infix arithmetic expressions into prefix (Polish) notation while preserving operator precedence and left‑associativity.

  • Grammar: E → E + T | E - T | T; T → T * F | F; F → digit, enforcing precedence ( *  > + / - ).
  • Semantic actions compute a val string for each non‑terminal, concatenating the operator before its operand strings.
  • Example results: 9 - 5 + 2 → + - 9 5 2; 9 - 5 * 2 → - 9 * 5 2.
  • Synthesized (S‑attributed) attributes allow immediate bottom‑up evaluation during LR‑style parsing.
  • Left‑recursive rules enable left‑associativity; to use LL parsers the grammar must be transformed and inherited attributes introduced.
3

Mastering Low Level Design (LLD)

Low‑Level Design (LLD) translates high‑level architecture into detailed, object‑oriented blueprints that emphasize high cohesion, low coupling, and clean code. The course explains core metrics, SOLID principles, design patterns, and a step‑by‑step workflow for building robust components.

  • Instability = Ce / (Ca + Ce); I = 0 means a highly stable, heavily depended‑upon component.
  • SOLID principles (SRP, OCP, LSP, ISP, DIP) guide modular, maintainable class design.
  • Strategy, Factory, and Observer patterns illustrate OCP, DIP, and decoupling of behavior.
  • Recommended LLD workflow: gather requirements → model domain → map relationships → apply patterns → ensure thread safety.
  • Favor composition over inheritance and avoid premature over‑engineering.
Browse all research articles