Recursive Descent and the Cost of One Token of Lookahead

Recursive descent is the parser shape a hand-written front end takes, and the reason is not that it accepts the widest class of grammars. It is that each grammar rule becomes one function, the call stack mirrors the derivation, and a diagnostic can name the construct it was in the middle of. The method’s constraint is narrow: at each decision point the parser may consult one token, and every grammar must be rewritten until one token is enough.

The shape of the parser

Each nonterminal becomes a function that consumes exactly the tokens the nonterminal derives and returns whatever the caller wants, usually a syntax node. Terminals are matched against the current token.

/* expr := term (('+' | '-') term)* */
Node *parse_expr(Parser *p) {
    Node *left = parse_term(p);
    while (p->tok.kind == TOK_PLUS || p->tok.kind == TOK_MINUS) {
        TokenKind op = p->tok.kind;
        advance(p);                 /* consume the operator */
        Node *right = parse_term(p);
        left = make_binary(op, left, right);
    }
    return left;
}

Two properties make this work. The loop implements the star without recursion, so a left-associative operator chain of any length runs in constant stack depth. And the decision to continue or stop is made from the current token alone: + or - means continue, anything else means stop. That single-token test is the entire lookahead requirement, and it is why the grammar above is written with a loop rather than a right-recursive rule.

A right-recursive rule expr := term ('+' expr)? would also parse the same language, but it would recurse once per operator, so a chain of n operators consumes n stack frames. A chain of hundreds of concatenations, which machine-written source produces, would exhaust the stack; the loop form avoids it.

FIRST sets: which production can start here

When a nonterminal has several productions, the parser must pick one before consuming anything. The set of terminals that can begin a string derived from a symbol is its FIRST set, and if the FIRST sets of a nonterminal’s alternatives are disjoint, the current token selects the production unambiguously.

Computing FIRST is a fixed point over the grammar. A terminal’s FIRST set is itself. For a production, the FIRST set is the FIRST of its first symbol, extended by the FIRST of the next symbol whenever the first can derive the empty string, and so on. If every symbol can derive empty, the production’s FIRST set includes empty.

The parser then compiles to a switch on the token kind, with one arm per alternative. Where two alternatives share a starting terminal, the grammar is not LL(1) as written and no amount of code will fix the decision; the grammar has to change.

Language specifications publish their grammars in EBNF, with | for alternatives and either a trailing ?/* or a bracket pair for an optional or a repetition. The Go specification is written in a variant of that notation, and the translation from those EBNF productions to the forms above is mechanical.

FOLLOW sets and the empty alternative

An optional construct produces an empty alternative, and an empty alternative has an empty FIRST set, so the token test cannot select it. The information needed is what may come after the nonterminal. That is the FOLLOW set: the terminals that can appear immediately to the right of the nonterminal in any sentential form, plus the end-of-input marker if the nonterminal can end the input.

The rule for an optional trailing part is therefore: take it when the current token is in its FIRST set, and skip it when the current token is in the FOLLOW set of the enclosing nonterminal, because a FOLLOW token can only be the one that comes after the optional part. A token that lies in both sets makes the choice undecidable from one token, and the grammar is not LL(1) at that point.

A worked case is a statement list: stmts := stmt stmts | ε. The FIRST of stmt is the set of tokens that can begin a statement. The FOLLOW of stmts is whatever can follow the list, typically the end marker or a closing brace. The parser loops while the current token is in FIRST and stops on anything in FOLLOW. If a stray token appears that is in neither, it is a syntax error, and that distinction between “stop correctly” and “error” is exactly what error recovery needs.

The two rewrites that make grammars LL(1)

Two grammar shapes break single-token prediction, and both have standard repairs.

Left recursion is the first. A rule e := e '+' t puts the nonterminal at the head of its own production, so the function calls itself before consuming any input and recurses forever. The repair is to rewrite the rule as a loop: factor the recursive alternative into a tail that repeats. e := t e' with e' := '+' t e' | ε produces a left-associative tree from a loop and needs no stack per operator. For direct left recursion the rewrite is mechanical; for indirect recursion through several rules it needs the full transformation.

Common prefixes are the second. Two alternatives that start with the same terminals cannot be distinguished until they diverge, so the shared prefix is factored out into a new nonterminal and the remainder becomes a decision. This is the same transformation as factoring a common prefix out of two strings, applied to grammar rules, and it pushes the decision later, to the point where the alternatives actually differ.

Both rewrites change the grammar, not the language, which means the syntax tree shape must be built by the functions rather than read off the derivation. That is usually an improvement: the hand-written tree is the one the later passes want.

Where one token is provably not enough

Expression grammars are the classic failure. A statement can begin with an identifier, and so can an assignment, a declaration, a function call, and a labelled loop. Deciding among them may require scanning past the identifier to the next token, and in some languages further still.

The case that cannot be repaired by rewriting is a grammar whose alternatives are distinguishable only by unbounded lookahead. C’s declaration syntax is the standard example: T * x; is either a declaration of a pointer or a multiplication, and which one it is depends on whether T was declared as a type. No grammar rewrite resolves that, because the answer lives in the symbol table, not the token stream. This is the reason C front ends are not pure LL(1) and why context-dependent lexing exists.

When the required lookahead is bounded but larger than one, the parser can buffer tokens and test k of them. The grammar is then LL(k), and the number of states in the canonical LL(k) table can grow exponentially in k, which is why building the table for k above two or three is rarely worth it and hand-written code usually does the buffering with an explicit check.

For expression grammars specifically, the loop rewrite fixes associativity but not precedence: a grammar with several precedence levels needs one nonterminal, and therefore one function, per level, and the set of functions must be edited whenever the operator table changes. The alternative that keeps precedence as data is set out in Precedence Climbing for Binary Expressions. For grammars where rewriting is not acceptable because the grammar is fixed by a standard or shared with other tools, table-driven methods that tolerate more conflict are covered in LALR Table Construction and What the Conflicts Mean.

Predictions and predicates beyond the token test

Some parsers extend the one-token decision with an arbitrary predicate. The parser calls a function that inspects the token stream, the symbol table, or a version flag, and takes an alternative based on the boolean. This keeps the grammar in recursive-descent form while admitting decisions that no context-free grammar can express.

The cost is that the parser’s behaviour is no longer described by the grammar, so a grammar-based tool cannot verify it, and two implementations of the same language may accept different inputs. Predicates also make error recovery harder, since a failed predicate produces no expected-token set to report. The usual compromise is to restrict predicates to places where the alternative is a syntactic extension and the fallback diagnostic is still accurate.

Left factoring versus precedence in code

Consider a grammar with statements that may begin with an identifier, where one form is an assignment and another is a call. Factoring produces a rule that parses the identifier and then switches on the following token. That is the rewrite in practice: the function reads the identifier, then looks at the next token, then commits.

def parse_statement(p):
    if p.peek().kind == "IDENT":
        name = p.expect("IDENT")
        if p.peek().kind == "ASSIGN":
            p.advance()
            return Assign(name, parse_expr(p))
        if p.peek().kind == "LPAREN":
            return parse_call_rest(p, name)
        raise ParseError(p.peek(), expected=["=", "("])
    if p.peek().kind == "IF":
        return parse_if(p)
    raise ParseError(p.peek(), expected=["IDENT", "IF"])

The expected list in each error is not decoration. It is the FIRST set of the alternatives at that point, and producing it is the one thing a table-driven parser can do more easily than a hand-written one. Hand-written parsers must maintain those sets by hand, which is where most of their maintenance cost sits, and the same sets are what error recovery consumes as described in Error Recovery in Recursive Descent.