Write a Recursive-Descent Parser by Hand (Once)

Parser generators exist. ANTLR, PEG.js, tree-sitter, and a dozen others will take a grammar file and produce a working parser faster than you can write one by hand. So why would anyone do it manually?

Three reasons, from my experience building xpr-lang’s parsers across TypeScript, Python, and Go.

First, error messages. Generated parsers produce errors like “unexpected token at position 47.” Hand-written parsers can say “missing closing parenthesis for the function call starting at line 3, column 12.” When your users are non-programmers writing transform expressions, error quality determines whether they can self-serve or file a support ticket.

Second, debuggability. When a generated parser misbehaves, you’re debugging generated code, which is roughly as fun as debugging minified JavaScript. A hand-written parser is just functions calling functions. Set a breakpoint in parseExpression() and step through the logic.

Third, zero dependencies. xpr-lang ships to npm, PyPI, and Go modules. Each runtime’s parser is self-contained, with no external grammar tooling required.

But honestly? The best reason is that writing a parser by hand permanently upgrades how you think about code. Every language you use afterward, you’ll understand more deeply.

Let’s build one. We’ll create a small expression language with variables, arithmetic, comparisons, and function calls in TypeScript. Tiny enough to fit in a blog post, complex enough to demonstrate the real techniques.

The Three Stages

Every language implementation follows the same pipeline:

Source Code  →  Lexer  →  Tokens  →  Parser  →  AST  →  Evaluator  →  Result

The lexer (tokenizer) breaks raw source text into meaningful chunks called tokens. 42 + x becomes three tokens: NUMBER(42), PLUS, IDENTIFIER(x).

The parser reads the token stream and builds an Abstract Syntax Tree (AST) that represents the structure. It enforces operator precedence and catches syntax errors.

The evaluator walks the AST and computes the result.

Here’s the grammar for our language, written in EBNF:

expression     = comparison
comparison     = addition (("==" | "!=" | "<" | ">" | "<=" | ">=") addition)*
addition       = multiplication (("+" | "-") multiplication)*
multiplication = unary (("*" | "/" | "%") unary)*
unary          = ("-" | "!") unary | call
call           = primary ("(" arguments? ")")*
arguments      = expression ("," expression)*
primary        = NUMBER | STRING | IDENTIFIER | "true" | "false"
               | "null" | "(" expression ")"

Each line is a precedence level. Lower in the grammar means higher precedence. primary binds tightest; comparison binds loosest. This structure is the key insight.

The Lexer

The lexer scans source text character by character and produces tokens:

type TokenType =
  | "NUMBER" | "STRING" | "IDENTIFIER"
  | "TRUE" | "FALSE" | "NULL"
  | "PLUS" | "MINUS" | "STAR" | "SLASH" | "PERCENT"
  | "BANG" | "BANG_EQUAL" | "EQUAL_EQUAL"
  | "LESS" | "LESS_EQUAL" | "GREATER" | "GREATER_EQUAL"
  | "LPAREN" | "RPAREN" | "COMMA" | "EOF";

interface Token {
  type: TokenType;
  value: string;
  position: number; // byte offset for error reporting
}

class ParseError extends Error {
  constructor(message: string, public position: number) {
    super(message);
  }
}

function tokenize(source: string): Token[] {
  const tokens: Token[] = [];
  let i = 0;

  const singles: Record<string, TokenType> = {
    "+": "PLUS", "-": "MINUS", "*": "STAR", "/": "SLASH",
    "%": "PERCENT", "!": "BANG", "<": "LESS", ">": "GREATER",
    "(": "LPAREN", ")": "RPAREN", ",": "COMMA",
  };

  // Two-char operators: first char → second char → token type
  const doubles: Record<string, Record<string, TokenType>> = {
    "!": { "=": "BANG_EQUAL" },
    "=": { "=": "EQUAL_EQUAL" },
    "<": { "=": "LESS_EQUAL" },
    ">": { "=": "GREATER_EQUAL" },
  };

  const keywords: Record<string, TokenType> = {
    true: "TRUE", false: "FALSE", null: "NULL",
  };

  while (i < source.length) {
    if (" \t\r\n".includes(source[i])) { i++; continue; }

    const start = i;
    const ch = source[i];

    // Try two-character token first
    if (doubles[ch]?.[source[i + 1]]) {
      const type = doubles[ch][source[i + 1]];
      tokens.push({ type, value: ch + source[i + 1], position: start });
      i += 2;
      continue;
    }

    // Single-character tokens
    if (singles[ch]) {
      tokens.push({ type: singles[ch], value: ch, position: start });
      i++;
      continue;
    }

    // Numbers (integer or decimal)
    if (ch >= "0" && ch <= "9") {
      while (i < source.length && source[i] >= "0" && source[i] <= "9") i++;
      if (i < source.length && source[i] === ".") {
        i++;
        while (i < source.length && source[i] >= "0" && source[i] <= "9") i++;
      }
      tokens.push({ type: "NUMBER", value: source.slice(start, i), position: start });
      continue;
    }

    // Strings (double-quoted)
    if (ch === '"') {
      i++;
      while (i < source.length && source[i] !== '"') i++;
      if (i >= source.length) throw new ParseError("Unterminated string", start);
      i++;
      tokens.push({ type: "STRING", value: source.slice(start + 1, i - 1), position: start });
      continue;
    }

    // Identifiers and keywords
    if (isAlpha(ch)) {
      while (i < source.length && isAlphaNumeric(source[i])) i++;
      const word = source.slice(start, i);
      tokens.push({ type: keywords[word] || "IDENTIFIER", value: word, position: start });
      continue;
    }

    throw new ParseError(`Unexpected character: ${ch}`, start);
  }

  tokens.push({ type: "EOF", value: "", position: i });
  return tokens;
}

function isAlpha(ch: string): boolean {
  return (ch >= "a" && ch <= "z") || (ch >= "A" && ch <= "Z") || ch === "_";
}

function isAlphaNumeric(ch: string): boolean {
  return isAlpha(ch) || (ch >= "0" && ch <= "9");
}

The lexer is a big while loop with pattern matching. Each iteration consumes one token and advances the position. The position field is critical for error messages later.

Notice the two-character token handling uses a lookup table instead of repeated if-chains. This is a small taste of how real lexers stay maintainable as the token set grows.

Precedence Climbing: The Parser

Here’s where it gets interesting. The parser needs to respect operator precedence: 2 + 3 * 4 must parse as 2 + (3 * 4), not (2 + 3) * 4.

Recursive-descent handles this elegantly. Each precedence level becomes a function, and each function calls the next-higher precedence level. Lower-precedence operators live in higher-level functions.

Here is that chain for the full xpr-lang grammar — twelve levels, each one function, descending from the loosest binding to the tightest. Associativity decides the shape of each function: left-associative levels loop over the operator, right-associative levels recurse into themselves.

type Expr =
  | { type: "number"; value: number }
  | { type: "string"; value: string }
  | { type: "boolean"; value: boolean }
  | { type: "null" }
  | { type: "identifier"; name: string }
  | { type: "unary"; operator: string; operand: Expr }
  | { type: "binary"; operator: string; left: Expr; right: Expr }
  | { type: "call"; callee: Expr; args: Expr[] };

class Parser {
  private current = 0;
  constructor(private tokens: Token[]) {}

  parse(): Expr {
    const expr = this.expression();
    if (!this.isAtEnd()) {
      throw new ParseError(`Unexpected token: ${this.peek().value}`, this.peek().position);
    }
    return expr;
  }

  // Each method corresponds to a grammar rule.
  private expression(): Expr { return this.comparison(); }

  private comparison(): Expr {
    let left = this.addition();
    while (this.matchAny("EQUAL_EQUAL", "BANG_EQUAL", "LESS",
                          "GREATER", "LESS_EQUAL", "GREATER_EQUAL")) {
      const op = this.previous().value;
      left = { type: "binary", operator: op, left, right: this.addition() };
    }
    return left;
  }

  private addition(): Expr {
    let left = this.multiplication();
    while (this.matchAny("PLUS", "MINUS")) {
      const op = this.previous().value;
      left = { type: "binary", operator: op, left, right: this.multiplication() };
    }
    return left;
  }

  private multiplication(): Expr {
    let left = this.unary();
    while (this.matchAny("STAR", "SLASH", "PERCENT")) {
      const op = this.previous().value;
      left = { type: "binary", operator: op, left, right: this.unary() };
    }
    return left;
  }

  private unary(): Expr {
    if (this.matchAny("MINUS", "BANG")) {
      return { type: "unary", operator: this.previous().value, operand: this.unary() };
    }
    return this.call();
  }

  private call(): Expr {
    let expr = this.primary();
    while (this.matchAny("LPAREN")) {
      const args: Expr[] = [];
      if (!this.check("RPAREN")) {
        do { args.push(this.expression()); } while (this.matchAny("COMMA"));
      }
      this.expect("RPAREN", "Expected ')' after arguments");
      expr = { type: "call", callee: expr, args };
    }
    return expr;
  }

  private primary(): Expr {
    if (this.matchAny("NUMBER"))     return { type: "number", value: parseFloat(this.previous().value) };
    if (this.matchAny("STRING"))     return { type: "string", value: this.previous().value };
    if (this.matchAny("TRUE"))       return { type: "boolean", value: true };
    if (this.matchAny("FALSE"))      return { type: "boolean", value: false };
    if (this.matchAny("NULL"))       return { type: "null" };
    if (this.matchAny("IDENTIFIER")) return { type: "identifier", name: this.previous().value };
    if (this.matchAny("LPAREN")) {
      const expr = this.expression();
      this.expect("RPAREN", "Expected ')' after grouped expression");
      return expr;
    }
    throw new ParseError(`Expected expression, got '${this.peek().value}'`, this.peek().position);
  }

  // Helpers
  private matchAny(...types: TokenType[]): boolean {
    for (const t of types) { if (this.check(t)) { this.current++; return true; } }
    return false;
  }
  private check(type: TokenType): boolean { return !this.isAtEnd() && this.peek().type === type; }
  private expect(type: TokenType, msg: string): Token {
    if (this.check(type)) { this.current++; return this.tokens[this.current - 1]; }
    throw new ParseError(msg, this.peek().position);
  }
  private peek(): Token { return this.tokens[this.current]; }
  private previous(): Token { return this.tokens[this.current - 1]; }
  private isAtEnd(): boolean { return this.peek().type === "EOF"; }
}

Study the call chain. When parsing 2 + 3 * 4, execution flows:

1. expression() calls comparison(), which calls addition()
2. addition() calls multiplication(), which parses 2
3. Back in addition(), we see +, so we call multiplication() again
4. multiplication() parses 3, sees *, parses 4, returns 3 * 4 as a binary node
5. addition() wraps the result as 2 + (3 * 4)

Precedence falls out of the call structure. Multiplication binds tighter because its function gets called deeper in the recursion, closer to the leaf nodes. This is the core insight. Once it clicks, you won’t forget it.

The Evaluator

With an AST in hand, evaluation is the simplest stage:

type Value = number | string | boolean | null;

const builtins: Record<string, (...args: Value[]) => Value> = {
  abs:   (n) => Math.abs(n as number),
  max:   (...a) => Math.max(...(a as number[])),
  min:   (...a) => Math.min(...(a as number[])),
  len:   (s) => (s as string).length,
  upper: (s) => (s as string).toUpperCase(),
  lower: (s) => (s as string).toLowerCase(),
};

function evaluate(expr: Expr, env: Record<string, Value> = {}): Value {
  switch (expr.type) {
    case "number": case "string": case "boolean": return expr.value;
    case "null":       return null;
    case "identifier": {
      if (expr.name in env) return env[expr.name];
      throw new Error(`Undefined variable: ${expr.name}`);
    }
    case "unary": {
      const val = evaluate(expr.operand, env);
      if (expr.operator === "-") return -(val as number);
      if (expr.operator === "!") return !val;
      throw new Error(`Unknown unary operator: ${expr.operator}`);
    }
    case "binary": {
      const l = evaluate(expr.left, env), r = evaluate(expr.right, env);
      switch (expr.operator) {
        case "+":  return (l as number) + (r as number);
        case "-":  return (l as number) - (r as number);
        case "*":  return (l as number) * (r as number);
        case "/":  return (l as number) / (r as number);
        case "%":  return (l as number) % (r as number);
        case "==": return l === r;  case "!=": return l !== r;
        case "<":  return (l as number) < (r as number);
        case ">":  return (l as number) > (r as number);
        case "<=": return (l as number) <= (r as number);
        case ">=": return (l as number) >= (r as number);
        default: throw new Error(`Unknown operator: ${expr.operator}`);
      }
    }
    case "call": {
      if (expr.callee.type !== "identifier") throw new Error("Can only call functions by name");
      const fn = builtins[expr.callee.name];
      if (!fn) throw new Error(`Unknown function: ${expr.callee.name}`);
      return fn(...expr.args.map(a => evaluate(a, env)));
    }
  }
}

Wire it all together:

function run(source: string, variables: Record<string, Value> = {}): Value {
  const tokens = tokenize(source);
  const ast = new Parser(tokens).parse();
  return evaluate(ast, variables);
}

// Try it out
console.log(run("2 + 3 * 4"));                     // 14
console.log(run("(2 + 3) * 4"));                    // 20
console.log(run("price > 100", { price: 150 }));    // true
console.log(run("upper(name)", { name: "alice" })); // "ALICE"
console.log(run("max(a, b) + 1", { a: 3, b: 7 })); // 8

In roughly 200 lines, you have a working expression evaluator with variables, operators, function calls, and proper precedence.

Error Messages: The Part That Matters Most

Generated parsers typically give you “Syntax error at offset 23.” Users stare at these and file tickets. Hand-written parsers can do much better because you control every error path.

Our Token carries a position field, and ParseError includes it. We can convert byte offsets to line and column numbers:

function formatError(source: string, error: ParseError): string {
  let line = 1, col = 1;
  for (let i = 0; i < error.position && i < source.length; i++) {
    if (source[i] === "\n") { line++; col = 1; } else { col++; }
  }
  const lines = source.split("\n");
  const sourceLine = lines[line - 1] || "";
  const pointer = " ".repeat(col - 1) + "^";
  return `Error at line ${line}, column ${col}: ${error.message}\n\n  ${sourceLine}\n  ${pointer}`;
}

Now max(3, ) produces:

Error at line 1, column 8: Expected expression, got ')'

  max(3, )
         ^

Compare that to “unexpected RPAREN.” The difference is night and day for anyone who isn’t a compiler engineer.

You can go further. In xpr-lang, the parser tracks context (“we’re inside a function call that started at line 3, column 5”) so that a missing closing paren says where the opening paren was, not just where the parser gave up. Extra bookkeeping, but the kind of polish that makes a language feel professional.

Where to Go from Here

The parser we built handles a useful subset. At xpr-lang scale, several things change:

More precedence levels. xpr-lang has pipe operators, logical AND/OR, nullish coalescing, and ternary conditionals. The recursive-descent structure scales cleanly: add more functions between expression() and primary().

Multiple runtimes. Writing the same parser in TypeScript, Python, and Go was tedious and deeply educational. Go doesn’t have union types, so the AST uses interfaces. Python’s match statement makes the evaluator elegant. Same logic, different texture.

The conformance suite. With 601 YAML test cases shared across three runtimes, the parser is the least of your worries. The real complexity lives in evaluation semantics. I wrote about those battles in One Grammar, Three Runtimes.

Further reading. Bob Nystrom’s Crafting Interpreters is the definitive guide. It walks through building a complete language with a tree-walk interpreter and then a bytecode VM. My parser above borrows its structure from Nystrom’s Lox parser, adapted for an expression-only language.

Every engineer should write one parser by hand. Just one. After that, you’ll understand what parser generators do for you, you’ll write better error messages in every tool you build, and you’ll read language specifications without flinching.

Check out xpr-lang or try it in the browser playground.

---

The code in this post is a simplified teaching example. xpr-lang’s actual parsers handle arrow functions, pipe operators, optional chaining, destructuring, regex literals, and more. The principles are identical; the implementation is just… longer.