A grammar is left recursive if we can find some non-terminal which
will eventually derive a sentential form with itself as the left-most symbol.
We have immediate left recursion of there is a rule of the form:
where each and
is any mixture of terminals and
non-terminals, with the condition that each
does not begin
with
.
The essential problem with such productions is that a parser could
keep applying some rule
which will not
ultimately generate some terminal symbol that we can compare with the
input string.
We fix this problem by introducing some new non-terminal , and
replacing the above rule with two new rules:
The first rule cannot be left-recursive since no begins with
, and the second rule will not be left-recursive as long as no
is
.
This process will always work if the left recursion is immediate;
however, it will not work if the recursion involves more than one
step.