Left recursion in context-free grammars is when a nonterminal when expanded, results in the same nonterminal symbol in the expansion as the first symbol. If the symbol is present as the first symbol in one of the expansion rules of the nonterminal, it is called a direct left-recursion. Below is a grammar with direct left-recursion. The nonterminal symbol <Ds> has a direct left-recursion.


  1. Prerequisites
  2. Definitions
  3. Artifacts

Important: Pyodide takes time to initialize. Initialization completion is indicated by a red border around Run all button.

An indirect left-recursion occurs when the symbol is found after more than one expansion step. Here is an indirect left-recursion.

Here, <I> has an indirect left-recursion as expanding <I> through <Ds> results in <I> being the first symbol again.

For context-free grammars, in many cases left-recursions are a nuisance. During parsing, left-recursion in grammars can make simpler parsers recurse infinitely. Hence, it is often useful to eliminate them.

It is fairly simple to eliminate them from context-free grammars. Here is a solution.


As before, we start with the prerequisite imports.

Available Packages These are packages that refer either to my previous posts or to pure python packages that I have compiled, and is available in the below locations. As before, install them if you need to run the program directly on the machine. To install, simply download the wheel file (`pkg.whl`) and install using `pip install pkg.whl`.
  1. simplefuzzer-0.0.1-py2.py3-none-any.whl from "The simplest grammar fuzzer in the world".

We need the fuzzer to generate inputs to parse and also to provide some utilities

As before, we use the fuzzingbook grammar style. A terminal symbol has exactly one character (Note that we disallow empty string ('') as a terminal symbol).

We have our grammar:

First, we need to check for left recursion.


Following Moore 1, we will use the following terminology.

  • A symbol X is a direct left corner of a nonetrminal symbol A if there is an expansion rule A -> X alpha, where alpha is any sequence of tokens.

  • A left corner relation is a reflexive transitive closure of the direct left corner relation.

  • A symbol is directly left recursive if it is in the direct left corner of itself.

  • A symbol is left recursive if it has a left corner relation with itself.

  • A symbol is indirectly left recursive if it is left recursive but not directly left recursive.

For this algorithm to work, we need the grammar to not have epsilon productions. You can refer to my previous post for the algorithm for removing epsilon productions.

Using it

Next, to eliminate direct left recursion for the nonterminal <A> we repeat the following transformations until the direct left recursions from <A> are removed.


A -> A alpha_1
  | ...
  | A alpha_2
  | beta_1
  | ..
  | beta_m

such that A -> A alpha_i is an expansion rule of A that contains a direct left recursion, and alpha_i is a sequence of tokens, and A -> beta_j represents an expansion rule without direct left recursion where beta_j is a sequence of tokens, for every beta_j, add a new expansion rule A -> beta_j A’ and for every alpha_i, add A’ -> alpha_i A’ to the grammar. Finally add A’ -> epsilon to the grammar.

Using it

Removing the indirect left-recursion is a bit more trickier. The algorithm starts by establishing some stable ordering of the nonterminals so that they can be procesed in order. Next, we apply an algorithm called Paull's algorithm 1, which is as follows: For any nonterminals Ai and Aj such that i > j in the ordering, and Aj is a direct left corner of Ai, replace all occurrences of Aj as a direct left corner of Ai with all possible expansions of Aj

Using it:

Let us see if the grammar results in the right language

A problem with this algorithm is its exponential case behavior as Moore 2 notes. The solution that Moore offers is to order the nonterminals in the decreasing order of the number of distinct left corners.


The runnable Python source for this notebook is available here.

The installable python wheel removeleftrecursion is available here.

  1. Marvin C. Paull, Algorithm design: a recursion transformation framework, 1988  2

  2. Robert C Moore, Removing Left Recursion from Context-Free Grammars *., 2000