Crafting a parser, part 2: grammars and recursive descent

With a token stream in hand, we can talk about grammar. A parser's job is to decide whether a sequence of tokens fits the language's rules — and to build a tree while it does.

Grammars in one screen

A context-free grammar maps a nonterminal to sequences of terminals (tokens) and other nonterminals. Written in EBNF, a slice of our toy language looks like this:

grammar.ebnf

1program    = statement* EOF ;2statement  = letDecl | exprStmt ;3letDecl    = "let" IDENT "=" expression ";" ;4exprStmt   = expression ";" ;

Why recursive descent

Each grammar rule becomes one function. statement() calls let_decl() or expr_stmt(); those call expression(); the call stack is the parse tree. It is the most readable parsing technique ever invented, and it is what GCC, Clang, and rustc all use by hand.

parser.rs

1fn statement(&mut self) -> Stmt {2    match self.peek().kind {3        TokenKind::Let => self.let_decl(),4        _ => self.expr_stmt(),5    }6}

The call graph mirrors the grammar — each rule is a node, each call an edge:

graph TD
  program --> statement
  statement --> letDecl
  statement --> exprStmt
  letDecl --> expression
  exprStmt --> expression
  expression --> term
  term --> factor

Left recursion is a trap

A rule like expr = expr "+" term translates directly into a function that calls itself with no progress — instant stack overflow. Recursive descent cannot handle left recursion. Rewrite it as iteration, term ("+" term)*, which is exactly what Pratt parsing formalizes.

Predictive parsing

The match above is predictive: one token of lookahead picks the rule, no backtracking. A grammar where lookahead-1 always suffices is called LL(1), and it is the sweet spot — fast, linear, and easy to reason about.

consume / expect

owns: terminals

`bump()` advances`expect(kind)` advances or records an error

The two primitives every rule is built from.

peek

owns: the decision

one token of lookaheadnever consumes

Drives every `match` that selects a production.

The parser struct

parser.rs

1pub struct Parser<'src> {2    tokens: Lexer<'src>,3    current: Token,4}

Holding the lexer (not a pre-collected Vec<Token>) keeps parsing streaming and lets us build the IDE-friendly variant in part seven.

Takeaways

One function per nonterminal; the call stack mirrors the tree.
Kill left recursion by rewriting to loops.
LL(1) + predictive dispatch gives linear-time, readable parsing.

Next: designing the AST.