The grammar whose productions are <stmt> → if id then <stmt> <stmt> → if id…

1996

 <stmt> → if id then <stmt>

 <stmt> → if id then  <stmt> else <stmt>

 <stmt> → id := id

Answer: D. the sentence if a then if b then c:= d else c:= f has two parse trees — A grammar is defined as ambiguous if there exists at least one string in its language that can produce two or more distinct parse trees (or two or more…

1. A.

   the sentence  if a then if b then c:= d  has two parse trees

2. B.

   the left most and right most derivations of the sentence  if a then if b then c:= d  give rise to different parse trees

3. C.

   the sentence  if a then if b then c:= d else c:= f  has more than two parse trees

4. D.

   the sentence  if a then if b then c:= d else c:= f  has two parse trees

Attempted by 50 students.

Show answer & explanation

Correct answer: D

A grammar is defined as ambiguous if there exists at least one string in its language that can produce two or more distinct parse trees (or two or more distinct leftmost/rightmost derivations).

Let's test the string mentioned in Options C and D:

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

Using the given grammar productions, we can construct two completely different parse trees for this single string depending on which if statement we attach the trailing else clause to: