328 views

Consider the following grammar: $G$ $E \rightarrow E+E \mid E-E \mid E^*E \mid (E)\mid \text{id}$

The number of derivation trees for the string $\text{id} +\text{id} ^* \text{id} – \text{id}$ is:

1. $5$
2. $6$
3. $7$
4. $8$

how 5? because i m getting only 4

@Bikram sir, I am getting 6. . . please check .. which one is redundant.

E--> E+E | E-E |E*E| (E)|id

id+id*id-id

1. E -> E+E

E -> E + E * E

E -> E + E * E - E

-> id + id * id - id

2. E -> E+E

E -> E + E - E

E -> E + E * E - E

-> id + id * id - id

3. E -> E*E

E -> E + E * E

E -> E + E * E - E

-> id + id * id - id

4. E -> E*E

E -> E * E - E

E -> E + E * E - E

-> id + id * id - id

5. E -> E - E

E -> E * E - E

E -> E + E * E - E

-> id + id * id - id

6. E -> E-E

E -> E + E - E

E -> E + E * E - E

-> id + id * id - id

i think 3rd one with 1st
edited by
ohhh.. got it.. actually, it is 3 and 4 ... each has same derivation tree.

Ans 5 is correct.

Thanks ..: )

Here is the solution by setting all possible associativity

### 1 comment

E--> E+E | E-E |E*E| (E)|id

id+id*id-id

1. E -> E+E

E -> E + E * E

E -> E + E * E - E

-> id + id * id - id

2. E -> E+E

E -> E + E - E

E -> E + E * E - E

-> id + id * id - id

3. E -> E*E

E -> E + E * E

E -> E + E * E - E

-> id + id * id - id

4. E -> E - E

E -> E * E - E

E -> E + E * E - E

-> id + id * id - id

5. E -> E-E

E -> E + E - E

E -> E + E * E - E

-> id + id * id - id
by

1
582 views