Skip to content
GATEiit

GATE CSE 2025 Session 2 Q51: LL(1) and ambiguity of two if-then-else grammars

Question

Consider two grammars G1G_1 and G2G_2 with the production rules given below:

G1G_1: S→if E then S∣if E then S else S∣aS \to \textit{if}\ E\ \textit{then}\ S \mid \textit{if}\ E\ \textit{then}\ S\ \textit{else}\ S \mid a

  E→b\quad\ \ E \to b

G2G_2: S→if E then S∣MS \to \textit{if}\ E\ \textit{then}\ S \mid M

  M→if E then M else S∣c\quad\ \ M \to \textit{if}\ E\ \textit{then}\ M\ \textit{else}\ S \mid c

  E→b\quad\ \ E \to b

where if,then,else,a,b,c\textit{if}, \textit{then}, \textit{else}, a, b, c are the terminals.

Which of the following option(s) is/are CORRECT?

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: C, D (official GATE 2025 final answer key)

Concept used: Alternatives sharing a FIRST set break LL(1); the dangling-else construction makes a grammar ambiguous.

First step: In both grammars two alternatives can start with if\textit{if}; then look for two parse trees of if b then if b then c else c\textit{if}\ b\ \textit{then}\ \textit{if}\ b\ \textit{then}\ c\ \textit{else}\ c in G2G_2.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2025 Session 2 CS question paper and final answer key, organised by IIT Roorkee. Question paper · Answer key

More Compiler Design PYQs

PracticePractise Compiler Design questions →Full paperAll GATE CSE 2025 Session 2 questions →