Skip to content
GATETECH
Official PYQ · 1996Q2.10Parsing (LL, LR)MCQ1 mark

GATE CS 1996 Q2.10 — Parsing (LL, LR)

Explain with AI

The grammar whose productions are

  • ⟨stmt⟩→ if id then ⟨stmt⟩\langle\text{stmt}\rangle \to\text{ if id then } \langle\text{stmt}\rangle
  • ⟨stmt⟩→ if id then ⟨stmt⟩ else ⟨stmt⟩\langle\text{stmt}\rangle\to\text{ if id then } \langle\text{stmt}\rangle\text{ else } \langle\text{stmt}\rangle
  • ⟨stmt⟩→ id := id\langle\text{stmt}\rangle \to\text{ id }:=\text{ id}

is ambiguous because

if a then if b then c:= d

has more than two parse trees

if a then if b then c:= d

give rise to different parse trees

if a then if b then c:= d else c:= f

has more than two parse trees

if a then if b then c:= d else c:= f

has two parse trees

Choose one option
View worked solution

Answer: D

A grammar is ambiguous if there exists at least one string in its language that has more than one distinct parse tree (or leftmost/rightmost derivation).

The given grammar represents the classic dangling-else problem. Consider the sentence in option D:

if a then if b then c:= d else c:= f

This sentence has exactly two distinct parse trees depending on which if the else clause associates with:

  1. Inner Association: The else belongs to the inner if.
    Structure: if a then (if b then c:= d else c:= f)
  2. Outer Association: The else belongs to the outer if.
    Structure: if a then (if b then c:= d) else c:= f

Since this sentence yields exactly two valid parse trees, the grammar is ambiguous, making D the correct option.

Free practice · Your answers on this page are not saved.

Published
Report a correction
Keep exploringMore Parsing (LL, LR) questions