6,575 views
8 votes
8 votes

Which of the following productions eliminate left recursion in the productions given below:

$S \rightarrow Aa \mid b$

$A \rightarrow Ac \mid Sd \mid \epsilon$

  1. $S \rightarrow Aa \mid b,  A \rightarrow bdA',  A' \rightarrow A'c \mid A'ba \mid A \mid \epsilon$
  2. $S \rightarrow Aa \mid b,  A \rightarrow A' \mid bdA',  A' \rightarrow cA' \mid adA' \mid \epsilon$
  3. $S \rightarrow Aa \mid b,  A \rightarrow A'c \mid A'd ,  A' \rightarrow bdA' \mid cA \mid \epsilon$
  4. $S \rightarrow Aa \mid b,  A \rightarrow cA' \mid adA' \mid bdA',  A' \rightarrow A \mid \epsilon$

3 Answers

Best answer
13 votes
13 votes
S-->Aa / b

A-->Ac / Sd / eps

A-->Ac / Aad /bd / eps

A-->bdA' / A'

A'-->cA' /adA' /eps

Finally Grammar is

S-->Aa / b

A-->bdA' / A'

A'-->cA' /adA' /eps

So option B is correct .
selected by
1 votes
1 votes
Your question is wrong

It should be

S-->Aa/d

and

A--> Ac / Aad/ epsilon

Then for this Option B is correct !
0 votes
0 votes

To convert Left Recursion to Right Recursion, we do this:

$A\rightarrow Ax|y$  $\equiv$ $A\rightarrow yA'$ and $A'\rightarrow xA'|e$

Here, 

$A→Ac∣Sd∣ϵ$ exhibits Left recursion. Expand it.

$A→Ac∣Aad∣bd| e$

Here: identify x's and y's

$x_1 = c$

$x_2 = ad$

$y_1 = bd$

$y_1 = e$

 

So, $A\rightarrow bdA'|A'$

$A'\rightarrow cA'|adA'| e$

 

hence, Option B

Answer:

Related questions

5 votes
5 votes
1 answer
1
makhdoom ghaya asked Apr 25, 2016
4,438 views
Shift reduce parsing belongs to a class ofBottom up parsing.Top down parsing.Recursive parsing.Predictive parsing.
5 votes
5 votes
2 answers
4