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?

$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)

Practise this question in The GATE Grind →

Show answer and explanation

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

Explanation

In the state containing $S \to d.c$ and $A \to d.$, SLR reduces on FOLLOW(A) = {a, c}, which conflicts with the shift on c. In LR(1)/LALR(1) the lookahead for that reduction is only 'a', and the state after 'bd' has different cores, so no states merge and there is no conflict.