4.3 Grammar Transformations, Left Recursion, Left Factoring

The grammar that best communicates a language definition is not always the grammar that a particular parser can consume directly. Compiler engineering therefore uses grammar transformations: carefully changing productions while preserving the language, the intended parse structure, or both.

Transformation is not cosmetic. A careless rewrite can change associativity, accidentally add or remove the empty string, make error messages worse, or move semantic actions to the wrong place. Treat every transformation as a proof obligation: state what language behavior must stay true, then test representative inputs before trusting the new grammar.

Two transformations appear constantly in predictive, top-down parsing:

• eliminating left recursion;

• left factoring shared prefixes.

They prepare grammars for parser decisions based on a small amount of lookahead. They do not magically make every grammar LL(1), and they are not universally desirable for every parser architecture.

Direct and Indirect Left Recursion

A grammar is directly left recursive when a nonterminal can immediately derive a string beginning with itself:

E -> E + T | T

The production E -> E + T asks a recursive-descent function parseE() to call parseE() before consuming any token. That call repeats forever:

parseE()
  -> parseE()
      -> parseE()
          -> ...

The standard direct-elimination pattern is:

A -> A α1 | A α2 | ... | β1 | β2 | ...

where each β does not begin with A. Transform it into:

A  -> β1 A' | β2 A' | ...
A' -> α1 A' | α2 A' | ... | ε

For addition:

E  -> E + T | T

becomes:

E  -> T E'
E' -> + T E' | ε

The transformed grammar first consumes a T, then repeats a + T tail zero or more times. It recognizes the same sequence shape: one term followed by any number of additional + term pieces.

Do Not Lose Associativity

The transformed grammar looks right-recursive because E' calls itself on the right. A naive AST builder can accidentally turn:

a - b - c

into:

a - (b - c)

when the language intended:

(a - b) - c

The parser implementation must fold the repeated tail in the intended direction. A common recursive-descent implementation parses the first operand, then loops:

left = parseTerm()
while next token is "+":
  consume "+"
  right = parseTerm()
  left = Add(left, right)
return left

The grammar controls recognition; the AST-construction strategy preserves semantic associativity. Keep these responsibilities connected.

Indirect left recursion is less obvious:

A -> B α
B -> A β | γ

A derives B α, then B derives A β, so A =>+ A β α. General elimination orders nonterminals, substitutes earlier productions into later ones, then removes direct left recursion. This algorithm can grow the grammar quickly, so it should be applied intentionally, with tests and source-level diagnostics in mind.

Left Factoring Delays a Decision Until Lookahead Is Useful

Suppose a parser sees:

Stmt -> if Expr then Stmt else Stmt
      | if Expr then Stmt
      | while Expr do Stmt

At the beginning of a statement, lookahead if cannot distinguish the first two alternatives. Both consume the same prefix. Left factoring extracts that shared prefix:

Stmt     -> if Expr then Stmt StmtTail
          | while Expr do Stmt
StmtTail -> else Stmt | ε

The parser now reads the common prefix once. Only after it has finished the nested statement does it ask whether else follows. That is exactly the point at which one token of lookahead can make a meaningful decision.

The general pattern is:

A -> α β1 | α β2

which becomes:

A  -> α A'
A' -> β1 | β2

If one original alternative is exactly the shared prefix, its tail becomes ε. The transformation changes the shape of the parse tree, so an implementation may need to reconstruct a more convenient AST shape afterward.

Parser-Friendly Rules Must Keep Source Meaning

Changing E -> E + T | T into E -> T E' and E' -> + T E' | epsilon removes dangerous left recursion, but it must not change associativity. An AST builder should fold the successive + T pieces from the left; recursively building the tail on the right would accidentally turn a-b-c into a right-associative expression.

Left factoring also delays a decision rather than removing it. After factoring IDENT = Expr and IDENT ( Args ), the next token = or ( supplies the missing information. Test the transformed grammar with empty, shortest, repeated, and nested inputs so optional tails do not introduce a new ambiguity.

Transform for the Parser You Actually Have

Left recursion is friendly to LR parsers and often expresses left associativity naturally. Removing it solely because it looks unpleasant can make an LR grammar less readable. Conversely, a hand-written recursive-descent parser usually needs left recursion removed or replaced by a loop/Pratt parser.

Left factoring has similar tradeoffs. It can make LL-style prediction clearer, but aggressive factoring can introduce many helper nonterminals and obscure user-facing syntax. Parser generators may also offer precedence declarations or conflict-resolution mechanisms that reduce the need for manual factoring.

Use these questions before transforming:

• Which parser strategy will consume this grammar?

• Is the transformation language-preserving, including the empty string?

• Does it preserve required precedence and associativity?

• Can the AST builder still emit useful source ranges and diagnostics?

• Do regression cases cover both ordinary programs and boundary cases?

The goal is not a grammar that is aesthetically transformed. The goal is a grammar and parser together that recognize the specified language predictably and report mistakes well.