edited by
10,865 views
32 votes
32 votes

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$?

  1. $E \rightarrow E-T \mid T$

    $T  \rightarrow T +F \mid F$

    $F \rightarrow (E) \mid id$
  2. $E \rightarrow TE’$

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

    $T \rightarrow T + F \mid F$

    $F \rightarrow (E) \mid id$

  3. $E \rightarrow TX $

    $X \rightarrow -TX \mid \epsilon$

    $T \rightarrow FY$

    $Y \rightarrow +FY \mid \epsilon$

    $F \rightarrow (E) \mid id$

  4. $E \rightarrow TX \mid (TX)$

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

    $T \rightarrow  id$

edited by

7 Answers

Best answer
54 votes
54 votes

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.

edited by
16 votes
16 votes
option a & b are left recursive...

option D has same priority for - & +

Option-C is the ans
5 votes
5 votes

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. 

2 votes
2 votes
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.
Answer:

Related questions

39 votes
39 votes
5 answers
1
Madhav asked Feb 14, 2017
9,518 views
Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it:$$\begin{array}{|l|l|}\hline \text{P. Syntax t...
20 votes
20 votes
8 answers
2
Arjun asked Feb 14, 2017
7,722 views
Which of the following statements about parser is/are CORRECT?$\text{Canonical LR}$ is more powerful than $\text{SLR}$$\text{SLR}$ is more powerful than $\text{LALR}$$\te...
47 votes
47 votes
6 answers
4
Madhav asked Feb 14, 2017
17,766 views
Consider the recurrence function$$T(n) = \begin{cases} 2T(\sqrt{n})+1, & n>2 \\ 2, & 0 < n \leq 2 \end{cases}$$Then $T(n)$ in terms of $\Theta$ notation is$\Theta(\log \l...