Q 83_Part B Consider the context-free grammar E → E + E E → (E * E) E → id…
2005
Q 83_Part B
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 non-terminals is {E}.
For the terminal string id + id + id + id, how many parse trees are possible?
- A.
5
- B.
4
- C.
3
- D.
2
Attempted by 64 students.
Show answer & explanation
Correct answer: A
The grammar is ambiguous, and the string 'id + id + id + id' consists of four terminals with only '+' operations. For an associative operation like addition, the number of distinct parse trees for a string with n+1 terminals is given by the (n)th Catalan number. Here, there are 4 id's, so n = 3. The 3rd Catalan number is C_3 = 5. Therefore, there are 5 possible parse trees.