Shift-Reduce Conflicts in LALR(1) Parsers: The “If and Only If” Characterization

To analyze shift-reduce conflicts for LR-family parsers, it is essential to understand how the parsing tables are constructed from LR(0) item sets and how lookahead sets (for SLR(1) and LALR(1)) affect whether an added reduce action collides with an existing shift action.

In an LALR(1) parse table, the shift actions come from transitions on terminals in LR(0)-based states, while reduce actions are inserted only when the item’s production is ready to reduce and the lookahead set contains the relevant input symbol. Conflicts therefore depend on whether, for some state and some terminal, a shift is required (from the goto transition) while a reduce is also placed (via lookahead propagation).

This yields a well-known relationship among the conflict presence across LR(0), SLR(1), and LALR(1) tables.

Key terms:

• shift-reduce conflict
• LR(0) automaton
• SLR(1) lookahead
• LALR(1) lookahead

A standard result for LALR(1) is:

For a grammar $G$, the LALR(1) parser has a shift-reduce conflict iff the grammar’s LR(0) or SLR(1) parsers have a shift-reduce conflict.

Thus, among the options given, the correct choice is (i)?? (ii)?? (iii)?? (iv)??—but we must map the theorem precisely to the listed statements.

The “only if” direction

Assume the LALR(1) parser for $G$ has a shift-reduce conflict on some LALR(1) state $I$ and terminal $a$.

• In LR-family tables, a shift action on $(I,a)$ exists when there is an LR(0) goto transition on terminal $a$ from state $I$.
• A reduce action on $(I,a)$ exists only when some LR item in $I$ is at the “handle” (dot at the end) and the lookahead set for that item contains $a$.

Now compare with:

• LR(0): reductions are not constrained by lookahead computation beyond the item being complete (so shift/reduce conflicts can exist whenever a complete item and a terminal shift coincide in the LR(0) core structure).
• SLR(1): reductions are constrained by FOLLOW sets; if a conflict survives even after FOLLOW restriction at the SLR(1) level, then it certainly manifests in the LALR(1) mechanism.

Intuitively:

• If the LR(0) core already contains a state where a complete item overlaps with a terminal shift, then LR(0) already has a shift-reduce conflict; and LALR(1) cannot “remove” that structural collision.
• Otherwise, LR(0) has no shift-reduce conflict; then any shift-reduce conflict in LALR(1) must arise due to the way LALR(1 approximates lookaheads relative to SLR(1). In that case, the lookahead collision would already reflect an SLR(1) conflict.

So conflict in LALR(1) implies conflict in LR(0) or SLR(1).

The “if” direction

Assume either:

1. the LR(0) parser has a shift-reduce conflict, or
2. the SLR(1) parser has a shift-reduce conflict.

• If LR(0) has a shift-reduce conflict, then there is an LR(0) state structure where a terminal shift and some complete-item reduction coexist. Since LALR(1) is built on the same LR(0) cores (merging LR(1) states by LR(0) core), the shift part persists and at least one reduction will remain possible for the relevant terminal—so LALR(1) will also have a conflict.
• If SLR(1) has a shift-reduce conflict, then SLR(1)’s FOLLOW-based lookahead inserted a reduction on a terminal that also has a shift action from the same core. LALR(1)’s lookahead computation (propagated lookaheads on merged cores) cannot eliminate every such collision caused by the LR(0) core and the terminal overlap; hence LALR(1) will inherit a shift-reduce conflict.

Therefore, a shift-reduce conflict in LR(0) or SLR(1) implies one in LALR(1).

Conclusion: picking the correct option

From the theorem:

• LALR(1) shift-reduce conflicts are present iff the LR(0) parser has shift-reduce conflicts or the SLR(1) parser has shift-reduce conflicts.

So the correct pair in your list is:

• (ii) The LR(0) parser for $G$ has S.R conflicts
• (iii) The SLR(1) parser for $G$ has S.R conflicts

That is, the intended correct statement is: (ii) OR (iii) (not (i) and not (iv)).