Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 61 ยท Context-Free Grammars

Eliminating Left Recursion and Left Factoring

See why top-down parsers need grammars without left recursion and with left factoring, learn both algorithms and run them in Python on real grammars.

The grammar you write for humans and the grammar a parser can actually use are often not the same grammar. The arithmetic grammar from the previous lessons, Expr -> Expr + Term | Term, is the most natural description of "a sum is a sum plus a term". It also makes a simple top-down parser run forever. Another common pattern, two alternatives that start with the same words, forces a parser to guess before it has enough information.

Both problems have mechanical cures: eliminating left recursion and left factoring. They rewrite the grammar so that it describes exactly the same language but is friendly to top-down parsers such as recursive descent and LL(1). In this lesson you will learn why the problems arise, how the algorithms work, and you will run both algorithms on grammars written as Python dictionaries (the representation from Context-Free Grammars). Bottom-up parsers do not need either transformation, so this lesson is mainly about the top-down world.

Why top-down parsers get stuck

A top-down parser starts at the start symbol and tries to rebuild a leftmost derivation. For each nonterminal it must decide which production to use, usually by looking at the next token (see Top-Down Parsing Basics). Two grammar shapes make that decision impossible:

  1. Left recursion: A -> A alpha. To parse an A, the parser first has to parse an A, which first has to parse an A, and so on. No token is consumed, and the parser recurses forever (in Python, until RecursionError).
  2. Common prefixes: A -> x y | x z. The next token is x in both cases, so the next token alone cannot choose between the alternatives. A backtracking parser would try one, fail, and try the other, which is slow and makes error messages poor.

Seeing the problem

The program below shows a parse function for Expr -> Expr - num | num that follows the grammar literally, and what happens when it runs. Then it parses the same input with the rewritten grammar:

TEXT
Expr  -> num Expr'
Expr' -> - num Expr' | epsilon
Python Left recursion loops forever; the rewrite does not

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The second half is the important part. The rewritten grammar Expr' -> - num Expr' | epsilon is right-recursive, and a naive reading of it suggests a right-leaning tree, which would give 8 - (4 - 2) = 6. The trick is that the parser passes the tree built so far into expr_rest (an inherited attribute, see Syntax-Directed Translation), and wraps it as the left child of the next node. The grammar changed shape, but the tree and the meaning did not. In practice, hand-written parsers turn the rewritten rule into a loop: while peek() == "-". That is also what EBNF's { ... } stands for.

Eliminating immediate left recursion

Suppose a nonterminal has some left-recursive alternatives and some that are not:

TEXT
A -> A alpha1 | A alpha2 | beta1 | beta2

Every sentence from A must start with one of the betas (the non-recursive alternatives), followed by any number of alphas. So rewrite it as exactly that:

TEXT
A  -> beta1 A' | beta2 A'
A' -> alpha1 A' | alpha2 A' | epsilon

A' ("A prime") is a new nonterminal that generates the repetition. The recursion has moved from the left to the right, and each A' alternative starts with a terminal or a different nonterminal, so the parser always consumes something before recursing.

flowchart LR
    subgraph L["Before: left-recursive"]
        L1["A"] --> L2["A"]
        L1 --> L3["alpha"]
    end
    subgraph R["After: right-recursive"]
        R1["A"] --> R2["beta"]
        R1 --> R3["A'"]
        R3 --> R4["alpha"]
        R3 --> R5["A'"]
    end

The recursion moves from the left edge of the rule to the right edge, where a parser can reach it after consuming input.

The code below implements this for one nonterminal and applies it to every nonterminal in the expression grammar. An empty list means epsilon.

Python Removing immediate left recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The new grammar has five nonterminals instead of three, and Expr' and Term' can be empty. It is less pretty, but every alternative can now be chosen by looking at one token: Expr' continues if the next token is + or -, and ends otherwise. Precedence is untouched, because Factor is still reached through Term, which is reached through Expr.

Indirect left recursion

Left recursion can hide. In this grammar S never starts with S directly:

TEXT
S -> A a | b
A -> A c | S d | epsilon

But S => A a => S d a: starting from S we reach S again at the left edge. This is indirect left recursion. The general algorithm orders the nonterminals A1, A2, ..., An and processes them in turn:

  1. For each Ai, and for each earlier Aj (with j < i), replace every production Ai -> Aj gamma by Ai -> delta gamma for each production Aj -> delta. (This is substitution: it exposes the hidden recursion.)
  2. Then remove the immediate left recursion of Ai as before.

After step 1, any leftover left recursion in Ai is immediate, because a production that began with an earlier nonterminal has been replaced. Productions beginning with a later nonterminal are handled when that later nonterminal is processed.

Python The full algorithm, including indirect recursion

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Follow A by hand. When A is processed, S -> A a | b is already in its final form. The rule A -> S d is substituted with both alternatives of S, giving A -> A a d | b d. Now A has the immediate left recursion A -> A c | A a d, so A becomes A -> b d A' | A' with A' -> c A' | a d A' | epsilon. The result has no left recursion, direct or indirect.

The textbook algorithm assumes the grammar has no cycles (derivations A =>+ A) and works best when epsilon productions are removed first. The grammar above contains an epsilon rule and still comes out right, but do not rely on that for arbitrary grammars. Substitution can also make the grammar noticeably larger, which is one reason many tools prefer to keep the left recursion and use a bottom-up parser instead.

Left factoring

Now the second problem. Look at a statement grammar:

TEXT
Stmt -> if Cond then Stmt
      | if Cond then Stmt else Stmt
      | id = Expr
      | id ( Args )
      | id

Three alternatives start with id, and two start with if Cond then Stmt. With only the next token to go on, a predictive parser cannot choose. Left factoring delays the decision: pull the common prefix out into one production, and let a new nonterminal cover the different endings.

TEXT
A  -> alpha beta1 | alpha beta2     becomes     A  -> alpha A'
                                                A' -> beta1 | beta2

The parser now consumes alpha and only afterwards decides between beta1 and beta2, when it has seen more input. The algorithm is: for each nonterminal, find alternatives that share a first symbol, compute their longest common prefix, introduce the new nonterminal, and repeat, because the new rule may itself contain common prefixes.

Python Left factoring a statement grammar

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After factoring, Stmt can be decided by one token: if or id. Stmt' (the if tail) then looks at the next token: else means take the else branch and anything else means epsilon. That is exactly the dangling-else decision from the previous lesson, and a predictive parser resolves it by taking else whenever it sees it, which attaches it to the nearest if. Stmt'' chooses between =, ( and nothing.

Notice that left factoring does not remove ambiguity. It only postpones a decision. The if rule shows this: the grammar is still ambiguous, and the parser's "always take else" rule is what settles it.

Order of the two transformations

If a grammar needs both, the usual order is: eliminate left recursion first, then left factor. Eliminating left recursion, especially through substitution, can create alternatives with common prefixes (substitution copies right-hand sides), so factoring afterwards cleans them up. After both, the next job is to check whether the grammar is LL(1), which needs the FIRST and FOLLOW sets from the following lesson.

What the transformations cost

  • Readability. The new nonterminals (Expr', Stmt'') mean nothing to a human reader. Document the original grammar and treat the rewritten one as generated.
  • Parse tree shape. The parse tree of the transformed grammar differs from the original. Parsers fix this when they build the abstract syntax tree, as in the expr_rest(left) example, so users never see the artificial nodes. This is why AST design is separate from the grammar.
  • Not always possible. Some grammars cannot be made LL(1) by these two transformations, and some languages are simply not LL(k) for any k. That is a reason to learn the more powerful LR methods.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Why does a naive recursive descent parser loop forever on Expr -> Expr + Term | Term?

    The first symbol of the first alternative is the same nonterminal, so the function calls itself with the input position unchanged.
  2. 2. A -> A x | y. What is the equivalent grammar without left recursion?

    Every sentence is a y followed by zero or more x, so A starts with y and the new nonterminal A' produces the x repetition.
  3. 3. What problem does left factoring solve?

    Factoring pulls the common prefix out and delays the choice until the parser has seen the symbols that differ.
  4. 4. Does eliminating left recursion change the language the grammar generates?

    The transformations are language-preserving. The parser can still build the original left-leaning tree by passing the partial tree along.
  5. 5. In the step for nonterminal Ai, why are productions Ai -> Aj gamma (j < i) substituted?

    Replacing the leading Aj by its alternatives makes any hidden recursion visible on the left edge, where the immediate-recursion rewrite can remove it.

Summary

  • Top-down parsers cannot handle left recursion (infinite recursion) or common prefixes (lookahead cannot choose), so grammars are rewritten first.
  • Immediate left recursion A -> A alpha | beta becomes A -> beta A' and A' -> alpha A' | epsilon.
  • Indirect left recursion is removed by ordering the nonterminals, substituting earlier ones, then applying the immediate rewrite.
  • Left factoring A -> alpha beta1 | alpha beta2 gives A -> alpha A' and A' -> beta1 | beta2, delaying the decision.
  • The language is unchanged; the parse tree shape changes, and a parser restores left associativity by passing the partial tree along (or by looping).
  • Do left-recursion elimination first, then left factoring, then check for LL(1) with FIRST and FOLLOW sets.

Next: FIRST and FOLLOW Sets