DefinitionPermalink

Definition: A grammar $G=(V,T,S,P)$ is left-recursive $⟺$ $\mathrm{\exists }A\in V$ such that $\mathrm{\exists }$ a derivation $A\stackrel{+}{\Rightarrow }A\alpha$, where $\alpha \in (V\cup T{)}^{\ast }$. $◼$

Eliminating Direct Left RecursionPermalink

Consider the easiest case:

where $\alpha ,\beta \in (V\cup T{)}^{\ast }$ and $\beta$ does not begin with $A$.

It can be rewritten to:

and done! The rewriting simply converts left recursion to right recursion.

If we have more productions like:

where $\mathrm{\forall }{\alpha }_i,\mathrm{\forall }{\beta }_j\in (V\cup T{)}^{\ast }$, and $\mathrm{\forall }{\beta }_j$ does not begin with $A$, we can rewrite the same way:

Eliminating Indirect Left RecursionPermalink

Indirect left recursion involves multiple derivation steps, like $\{\begin{array}{l}A\to BC\\ B\to AD\end{array}$ which essentially leads to $A\to ADC$.

Intuition: If we know there would be an indirect left recursion $A\stackrel{+}{\Rightarrow }A\alpha$, we can repeatedly substitute the leftmost variable $B$ in production $A\to B\beta$ until it becomes a direct left recursion.

Problem: How do we find such variable $A$ that is bound to an indirect left recursion? It’ simply not practical to try all variables in $V$.

Method #1: VDG (Variable Dependency Graph) on LHS variables and leftmost variables on RHS. E.g. draw an edge $A\to B$ if $\mathrm{\exists }(A\to B\beta )\in P$. If vertex $A$ has a loop in VDG, then it has an indirect left recursion. $◼$

Method #2: Variable Relabeling:

1. Relabel the variables in some order $A_1,A_2,\dots ,A_n$. Any order should work, but the naive one (left-to-right in any single production, top-down in the production list) is the most straightforward.
2. If there is an indirect left recursion, it must be like $\{\begin{array}{l}{A}_i\to A_j\alpha \\ A_j\to A_i\beta \end{array}$ (or more productions involved, depending on the length of the $A_i$-loop in VDG described above).
3. Therefore whenever we see a production $A_j\to A_i\beta$ where $j>i$, it is possible that $A_i$ has an indirect left recursion.
   • We say “possible” because an $A_i⇝A_j$ path might not exist in the VDG to begin with.

$◼$

However anyway we can just substitute $A_i$ in such $A_j\to A_i\beta$ productions where $j>i$. It suffices to break any $A_i$-loop (if exists) in the VDG.

In the Dragon Book we have the following algorithm:

Note that it uses subscripts $i,j$ the other way, where $j<i$ is guaranteed in the double for-loops.