LR items, shift–reduce parsing and conflicts
Goal and conventions
Build a small LR automaton, distinguish LR(0), SLR(1), canonical LR(1) and LALR(1), and trace reductions. LR reads input left-to-right and constructs a rightmost derivation in reverse. The stack top is on the RIGHT here. A dot in A→α·β means α has been recognized and β remains. Augment a grammar with a fresh start rule S′→S. Accept only on S′→S· with lookahead $, not on an arbitrary completed item.
1. Closure and goto
If an item has a dot before nonterminal B, LR(0) closure adds B→·γ for every B production and repeats. goto(I,X) moves the dot past X in all matching items, then takes closure. A transition on a terminal supplies a shift; a transition on a nonterminal supplies a goto used after a reduction.
Use S′→S, S→CC, C→cC | d. A complete deterministic numbering is:
- I0: S′→·S; S→·CC; C→·cC; C→·d.
- I1=goto(I0,S): S′→S·.
- I2=goto(I0,C): S→C·C; C→·cC; C→·d.
- I3=goto(I0,c): C→c·C; C→·cC; C→·d.
- I4=goto(I0,d): C→d·.
- I5=goto(I2,C): S→CC·.
- I6=goto(I3,C): C→cC·.
Other transitions: I2 on c→I3 and d→I4; I3 on c→I3 and d→I4. I4, I5 and I6 each contain exactly one completed ordinary item and no terminal shifts; I1 only accepts. This grammar has no LR(0) conflict. State labels are arbitrary; item sets and transitions determine correctness.
2. Full shift–reduce trace for c d d $
Write alternating states and grammar symbols, initially [0].
- Lookahead c: shift to [0 c 3]; remaining dd$.
- Lookahead d: shift to [0 c 3 d 4]; remaining d$.
- Reduce C→d: pop d and state 4, exposing 3; goto(3,C)=6 gives [0 c 3 C 6]. Input remains d$.
- Reduce C→cC: pop two symbols and their states, exposing 0; goto(0,C)=2 gives [0 C 2]. Input remains d$.
- Shift d: [0 C 2 d 4]; remaining $.
- Reduce C→d: expose 2; goto(2,C)=5 gives [0 C 2 C 5].
- Reduce S→CC: expose 0; goto(0,S)=1 gives [0 S 1]. With $ accept.
A reduction does not consume input. For A→ε, pop zero grammar symbols, then use goto on A. Handles are the substrings reduced in this reverse-rightmost derivation; they are not arbitrary occurrences matching a production RHS.
3. Where reductions are allowed
LR(0) installs a completed A→α· reduction on every terminal/end-marker column. SLR restricts that reduction to FOLLOW(A). Canonical LR(1) items attach individual lookaheads: [A→α·β,a]. For [A→α·Bβ,a], closure adds [B→·γ,b] for each b in FIRST(βa). When the item is complete, reduce only on its own lookahead.
Example S→Aa | b; A→b. After b, the state contains S→b· and A→b·: an LR(0) reduce/reduce conflict. But FOLLOW(S)={$} and FOLLOW(A)={a}, so SLR places the two reductions in different columns; the grammar is SLR(1). A completed item alone is not sufficient to claim an SLR conflict: inspect overlapping lookahead columns.
A shift/reduce conflict means one cell offers a terminal shift and a reduction. A reduce/reduce conflict means one cell offers two different reductions. Precedence declarations can resolve some table conflicts, but that does not make the original unqualified grammar conflict-free.
4. LALR merging and limits
LALR merges canonical LR(1) states with the same LR(0) core, taking unions of lookaheads for matching items. This saves states but can create reduce/reduce conflicts absent in canonical LR(1). A conflict-free canonical LR(1) automaton cannot acquire a new shift/reduce conflict solely from equal-core merging: the same core supplies the shift in every merged state, so any conflicting reduction lookahead would already conflict in its source state.
For a fixed grammar, LR(0) grammars are included in SLR(1), then LALR(1), then canonical LR(1). Deterministic LR grammars are unambiguous. An unambiguous grammar need not be LR(1), and a conflict in a weaker construction does not prove ambiguity. Always name both the grammar and construction being tested.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. An LR parser constructs which derivation?
A. Leftmost in forward order B. Rightmost in reverse C. Rightmost in forward order D. Any derivation without order
Answer: B
A: This describes top-down rather than LR reconstruction.
B: Bottom-up reductions reverse a rightmost derivation.
C: Reductions go in the reverse direction.
D: The handle sequence has a specific derivational meaning.
P02. Reducing C→cC on [0 c 3 C 6] leaves which stack in the example?
A. [0 C 2] B. [0 c 3] C. [0 C 6] D. [0 S 1]
Answer: A
A: Pop two symbols and use goto(0,C)=2.
B: Both RHS symbols must be popped.
C: The exposed state is 0, whose goto on C is 2.
D: This reduction has LHS C, not S.
P03. SLR reduces A→α on which columns?
A. FIRST(A) B. Every terminal regardless of FOLLOW C. FOLLOW(A) D. Only the next symbol after the dot
Answer: C
A: FIRST predicts beginnings, not contexts after a reduced A.
B: This is the LR(0) rule.
C: FOLLOW restricts the completed-item reduction.
D: A completed item has no symbol after its dot.
P04. For S→Aa|b; A→b, after b the two reductions are:
A. An unavoidable SLR conflict B. No LR(0) conflict C. An LR(0) conflict resolved by SLR lookaheads D. Proof that the language is ambiguous
Answer: C
A: Their FOLLOW sets are disjoint.
B: LR(0) enables both on all columns.
C: S reduces on $ and A on a.
D: This conflict does not prove ambiguity.
P05. Equal-core merging of conflict-free canonical LR(1) states can newly introduce:
A. Only a new shift action B. A reduce/reduce conflict C. A new terminal in the grammar D. A guaranteed shift/reduce conflict
Answer: B
A: The core already determines shifts.
B: Unioned lookaheads can make different reductions overlap.
C: Merging changes states, not the terminal alphabet.
D: A new shift/reduce conflict cannot arise solely this way.
P06. For a reduction A→ε, how many grammar symbols are popped?
A. 0 B. 1 C. 2 D. All symbols
Answer: A
A: The RHS has length zero; then goto on A is applied.
B: ε is not a stack grammar symbol to pop.
C: There are no RHS symbols here.
D: Only RHS length determines the pop count.
Sources and scope
Aligned to the official 2026 course. This lesson covers a bounded topic slice; no claim of 2027 completeness. All examples and exercises are original.
Sign in to keep your progress. Sign in