The Gateway to Computer Science Excellence
+7 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$
in Compiler Design by Boss (30.9k points) | 3.3k views
please do not post wrong question....
@ arjun sir this is not the correct question in another pdf it is correct

3 Answers

+12 votes
Best answer
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 .
by Boss (45.4k points)
selected by
+1 vote
Your question is wrong

It should be



A--> Ac / Aad/ epsilon

Then for this Option B is correct !
by Loyal (9.9k points)
yes correct :)
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$


$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

by Loyal (7k points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,391 answers
105,442 users