in Compiler Design
309 views
0 votes
0 votes

Here i am getting ans 8. Please explain

in Compiler Design
309 views

4 Comments

A->cA’/daA’

A’->baA’|aA’|e

B->dB’

B’->bB’|abB’|e

like this ?
0
0
I could be horribly wrong but I don’t think this is accurate, cause the original grammar can generate ‘dba’; but this grammar you have written: all its strings start either with ‘c’ or ‘da’.
0
0

@Amit Mehta  bro I am getting this :-

$A->BaA’|cA’$

$A’->aA’|\epsilon$

$B->cA’B’|dB’$

$B’->bB’|aA’bB’|\epsilon$

1
1

1 Answer

5 votes
5 votes
Best answer
Left recursion is eliminated by converting the grammar into a right recursive grammar.

Consider the grammar with left recursion: $A\rightarrow A\alpha/\beta$

Then we can eliminate left recursion by: $A\rightarrow\beta A’,A’\rightarrow\alpha A’/\epsilon$

Consider the given grammar:

$A → Ba / Aa / c$

$B → Bb / Ab / d$

First eliminate left recursion from $A →  Aa/Ba / c$ we get:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

Now the given grammar is:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

$B → Bb / Ab / d$

Now put the A productions into $B\rightarrow Ab$ we get:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

$B → Bb / BaA’b / cA’b / d$

now remove the left recursion from B’s production we get:

$A → BaA’ / cA’$

$A’ → aA’ / ∈$

$B → cA’bB’ / dB’$

$B’ → bB’ / aA’bB’ / ∈$
selected by

2 Comments

edited by

But look this video same question and its ans matching with mine

https://youtu.be/jCSSxKuQY0w

A->cA’

A’->baA’|aA’|e

B->dB’

B’->bB’|abB’|e

can somebody explain how to remove indirect left recursion because getting confused please?

0
0

Related questions