GATE CS 2025 Set 2 Q30 — Parsing (LL, LR)

To determine the parsing class of the grammar $G$, we analyze the $\text{LR}(0)$ and $\text{LR}(1)$ states.

1. SLR(1) Analysis:
First, let's compute the $\text{Follow}$ set of the non-terminal $A$: $$\text{Follow}(A) = \{a, c\}$$ Consider the $\text{LR}(0)$ state $I$ reached after scanning the terminal $d$ from the start state: $$I = \{S \rightarrow d.c, \; A \rightarrow d.\}$$ In this state:

• There is a shift action on terminal $c$ (from $S \rightarrow d.c$).
• There is a reduce action for $A \rightarrow d$ on any terminal in $\text{Follow}(A) = \{a, c\}$.

2. LR(1) and LALR(1) Analysis:
Let's construct the corresponding $\text{LR}(1)$ states to see if lookaheads resolve the conflict:

• From the path $S \rightarrow d c$, we get the state: $$I_1 = \{S \rightarrow d.c, \; [\$], \quad A \rightarrow d., \; [a]\}$$ Here, the shift is on $c$ and the reduce is on $a$. There is no conflict.
• From the path $S \rightarrow b d a$, we get the state: $$I_2 = \{S \rightarrow b d.a, \; [\$], \quad A \rightarrow d., \; [c]\}$$ Here, the shift is on $a$ and the reduce is on $c$. There is no conflict.

Therefore, $G$ is $\text{LALR}(1)$ but not $\text{SLR}(1)$.