GATE IT 2005 | Question: 83b

Question

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?

• A. $5$
• B. $4$
• C. $3$
• D. $2$

Comments

Can you please elaborate for what string you want to count the parse trees ? As there are many strings possible using the above grammer.

---

Added that :)

---

Okay :)

---

.

Answer 1

$5$ Parse trees are possible

Comments

How to enumerate all such possible parse trees,especially in exam setting where there is lots of tension due to which there is some chance of missing some trees !!

 

How to tackle such questions ? Is there any better solution rather than enumerating all possible trees ?

---

I think red coloured box should be E –> id

---

One can enumerate atleast this example where we have $4$ $id's$.

First thing, we have to use only $E \to E + E$ production. So from $2$ $E's$ we have to create $4$ $E's$.

So there are these possible cases,

1. Get 2 E's from one E and other 2 E's from another E.

2. Get 3 E's from first E and leave the another E as it is.

3. Keep first E as it is and get 3 E's from second E.

Now, to get 3 E's from 1 E, we again have 2 cases.

So, in total we will have 1 case for (1) and 2 cases for (2) and (3) each.

Answer 2

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.

Comments

Correct thinking.

---

nice

---

nice approach .

Answer 3

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 C_n, the nth Catalan number.

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

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

Comments

@Danishgupta read @tanaya answer you will get why n is used as 3.

---

the problem is quite similar to the DP problem of matrix-chain multiplication. there also we find no of ways to parenthesize the matrix multiplications in given expression.

parenthesization makes it explicit what what production to use at a given time. So there is no ambiguity

---

https://gemini.google.com/share/76785d7b581c

Answer 4

5 parse trees are possible.

Comments

can you elaborate your answer

I could count upto 4 parse trees

---

this is 5th..