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

In G1 the productions for S share the prefix 'if E then S', so it is not LL(1) and it is the ambiguous dangling-else grammar. In G2, S → if… and S → M both have 'if' in their FIRST sets, so it is not LL(1), but G2 is unambiguous. Hence only C is correct.