Elimination Of Left Recursive

The goal is to eliminate both direct and indirect left recursive.

Direct Recursive

Single RHS

Let’s start with one single left-recursive Production RHS:

$$ A \to Aa $$

We could create a new Production to solve the recursive:

$$ \begin{aligned} A \to & A' \ A' \to & aA' | \epsilon \ \end{aligned} $$

Multiple RHS

When considering Production with more than one RHS:

$$ A \to Aa | b $$

If we analyze the language this Production will generate, it would be like:

b
baa
baaa
baaaaaaa
...

It's actually equivalent to RegExp b(a*). Knowing this, the previous Production could be converted to the pattern below:

$$ \begin{aligned} A \to & b A' \ A' \to & aA' | \epsilon \ \end{aligned} $$

This Production will produce the same language as the one above.

Conclusion

In general, for a Production like:

$$ \begin{aligned} A \to & Ax_1 | Ax_2 | \cdots | Ax_m \ & | y_1 | y_2 | \cdots | y_n \end{aligned} $$

It could be converted to:

$$ \begin{aligned} A \to & y_1A' | y_2A' | \cdots | y_nA' \ A' \to & x_1A' | x_2A' | \cdots | x_mA' | \epsilon \end{aligned} $$

This rules is acutally the enhanced version of the one in Multiple RHS sectoin.

Indirect Recursive

The idea is to first convert indirect left-recursive into direct recursive, then using the method mentioned above to eliminate.

One algorithm is to use loops to iterate through all Productions to eliminate all possible recursive:

for prod_current in prodcutions:

    # get all productions before prod_current
    for prod_prev in productions.slice(from=0, to=prod_current):
        prod_current.replace_nonterminal_using_production(prod_prev)

    # eliminate direct recursive in modified prod
    prod_current.eliminate_direct_left_recursive() 

Let's see an example:

Check out Compilers-TSU P83 for original example.