The GATE Grind

GATE 2025 CS (CS2) – Question 51

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

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?

  1. $G_1$ is not $LL(1)$ and $G_2$ is $LL(1)$.
  2. $G_1$ is $LL(1)$ and $G_2$ is not $LL(1)$.
  3. $G_1$ and $G_2$ are not $LL(1)$.
  4. $G_1$ and $G_2$ are ambiguous.

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**.

Answer: C.

More Parsing and Syntax Analysis questions

All Parsing and Syntax Analysis questions →