ToolSphere
Back to all articles
student

Left Recursion and Left Factoring Examples

2026-11-0210 min read

Try it: free Left Recursion and Left Factoring Calculator

Remove left recursion and left factor a grammar step by step

Open →

Left recursion and a shared prefix cause different problems for a predictive parser. A left-recursive rule can call the same parsing function before consuming input. Shared prefixes make the parser postpone a choice between alternatives. Removing one problem does not automatically remove the other, and neither transformation alone guarantees an LL(1) grammar.

This guide runs the site's grammar transformations on direct recursion, indirect recursion and shared-prefix examples. Every displayed grammar, FIRST/FOLLOW set and parsing-table cell comes from the same library used by the compiler tools. The word end denotes the end-of-input marker in the tables.

Immediate left recursion: an expression grammar

Start with:

E -> E + T | T
T -> T * F | F
F -> ( E ) | id

The library detects left recursion in E and T. For a general rule A → A α | β, replace it with A → β A′ and A′ → α A′ | ε. If there are several recursive or nonrecursive alternatives, retain each appropriate suffix or prefix; do not throw alternatives away.

Applied to the expression grammar, the result is:

E -> T E'
E' -> + T E' | ε
T -> F T'
T' -> * F T' | ε
F -> ( E ) | id

E now starts by deriving T. The helper E′ represents a sequence of additional additions, including an empty sequence. T and T′ do the same for multiplication. Parentheses and identifiers remain in F. No left recursion is detected in the transformed grammar.

The transformation preserves the terminal language, but its parse-tree shape changes. If an implementation must preserve left-associative evaluation, it should accumulate a running left value while processing the helper's repeated suffixes. Merely adopting a right-recursive parse tree as an evaluation tree can change the meaning of subtraction or division.

Check FIRST and FOLLOW rather than guessing

Nonterminal FIRST FOLLOW
E (, id end, )
E' +, ε end, )
T (, id +, end, )
T' *, ε +, end, )
F (, id *, +, end, )

FIRST tells us how an alternative may begin; FOLLOW supplies the lookaheads for an alternative that can vanish. ε belongs in FIRST when appropriate, but never in FOLLOW. The FIRST/FOLLOW calculator can reproduce these sets.

Here is the complete generated predictive table. A dash is an error cell, not an instruction to accept or silently skip a token.

Nonterminal + * ( ) id end
E — — E → T E' — E → T E' —
E' E' → + T E' — — E' → ε — E' → ε
T — — T → F T' — T → F T' —
T' T' → ε T' → * F T' — T' → ε — T' → ε
F — — F → ( E ) — F → id —

This transformed example has no competing productions in a cell. It is LL(1), but that conclusion comes from its table, not simply from the absence of left recursion. Try a token sequence in the LL(1) parser to follow the stack operations.

Indirect left recursion: substitute before rewriting

Consider the ordered nonterminals S, A:

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

Neither production starts directly with its own left side, but S can start with A and A can start with S. The library reports S and A as left-recursive.

Process S first. While processing A, replace the leading S in A → S c with S's alternatives. This exposes an alternative starting with A. Remove that immediate recursion using a fresh helper, giving:

S -> A a | b
A -> b c A' | d A'
A' -> a c A' | ε

The generated helper name follows the library's prime-name convention. The final detector reports no left-recursive nonterminals. Alternative nonterminal orderings may produce differently named or structured equivalent grammars; copying a different textbook's names without checking its substitution order is unnecessary.

Importantly, removing recursion did not make this example predictive. Its remaining generated conflicts are:

  • M[S, b]: S → A a vs S → b
  • M[A', a]: A' → a c A' vs A' → ε

The algorithm used here is the ordered substitution method for grammars without the problematic epsilon/cycle cases excluded by its preconditions. It is not a promise to normalise every arbitrary grammar. Inspect nullable cycles and useless alternatives separately; a nonterminal with only recursive alternatives cannot produce a finite terminal word.

Left factoring: pull out the shared prefix

A different issue appears in:

S -> a b c | a b d | a e | f

Reading a alone does not determine whether the intended suffix is b c, b d or e. Factoring pulls the common prefix into a single alternative and repeats the process inside helpers:

S -> a S' | f
S' -> b S'' | e
S'' -> c | d

The helper after a delays the decision until the next input symbol. Another helper delays the c-versus-d choice until after b. The transformed grammar derives the same words; it does not delete a branch merely because that branch was inconvenient for prediction.

Factoring operates on a common sequence of grammar symbols, not common letters in printed nonterminal names. Use spaces to make token boundaries explicit when entering multi-character terminals and nonterminals.

Dangling else: factoring leaves a real conflict

Now use a statement grammar whose two if alternatives share a long prefix:

S -> if E then S else S | if E then S | other
E -> condition

Factoring produces:

S -> if E then S S' | other
S' -> else S | ε
E -> condition

The generated sets are:

Nonterminal FIRST FOLLOW
S if, other end, else
S' else, ε end, else
E condition then

The predictive table still contains:

  • M[S', else]: S' → else S vs S' → ε

The helper may either consume else or disappear. But else can also follow that helper because an enclosing if may own the same token. One-token lookahead cannot choose between those alternatives from this grammar alone. This is a FIRST/FOLLOW conflict, not a forgotten common prefix.

In a nested statement, the else may attach to the nearest unmatched if or to an outer if. Factoring moves the point where the choice occurs; it does not remove the ambiguity. A language specification can impose a nearest-if convention, or use delimiters and a suitable unambiguous grammar. A parser's conflict-resolution convention should be described explicitly rather than claiming the factored grammar became LL(1).

A reliable exam workflow

First identify direct and indirect left-recursive paths. Apply ordered substitution where its preconditions hold, then remove direct recursion with fresh helper symbols. Next factor common prefixes. Finally recompute FIRST, FOLLOW and every predictive-table entry. Check all conflict cells, including helpers introduced by the transformations.

Keep the original grammar beside the result so that missing alternatives are easy to spot. Preserve epsilon where it represents a legitimate empty suffix. Do not put epsilon into a FOLLOW set, and do not treat an error cell as an epsilon production.

For a parsing method that can handle many left-recursive grammars directly, compare the canonical LR and LALR worked example and the LR parser. Grammar rewriting is a tool for a specific parsing strategy, not a requirement that every compiler must erase left recursion.

Looking for other tools?

Explore ToolSphere Homepage →