The grammar whose productions are <stmt> → if id then <stmt> <stmt> → if id…
1996
The grammar whose productions are
<stmt> → if id then <stmt>
<stmt> → if id then <stmt> else <stmt>
<stmt> → id := id
is ambiguous because
- A.
the sentence if a then if b then c:= d has two parse trees
- 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
- C.
the sentence if a then if b then c:= d else c:= f has more than two parse trees
- D.
the sentence if a then if b then c:= d else c:= f has two parse trees
Attempted by 5 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:
