Part 1 · 1 chapters · ~8 min

Parsing: Recursive Descent, Pratt, LR

Recursive descent for statements, Pratt parsing (top-down operator precedence) for expressions, binding powers and associativity, prefix operators, error messages and recovery, LL and LR parsing, parser generators (yacc, Bison, ANTLR, tree-sitter), and why most production compilers hand-write parsers.

The BYO Pratt loop

code

// from src/parser.ts
const BP = { '||': 1, '&&': 2, '==': 3, '!=': 3, '<': 4, '<=': 4, '>': 4, '>=': 4, '+': 5, '-': 5, '*': 6, '/': 6, '%': 6 };

function expr(minBp = 0): Expr {
  let left = prefix();                                  // number, bool, var, call, ( expr ), -e or !e (bp 7)
  for (;;) {
    const op = peek(); const bp = BP[op.text];
    if (op.kind !== 'op' || bp === undefined || bp <= minBp) break;   // left-associative: <=
    next();
    left = { k: 'binary', op: op.text, l: left, r: expr(bp), line: op.line, col: op.col };
  }
  return left;
}

technique	strength	used by
recursive descent (hand-written)	simple, great errors, easy to extend	GCC (C++ since 3.4 in 2004, C since 4.1 in 2006), Clang, Go, V8, TypeScript, Rust
Pratt / precedence climbing	expressions with many operators in one loop	many hand-written parsers for their expression part
LR / LALR (generated)	handles large grammars, finds ambiguity	yacc, Bison; PostgreSQL's SQL grammar
GLR / incremental	error-tolerant, re-parses on each keystroke	tree-sitter (editors, GitHub code navigation)

PRATT PARSING 1 - 2 - 3 * 4

binding powers decide where each operator attaches

swipe the figure sideways, or tap expand for full screen

1/4

binding power

Each infix operator has a binding power: || 1, && 2, comparison 3-4, + and - 5, * / % 6. The loop keeps consuming operators stronger than the current minimum.

one table of powersBP in parser.ts