Left Recursion Removal

Question

Remove Left Recursion from the following Context Free Grammar.

$S \rightarrow Aa| Sa|c$

$A \rightarrow Ab|Sd|e$

Comments

Substitute Aa in Place of A->'S'd and Sd in S-> 'A'a

and you get usual recursion removal problem.

---

it will be,

$S->cS'/AaS'$

$S'->aS'/\epsilon$

$A->cS'dA'/eA'$

$A'->bA'/aS'dA'/\epsilon$

---

correct.

Answer 1

$S \rightarrow Aa \ | \ Sa \ | \ c$
$A \rightarrow Ab \ | \ Sd \ | \ e$

First we will remove direct recursion from $S \rightarrow Aa | Sa | c$,

$S \rightarrow AaS' \ | \ cS'$
$S' \rightarrow aS' \ | \ \epsilon $
$A \rightarrow Ab \ | \ Sd \ | \ e$

Then next we can replace productions of $S$ in $A$,

$S \rightarrow AaS' \ | \ cS'$
$S' \rightarrow aS' \ | \ \epsilon $
$A \rightarrow Ab \ | \ AaS'd \ | \  cS'd  \ | \ e$

Next we can remove direct recursion from A,

$S \rightarrow AaS' \ | \ cS'$
$S' \rightarrow aS' \ | \ \epsilon $
$A \rightarrow cS'dA' \ | \ eA'$
$A' \rightarrow bA' \ | \ aS'dA' \ | \ \epsilon$