The Gateway to Computer Science Excellence
+21 votes

Consider the context-free grammar

$E  \rightarrow E + E$
$E \rightarrow (E * E)$
$E  \rightarrow 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?

  1. $id + id + id + id$
  2. $id + (id* (id * id))$
  3. $(id* (id * id)) + id$
  4. $((id * id + id) * id)$
in Compiler Design by Boss (16.3k points)
edited by | 1.4k views

2 Answers

+21 votes
Best answer

Answer is A.

by Boss (19.9k points)
edited by
For option D to get nested brackets we will have yo use E→(E∗E) twice. We are left only one option to generate + id part. How are you getting 2?

Can you please show the derivation?

My Bad @tusharp. I got two trees coz I ignored the brackets. Option A is the only right choice. Thanks! 


@digvi i m getting 2 parse tree in option D, while ignoring precdence. plz ckeck it.
+5 votes
5 parse trees
by Loyal (8.1k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,578 answers
101,766 users