GATE CS 2025 Set 2 Q.40: Parsing and Syntax Analysis (LL and LR)

Given a Context-Free Grammar $G$ as follows:

$S \rightarrow Aa \mid bAc \mid dc \mid bda$
$A \rightarrow d$

Which ONE of the following statements is TRUE?

$G$ is neither LALR(1) nor SLR(1)

$G$ is CLR(1), not LALR(1)

$G$ is LALR(1), not SLR(1)

$G$ is LALR(1), also SLR(1)

Official answer and solution

Official answer: C
From: Official GATE 2025 answer key

Solution

Check the LR(0) state reached on input d from the initial state for SLR(1) conflicts, and compare with LR(1)/LALR(1) lookaheads.

Why $G$ is not SLR(1): In the initial state $I_0$ , shifting terminal d leads to a state containing the LR(0) items $[A \rightarrow d\cdot]$ and $[S \rightarrow d\cdot c]$ . Since $S \rightarrow bAc$ puts $c \in \text{FOLLOW}(A)$ , we have $\text{FOLLOW}(A) = \{a, c\}$ . On lookahead c, SLR(1) has a shift-reduce conflict between shifting c (in $S \rightarrow d\cdot c$ ) and reducing $A \rightarrow d$ .
Why $G$ is LALR(1): In the LR(1) automaton, the state reached from $I_0$ on d has item $[A \rightarrow d\cdot, \; a]$ (lookahead is only a, not c, because $A$ at the start of $S$ is only followed by a), whereas the state reached after b then d has $[A \rightarrow d\cdot, \; c]$ and $[S \rightarrow bd\cdot a, \; \$]$ (no conflict on c or a). Moreover, these two states have different LR(0) cores and are never merged in LALR(1). Thus $G$ is LALR(1), not SLR(1).

Final answer

Option (C)

Common trap

Confusing this grammar with the standard example that is CLR(1) but not LALR(1) ( $S \rightarrow Aa \mid bAc \mid Bc \mid bBa, \; A \rightarrow d, \; B \rightarrow d$ ).

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2025 Computer Science and Information Technology - Session 2 (CS2)
Question: 40 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source