After you remove the obvious left recursion, a top-down generator still calls the rule set left recursive; how do you find what it means?
answer
- no single rule looks wrong
- follow leading symbols around a cycle
- nullable prefixes extend the relation
- inline earlier rules until it is direct
- clear empty and unit rules first
basics
~20 sLook for indirect recursion: a cycle in the can-begin-with relation, where one nonterminal's first symbol is another that eventually leads back. Substitute the intermediate rules inline until the recursion becomes direct, then apply the usual tail rewrite.
solid answer
~50 sThe generator is reporting **indirect** left recursion: no rule begins with itself, but a chain does. With `S -> A 'a' | 'b'` and `A -> A 'c' | S 'd' | empty`, the alternative `S 'd'` makes `A` able to begin with `S`, and `S` can begin with `A`. Build the relation *X can have Y as its leading symbol*, take its transitive closure, and any nonterminal that reaches itself is in a cycle — that is the report. To fix it, order the nonterminals and work through them: for each one, substitute the productions of every earlier nonterminal that appears at the front of one of its alternatives, which exposes the recursion as direct, then eliminate it with the standard primed-tail rewrite. The algorithm assumes the rule set has no unit-production cycles and no empty productions, so remove those first.
code
pseudocode · 10 linesgiven:
S -> A 'a' | 'b'
A -> A 'c' | S 'd' | empty
substitute S into A's second alternative:
A -> A 'c' | A 'a' 'd' | 'b' 'd' | empty
now eliminate the direct left recursion:
A -> 'b' 'd' A2 | A2
A2 -> 'c' A2 | 'a' 'd' A2 | emptygo deeper
Recall that left recursion can be spread over several rules, so a rule set can loop even when no rule visibly begins with itself.
Explain the leading-symbol relation and its closure, and carry out one substitution step that turns an indirect cycle into a direct one.
Demonstrate the whole repair under real conditions: order the nonterminals, clear empty and unit productions first, watch for nullable prefixes, and re-check for new shared prefixes afterwards.
Decide how much of this belongs in the authored rule set at all — the transformed grammar is machine output, and treating it as the source of truth is what makes a specification unreadable.
## Direct versus indirect **Direct (immediate) left recursion** is visible in one production: the nonterminal is the first symbol of its own right-hand side. **Indirect (hidden) left recursion** is a cycle spread over several productions — no single rule looks wrong, but following leading symbols leads back to where you started: ``` S -> A 'a' | 'b' A -> A 'c' | S 'd' | empty ``` Here `A -> A 'c'` is direct and easy to spot. Remove it and the generator still complains, because `A -> S 'd'` means `A` can begin with `S`, and `S -> A 'a'` means `S` can begin with `A`. Expanding `A` can reach `A` again with nothing consumed, which is exactly the non-termination the direct case had. ## Finding the cycle mechanically Do not hunt by eye. Build a relation over nonterminals — *X begins with Y* — and close it: 1. For each production `X -> Y …` where `Y` is a nonterminal, record the edge X → Y. 2. If a leading nonterminal is **nullable** (can derive nothing), also record an edge to the symbol after it, and keep going while the symbols are nullable — hidden recursion loves to sit behind a nullable prefix. 3. Take the transitive closure of the edges. 4. Any nonterminal with an edge to itself sits on a left-recursive cycle, and the path that produced the edge is the chain to report. Step 2 is the one people skip, and it is why a rule set that looks acyclic still loops: `X -> Opt Y …` with `Opt` nullable means `X` can genuinely begin with `Y`. ## The elimination algorithm The classic algorithm makes the hidden case direct by substitution: 1. Fix an arbitrary order of the nonterminals: `A1, A2, …, An`. 2. For each `i` in order, for each `j < i`: replace every production `Ai -> Aj gamma` by `Ai -> delta1 gamma | delta2 gamma | …`, where the `delta`s are the current right-hand sides of `Aj`. This inlines the earlier nonterminal. 3. After the inner loop, eliminate the now-direct left recursion in `Ai` with the primed-tail rewrite. 4. Move to `i + 1`. Because every substitution only ever inlines an *earlier* nonterminal, the process terminates. On the example, ordering `S, A` and processing `A`: substituting `S`'s productions into `A -> S 'd'` gives `A -> A 'c' | A 'a' 'd' | 'b' 'd' | empty`. The recursion is now direct, with recursive tails `'c'` and `'a' 'd'`, and non-recursive alternatives `'b' 'd'` and the empty one. The standard rewrite yields `A -> 'b' 'd' A2 | A2` and `A2 -> 'c' A2 | 'a' 'd' A2 | empty`. ## Preconditions that are easy to miss | precondition | why the algorithm needs it | what to do first | |---|---|---| | no empty (epsilon) productions | a nullable leading symbol hides recursion the substitution step will not see | remove empty productions, restoring the empty string with a fresh start symbol if the language contains it | | no unit-production cycles | `X -> Y`, `Y -> X` makes substitution churn without progress | remove unit productions first | | a fixed nonterminal order | substitution must only ever inline earlier nonterminals, or it may not terminate | choose one order and keep it | ## What it costs - **Rule count grows.** Every substitution multiplies alternatives, and a chain through several nonterminals can enlarge the rule set noticeably. - **Readable structure is destroyed.** The intermediate nonterminal that carried meaning — the one you inlined — is gone from those alternatives, so the tree no longer has a node where a reader expects one. - **Diagnostics degrade.** Error messages now name generated helpers rather than the construct the author wrote, which is worth compensating for with explicit naming. - **It is worth re-checking afterwards.** The substitution can create new shared prefixes, so factoring may be needed again after elimination. ## The short answer to give Say that the report is about a *cycle in the leading-symbol relation*, that you would compute that relation and its closure rather than reading rules one by one, that nullable prefixes extend the relation, and that the repair is substitution-until-direct followed by the ordinary tail rewrite — with empty and unit productions cleared first so the substitution is sound.
- Why does the algorithm require empty productions to be removed first?Because a nullable leading symbol hides a recursion the substitution step never sees: `X -> Opt X …` with `Opt` nullable is left recursive in effect but not in form. Clearing empty productions makes every leading symbol a real one, so the leading-symbol relation and the substitution both tell the truth.
- Does the order you pick for the nonterminals change the result?It changes the rules you end up with — a different order inlines different nonterminals and produces a different, usually differently sized, rule set — but any valid order removes the left recursion and preserves the language. Ordering is therefore a size and readability choice, not a correctness one.
- The rule set got much larger after elimination. Is that expected?Yes. Each substitution replaces one alternative with one copy per production of the inlined nonterminal, so alternatives multiply along the chain. That growth is the usual argument for keeping the readable rule set as the specification and treating the transformed one as generated output.
saying these in an interview costs you the question
- Looks only for a rule that names itself first.
- Ignores nullable leading symbols when tracing the cycle.
- Substitutes in arbitrary order and never terminates.
- Runs the algorithm before removing empty productions.
- Assumes elimination cannot change the number of rules much.
- Thinks the cycle means the rule set is ambiguous.