Eliminating Immediate Left Recursion

A grammar is left recursive if we can find some non-terminal $A$ 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:

$$\begin{array}{rcl} A & \rightarrow & A \alpha_1\; \mid\; \ldo... ...\mid\; \beta_1\; \mid\; \ldots\; \mid\; \beta_m \\ \end{array}$$

where each $\alpha_i$ and $\beta_j$ is any mixture of terminals and non-terminals, with the condition that each $\beta_j$ does not begin with $A$.

The essential problem with such productions is that a parser could keep applying some rule $A\; \rightarrow\; A \alpha_i$ 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 $A'$, and replacing the above rule with two new rules:

$$\begin{array}{rcl} A & \rightarrow & \beta_1A'\; \mid\; \ldot... ...\ldots\; \mid\; \alpha_nA'\; \mid\; \varepsilon \\ \end{array}$$

The first rule cannot be left-recursive since no $\beta_j$ begins with $A$, and the second rule will not be left-recursive as long as no $\alpha_i$ is $\varepsilon$.

This process will always work if the left recursion is immediate; however, it will not work if the recursion involves more than one step.