Recursive Descent and LL Analysis

Recursive descent expresses grammar structure through function calls: expression functions call sub-expression functions, and statement functions call expression functions. LL analysis explains when you can select a production rule by looking at only a limited amount of lookahead; Pratt parsing organizes the decision-making for expression operators based on binding strength.

Hand-writing a recursive descent parser does not necessarily mean it is LL(1). Implementations may also use multi-token lookahead, backtracking, or semantic predicates; each added mechanism requires re-evaluating complexity, error recovery, and side effects.

From Grammar to Functions

Below, four arithmetic operations are described using EBNF repetition notation:

expr   = term, { ("+" | "-"), term } ;
term   = factor, { ("*" | "/"), factor } ;
factor = NUMBER | "(", expr, ")" ;

expr first parses a term, then loops to consume + or - operators followed by the next term; term handles * and / in the same way; factor handles numbers and parentheses. Higher precedence operators reside in deeper call layers, so 2 + 3 * 4 treats multiplication as the right subtree of addition.

A parsing function should define what it consumes, when it stops (before which tokens), and what it returns on success or failure. The entry point for a complete expression should also check for EOF; otherwise, 1 2 might be incorrectly parsed as a successful parse of 1.

Left-Recursion Elimination and Left-Associativity Are Not the Same Thing

Naive recursive descent directly implementing E → E - T | T will cause infinite recursion because it calls E again before consuming any input. Direct left-recursion can be rewritten as E → T E' and E' → - T E' | ε. Indirect left-recursion requires separate handling based on dependencies between non-terminals; some extended parsing algorithms also support left-recursion directly.

The right-recursive tail in the rewritten grammar does not imply that subtraction should be right-associative. When constructing the AST, use the current result as the left child of the new node, folding sequentially: after reading 8, you get Number; after reading - 3, you get Sub(8,3); after reading - 2, you get Sub(Sub(8,3),2).

FIRST, FOLLOW, and Predictive Sets

FIRST(α) is the set of terminal symbols that can begin strings derived from α; if α can derive the empty string, it also includes ε. FOLLOW(A) is the set of terminal symbols that can immediately follow A in some sentential form; the FOLLOW set of the start symbol includes the input end marker $.

When computing FIRST, propagate from left to right along the production rules; only continue to the next symbol if the previous one can be empty. For A → α B β, add FIRST(β) − {ε} to FOLLOW(B); if β can be empty, also add FOLLOW(A). For cyclic grammars, iterate until the sets no longer change.

Consider this simplified grammar:

E  → T E'
E' → + T E' | ε
T  → id

For a production A → α, the predictive set is FIRST(α) − {ε}; if α can be empty, merge in FOLLOW(A). The predictive sets for different alternatives of the same non-terminal must be pairwise disjoint to build an unambiguous LL(1) selection. Checking only that FIRST sets are disjoint will miss conflicts involving empty productions.

In the example, when E' sees +, it chooses to continue; when it sees $, it chooses ε; when it sees id, it should report an error and cannot unconditionally take ε. The predictive table simply tabulates these decisions, while recursive descent implements them as function branches.

Why Empty Productions Compete for the Same Token as Regular Alternatives

Consider S → A a and A → a | ε, where lowercase a is a terminal. The FIRST sets for the two right-hand sides of A are {a} and {ε}, which appear disjoint; however, FOLLOW(A) contains a, so the predictive set for the empty production is also {a}. When the parser sees a at A, it cannot decide solely based on this single token whether to consume it or leave it for the end of S.

For an input of length 1 (a), the choice should be A→ε; for an input of length 2 (aa), the choice should be A→a. This small grammar is not ambiguous, but it does not satisfy the LL(1) prediction condition for this grammar; you can rewrite the grammar corresponding to the language, or use more lookahead. Do not equate predictive table conflicts directly with language ambiguity.

def predict(first, nullable, follow):
    # first already excludes ε; nullable records whether it can be empty separately.
    return set(first) | (set(follow) if nullable else set())


def table(candidates):
    cells = {}
    for rule, lookaheads in candidates:
        for token in lookaheads:
            if token in cells:
                raise ValueError(f"conflict on {token}: {cells[token]} / {rule}")
            cells[token] = rule
    return cells


assert table([
    ("E' -> + T E'", predict({"+"}, False, {"$"})),
    ("E' -> empty", predict(set(), True, {"$"})),
]) == {"+": "E' -> + T E'", "$": "E' -> empty"}
try:
    table([
        ("A -> a", predict({"a"}, False, {"a"})),
        ("A -> empty", predict(set(), True, {"a"})),
    ])
except ValueError as error:
    assert "conflict on a" in str(error)
else:
    raise AssertionError("FIRST/FOLLOW conflict missed")

The code only constructs a predictive table for one non-terminal and is not responsible for computing the complete FIRST/FOLLOW sets for the entire grammar. It preserves the sources of the two conflicting productions to prevent later-inserted alternatives from silently overwriting existing ones; a real parser generator should also point out the relevant paths involving empty-string derivation and FOLLOW propagation to help locate grammar issues.

Why can epsilon compete for a lookahead?

Compare what production a consumes with what epsilon leaves for the caller. Under S→Aa both may see lookahead a: the short string a leaves it outside; aa consumes one inside. Changing S’s final terminal to b separates predictions. This changes the grammar’s prediction condition, not epsilon’s input consumption.

$$\mathrm{PRED}(A\to \alpha )=(\mathrm{FIRST}(\alpha )\setminus \{\epsilon \})\cup \{\begin{array}{ll}\mathrm{FOLLOW}(A)& \epsilon \in \mathrm{FIRST}(\alpha )\\ \varnothing & \text{otherwise}\end{array}$$

Common Prefixes, Ambiguity, and Backtracking

Left-factoring transforms A → αβ | αγ into A → αA' and A' → β | γ, delaying the choice until after the common prefix. However, this does not guarantee that any grammar becomes LL(1), nor does it automatically eliminate ambiguity.

The dangling else problem concerns which if block it should bind to. A language can specify matching the nearest unmatched if, require explicit end markers, or use grammar rules to distinguish matched and unmatched statements. Specific rules need to be stated; it is insufficient to simply call it "insufficient lookahead."

If speculative parsing backtracks, it must simultaneously restore the cursor, saved diagnostics, and other mutable state. Frequent retries may re-parse the same prefix; memoization increases memory usage and requires results to be correctly included in cache keys.

Pratt: Left and Right Binding Strength Control the Tree

Below is a runnable Python teaching implementation. The input is a list of already-tokenized tokens; numbers are non-negative decimal integers, and unary minus is parsed separately. Here, ^ is defined by this example language as exponentiation, unrelated to Python's bitwise XOR ^.

class Parser:
    # (left binding power, right recursion threshold)
    INFIX = {"+": (10, 11), "-": (10, 11),
             "*": (20, 21), "/": (20, 21), "^": (30, 30)}

    def __init__(self, tokens):
        self.tokens = list(tokens) + [None]
        self.pos = 0

    def peek(self):
        return self.tokens[self.pos]

    def take(self):
        token = self.peek()
        if token is None:
            raise SyntaxError("expected expression before EOF")
        self.pos += 1
        return token

    def expr(self, minimum=0):
        token = self.take()
        if token.isascii() and token.isdecimal():
            left = ("number", int(token))
        elif token == "-":
            left = ("negate", self.expr(30))
        elif token == "(":
            left = self.expr()
            if self.peek() != ")":
                raise SyntaxError("expected closing parenthesis")
            self.take()
        else:
            raise SyntaxError(f"expected expression, got {token!r}")

        while self.peek() in self.INFIX:
            op = self.peek()
            lbp, rbp = self.INFIX[op]
            if lbp < minimum:
                break
            self.take()
            left = (op, left, self.expr(rbp))
        return left

    def parse(self):
        result = self.expr()
        if self.peek() is not None:
            raise SyntaxError(f"unexpected trailing token {self.peek()!r}")
        return result

assert Parser(["8", "-", "3", "-", "2"]).parse() == (
    "-", ("-", ("number", 8), ("number", 3)), ("number", 2))

This implementation allows operators with lbp >= minimum to enter the current call. Left-associative subtraction uses 11 for the right side, so the right side does not consume the next minus sign with lbp 10, leaving it for the outer loop. Right-associative exponentiation has both left and right thresholds at 30, allowing the right side to continue absorbing subsequent exponentiation.

Unary minus starts its operand at 30, so - 2 ^ 2 is parsed as -(2^2). This is a deliberately chosen language rule; modifying the thresholds can define different rules. Parentheses and EOF are not in the infix table, naturally terminating the loop, and should not be assigned a fictitious minimum infix priority.

A complete Pratt implementation can also configure prefix, postfix, and infix handlers for tokens, adding function calls, member access, or ternary expressions. This example focuses on binding direction and does not include source positions, resource limits, or error recovery; deep nesting in actual implementations also requires avoiding stack overflow. The author's tutorial demonstrates this token-organized approach to expression compilation. Crafting Interpreters Chapter 17

Tracking Thresholds to Observe Which Call Consumes Which Token

For 8 - 3 - 2, the outer level sees the first minus sign and recursively parses the right side with a threshold of 11. The right side reads 3, then sees the second minus sign with a left binding power of 10, which is less than 11, so it returns without consuming the minus sign. The outer level first forms 8−3, then continues to consume the second minus sign, finally resulting in (8−3)−2.

Append the following assertions after the Parser definition to check the AST directly, without masking tree differences with evaluation results:

N = lambda x: ("number", x)
assert Parser(["2", "+", "3", "*", "4"]).parse() == ("+", N(2), ("*", N(3), N(4)))
assert Parser(["2", "^", "3", "^", "2"]).parse() == ("^", N(2), ("^", N(3), N(2)))
assert Parser(["-", "2", "^", "2"]).parse() == ("negate", ("^", N(2), N(2)))
assert Parser(["(", "-", "2", ")", "^", "2"]).parse() == ("^", ("negate", N(2)), N(2))
for tokens in ([], ["1", "2"], ["1", "+"], ["(", "1"], ["1", ")"], ["*", "2"]):
    try:
        Parser(tokens).parse()
    except SyntaxError:
        pass
    else:
        raise AssertionError(f"invalid input accepted: {tokens}")

Empty input, trailing tokens, missing right operand, missing closing parenthesis, and illegal prefixes originate from different failure points. Checking these entry and exit conditions reveals more about whether the parser fully consumes input than just observing whether a single expression yields the correct number.

How does one binding threshold change the tree?

Binding power is a consumption threshold for a recursive parse, not evaluation speed. A restricted Pratt parser produces the tree, parenthesized form and result below. Changing subtraction’s right threshold changes associativity; lowering multiplication below addition changes grouping. The decision log explains the transformation rather than merely displaying different answers.

Selection and Next Steps

Layered recursive descent is suitable for directly mapping language rules; Pratt is suitable for centrally managing expression operators. Generators can also provide good diagnostics, while hand-written parsers may have poor recovery; quality depends on implementation effort. For more general deterministic grammar handling, see LR Parsing; for the resulting tree structure, see AST Design and Error Recovery.

Keywords: recursive descent, LL(1), FIRST, FOLLOW, prediction set, left recursion, left factoring, Pratt parser, binding power, associativity