Recursive-descent parsing

Intermediate

Introduction

The parser is the heart of a compiler's front end. It checks that the tokens follow the grammar and builds a tree that later phases use. The simplest kind of parser to write by hand is recursive descent: each grammar rule becomes a function, and the functions call each other the same way the rules mention each other. GCC, Clang, Go, the TypeScript compiler and CPython's newer parser are all recursive-descent parsers at heart. If you can write a grammar, you can write this kind of parser.

How it works

Start from a grammar for expressions with operators at several precedence levels:

expr   → term (("+" | "-") term)*
term   → unary (("*" | "/") unary)*
unary  → "-" unary | power
power  → atom ("^" unary)?
atom   → NUMBER | NAME | "(" expr ")"

Each rule becomes one function. Lower precedence calls higher precedence, so expr calls term, which calls unary, and so on. That alone makes * bind tighter than +: by the time expr sees a +, both sides have already been parsed as complete terms.

Associativity comes from the shape of the code. A while loop that builds (op, left, right) and keeps going makes the operator left-associative: 8 − 3 − 2 becomes (8 − 3) − 2. Calling the function again on the right-hand side makes it right-associative: 2 ^ 3 ^ 2 becomes 2 ^ (3 ^ 2), as in mathematics.

Left recursion is the one thing recursive descent cannot handle directly. The natural rule E → E + T would make expr call expr immediately, forever. The fix is to rewrite it as E → T (+ T), which is exactly the loop above. In general, A → A α | β becomes A → β α.

The parser consumes tokens with two helpers: peek looks at the next token, and take consumes it, optionally checking that it is the expected one. When something unexpected appears, the parser raises an error that names what it found, so the user knows where the problem is.

Syntax

def expr():
    node = term()
    while peek() in ("+", "-"):           # loop: left-associative
        node = (take(), node, term())
    return node

def power():
    base = atom()
    if peek() == "^":                      # recursion on the right: right-associative
        take(); return ("^", base, unary())
    return base

Example

import re


def parse(text):
    tokens = re.findall(r"\d+|[A-Za-z_]\w*|\S", text)
    pos = 0

    def peek():
        return tokens[pos] if pos < len(tokens) else None

    def take(expected=None):
        nonlocal pos
        token = peek()
        if expected and token != expected:
            found = "the end" if token is None else repr(token)
            raise SyntaxError(f"expected {expected!r} but found {found}")
        pos += 1
        return token

    def expr():
        node = term()
        while peek() in ("+", "-"):
            node = (take(), node, term())
        return node

    def term():
        node = unary()
        while peek() in ("*", "/"):
            node = (take(), node, unary())
        return node

    def unary():
        if peek() == "-":
            take()
            return ("neg", unary())
        return power()

    def power():
        base = atom()
        if peek() == "^":
            take()
            return ("^", base, unary())
        return base

    def atom():
        token = peek()
        if token == "(":
            take()
            node = expr()
            take(")")
            return node
        if token is not None and (token.isdigit() or token.isidentifier()):
            return take()
        raise SyntaxError(f"unexpected {token!r}")

    tree = expr()
    if peek() is not None:
        raise SyntaxError(f"unexpected {peek()!r} after the expression")
    return tree


def lisp(node):
    if isinstance(node, str):
        return node
    return "(" + " ".join([node[0]] + [lisp(child) for child in node[1:]]) + ")"


for text in ["1 + 2 * 3", "(1 + 2) * 3", "2 ^ 3 ^ 2", "-x ^ 2", "8 - 3 - 2", "1 + * 2", "(4 + 5"]:
    try:
        print(f"{text:12} -> {lisp(parse(text))}")
    except SyntaxError as error:
        print(f"{text:12} -> error: {error}")
Open in compiler

Line by line

  1. The lexer is one regular expression: numbers, names, or any single non-space character.
  2. expr, term, unary, power and atom follow the grammar, one level each.
  3. The tree is printed in prefix form, such as (+ 1 (* 2 3)), where each bracket is one node with its operator first.
  4. 2 ^ 3 ^ 2 groups to the right, 8 - 3 - 2 to the left, and -x ^ 2 is the negation of x², as in mathematics.
  5. 1 + * 2 fails at the *, which cannot start an operand, and (4 + 5 fails because the input ends where the closing bracket should be.

Expected result

1 + 2 * 3    -> (+ 1 (* 2 3))
(1 + 2) * 3  -> (* (+ 1 2) 3)
2 ^ 3 ^ 2    -> (^ 2 (^ 3 2))
-x ^ 2       -> (neg (^ x 2))
8 - 3 - 2    -> (- (- 8 3) 2)
1 + * 2      -> error: unexpected '*'
(4 + 5       -> error: expected ')' but found the end

In the real world

Hand-written recursive-descent parsers are popular because they are fast, easy to debug and give good error messages. Clang parses all of C, C++ and Objective-C this way. Many parsers use a variant called Pratt parsing or precedence climbing, which handles dozens of operators with one function and a precedence table.

Common mistakes

  • Writing E → E + T directly, which recurses forever: rewrite it as a loop.
  • Getting the precedence order backwards: the lowest-precedence operator belongs in the outermost function.
  • Making every operator right-associative by recursing, so 8 − 3 − 2 becomes 8 − (3 − 2).
  • Forgetting to check that all tokens were used, so 1 + 2 3 is silently accepted.

Best practices

  • Write the grammar first, then translate it rule by rule.
  • Keep peek and take as the only ways to touch the token list.
  • Print the tree in prefix form while testing; it shows the grouping at a glance.

Summary

A recursive-descent parser has one function per grammar rule. Calling lower-precedence functions from higher ones in order gives precedence; loops give left associativity and recursion on the right gives right associativity. Left recursion must be rewritten as a loop, and every unexpected token should produce a clear error.

Quick check

1. Which function should handle + in an expression parser?
2. Why can't recursive descent use E → E + T directly?
3. With a while loop for −, how is 8 − 3 − 2 grouped?
4. How does the parser make ^ right-associative?

Key takeaways

  • One function per precedence level, lowest first, gives precedence for free.
  • A loop gives left associativity; a recursive call on the right gives right associativity.
  • Rewrite E → E + T as E → T (+ T)* before writing the parser.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.