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.