Choose the Correct Answer: Shift–Reduce Conflicts in LALR(1) Parsers

A grammar $G$ has a shift–reduce conflict in a particular LR-style parser construction when, in some parsing state, the action table cell $ACTION[i, a]$ is forced to contain both a shift action and a reduce action for the same lookahead terminal $a$.

In LR-family terms, we distinguish:

• keyword: LR parser using only LR(0) items (no lookahead terminals).
• keyword: Uses lookaheads from FOLLOW sets (coarse approximation).
• keyword: Uses exact lookaheads computed per LR(1) items.
• keyword: Approximates LR(1) by merging states with the same LR(0) core, unioning lookaheads.

The key fact behind the multiple-choice question is that LALR(1) is a “merged” version of LR(1): it can introduce conflicts that LR(1) might avoid, but it cannot “hide” conflicts that are already forced by the LR(0) core behavior.

A precise characterization (used in standard compiler-construction reasoning) is:

• If LR(0) already forces a shift–reduce conflict in some state, then every LR variant that uses the same LR(0) core (including SLR(1), LALR(1), and LR(1)) will also have a shift–reduce conflict.
• Conversely, if there is no shift–reduce conflict in the LR(0) automaton, then any shift/reduce ambiguity in LALR(1) must arise from lookahead behavior; that can occur only when lookaheads interact in LALR/SLR-style merging/approximation.

In the options given, the statement that matches this “iff” condition is that LALR(1) shift–reduce conflicts are present exactly when the LR(0) parser for $G$ has shift–reduce conflicts.

To visualize why, consider the LR(0) situation: a shift–reduce conflict at LR(0) level means there exists an LR(0) state containing an item of the form $A \to \alpha\bullet a\beta$ (shift possibility on terminal $a$), and also an item of the form $B \to \gamma\bullet$ (reduce possibility without any lookahead restriction at LR(0) level).

Since LALR(1) uses the same LR(0) cores for its merged states, that structural overlap cannot disappear by refining lookaheads; it persists and therefore yields a shift–reduce conflict.

Mermaid intuition (cores are what gets merged in LALR(1)):

Therefore, the correct choice is:

(iv) the SLR(0) parser for $G$ has S-R conflicts is not the intended option name (it’s a typo-like mismatch in the question). Interpreting the intended LR family consistently, the correct statement is option (ii).

Correct answer: (ii) the LR(0) parser for $G$ has S-R conflicts.

Note: Many textbooks phrase this using “LR(0) conflicts imply LR-family conflicts in that same merged core,” and the “iff” in this multiple-choice format aligns to LR(0) ⇔ LALR(1) for shift–reduce conflict presence (not necessarily the exact set of conflicts).

Choosing the Correct Option

The question:

For grammar $G$, shift–reduce conflicts are present in LALR(1) parser, if and only if which condition holds?

Using the structural argument about LR(0) core overlap and the definition of LALR(1 via LR(0) core merging, the correct selection is:

• (ii) the LR(0) parser for $G$ has S–R conflicts