GATE 2025 CS (CS2) – Question 51
Consider two grammars $G_1$ and $G_2$ with the production rules given below:
$G_1$: $S \to if\ E\ then\ S \mid if\ E\ then\ S\ else\ S \mid a$
$E \to b$
$G_2$: $S \to if\ E\ then\ S \mid M$
$M \to if\ E\ then\ M\ else\ S \mid c$
$E \to b$
where $if, then, else, a, b, c$ are the terminals.
Which of the following option(s) is/are CORRECT?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (C) $G_1$ and $G_2$ are not $LL(1)$.
Explanation
**$G_1$:** $S\to if\ E\ then\ S\mid if\ E\ then\ S\ else\ S\mid a$. Two alternatives start with the same prefix `if E then S`, so a single lookahead cannot choose between them. $G_1$ is **not LL(1)**. It is also the classic **dangling-else** grammar, which is **ambiguous**.
**$G_2$:** $S\to if\ E\ then\ S\mid M$, $M\to if\ E\ then\ M\ else\ S\mid c$. Both $S$-alternatives can begin with `if`, so $FIRST$ sets overlap and $G_2$ is **not LL(1)** either. However, $G_2$ forces each `else` to attach to the nearest unmatched `then`, so it is **unambiguous**.
- (A), (B): false, since both grammars are not LL(1).
- (C): true.
- (D): false, since only $G_1$ is ambiguous.
Answer: C.