Recursive-descent parsing

Deep dive

How it works

In: source text lexed on demand, one token of lookahead · Out: an AST (arena nodes) or the byte offset of the first error · State: the current token and the recursion depth · Cost: O(n) time for LL(1) grammars, order of 300 MB/s measured below; stack O(nesting)

1. Write the grammar in EBNF with no left recursion; make every choice decidable by the next token (LL(1)), factoring common prefixes (IDENT ["(" ...]) if needed.
2. One function per nonterminal. { x } becomes a while loop on FIRST(x), [ x ] an if, a | b a match on the lookahead token.
3. Keep a single current token and advance with bump(); lex on demand, no token array.
4. Binary operators: one function per precedence level (loop = left-associative), or one table-driven function (Pratt parsing).
5. Build nodes bottom-up as each function returns; report the byte offset of the offending token on the first failure (or resynchronise, see parser error recovery).

expr    = term   { ("+" | "-") term }
term    = unary  { ("*" | "/") unary }
unary   = "-" unary | power
power   = primary [ "^" unary ]          -- 2^3^2 = 2^(3^2)
primary = NUM | IDENT | "(" expr ")"

Code

#[derive(Clone, Copy, PartialEq, Debug)]
pub enum Tok { Num(f64), Ident, Op(u8), LParen, RParen, Eof }

#[derive(Debug)]
pub struct ParseError { pub pos: usize, pub msg: &'static str }
type R<T> = Result<T, ParseError>;

/// Arena AST: children are u32 indices into `nodes`, no Box per node.
#[derive(Debug, PartialEq)]
pub enum Node { Num(f64), Var(u32, u32), Neg(u32), Bin(u8, u32, u32) } // Var = byte span of the name

const MAX_DEPTH: u32 = 200; // bounds native stack use on hostile input

pub struct Parser<'a> {
    src: &'a [u8],
    i: usize,     // lexer cursor
    tok: Tok,     // the single lookahead token (LL(1))
    start: usize, // byte offset where `tok` began
    depth: u32,
    pub nodes: Vec<Node>,
}

impl<'a> Parser<'a> {
    pub fn parse(src: &'a str) -> R<(Vec<Node>, u32)> {
        let mut p = Parser { src: src.as_bytes(), i: 0, tok: Tok::Eof, start: 0, depth: 0, nodes: Vec::new() };
        p.bump()?;
        let root = p.expr()?;
        if p.tok != Tok::Eof { return p.err("unexpected token after expression"); }
        Ok((p.nodes, root))
    }
    fn err<T>(&self, msg: &'static str) -> R<T> { Err(ParseError { pos: self.start, msg }) }
    fn push(&mut self, n: Node) -> u32 { self.nodes.push(n); (self.nodes.len() - 1) as u32 }
    fn scan(&mut self, f: impl Fn(u8) -> bool) { while self.i < self.src.len() && f(self.src[self.i]) { self.i += 1; } }

    /// Lexer on demand: no token Vec, no allocation.
    fn bump(&mut self) -> R<()> {
        self.scan(|c| c.is_ascii_whitespace());
        self.start = self.i;
        let Some(&c) = self.src.get(self.i) else { self.tok = Tok::Eof; return Ok(()) };
        self.i += 1;
        self.tok = match c {
            b'+' | b'-' | b'*' | b'/' | b'^' => Tok::Op(c),
            b'(' => Tok::LParen,
            b')' => Tok::RParen,
            b'0'..=b'9' | b'.' => {
                self.scan(|c| c.is_ascii_digit() || c == b'.');
                match std::str::from_utf8(&self.src[self.start..self.i]).unwrap().parse() {
                    Ok(v) => Tok::Num(v),
                    Err(_) => return self.err("bad number"),
                }
            }
            b'a'..=b'z' | b'A'..=b'Z' | b'_' => { self.scan(|c| c.is_ascii_alphanumeric() || c == b'_'); Tok::Ident }
            _ => return self.err("unexpected character"),
        };
        Ok(())
    }
    /// Run `f` one nesting level deeper; fail instead of overflowing the stack.
    fn nested(&mut self, f: fn(&mut Self) -> R<u32>) -> R<u32> {
        self.depth += 1;
        if self.depth > MAX_DEPTH { return self.err("nesting too deep"); }
        let r = f(self);
        self.depth -= 1;
        r
    }
    // expr = term { ("+" | "-") term }       left-assoc: a loop, never left recursion
    fn expr(&mut self) -> R<u32> {
        let mut lhs = self.term()?;
        while let Tok::Op(op @ (b'+' | b'-')) = self.tok {
            self.bump()?;
            let rhs = self.term()?;
            lhs = self.push(Node::Bin(op, lhs, rhs));
        }
        Ok(lhs)
    }
    // term = unary { ("*" | "/") unary }
    fn term(&mut self) -> R<u32> {
        let mut lhs = self.unary()?;
        while let Tok::Op(op @ (b'*' | b'/')) = self.tok {
            self.bump()?;
            let rhs = self.unary()?;
            lhs = self.push(Node::Bin(op, lhs, rhs));
        }
        Ok(lhs)
    }
    // unary = "-" unary | power
    fn unary(&mut self) -> R<u32> {
        if self.tok != Tok::Op(b'-') { return self.power(); }
        self.bump()?;
        let e = self.nested(Self::unary)?;
        Ok(self.push(Node::Neg(e)))
    }
    // power = primary [ "^" unary ]          right-assoc: recurse on the right
    fn power(&mut self) -> R<u32> {
        let base = self.primary()?;
        if self.tok != Tok::Op(b'^') { return Ok(base); }
        self.bump()?;
        let exp = self.nested(Self::unary)?;
        Ok(self.push(Node::Bin(b'^', base, exp)))
    }
    // primary = NUM | IDENT | "(" expr ")"
    fn primary(&mut self) -> R<u32> {
        match self.tok {
            Tok::Num(v) => { self.bump()?; Ok(self.push(Node::Num(v))) }
            Tok::Ident => {
                let n = Node::Var(self.start as u32, self.i as u32);
                self.bump()?;
                Ok(self.push(n))
            }
            Tok::LParen => {
                self.bump()?;
                let e = self.nested(Self::expr)?;
                if self.tok != Tok::RParen { return self.err("expected ')'"); }
                self.bump()?;
                Ok(e)
            }
            _ => self.err("expected expression"),
        }
    }
}

Tested with asserts: precedence, left/right associativity, error positions, 100 000-deep nesting rejected, 150 accepted.

Complexity and constants

• Time O(n) for LL(1): each token is lexed once and costs a few branches plus one arena push per node.
• Measured on one Apple-silicon Mac, release build, the code above on a 3.9 MB synthetic sum of products: about 12 ms, 1.2 M nodes, order of 300 MB/s. Real languages are slower (keywords, strings, larger grammars); order of 10-100 MB/s.
• Node is 16 bytes here; per-node Box allocations would cost an allocator call and a pointer chase each.
• Stack: one native frame per grammar level per nesting level (here about six frames per (). Frame size is compiler-dependent; measure it before choosing the limit.

Efficiency

• Cost: 3.9 MB of synthetic sums of products in about 12 ms (1.2 M nodes, order of 300 MB/s; measured above, Apple-silicon Mac, release build). Real languages are slower, order of 10-100 MB/s. Memory is 16 bytes per node; stack is about six frames per (. Bound: branch mispredictions on the lookahead match and allocation, not arithmetic.
• Levers:
  • arena Vec<Node> with u32 child indices — no allocator call or pointer chase per node — every parser; pre-size and free in one go
  • spans into the source, one-token window — no string copies, no token vector — parsers with on-demand lexing
  • one Pratt or precedence-climbing loop — one frame per atom instead of one per level — operator-heavy grammars
  • jump-table match on the first byte, tight or SIMD scans for strings and comments — fewer branches per byte — lexers
  • depth counter — turns a stack overflow into an error — input from outside
• Naive → standard → state of the art:
  • Box per node, string per token, one call per precedence level · allocator and call overhead per atom
  • arena nodes, on-demand lexing, one function per level · order of 300 MB/s on the synthetic input (measured)
  • same with a Pratt loop, spans and SIMD scanning · fewer calls per atom and fewer bytes touched (design claim, not measured)

Implementation notes

• Arena + u32 indices: one Vec<Node>, children as indices. Pre-sized with Vec::with_capacity, it avoids per-node malloc and frees in one go.
• Spans, not strings: store byte offsets into the source instead of copying identifiers; intern only when later phases need equality.
• Lex on demand with a one-token window; never materialise tokens unless you need unlimited lookahead or incremental reuse.
• Dispatch on the byte: match on the first byte compiles to a jump table; scan runs with tight loops, or SIMD for long strings and comments.
• Collapse levels: with many precedence levels, a function per level costs a chain of calls for every atom; a precedence-climbing or Pratt loop does it in one frame.
• Depth limit (a counter at each recursive entry, as nested above) turns a stack overflow, which is a process abort, into an ordinary error. Alternatively grow the stack (e.g. the stacker approach) or parse iteratively with an explicit stack.
• Peek further than one token only where needed, with a cheap peek2(); for rare cases of real ambiguity, try-parse with a saved cursor and rewind.

Pitfalls

• Left recursion: an infinite loop or stack overflow with no diagnostic; always rewrite as a loop.
• Wrong associativity: the loop form builds (a-b)-c; building the right-recursive form for - gives a-(b-c).
• Unary vs. binary minus and ^: decide where - sits relative to ^ explicitly (-x^2 here is -(x^2)), and test it.
• Unbounded recursion on adversarial input (((((...): a denial of service for any parser reachable from the network.
• Unchecked EOF: forgetting the final tok == Eof check accepts 1 2 as 1.
• Backtracking over nested alternatives multiplies: each failed try re-parses its subtree. Factor the grammar or memoise.
• Error cascades: after the first error, naive continuation emits garbage; either stop or resynchronise at known tokens (;, }).

Variants and alternatives

In production

• Language front ends: Lua's compiler is a single-pass recursive-descent parser that emits bytecode directly (lparser.c); Go's go/parser and the Rust parser (rustc_parse) are hand-written recursive descent, as is the TypeScript parser; Clang's C-family parser is hand-written recursive descent.
• Databases: ClickHouse parses queries with a hand-written recursive descent parser (architecture); sqlparser (Apache DataFusion) parses SQL statements the same way, with a Pratt parser for expressions (README).
• Editors and IDEs: rust-analyzer's parser crate is resilient recursive descent producing events for a lossless tree.

Implementations

Sources

• Robert Nystrom, Crafting Interpreters, 2021, chapter "Parsing Expressions". read
• Bryan Ford, Packrat Parsing: Simple, Powerful, Lazy, Linear Time, ICFP 2002; and Parsing Expression Grammars: A Recognition-Based Syntactic Foundation, POPL 2004. PEG paper · project page
• Niklaus Wirth, Compiler Construction, Addison-Wesley 1996 (recursive descent for Oberon-0).
• Lua source, lparser.c. code