Q83 Part_A Consider the context-free grammar E → E + E E → (E * E) E → id…
2005
Q83 Part_A
Consider the context-free grammar
E → E + E
E → (E * E)
E → id
where E is the starting symbol, the set of terminals is {id, (,+,),*}, and the set of nonterminals is {E}.
Which of the following terminal strings has more than one parse tree when parsed according to the above grammar?
- A.
id + id + id + id
- B.
id + (id* (id * id))
- C.
(id* (id * id)) + id
- D.
((id * id + id) * id)
Attempted by 70 students.
Show answer & explanation
Correct answer: A
The grammar E → E + E allows left and right recursion, leading to ambiguity. The string 'id + id + id + id' can be parsed in multiple ways due to the associative nature of addition. For example, it can be grouped as ((id + id) + id) + id or id + (id + (id + id)), resulting in more than one parse tree. The other options involve parentheses that enforce a unique structure, eliminating ambiguity. Thus, option A is the only one with multiple parse trees.