GATE CSE 2017 Set 2 | Question: 32

Question

Consider the following expression grammar $G$:

• $E \rightarrow E-T \mid T$
• $T \rightarrow T + F \mid F$
• $F \rightarrow (E) \mid id$

Which of the following grammars is not left recursive, but is equivalent to $G$?

• A. $E \rightarrow E-T \mid T$

  $T  \rightarrow T +F \mid F$

  $F \rightarrow (E) \mid id$

• B. $E \rightarrow TE’$

  $E’ \rightarrow -TE’ \mid \epsilon$

  $T \rightarrow T + F \mid F$

  $F \rightarrow (E) \mid id$

• C. $E \rightarrow TX $

  $X \rightarrow -TX \mid \epsilon$

  $T \rightarrow FY$

  $Y \rightarrow +FY \mid \epsilon$

  $F \rightarrow (E) \mid id$

• D. $E \rightarrow TX \mid (TX)$

  $X \rightarrow -TX \mid +TX \mid \epsilon$

  $T \rightarrow  id$

Comments

Arjun sir,

Please verify option d,statement number:-

T−>+FY∣ϵ

Is it Y or X?

---

Also, option c has 5 productions in the actual paper.Please cross check once

Answer 1

Since, the grammar given in the question is left recursive, we need to remove left recursion , 

If Grammar is of form

$A \rightarrow Aα \mid β$

then after removal of left recursion it should be written as

$A \rightarrow βA'$

$A' \rightarrow αA' \mid \epsilon$

Since the grammar is :

$E \rightarrow E - T \mid T$  $($Here $α$ is  '$-T$' and $β$ is $T$$)$

$T \rightarrow T + F \mid F$  $($Here $α$ is  '$+F$' and $β$ is $F$$)$ 

$F \rightarrow (E) \mid id$  $($It is not having left recursion$)$ 

Rewriting after removing left recursion :

$E \rightarrow TE'$ 

$E' \rightarrow  -TE' \mid \epsilon$

$T \rightarrow FT'$

$T' \rightarrow +FT' \mid \epsilon $

$F \rightarrow (E) \mid id$

Now replace $E'$ with $X$ and $T'$ with $Y$ to match with Option C.

$E \rightarrow TX $

$X \rightarrow -TX \mid \epsilon$

$T \rightarrow FY$

$Y \rightarrow +FY \mid  \epsilon$

$F \rightarrow (E) \mid id$

Hence C is correct.

Comments

X -> -TX ∣ +TX ∣ ϵ

in this production isnt + and - having same precedence???

---

Moreover, option (d) is not able to generate (id+id) expression but option (c) and original grammar can.

---

@sushmita

yes.

---

@ Ayush Upadhyaya

d can generate (id+id)

---

can someone tell  a string which belong to d option but not to the gammer given in question.

Two grammars G1 and G2 are equal iff L(g1)=L(g2),

---

@rahul sharma 5

I think they both represent set of all arithmetic expressions over the operators + and -.

But, In grammar given in question '+' is having more precedence than '-' .

eg : If we have a string 1 - 1 + 1

Given grammar evaluates has =1-(1+1) =1-2= -1

Then ,

Option (c) evaluates has = 1-(1+1) =1-2= -1

Option (d) evaluates has

1-(1+1) =1-2= -1         or     (1-1)+1 =0+1=1

Hence , Option(c) is more appropriate.

---

yes.you are correct.thanks

---

Very nice indranil

---

Since there is no production that’s referring to start symbol E again, Option D can only generate parenthesis at most once.

So option D can’t generate (id+(id-id))

Answer 2

option a & b are left recursive...

option D has same priority for - & +

Option-C is the ans

Comments

can you please explain how do we decided upon priority...

Answer 3

This one is te standard example for compiler design. The language originally is 

E -> E+E / E*E / id

As it is ambigous we remove the left recursion and assign prcedence.

Any pproduction of the form 

A -> A alpha / beta 

can be written as 

A-> beta A'

A' -> alpha A' / nulL

Hence C is the correct answer. 

Answer 4

We can mark the option C without much work here,

See option A has left recursion, so we can discard this.
Option B also has left recursion, again we can discard this too.

If we look at option D it's allowing me to have null string.For example, E-> TX  where T and X both can be epsilon, so E can be epsilon or empty which is not supported in the given expression grammar. So we can discard this option too.

Hence C is the correct answer for this. We can check for option C too whether it is correct or not.