Lesson 2.4 — Grammar transformations for top-down parsing¶

Techniques: direct left-recursion removal, Paull's algorithm for indirect left recursion (textbook and SCC-restricted), left factoring · Pebble implements: all three (lab exercises E7, E8) · Lab: labs/ch02-ll1-toolkit (SPEC, contract eliminateLeftRecursion, leftFactor; ll1 transform) · Prerequisites: Lesson 2.3 · Time: 3–4 hours

The natural way to write "a sum is a sum plus a term" is \(E \to E + T\), and the natural way to write if-statements is to list both forms. A top-down parser can use neither: \(E \to E + T\) makes a recursive-descent parser call itself forever without reading a token, and two alternatives that both begin \(i\, E\, t\, S\) give a FIRST/FIRST conflict. This lesson rewrites such grammars into equivalent ones (same language) that a predictive parser can use, proves that the rewrites preserve the language, and shows what they cost: bigger grammars, different trees, and no help at all against ambiguity.

1. Problem and motivation¶

Input: a grammar \(G\). Output: a grammar \(G'\) with \(L(G') = L(G)\), no left recursion, and no two alternatives of one nonterminal with a common first symbol. \(G'\) is then often LL(1), but not always: an ambiguous grammar's language may have no LL(1) grammar at all. In a compiler these rewrites happen once, by the grammar author or the parser generator, before the table of Lesson 2.3 is built; hand-written parsers apply the same ideas as loops (while (Tok.is(tok::plus))) and shared prefixes.

Direct left-recursion removal¶

\(A \to A \alpha \mid \beta\) generates \(\beta\) followed by any number of \(\alpha\)'s; so does \(A \to \beta A'\), \(A' \to \alpha A' \mid \varepsilon\), which is right-recursive. The rewrite is folklore of the early top-down compilers and is the base case of Greibach's normal-form construction [Gre65]; textbooks present it as the first step of making a grammar LL(1) [ALSU07 §4.3.3].

Paull's algorithm (indirect left recursion)¶

Left recursion can go through other nonterminals: \(S \to A\, a\), \(A \to S\, d\) gives \(S \Rightarrow A\, a \Rightarrow S\, d\, a\). Ordering the nonterminals and substituting earlier ones into later ones turns every indirect left recursion into a direct one, which the first technique removes. The algorithm is known as Paull's algorithm [Moo00]; it is the construction behind Greibach normal form [Gre65; HU79 §4.6] and Algorithm 4.19 of the Dragon book [ALSU07 §4.3.3]. The course's version restricts substitution to the nonterminals that can actually close a cycle (the left-corner strongly connected components), which avoids blowing up grammars that are not left-recursive at all.

Left factoring¶

\(S \to i\, E\, t\, S \mid i\, E\, t\, S\, e\, S\) cannot be decided with one token, but both alternatives agree on their first four symbols, so the parser can postpone the choice: \(S \to i\, E\, t\, S\, S'\) with \(S' \to e\, S \mid \varepsilon\). Left factoring is the standard companion of left-recursion removal [ALSU07 §4.3.4]; it is exactly what hand-written parsers do when they parse the common part first and then test for else.

2. Definitions and algorithms¶

Definition 2.4.1 (Left recursion)

\(A \in N\) is left-recursive if \(A \Rightarrow^{+} A \gamma\) for some \(\gamma\). It is directly left-recursive if some production is \(A \to A \gamma\), indirectly otherwise; the left recursion is hidden if it passes through a nullable prefix (\(A \to B A \gamma\) with \(B \Rightarrow^{*} \varepsilon\)). \(G\) is cycle-free if no \(A \Rightarrow^{+} A\), and \(\varepsilon\)-free if it has no \(A \to \varepsilon\) (except possibly \(S \to \varepsilon\) with \(S\) on no right side).

Definition 2.4.2 (Left-corner graph)

The left-corner graph of \(G\) has vertex set \(N\) and an edge \(A \to B\) whenever \(A \to \alpha B \beta \in P\) with \(\alpha\) nullable. Then \(A \Rightarrow^{+} B \gamma\) for some \(\gamma\) iff \(B\) is reachable from \(A\) by a non-empty path; in particular \(A\) is left-recursive iff it lies on a cycle. The left-corner SCC of \(A\), \(\mathrm{SCC}(A)\), is its strongly connected component.

Left-corner graphs of the two running grammars

In \(G_4\) (§3), \(E \to E + T \mid T\) gives the edges \(E \to E\) and \(E \to T\): \(\{E\}\) is an SCC with a cycle, so \(E\) is directly left-recursive. In \(G_{4.20}\), \(S \to A\, a\) and \(A \to S\, d\) give \(S \to A \to S\): \(\{S, A\}\) is one SCC and both are indirectly left-recursive.

Definition 2.4.3 (Common prefix, fresh names, equivalence)

For alternatives \(A \to \alpha \beta_1 \mid \cdots \mid \alpha \beta_k\) (\(k \ge 2\)), their longest common prefix is the longest \(\alpha\) that begins all of them; a group of \(A\) is the set of all alternatives of \(A\) that start with one given symbol, when it has at least two members. \(\mathrm{fresh}(A)\) is the first unused name among \(A'\), \(A''\), \(A'''\), …. Two grammars are equivalent if they have the same terminals and \(L(G) = L(G')\); a transformation is language-preserving if \(L_{G'}(X) = L_G(X)\) for every original nonterminal \(X\). Transformations may change the trees.

Direct left-recursion removal¶

Algorithm 2.4.4 (RemoveDirect)

Input: the alternatives of one nonterminal \(A\).
Output: equivalent alternatives for \(A\) and, if needed, a fresh \(A'\).
Precondition: some alternative does not start with \(A\) (else \(A\) derives nothing); no \(A \to A \alpha\) with \(\alpha\) nullable (a cycle).
Postcondition: no alternative of \(A\) or \(A'\) starts with \(A\); \(L(A)\) is unchanged (Theorem 2.4.7).
Invariant: the tails \(\alpha\) and bases \(\beta\) keep their relative order.

function RemoveDirect(A, alts):
    alts ← alts − {A → A}                               # A → A adds no strings
    αs ← [ α : A → A α ∈ alts ]                          # the "tails"
    βs ← [ β : A → β ∈ alts, β does not start with A ]  # the "bases", in order
    if αs is empty: return (alts, none)
    if βs is empty: fail "A has only left-recursive alternatives: it derives no terminal string"
    A′ ← fresh(A)
    return ( [ A → β A′ for β in βs ],  [ A′ → α A′ for α in αs ] + [ A′ → ε ] )

ANTLR 4 removes direct left recursion for you

Reproduce (ANTLR 4.13.2 complete jar, OpenJDK 21.0.10; download antlr-4.13.2-complete.jar from antlr.org):

cat > Expr.g4 <<'EOF'
grammar Expr;
e  : e '*' e | e '-' e | '(' e ')' | ID ;
ID : [a-z]+ ;
WS : [ \t\r\n]+ -> skip ;
EOF
java -jar antlr-4.13.2-complete.jar Expr.g4
javac -cp antlr-4.13.2-complete.jar Expr*.java
echo 'a - b - c * d' | java -cp antlr-4.13.2-complete.jar:. org.antlr.v4.gui.TestRig Expr e -tree
grep -n 'precpred' ExprParser.java

Output (complete):

(e (e (e a) - (e b)) - (e (e c) * (e d)))
168:                        if (!(precpred(_ctx, 4))) throw new FailedPredicateException(this, "precpred(_ctx, 4)");
180:                        if (!(precpred(_ctx, 3))) throw new FailedPredicateException(this, "precpred(_ctx, 3)");
217:            return precpred(_ctx, 4);
219:            return precpred(_ctx, 3);

What to notice: ANTLR is a top-down tool, yet it accepts the directly left-recursive rule e. LeftRecursiveRuleTransformer.translateLeftRecursiveRules [ANTLR4-LeftRec] rewrites it into the loop form of §6 ("EBNF iteration"): a base alternative followed by ( '*' e | '-' e )*, with precedence predicates precpred(_ctx, 4) for * and precpred(_ctx, 3) for - (earlier alternatives bind tighter [ANTLR4-LeftRecDoc]). The tree is still left-nested, ((a - b) - (c * d)): the loop rebuilds the associativity that plain RemoveDirect would turn into a right-nested chain of \(E'\) nodes.

Paull's algorithm (indirect left recursion)¶

Algorithm 2.4.5 (Paull, textbook and SCC-restricted)

Input: \(G\) and a flag textbook.
Output: an equivalent \(G'\) without left recursion, or an error.
Precondition: \(G\) cycle-free. If \(G\) is also \(\varepsilon\)-free the algorithm always succeeds (Theorem 2.4.10); with \(\varepsilon\)-productions it may report hidden left recursion.
Postcondition: on success \(G'\) has no left-recursive nonterminal (checked in step (c)) and \(L_{G'}(X) = L_G(X)\) for every original \(X\).
Invariant: after iteration \(i\), every alternative of \(A_k\) (\(k \le i\)) starts with a terminal, with \(\varepsilon\), with a primed nonterminal, or with \(A_j\) for some \(j > k\); in the SCC-restricted version also possibly with an \(A_j\), \(j < k\), from a different left-corner SCC (Lemma 2.4.9).

Reference solution: solutions/labs/ch02-ll1-toolkit/src/Transform.cpp; contract ll1::eliminateLeftRecursion (SCC-restricted).

function Paull(G, textbook):
    A1 … An ← the nonterminals in grammar order
    SCC ← LeftCornerSCCs(G)                           # computed once, on the input grammar
    for i ← 1 to n:
        for j ← 1 to i − 1:                                               # (a) substitute
            if not textbook and Aj ∉ SCC(Ai): continue
            replace every Ai → Aj γ by Ai → δ1 γ | … | δk γ, where Aj → δ1 | … | δk now
            remove duplicate alternatives of Ai (keep the first)
        (Ai's alternatives, new) ← RemoveDirect(Ai, Ai's alternatives)    # (b)
        output Ai, then new (if any) right after it
    if the result still has a left-recursive nonterminal B:               # (c) check
        fail "hidden left recursion through a nullable prefix remains in B"
    return the result

function LeftCornerSCCs(G):
    nullable ← Nullable(G)                            # Lesson 2.2
    edges ← { A → B : A → α B β, α nullable }
    reach(A) ← nonterminals reachable from A along edges (a DFS from A)
    return A ↦ { B : B ∈ reach(A) and A ∈ reach(B) }

ANTLR 4 rejects indirect left recursion

Reproduce (ANTLR 4.13.2, OpenJDK 21.0.10):

cat > Mutual.g4 <<'EOF'
grammar Mutual;
s : a 'a' | 'b' ;
a : a 'c' | s 'd' | ;
EOF
java -jar antlr-4.13.2-complete.jar Mutual.g4

Output (complete; exit status 1):

error(119): Mutual.g4::: The following sets of rules are mutually left-recursive [s, a]

What to notice: this is \(G_{4.20}\) from §3 (the Dragon book's example for Algorithm 4.19). ANTLR computes the same left-corner SCC \(\{S, A\}\) as LeftCornerSCCs and reports it (error 119, LEFT_RECURSION_CYCLES in tool/src/org/antlr/v4/tool/ErrorType.java) instead of running Paull's algorithm, because the rewritten grammar would be unreadable and its trees unrelated to the author's rules [ANTLR4-LeftRecDoc]. §3 shows what Paull's algorithm would produce.

Left factoring¶

Algorithm 2.4.6 (LeftFactor)

Input: \(G\).
Output: an equivalent \(G'\) in which no two alternatives of one nonterminal start with the same symbol.
Precondition: none.
Postcondition: no nonterminal of \(G'\) has a group (Definition 2.4.3); \(L_{G'}(X) = L_G(X)\) for every original \(X\) (Theorem 2.4.11).
Invariant: every step replaces one group of \(A\) by one alternative \(A \to \alpha A'\) and gives \(A'\) the group's suffixes; the potential \(\Psi\) (total length of all alternatives that belong to a group) strictly decreases.

Reference solution: solutions/labs/ch02-ll1-toolkit/src/Transform.cpp; contract ll1::leftFactor.

function LeftFactor(G):
    order ← the nonterminals in grammar order
    repeat
        changed ← false
        for each A in order:
            group ← the first group of A (by its first member): all alternatives
                    of A that start with the same symbol, if there are ≥ 2
            if group is empty: continue
            α ← the longest common prefix of the group
            A′ ← fresh(A);  insert A′ into order right after A (and after A's earlier primes)
            replace the group's first member by A → α A′ and delete the other members
            A′'s alternatives ← [ β : A → α β in the group ], duplicates removed (β may be ε)
            changed ← true;  break                     # restart the scan
    until not changed
    return G with the productions grouped by order

CPython 3.8's pgen left-factors inside a rule by subset construction

Reproduce (CPython source at tag v3.8.0, run with Python 3.11.15; needs network for the clone):

git -c advice.detachedHead=false clone -q --depth 1 --filter=blob:none --sparse -b v3.8.0 https://github.com/python/cpython
cd cpython && git sparse-checkout set Parser/pgen Grammar
cat > ifstmt.gram <<'EOF'
file_input: stmt ENDMARKER
stmt: 'if' NAME ':' NAME | 'if' NAME ':' NAME 'else' ':' NAME | NAME
EOF
python3 -m Parser.pgen -v ifstmt.gram Grammar/Tokens /dev/null /dev/null \
  | sed -n '/^Dump of DFA for stmt/,/^First set for file_input/p'

Output (complete):

Dump of DFA for stmt
  State 0 
    'if' -> 1
    NAME -> 2
  State 1 
    NAME -> 3
  State 2 (final)
  State 3 
    ':' -> 4
  State 4 
    NAME -> 5
  State 5 (final)
    'else' -> 6
  State 6 
    ':' -> 7
  State 7 
    NAME -> 2
  State 8 (final)
First set for file_input

What to notice: the two if alternatives share the prefix 'if' NAME ':' NAME, a group in the sense of Definition 2.4.3, yet pgen raises no conflict (compare the FIRST/FIRST error in Lesson 2.3). Each rule's right side is a regular expression, and pgen turns its NFA into a DFA by subset construction (Ch 1) [CPY38-pgen]: states 0 → 1 → 3 → 4 → 5 are the common prefix, and state 5 is final (the \(S' \to \varepsilon\) case) with an 'else' edge (the \(S' \to e\, S\) case). That is Algorithm 2.4.6 performed automatically, but only within one rule; state 8 is an unreachable leftover of the construction.

3. Worked example¶

Running example (direct left recursion and a common prefix in one grammar), and Dragon book Example 4.20 for indirect left recursion:

G4:  (1) S → i E t S          (4) E → E + T      (6) T → ( E )        G4.20:  S → A a | b
     (2) S → i E t S e S      (5) E → T          (7) T → x                    A → A c | S d | ε
     (3) S → a

Left-corner graphs (an edge A → B means B can be A's leftmost symbol): in G4, E has a self-loop, so {E} is an SCC with a cycle; in G4.20, S → A and A → S form one SCC.

flowchart LR
  subgraph G4only ["G4"]
    E[E] --> E
    E --> T[T]
  end
  subgraph G420 ["G4.20"]
    S[S] --> A[A]
    A --> A
    A --> S
  end

Direct left-recursion removal on the running example¶

step	Ai	action	Ai's alternatives afterwards
1	S	no direct left recursion	i E t S \| i E t S e S \| a
2	E	αs = [+ T], βs = [T]; new E′	E → T E′; E′ → + T E′ \| ε
3	T	no direct left recursion	( E ) \| x

The tree changes shape: x + x + x was left-nested under \(E \to E + T\); now it is a right-nested chain of \(E'\) nodes. Lesson 2.5 shows how a parser rebuilds the left-associative AST anyway (and ANTLR does it with a loop, real-world box in §2).

Paull's algorithm on the running example¶

\(G_{4.20}\), order S, A; \(\mathrm{SCC}(S) = \mathrm{SCC}(A) = \{S, A\}\) (oracle trace of eliminate_left_recursion):

step	Ai	action	Ai's alternatives afterwards
1	S	j < 1: nothing to substitute; no direct left recursion	A a \| b
2	A	substitute S (same SCC): A → S d becomes A → A a d \| b d	A c \| A a d \| b d \| ε
3	A	RemoveDirect: αs = [c, a d], βs = [b d, ε]; new A′	A → b d A′ \| A′; A′ → c A′ \| a d A′ \| ε

Result: \(S \to A\, a \mid b\); \(A \to b\, d\, A' \mid A'\); \(A' \to c\, A' \mid a\, d\, A' \mid \varepsilon\), the Dragon book's answer. The check (c) passes although \(G_{4.20}\) has an \(\varepsilon\)-production: \(A \to A'\) with \(A'\) nullable could hide left recursion only if \(A'\) led back to \(A\), and it does not. Both grammars derive the same 28 sentences of length \(\le 6\) (language_upto).

On \(G_4\) Paull does exactly the direct removal above: no two nonterminals share an SCC. The textbook version (no SCC test) would behave the same on \(G_4\) but not on tests/ch02/Inputs/json.grammar: Value comes before Elems, and Elems → Value MoreV starts with Value, so Algorithm 4.19 substitutes Value's seven alternatives into Elems although nothing is left-recursive (18 productions become 24; the SCC version returns the grammar unchanged).

Left factoring on the running example¶

After the removal, \(S\) still has two alternatives starting with \(i\):

step	nonterminal	group	longest common prefix α	result
1	S	(1) i E t S, (2) i E t S e S	i E t S	S → i E t S S′ \| a; S′ → ε \| e S
2	S, S′, E, E′, T	none	—	no change: done

S  → i E t S S' | a       E  → T E'            T → ( E ) | x
S' → ε | e S              E' → + T E' | ε

Every transformation succeeded, and the result is still not LL(1): \(M[S', e] = \{S' \to \varepsilon, S' \to e\, S\}\) is the dangling-else FIRST/FOLLOW conflict of Lesson 2.3. \(G_4\) is ambiguous. Its language does have unambiguous grammars (matched/unmatched statements [ALSU07 §4.3.2]), but none of them is LL(1): the dangling else is the classical example of a language with no LL(k) grammar, because a top-down parser would have to decide, before seeing the es, which pending i each of them closes. No transformation can help: the conflict has to be resolved by priority (Proposition 2.3.12).

Try it

./course drill left-recursion --seed 7 --difficulty medium (indirect) or --difficulty hard (indirect + \(\varepsilon\) + left factoring, answer must be LL(1)). Any equivalent grammar earns full marks: the checker compares languages up to a length bound.

4. Invariants and correctness¶

All proofs work with parse trees; "\(t\) is a tree of \(X\)" means a tree with root \(X\) in the grammar at hand, and \(L(X)\) is the set of their yields.

Direct left-recursion removal¶

Theorem 2.4.7 (RemoveDirect preserves the language)

Let \(G'\) result from \(G\) by applying Algorithm 2.4.4 to \(A\), with \(A \to A \alpha_1 \mid \cdots \mid A \alpha_m \mid \beta_1 \mid \cdots \mid \beta_n\) (\(n \ge 1\)). Then \(L_{G'}(X) = L_G(X)\) for every \(X \in N\), and

\[ L(A) = L(\beta_1 \mid \cdots \mid \beta_n) \cdot L(\alpha_1 \mid \cdots \mid \alpha_m)^{*}, \qquad L_{G'}(A') = L(\alpha_1 \mid \cdots \mid \alpha_m)^{*}. \]

No alternative of \(A\) or \(A'\) starts with \(A\).

Proof

By induction on tree height, simultaneously for all nonterminals (the other nonterminals' productions are identical in \(G\) and \(G'\), so it suffices to handle nodes labelled \(A\)). \(G\) to \(G'\). In a \(G\)-tree with root \(A\), follow the spine: the root's leftmost child while it is an \(A\) expanded by some \(A \to A \alpha_{i}\). The spine has \(k \ge 0\) such nodes (finitely many, trees are finite) and ends in a node expanded by some \(A \to \beta_j\). The yield is \(y(\beta_j)\, y(\alpha_{i_k}) \cdots y(\alpha_{i_1})\), where \(i_1\) is at the root. In \(G'\), build \(A \to \beta_j A'\), then \(A' \to \alpha_{i_k} A'\), …, \(A' \to \alpha_{i_1} A'\), \(A' \to \varepsilon\), reusing the subtrees for \(\beta_j\) and the \(\alpha\)'s, converted by the induction hypothesis (they are lower). Same yield. \(G'\) to \(G\). Every \(G'\)-tree of \(A\) is of this shape (the only productions of \(A\) are \(A \to \beta_j A'\) and \(A'\) only produces \(\alpha A'\) or \(\varepsilon\)), and the construction reverses. The displayed formula is the spine decomposition read as languages. The removed \(A \to A\) only adds trees that contract to smaller trees with the same yield. No leading \(A\): the \(\beta\)'s do not start with \(A\) by definition, and \(A'\)'s alternatives start with an \(\alpha\) or are \(\varepsilon\).

No new left recursion. \(A' \to \alpha A'\) is left-recursive only if some \(\alpha \Rightarrow^{*} \varepsilon\) (then \(A \Rightarrow A \alpha \Rightarrow^{*} A\) is a cycle, excluded by the precondition) or \(\alpha \Rightarrow^{*} A' \cdots\) (\(A'\) is new and occurs only at the end of \(A\)'s alternatives, so this would need \(\alpha \Rightarrow^{*} A \cdots \Rightarrow \beta A' \cdots\) with \(\beta\) nullable, which is again a hidden left recursion through \(A\)). When it breaks: if every alternative is left-recursive, \(\beta\)s is empty and \(A\) derives nothing; the algorithm reports it rather than silently dropping \(A\).

Paull's algorithm (indirect left recursion)¶

Lemma 2.4.8 (Substitution preserves the language)

Replacing a production \(A_i \to A_j \gamma\) (\(i \ne j\)) by \(A_i \to \delta_1 \gamma \mid \cdots \mid \delta_k \gamma\), where \(A_j \to \delta_1 \mid \cdots \mid \delta_k\) are all current alternatives of \(A_j\), preserves \(L(X)\) for every \(X\).

Proof

A tree node \(A_i\) using \(A_i \to A_j \gamma\) has a first child \(A_j\) that uses some \(A_j \to \delta_r\); merge the two levels into one node using \(A_i \to \delta_r \gamma\) with the same children in the same order. Conversely, a node using the new \(A_i \to \delta_r \gamma\) splits into the two levels. Both operations keep the yield, and repeating them bottom-up (induction on the number of affected nodes) maps trees of one grammar to trees of the other.

Lemma 2.4.9 (Paull invariant)

Let \(G\) be cycle-free and \(\varepsilon\)-free. After iteration \(i\) of the textbook algorithm, every alternative of \(A_k\), \(k \le i\), starts with a terminal or with \(A_j\) for some \(j > k\) (primed nonterminals never occur first in an \(A_k\)-alternative). In the SCC-restricted version, an alternative of \(A_k\) may also start with \(A_j\), \(j < k\), where \(A_j \notin \mathrm{SCC}(A_k)\).

Proof

By induction on \(i\). Consider iteration \(i\). Before it, an alternative of \(A_i\) may start with any \(A_j\). Step (a) processes \(j = 1, 2, \dots, i - 1\) in increasing order. Substituting \(A_j\) replaces a leading \(A_j\) by \(A_j\)'s alternatives, which (induction hypothesis, since \(j < i\) was processed in an earlier iteration) start with a terminal or with \(A_{j'}\), \(j' > j\); \(\varepsilon\)-freeness guarantees that \(\delta_r \gamma\) starts with the first symbol of \(\delta_r\), not with a symbol of \(\gamma\). So after handling \(j\), no alternative of \(A_i\) starts with \(A_1, \dots, A_j\), and after \(j = i - 1\) every leading nonterminal has index \(\ge i\). RemoveDirect then removes leading \(A_i\), and \(A_i\)'s new alternatives \(\beta A_i'\) start with the first symbol of \(\beta\), index \(> i\) or terminal. Earlier \(A_k\) (\(k < i\)) are not modified. In the restricted version, substitutions with \(A_j \notin \mathrm{SCC}(A_i)\) are skipped, which leaves exactly those leading symbols.

Theorem 2.4.10 (Correctness of Paull's algorithm)

If \(G\) is cycle-free and \(\varepsilon\)-free, both versions of Algorithm 2.4.5 terminate, succeed, and return \(G'\) with \(L_{G'}(X) = L_G(X)\) for every original \(X\) and no left-recursive nonterminal. With \(\varepsilon\)-productions the result is still equivalent whenever step (c) passes.

Proof sketch (textbook version in full: [HU79, §4.6, Lemmas 4.3–4.4]; [ALSU07 §4.3.3])

Language: each step is either a substitution (Lemma 2.4.8) or RemoveDirect (Theorem 2.4.7), and removing duplicate alternatives does not change any language. Termination: \(n\) iterations of finitely many finite substitutions. No left recursion, textbook: by Lemma 2.4.9 a leftmost derivation step from \(A_k\) produces a leading \(A_j\) with \(j > k\) or a terminal, and primed nonterminals only lead with symbols that came from the tails \(\alpha\) (the same argument as in Theorem 2.4.7); a cycle \(A_k \Rightarrow^{+} A_k \cdots\) would need the leading index to return to \(k\), impossible for a strictly increasing sequence. No left recursion, SCC-restricted: substitution only merges derivation steps, so it never adds a left-corner edge between two SCCs of the input's left-corner graph that did not already have a path; hence any cycle of the output lies inside one input SCC, and inside one SCC every substitution the textbook version would do is done, so its argument applies. With \(\varepsilon\): the invariant can fail (a leading nullable symbol exposes the next one), which is why step (c) re-checks the result.

When it breaks: tests/ch02/Inputs/hidden-left-recursion.grammar (\(S \to A\, S\, a\) with \(A \to c \mid \varepsilon\)) is left-recursive only through the nullable \(A\); step (c) detects it, and the fix is to remove \(\varepsilon\)-productions first. With cycles (\(A \Rightarrow^{+} A\)) the result is not defined.

Left factoring¶

Theorem 2.4.11 (Left factoring terminates and preserves the language)

Algorithm 2.4.6 terminates on every grammar, the result has no group, and \(L_{G'}(X) = L_G(X)\) for every original \(X\).

Proof

Language: a node using \(A \to \alpha \beta_r\) becomes a node \(A \to \alpha A'\) whose last child \(A'\) uses \(A' \to \beta_r\), keeping all other children; conversely merge the two levels. (As languages: \(\alpha(\beta_1 \mid \cdots \mid \beta_k) = \alpha\beta_1 \mid \cdots \mid \alpha\beta_k\).) Removing duplicate \(\beta\)'s does not change \(L(A')\). Termination: let \(\Psi\) be the total length of all alternatives (over all nonterminals) that belong to some group. A step removes a whole group of \(A\), of total length \(\sum_r \lvert \alpha \beta_r \rvert\), and adds (i) \(A \to \alpha A'\), which is in no group, because the group contained every alternative of \(A\) starting with that symbol, and (ii) \(A'\)'s alternatives \(\beta_r\), of total length at most \(\sum_r \lvert \beta_r \rvert\). Other groups are untouched. So \(\Psi\) decreases by at least \(k \lvert \alpha \rvert \ge 2\). \(\Psi\) is a non-negative integer, so the loop terminates, and it stops only when no nonterminal has a group.

When it breaks: common prefixes hidden behind nonterminals (\(S \to A\, x \mid B\, y\) with \(A \to a\), \(B \to a\)) are not factored, and FIRST/FOLLOW conflicts are untouched.

5. Complexity¶

Variables: \(\lvert G \rvert\) grammar size, \(\lvert P \rvert\) productions, \(n\) nonterminals, \(r\) longest right side.

Technique	Time (worst)	Time (typical)	Space	Variables
Direct removal	\(O(\lvert G \rvert)\)	linear	\(+1\) nonterminal and \(+1\) production per left-recursive \(A\)	as above
Paull (textbook or SCC-restricted)	output size can be \(\Theta(2^{n})\); time proportional to the output	a few new primes	output size	\(n\) nonterminals
Left factoring	\(O(\lvert P \rvert \cdot r)\) per step, \(\le \lvert G \rvert / 2\) steps: \(O(\lvert G \rvert^{2} \cdot r)\)	one step per shared prefix	\(\le\) one new nonterminal per step	as above

Proposition 2.4.12 (Exponential blow-up of Paull's algorithm)

For \(n \ge 2\) let \(G_n\) have \(N_1 \to N_n\, c \mid d\) and \(N_i \to N_{i-1}\, a \mid N_{i-1}\, b\) (\(2 \le i \le n\)), in this order: \(2n\) productions. Both versions of Algorithm 2.4.5 output \(2^{n+1} - 1\) productions.

Proof

All \(N_i\) lie on the cycle \(N_n \to N_{n-1} \to \cdots \to N_1 \to N_n\) of the left-corner graph, so they form one SCC and the restriction changes nothing. By induction on \(i < n\): after iteration \(i\), \(N_i\) has \(2^{i}\) alternatives, each starting with \(N_n\) or \(d\) and half of each kind. \(N_1\) has 2. Iteration \(i\) substitutes \(N_{i-1}\)'s \(2^{i-1}\) alternatives into each of \(N_i\)'s two alternatives (no duplicates arise, because the suffixes \(a\) and \(b\) differ). Iteration \(n\) gives \(N_n\) \(2^{n}\) alternatives, \(2^{n-1}\) of them starting with \(N_n\) (directly left-recursive) and \(2^{n-1}\) with \(d\); RemoveDirect produces \(2^{n-1}\) alternatives for \(N_n\) and \(2^{n-1} + 1\) for \(N_n'\). Total: \(\sum_{i=1}^{n-1} 2^{i} + 2^{n-1} + 2^{n-1} + 1 = (2^{n} - 2) + 2^{n} + 1 = 2^{n+1} - 1\).

Pathological input: that family, measured with eliminate_left_recursion: 7, 15, 31, 63, 127, 255, 511 productions for \(n = 2, \dots, 8\), from an input of \(2n\).

At scale: on the corpus, SCC restriction matters only where a non-left-recursive nonterminal starts with an earlier one: json.grammar grows from 18 to 24 productions with the textbook algorithm and stays at 18 with the restriction; statements.grammar (19 productions, unchanged) and precedence.grammar (12 productions, 14 after either version) are unaffected by the restriction. Moore reports that on large natural-language grammars the choice of variant changes the output size by orders of magnitude, and proposes a left-corner-based transform that stays small [Moo00].

Direct left-recursion removal¶

EBNF iteration [Wir77]: write \(E \to T\ \{\, +\ T \,\}\) and parse the braces with a loop; the loop can build a left-nested AST, keeping the associativity the grammar lost — trade-off: needs a parser that understands EBNF (hand-written, ANTLR, pgen), not a plain LL(1) table. ANTLR 4 generates exactly this (real-world box in §2).
Keep left recursion, change the parser: memoization with curtailment [FH06] or seed growing in packrat parsers [WDM08] (CPython's pegen, memoize_left_rec [CPY-pegen]) handle left-recursive rules directly — trade-off: a more complex parser, but the grammar and its trees stay natural (Ch 4).

Paull's algorithm (indirect left recursion)¶

SCC restriction (this course; the same left-corner SCCs that pegen computes as "leaders", compute_left_recursives [CPY-pegen]): skip substitutions that cannot close a cycle — trade-off: an extra graph analysis; worst case unchanged (Proposition 2.4.12's family is one SCC).
Left-corner transform [RL70; Moo00]: a different construction whose output is polynomial in the input — trade-off: introduces many more nonterminals of the form \(A\text{-}B\) and changes trees more drastically.
\(\varepsilon\)-removal first / Greibach normal form [Gre65; HU79 §4.6]: make the grammar \(\varepsilon\)-free so that Paull always succeeds (Theorem 2.4.10) — trade-off: \(\varepsilon\)-removal can double productions per nullable symbol occurrence, and GNF grammars are unreadable.

Left factoring¶

Factoring through nonterminals: substitute leading nonterminals to expose hidden common prefixes, then factor — trade-off: may not terminate (with left recursion) and can blow up the grammar.
Per-rule subset construction [CPY38-pgen]: compile each rule's regular right side to a DFA, which factors every shared prefix within the rule (real-world box in §2) — trade-off: automatic, but only within one rule.
More lookahead instead (Lesson 2.6): LL(k) or ALL(*) decisions leave the grammar and the trees alone — trade-off: a more complex parser generator.

7. In real compilers¶

Direct left-recursion removal¶

Clang (LLVM 23.1.2) never has left-recursive functions: clang/lib/Parse/ParseExpr.cpp — Parser::ParseRHSOfBinaryExpression is an EBNF-style loop (while (true), leaving when NextTokPrec < MinPrec) that builds left-nested BinaryOperator ASTs, i.e. left-recursion removal plus left-associative AST building [CLANG-ParseExpr].
ANTLR 4 rewrites directly left-recursive rules for you: tool/src/org/antlr/v4/analysis/LeftRecursiveRuleTransformer.java — translateLeftRecursiveRules (4.13.2) turns e : e '*' e | e '-' e | … ; into a precedence-climbing loop (real-world box in §2) [ANTLR4-LeftRec].

Paull's algorithm (indirect left recursion)¶

Production parser generators do not run Paull's algorithm: they reject indirect left recursion (ANTLR 4, error 119, real-world box in §2 [ANTLR4-LeftRecDoc]) or support left recursion natively (CPython's pegen; Bison, which is LR). The algorithm lives in grammar-engineering tools and textbooks, and its SCC computation lives on in CPython pegen Tools/peg_generator/pegen/parser_generator.py — compute_left_recursives (v3.13.0), which finds the left-corner SCCs and picks a "leader" through which every cycle passes [CPY-pegen].

Left factoring¶

Clang clang/lib/Parse/ParseStmt.cpp — Parser::ParseIfStatement is the factored grammar \(S \to \mathtt{if}\ (E)\ S\ S'\): it parses the common part, then tests Tok.is(tok::kw_else) [CLANG-ParseStmt].
GCC gcc/c/c-parser.cc — c_parser_if_statement (GCC 15) has the same shape [GCC-CParser].
CPython 3.8 pgen factors within each rule by subset construction (real-world box in §2) [CPY38-pgen].

Find where LLVM does it. Open clang/lib/Parse/ParseExpr.cpp (LLVM 23.1.2) and find Parser::ParseRHSOfBinaryExpression. Question: which local variable decides that ?: and assignment group to the right? (quiz clang-right-assoc)

8. Comparison¶

Technique	Power / precision	Speed (asymptotic · practical)	Output / error quality	Implementation effort	Typical use
Direct left-recursion removal	Removes immediate left recursion; preserves the language, not the tree shape	O(\|G\|) · instant	Right-nested trees: the AST must re-associate	Low	Every LL grammar for left-associative operators; as EBNF loops in hand-written parsers
Paull's algorithm (textbook / SCC-restricted)	Removes all left recursion from cycle-free, ε-free grammars; reports hidden left recursion otherwise	Θ(2ⁿ) output in the worst case · SCC restriction avoids needless growth (json: 18 vs 24 productions)	Unreadable grammars, renamed structure	Medium	Grammar tools, textbooks; production generators reject or natively support left recursion instead
Left factoring	Removes FIRST/FIRST conflicts caused by syntactic common prefixes only	O(\|G\|²·r) · instant	Adds helper nonterminals; trees change shape	Low	if/else, statement starts; grammars for JavaCC or LL(1) tables

Choose direct removal (or its loop form) when you write a top-down parser for left-associative operators; build the AST in the loop so associativity survives. Choose Paull's algorithm when a grammar is given to you with indirect left recursion and you must feed an LL tool; prefer the SCC-restricted version, and check the output size (Proposition 2.4.12). Choose left factoring when alternatives share a visible prefix; when the shared part is hidden behind nonterminals or the conflict is FIRST/FOLLOW, look at more lookahead (Lesson 2.6) or priority (Lesson 2.3) instead.

9. Assessment¶

Technique	Quiz ids (`solutions/quizzes/ch02.yaml`)	Drill	Flashcard tag	Exercises
Direct left-recursion removal	`paull-indirect` (its last step), `transform-properties`, `clang-right-assoc`	`./course drill left-recursion --difficulty easy`	`direct-lr`	E7
Paull's algorithm	`paull-indirect`, `paull-blowup`	`./course drill left-recursion --difficulty medium`	`paull`	E7
Left factoring	`left-factor-result`, `transform-properties`	`./course drill left-recursion --difficulty hard`	`left-factoring`	E8

Same language, different meaning

These transformations preserve the language, not the meaning: after removing left recursion, a - b - c parses as a right-nested chain. If you evaluate that tree naively you compute \(a - (b - c)\). Build the AST in a loop (Lesson 2.5, lab exercise L2) or re-associate afterwards.

References¶

See the chapter references.

Lesson 2.4 — Grammar transformations for top-down parsing¶

1. Problem and motivation¶

Direct left-recursion removal¶

Paull's algorithm (indirect left recursion)¶

Left factoring¶

2. Definitions and algorithms¶

Direct left-recursion removal¶

Paull's algorithm (indirect left recursion)¶

Left factoring¶

3. Worked example¶

Direct left-recursion removal on the running example¶

Paull's algorithm on the running example¶

Left factoring on the running example¶

4. Invariants and correctness¶

Direct left-recursion removal¶

Paull's algorithm (indirect left recursion)¶

Left factoring¶

5. Complexity¶

6. Variants and refinements¶

Direct left-recursion removal¶

Paull's algorithm (indirect left recursion)¶

Left factoring¶

7. In real compilers¶

Direct left-recursion removal¶

Paull's algorithm (indirect left recursion)¶

Left factoring¶

8. Comparison¶

9. Assessment¶

References¶