Eliminating Left Recursion without the Epsilon
share
The standard algorithm to eliminate indirect left recursion takes a preventative approach, reorganising a grammar in such a way that indirect left recursion is no longer possible, rather than eliminating it only as and when it occurs. This approach results in many of the grammar's rules being lost, however, so that the resulting parse trees are often devoid of the detail that the grammar was supposed to pick out in the first place. To avoid this pitfall, we extend a revised version of the standard algorithm to eliminate immediate left recursion to a recursive algorithm to explicitly eliminate indirect left recursion. By taking this approach, all of the grammar's original rules are retained, resulting in parse trees that are still useful in practice. A novel quirk of this approach is that the usual empty definitions with ϵ parts are eschewed in favour of optional parts in the right recursive rules that the algorithm generates.
READ FULL TEXT