skip to content

A recursive-descent parser overflows its call stack having consumed no tokens at all — what property of the grammar causes this?

level: middleimportance: must knowfreq 58%

answer

  1. crash before any progress is made
  2. the function's very first act
  3. the input position never advances
  4. recursion without consumption
  5. a chain of rules can hide it

basics

~20 s

Left recursion: a rule whose first symbol is the rule itself, directly or through a chain. Its function calls itself before consuming anything, so every level re-enters at the same input position and the recursion never terminates.

solid answer

~50 s

The rule set contains a **left-recursive** rule — one that can begin with itself, such as `directives -> directives directive`. Turning that rule into a function makes the function's first action a call to itself, with the input position unchanged and the same lookahead token. Nothing has been consumed, so the next level takes the identical branch, and the recursion descends until the stack is exhausted. The give-away in the stack trace is that the same frame repeats with no progress: a crash on deeply nested but legal input consumes tokens first and shows a varied trace, while this one dies on the first token. Indirect cycles behave the same way and are harder to spot, because no single rule names itself. The repair is to restate the rules so the recursive call is no longer the first thing the function does — a grammar transformation, and a subject of its own.

code

pseudocode · 16 lines
pseudocode
// rule:  directives -> directives directive | (nothing)

function parse_directives():
    // first symbol of the alternative is this same rule,
    // so this call runs with the input position unchanged
    left  = parse_directives()      // re-enters here forever
    right = parse_directive()       // never reached
    return Sequence(left, right)

// contrast:  directives -> directive directives | (nothing)
function parse_directives_right():
    if peek() is not one of 'every', 'retry', 'run':
        return empty            // the base case the input can reach
    head = parse_directive()    // consumes at least one token
    tail = parse_directives_right()
    return Sequence(head, tail)

go deeper

for a junior

Recall the shape to look for: a rule that starts with itself makes its function call itself before reading anything, so it never stops. Recognising the pattern in a printed rule is enough here.

for a middle

Explain why the recursion cannot terminate — same position, same lookahead, same branch at every level — and contrast it with right recursion, which consumes a token before recursing and so always advances.

for a senior

Diagnose from evidence: distinguish a repeating-frame trace at position zero from a genuine deep-nesting overflow, and follow the chain of first symbols to find an indirect or hidden cycle that no single rule reveals.

for a principal

Recognise the structural consequence: rule sets written for a bottom-up family carry left recursion by design, so adopting one for a hand-written parser means owning a transformation step and whatever it does to the resulting tree shape.

## The symptom, precisely A top-down parser written as one function per rule crashes on the very first token of the input, with a stack trace showing the same small set of frames repeated thousands of times, and with the input position still at zero. That combination is diagnostic. It is not a resource problem and a larger stack does not fix it; the recursion has no base case that the input can reach. ## Why the recursion cannot terminate A rule function makes progress only by consuming a token. Consider a rule written to gather directives by appending on the right: ```pseudocode directives -> directives directive | (nothing) ``` The first symbol of the first alternative is the nonterminal itself, so `parse_directives()` begins by calling `parse_directives()`. Three facts combine: 1. The call happens **before** any token is consumed, so the input position is identical in the child call. 2. The lookahead token is therefore identical too. 3. Prediction is a pure function of the lookahead, so the child takes the **same** branch as the parent. Each level is an exact copy of the one above it. The only thing that changes is the stack depth, and the only terminating event is exhaustion. ## Direct and indirect forms | form | shape | how it is spotted | |---|---|---| | direct | `A -> A ...` | visible by reading one rule | | indirect | `A -> B ...`, `B -> C ...`, `C -> A ...` | only by following the chain of first symbols | | hidden | `A -> X A ...` where `X` can derive nothing | only after noticing `X` may vanish | The hidden form is the nastiest: the recursive symbol is not literally first, but everything before it can disappear, so at run time the function still re-enters itself without consuming. The general test is a cycle in the relation *"this nonterminal can appear as the first consuming symbol of that one"* — the same relation a FIRST-set computation walks, which is why the analysis that precedes writing the parser catches this on paper. ## Right recursion is not the same problem Write the same list the other way: ```pseudocode directives -> directive directives | (nothing) ``` Now the function parses a directive **first**, consuming at least one token, and only then recurses. Every level advances the input, so the recursion is bounded by the number of tokens and it terminates. This is why hand-written parsers use right recursion, or more often a plain loop, for repeated constructs. Be careful not to overstate it: right recursion terminates, but it still costs one stack frame per list element, so a list of a hundred thousand items can exhaust the stack too. That failure is different in kind — tokens *were* consumed, the depth tracks the input length, and replacing the recursion with a loop removes it. Left recursion cannot be fixed by a loop in the same way, because the problem is in the rule, not in the coding of it. ## Where the formal and the practical meet A left-recursive rule is not merely awkward for a hand-written parser; it is outside the class such a parser can handle at all. Every token that can begin the recursive alternative can also begin the non-recursive one — the recursion must eventually bottom out through it — so the two alternatives' prediction sets overlap and the rule is not LL(1). Adding lookahead does not help, because the overlap is unbounded rather than one token deep. That has a design consequence. Left recursion is not a defect in the grammar author's taste: it is the natural way to write a left-associative structure, which is why rule sets written for a bottom-up parser are full of it and cannot be handed to a top-down one unchanged. Restating the rules so the recursion stops being the function's first act is the standard repair; it is a grammar transformation with its own subtleties, including what it does to the shape of the tree you get back. ## Diagnosis checklist - Read the stack trace for a repeating cycle of frames, not a deep but varied one. - Check the input position at the crash: zero consumed means left recursion, not nesting depth. - Follow the chain of first symbols out of the repeating rule until it returns to itself. - Ask of each symbol crossed on the way whether it can derive nothing, which reveals the hidden form.

  • How do you tell this crash apart from one caused by legitimately deep nesting?
    By what the input position shows. Deep nesting consumes tokens on the way down, so the crash happens well into the file and the trace alternates between the several rules that nest. Left recursion crashes with nothing consumed and the same frame cycle repeating. A depth counter that reports the current token when it trips makes the distinction immediately.
  • Why is left recursion common in rule sets written for other parser families?
    Because it is the natural way to express a left-associative repeated structure, and a bottom-up parser handles it directly — it accumulates the left part on a stack rather than descending into it. Such a rule set therefore cannot be transcribed into a top-down parser unchanged; the rules must be restated first.
  • Is right recursion always safe in a hand-written parser?
    It terminates, which left recursion does not, but it uses one stack frame per element, so a very long list can still exhaust the stack. For repeated constructs most hand-written parsers replace the recursion with a loop, which keeps the same grammar and removes the depth entirely. Genuine nesting still needs recursion and so still needs a depth limit.

saying these in an interview costs you the question

  • Blames deeply nested input rather than the shape of the rule
  • Says the rule that derives nothing is what loops forever
  • Thinks a larger call stack fixes a left-recursive rule
  • Claims right recursion runs away for the same reason
  • Looks only for a rule that names itself directly, missing chains