ToolSphere

Left Recursion and Left Factoring Calculator

Computer science

Remove direct and indirect left recursion and left factor any grammar online, with every substitution and step shown, then check it is LL(1).

Type grammar rules to remove left recursion or factor shared prefixes.

Transformed grammar
S -> A a | b
A -> b d A' | A'
A' -> c A' | a d A' | ε
Grammar (one rule per line)

One rule per line, spaces between symbols: E -> E + T | T. Write ε (or eps) for an empty right side, one that matches nothing. The first rule is the start.

What to do

Fixed grammar

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

The result still has 2 LL(1) conflicts. These two rewrites are not always enough: an ambiguous grammar (the dangling else) can never be LL(1), and others need a leading non-terminal substituted before factoring. The LL(1) parser shows each conflict.

Paste the result into the FIRST & FOLLOW calculator or the LL(1) parser to build its table.

What is wrong with it

Left-recursive: S (indirect), A (direct). No common prefixes.

Removing left recursion

Non-terminals are taken in order (S, A). Each one first has earlier non-terminals substituted into its leading position, which turns indirect recursion into direct recursion, then its direct recursion is removed.

  1. Non-terminal A

    Substitute S's rules where S comes first: A → A c | S d | ε becomes A → A c | A a d | b d | ε

    Direct recursion A → A α | β with α = { c, a d } and β = { b d, ε }, so A → β A' and A' → α A' | ε:

    A → b d A' | A'
    A' → c A' | a d A' | ε

Left factoring

Left factoring pulls out a shared start, so a parser that looks one symbol ahead can choose: A → a b | a c becomes A → a A′, A′ → b | c.

No two alternatives share a first symbol, so nothing needs factoring.

On this browser only

Give feedback

Did this tool help?

Tell us what worked, what didn’t, or what you’d like next.

Opens Google Forms in a new tab with this tool’s name filled in. No sign-in or email required. Feedback is optional.

How to use Left Recursion and Left Factoring Calculator

  1. 1Type the grammar, one rule per line, as E -> E + T | T, or load an example such as the indirect Dragon Book grammar.
  2. 2Choose Both to prepare a grammar for an LL(1) parser, or run only left-recursion removal or only left factoring.
  3. 3Read the steps: each substitution of an earlier non-terminal, the α and β parts of every direct recursion, and every prefix pulled out.
  4. 4Copy the result grammar, and check the verdict line to see whether it is now LL(1).
  5. 5Paste the result into the LL(1) parser or the FIRST and FOLLOW calculator to build its table.

About Left Recursion and Left Factoring Calculator

What this tool does

Top-down parsers, both recursive descent and table-driven LL(1), cannot handle two features that are completely natural in a grammar. A left-recursive rule such as E → E + T sends a recursive-descent parser into an infinite loop, because expanding E starts by expanding E again without reading any input. Two alternatives that begin the same way, such as S → i E t S | i E t S e S, leave a one-token-lookahead parser unable to choose between them. Compiler courses therefore teach two rewrites: eliminating left recursion and left factoring. This tool performs both on any grammar you type, shows every step the way an exam answer is expected to, and then tells you whether the result is LL(1).

Removing direct left recursion

A non-terminal A is directly left-recursive when one of its own alternatives starts with A. Group its alternatives into the recursive ones, A → A α₁ | A α₂ | …, and the rest, A → β₁ | β₂ | …. Every string A derives is one β followed by any number of α parts, so the same language comes from

A → β₁ A' | β₂ A' | …
A' → α₁ A' | α₂ A' | … | ε

The new non-terminal A' is right-recursive, which a top-down parser handles without trouble. The tool lists the α set and the β set for every non-terminal before writing the new rules, because that grouping is exactly where students lose marks.

Removing indirect left recursion

Recursion can also hide behind another non-terminal: S → A a and A → S d mean that S derives A a, then S d a, which starts with S again. The standard algorithm (Aho, Lam, Sethi and Ullman, Algorithm 4.19) orders the non-terminals A₁, A₂, …, Aₙ. For each Aᵢ it first replaces every rule Aᵢ → Aⱼ γ with j < i by the alternatives of Aⱼ followed by γ. After those substitutions any remaining left recursion of Aᵢ is direct, and the rule above removes it. The order is the order in which non-terminals first appear on a left-hand side, so put the start symbol first, as textbooks do.

Worked example: the Dragon Book grammar

The indirect example from the textbook is S → A a | b with A → A c | S d | ε. The tool produces these steps:

Step Rules
S has no left recursion of its own S → A a | b
Substitute S into A A → A c | A a d | b d | ε
Direct recursion in A: α = { c, a d }, β = { b d, ε } A → b d A' | A'
New non-terminal A' → c A' | a d A' | ε

The final grammar is S → A a | b, A → b d A' | A', A' → c A' | a d A' | ε, matching the textbook answer. The verdict line then reports two LL(1) conflicts, which is the honest result: removing left recursion does not make every grammar LL(1). Here S → A a and S → b can both start with b, and a FIRST/FOLLOW conflict remains on A'.

Left factoring

When two alternatives share a leading prefix α, factor it out: A → α β₁ | α β₂ | γ becomes A → α A' | γ with A' → β₁ | β₂. The tool repeats this until no two alternatives of any non-terminal start with the same symbol, so nested prefixes are handled too. For A → a b c | a b d | a e | f the steps are A → a A' | f with A' → b c | b d | e, and then A' → b A'' | e with A'' → c | d. The dangling-else grammar S → i E t S | i E t S e S | a factors to S → i E t S S' | a with S' → e S | ε. The ε appears because one alternative was exactly the shared prefix.

Doing both, in the right order

For an LL(1) parser you need both rewrites, and the usual order is to remove left recursion first and then left factor, because substitution can create new common prefixes. The grammar S → S a | b c | b d shows this. Removing the recursion gives S → b c S' | b d S' with S' → a S' | ε, and only then does the shared b appear, so factoring gives S → b S'' with S'' → c S' | d S'. That result has no LL(1) conflicts. The tool names new non-terminals with primes and adds another prime whenever a name is already taken, which is why the second one here is S''.

Reading the verdict

After rewriting, the tool builds the LL(1) table of the result. No conflicts means the grammar is ready for a predictive parser. Remaining conflicts have three usual causes. The grammar may be ambiguous, like the dangling else, and no rewrite can fix that. A leading non-terminal may hide a shared prefix, as in the Dragon Book example, and that needs that non-terminal substituted before factoring. Or the language may need more than one token of lookahead. The LL(1) parser shows each conflicting cell and why the productions landed there.

Common mistakes

  • Forgetting ε in A'. Without A' → ε the rewritten grammar cannot stop repeating α and derives nothing finite.
  • Dropping the β alternatives. Every non-recursive alternative of A, including ε, becomes β A'. The example above keeps A → A' because ε was a β.
  • Substituting in the wrong direction. Only earlier non-terminals are substituted into later ones. Substituting everything everywhere can loop forever.
  • ε-productions in a cycle. The algorithm assumes no non-terminal can derive ε and then itself. If recursion survives, the tool says so, and you should remove ε-productions first.
  • Factoring only one level. After pulling out a, the new non-terminal can itself need factoring.

Related tools and guides

Compute the sets of the new grammar with the FIRST and FOLLOW calculator, then build the table with the LL(1) parser. Bottom-up parsers do not need these rewrites, and the LR parser accepts left-recursive grammars as they are. The guide left recursion and left factoring examples works through more exam questions by hand.

Guides and tutorials

Frequently asked questions

How do you eliminate left recursion from a grammar?

For a directly left-recursive non-terminal A -> A alpha | beta, write A -> beta A' and A' -> alpha A' | ε. For indirect recursion, order the non-terminals and first substitute each earlier non-terminal into the leading position of later rules, then remove the direct recursion. The tool shows both stages for every non-terminal.

What is the difference between direct and indirect left recursion?

Direct left recursion is a rule whose right side starts with its own left side, such as E -> E + T. Indirect left recursion goes through other non-terminals, such as S -> A a with A -> S d, so S derives a string starting with S after two steps. The tool labels each left-recursive non-terminal as direct or indirect.

What is left factoring and why is it needed?

Left factoring pulls a common prefix out of alternatives, turning A -> alpha beta1 | alpha beta2 into A -> alpha A' and A' -> beta1 | beta2. A predictive parser chooses a production from one token of lookahead, so two alternatives starting with the same symbol make that choice impossible until the prefix is factored out.

Should I remove left recursion or left factor first?

Remove left recursion first, then left factor. Substitution during left-recursion removal can create new common prefixes, as in S -> S a | b c | b d, where the shared b only appears after the recursion is removed. The Both option runs them in that order.

Does removing left recursion make a grammar LL(1)?

Not always. It removes one obstacle, but the result can still have FIRST/FIRST or FIRST/FOLLOW conflicts. The Dragon Book grammar S -> A a | b, A -> A c | S d | ε still has two conflicts afterwards, and the tool reports them instead of claiming success.

Can left factoring fix an ambiguous grammar?

No. Left factoring the dangling-else grammar gives S -> i E t S S' | a with S' -> e S | ε, which is still ambiguous, so its LL(1) table keeps a conflict on e. Parsers resolve it by a rule such as matching each else with the nearest then, not by rewriting.

Why does the new grammar contain A' -> ε?

A' generates the repeated alpha parts that used to come from the left recursion, and it must be able to stop. Without the ε alternative A' would have to repeat forever and the grammar would generate no complete strings.

Does the tool handle ε-productions?

Yes, write ε, eps or epsilon. The textbook algorithm assumes there are no ε-cycles. If left recursion survives because a non-terminal can derive ε and then reach itself, the tool warns you, and removing ε-productions first fixes it.

Why is the new non-terminal called S'' and not S'?

Each new non-terminal gets a prime added to the original name, with one more prime whenever that name is already used. When both rewrites create a non-terminal from S, the second one becomes S''. Rename them in your answer if your course uses different letters.

Do LR parsers need left recursion removed?

No. Bottom-up parsers such as LR(0), SLR, LALR and canonical LR handle left recursion naturally and usually prefer it, because it keeps the stack short. These rewrites are only needed for top-down parsers: recursive descent and LL(1).

Have a suggestion for Left Recursion and Left Factoring Calculator?Share your feedback ↗