1
$\begingroup$

Im currently learning about removing left recursion. Ive watched a few youtube clips and understand the basics. For example, i can remove left recursion for the following;

$E \rightarrow E+T \mid T$

Answer

$E \rightarrow TE'$

$E'\rightarrow \varepsilon \mid +TE'$

Ive been given the following question which has sort of 3 parts to it and has me confused a lot (compared to the question example above). The question is remove the left recursion from the following grammar;

$A \rightarrow Ba$

$B \rightarrow dab \mid cB$

$C\rightarrow cB\mid Ac$

Is there another rule to follow for this, or when it has more than 1 statement as such.

Any help will be much appreciated

$\endgroup$
  • $\begingroup$ The $C$ rules can't be reached (assuming $A$ is the starting nonterminal), should on of the $c$s be a $C$? $\endgroup$ – Luke Mathieson May 9 '15 at 5:48
  • 1
    $\begingroup$ Please, watch your syntax. Use a capital "I"in the first person, and use apostrophy where needed: "Im" is not proper English syntax. $\endgroup$ – babou May 9 '15 at 10:49
1
$\begingroup$

The fact confusing you might be, that the given grammar isn't left recursive at all and so nothing has to be done.

To be left recursive there would have to be a nonterminal Symbol, that by a chain of productions results in a sequence of sybols starting with the same nonterminal.

This is not true for A since after A -> B the only options available are A -> B -> dab and A -> B -> cB both already starting with terminal symbols on the left.

Trivially the same goes for B as B -> dab and B -> cB are the only options.

Taking a look at C the production C -> cB can't cause any trouble, since the sequence is already starting with a terminal.

But even the second option C -> Ac is harmless, as after C -> Ac -> Bac the only options are C -> Ac -> Bac -> dabac and C -> Ac -> Bac -> cBac, both starting with a terminal symbol again.

$\endgroup$
  • $\begingroup$ Would you not substitute B into A and then C into A, resulting in one recursive function? $\endgroup$ – Edwin May 9 '15 at 16:16
  • $\begingroup$ The only productions available for B are dab and cB ! Thus step 1 of your question "substitute B into A" is not possible. It is only possible to 'substitute' B into dab or cB. $\endgroup$ – mikyra May 10 '15 at 18:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.