edited by
6,798 views
37 votes
37 votes

Consider the context-free grammar

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

  1. $5$
  2. $4$
  3. $3$
  4. $2$
edited by

4 Answers

Best answer
33 votes
33 votes

$5$ Parse trees are possible

edited by
47 votes
47 votes

A simpler method is to calculate how many ways the expression can be parsed

((id+id)+(id+id))

((id+(id+id))+id)

(id+((id+id)+id))

(((id+id)+id)+id)

(id+(id+(id+id)))

Note-The parentheses are given just for better understanding....they are not in the grammar for addition.

It's a better time-saving method than drawing parse trees, although parse trees represent the same idea.

 

Edit- Rather than writing all the ways the given expression can be parsed, it can be seen that the answer is 3rd Catalan number i.e number of valid expressions with three sets of parenthesis.

edited by
35 votes
35 votes

Here number of parse tree is equal to number of ways to parenthesize an expression.

It turns out that the number of ways to parenthesize an expression with n+1 terms is Cn, the nth Catalan number.

catalan number

If we set n = 3, we get C3 = 5, confirming that there are five ways to parenthesize four terms.

https://www.johndcook.com/blog/2013/10/03/parenthesize-expression-catalan/

Answer:

Related questions

31 votes
31 votes
2 answers
2
go_editor asked Nov 27, 2016
11,390 views
Consider the following expression grammar. The semantic rules for expression evaluation are stated next to each grammar production.$$\begin{array}{l|l} E\rightarrow numbe...
23 votes
23 votes
4 answers
4