Menu
I've seen this algorithm one should be able to use to remove all left recursion. Yet I'm running into problems with this particular grammar:
A -> Cd
B -> Ce
C -> A | B | f
Whatever I try I end up in loops or with a grammar that is still indirect left recursive.
What are the steps to properly implement this algorithm on this grammar?
916
Left Recursion can be eliminated by introducing new non-terminal A such that. This type of recursion is also called Immediate Left Recursion.
Removing left recursion Left recursion often poses problems for parsers, either because it leads them into infinite recursion (as in the case of most top-down parsers) or because they expect rules in a normal form that forbids it (as in the case of many bottom-up parsers, including the CYK algorithm).
Due to the presence of left recursion some top-down parsers enter into an infinite loop so we have to eliminate left recursion. The nonterminal A generates the same strings as before but is no longer left recursive.
Rule is that you first establish some kind of order for non-terminals, and then find all paths where indirect recursion happens.
In this case order would be A < B < C, and possible paths for recursion of non-terminal C would be
C=> A => Cd
and
C=> B => Ce
so new rules for C would be
C=> Cd | Ce | f
now you can simply just remove direct left recursion:
C=> fC'
C'=> dC' | eC' | eps
and the resulting non-recursive grammar would be:
A => Cd
B => Ce
C => fC'
C' => dC' | eC' | eps
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
