GATE CS 2008 Q55 — Parsing (LL, LR)

An LALR(1) parser is constructed by merging the states of an LR(1) parser that share the same core (i.e., the same set of LR(0) items, ignoring the lookahead sets).

Why merging states cannot introduce new Shift-Reduce (S-R) conflicts:

Suppose the merged LALR(1) state has a shift-reduce conflict on a terminal symbol $a$. This means the state contains:

1. A shift item: $A \to \alpha \cdot a \beta$
2. A reduce item: $B \to \gamma \cdot$ with lookahead $a$

Since the LALR(1) state is formed by taking the union of lookaheads of LR(1) states with the same core:

• The core of this state must contain both $A \to \alpha \cdot a \beta$ and $B \to \gamma \cdot$.
• The lookahead $a$ for the reduction $B \to \gamma \cdot$ must have been present in at least one of the original LR(1) states, say state $S_1$, before merging.

Since state $S_1$ has the same core, it also contains the item $A \to \alpha \cdot a \beta$. Thus, in the original LR(1) parser, state $S_1$ already had a shift-reduce conflict on terminal $a$ (shift on $a$ due to $A \to \alpha \cdot a \beta$, and reduce on $a$ due to $B \to \gamma \cdot, [a]$).

Therefore, merging states to construct an LALR(1) parser never introduces new shift-reduce conflicts. An LALR(1) parser has an S-R conflict if and only if the LR(1) parser for $G$ has an S-R conflict.

Analysis of other options:

• Option A & C: SLR(1) and LR(0) parsers are weaker than LALR(1). They can have S-R conflicts even when the LALR(1) parser does not.
• Option D: Merging states can introduce new reduce-reduce (R-R) conflicts, but this is independent of whether there is an S-R conflict.