The GATE Grind

GATE 2025 CS (CS2) – Question 40

Compiler Design · Parsing and Syntax Analysis · 2 marks · Multiple choice

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

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

Which ONE of the following statements is TRUE?

  1. $G$ is neither LALR(1) nor SLR(1)
  2. $G$ is CLR(1), not LALR(1)
  3. $G$ is LALR(1), not SLR(1)
  4. $G$ is LALR(1), also SLR(1)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (C) $G$ is LALR(1), not SLR(1)

Explanation

**1. Calculate FOLLOW(A).** From S → Aa, a can follow A; from S → bAc, c can follow A. Hence FOLLOW(A) = {a,c}.

**2. Exhibit the SLR conflict.** After reading d initially, an LR(0) state contains S → d·c and A → d·. SLR would shift on c for the first item and reduce A → d on every symbol in FOLLOW(A), including c. That is a shift/reduce conflict.

**3. Use the LR(1) lookaheads.** In that state, A → d· has lookahead only a, so it does not conflict with shifting c. After reading bd, the completed A item instead has lookahead c, while S → bd·a shifts a. These LR(0) cores differ, so LALR merging does not combine their conflicting lookaheads.

**4. Classify the grammar.** The relevant LR(1)/LALR actions are conflict-free, while SLR is not. **Answer: C — LALR(1), not SLR(1).**

More Parsing and Syntax Analysis questions

All Parsing and Syntax Analysis questions →