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

here we need to remove left recursion

E->TE'

E'->-TE'/ epsilon

T->FT'

T->+FT'/ epsilon

F->(E)/id

above by applying rule

A->Ax/y then

A->yA'

A'->xA'/ epsilon

were by expansion of the same we got the same strings.

Answer 2

option C

Comments

Can we say that left recursion of grammar does not produce same language as the original grammar..?

Answer 3

Options A and B shows left recursion, while option D can’t make a parse tree for the following input for which the given CFG can make.