3.11 — Capstone: Build a Toy Language

3.1 described the compiler pipeline — lexer, parser, semantic analysis, execution — as a sequence of stages. Reading that is one thing; building it is another, and the gap between them is where real understanding lives. This closing chapter of Part 3 is a capstone: we build a small but genuinely working programming language from scratch, in about 150 lines of JavaScript, and by the end you will have implemented every stage 3.1 named.

The payoff is disproportionate. Once you have written a lexer and a parser, compilers stop being magic, ASTs stop being jargon, and a whole category of tools — linters, formatters, bundlers, template engines, query parsers, configuration languages, DSLs — become things you could build rather than merely use. It is also the single most effective way to make 3.1 and 1.7 permanent.

1. Designing the language

Keep the scope ruthlessly small — a capstone that never finishes teaches nothing. Our language, Toy, will support numbers, arithmetic with correct precedence, variables, and printing:

let x = 2 + 3 * 4;
print x;              // 14 — precedence must work
let y = (x + 1) / 3;
print y;              // 5

That's enough to require every pipeline stage: tokenizing text, parsing with precedence and parentheses, tracking variables in an environment, and evaluating. We'll build an interpreter rather than a compiler (3.2) because it's dramatically shorter — we walk the AST and perform the operations directly, rather than generating machine code.

The architecture is exactly 3.1's:

Figure 1 — What we're building. The same pipeline as any real compiler, minus the IR and code generation: text → tokens → tree → execution.

2. The lexer: text → tokens

The lexer scans characters and groups them into tokens (3.1). Its logic is a loop with a switch: look at the current character, decide what kind of token starts here, consume it, repeat.

function lex(src) {
  const tokens = [];
  let i = 0;

  while (i < src.length) {
    const c = src[i];

    // 1. Skip whitespace — carries no meaning, so it never becomes a token
    if (/\s/.test(c)) { i++; continue; }

    // 2. Numbers: consume a run of digits
    if (/[0-9]/.test(c)) {
      let num = "";
      while (i < src.length && /[0-9]/.test(src[i])) num += src[i++];
      tokens.push({ type: "NUMBER", value: Number(num) });
      continue;
    }

    // 3. Identifiers and keywords: a run of letters
    if (/[a-zA-Z]/.test(c)) {
      let word = "";
      while (i < src.length && /[a-zA-Z]/.test(src[i])) word += src[i++];
      const type = (word === "let" || word === "print") ? word.toUpperCase() : "IDENT";
      tokens.push({ type, value: word });
      continue;
    }

    // 4. Single-character symbols
    const symbols = { "+": "PLUS", "-": "MINUS", "*": "STAR", "/": "SLASH",
                      "=": "EQUALS", "(": "LPAREN", ")": "RPAREN", ";": "SEMI" };
    if (symbols[c]) { tokens.push({ type: symbols[c], value: c }); i++; continue; }

    throw new Error(`Unexpected character: ${c}`);
  }

  tokens.push({ type: "EOF" });
  return tokens;
}

Three things to notice, each illustrating a point from 3.1. Whitespace is discarded — it has no meaning for execution, which is why formatting can't change program behaviour. Keywords are just identifiers with special names: we scan any word, then check whether it happens to be let or print. And the whole thing is a finite automaton (1.7) — a state machine with no memory beyond the current position, which is exactly why regular languages are the right theoretical tool for lexing.

The EOF token at the end is a small but important convenience: the parser can always look at "the next token" without checking for the end of the array.

3. The parser: tokens → AST

Now the interesting part. We need to turn a flat token list into a tree that encodes precedence — so 2 + 3 * 4 groups as 2 + (3 * 4), not (2 + 3) * 4.

The classic technique is recursive descent: write one function per grammar rule, and let the call structure express precedence. The trick is a hierarchy — the rule for the lowest-precedence operator calls the rule for the next level up, and so on. Because the deepest rules bind first, the tree naturally nests tighter operators lower:

expression → term (("+" | "-") term)*        ← lowest precedence
term       → factor (("*" | "/") factor)*    ← binds tighter
factor     → NUMBER | IDENT | "(" expression ")"   ← tightest

function parse(tokens) {
  let pos = 0;
  const peek  = () => tokens[pos];
  const next  = () => tokens[pos++];
  const expect = (type) => {
    if (peek().type !== type) throw new Error(`Expected ${type}, got ${peek().type}`);
    return next();
  };

  // factor → NUMBER | IDENT | ( expression )
  function factor() {
    const t = peek();
    if (t.type === "NUMBER") { next(); return { kind: "Number", value: t.value }; }
    if (t.type === "IDENT")  { next(); return { kind: "Variable", name: t.value }; }
    if (t.type === "LPAREN") {
      next();                        // consume "("
      const inner = expression();    // recurse — parentheses restart at the bottom
      expect("RPAREN");
      return inner;
    }
    throw new Error(`Unexpected token ${t.type}`);
  }

  // term → factor (("*" | "/") factor)*
  function term() {
    let left = factor();
    while (peek().type === "STAR" || peek().type === "SLASH") {
      const op = next().type;
      const right = factor();
      left = { kind: "Binary", op, left, right };   // build the tree as we go
    }
    return left;
  }

  // expression → term (("+" | "-") term)*
  function expression() {
    let left = term();
    while (peek().type === "PLUS" || peek().type === "MINUS") {
      const op = next().type;
      const right = term();
      left = { kind: "Binary", op, left, right };
    }
    return left;
  }

  // statement → "let" IDENT "=" expression ";" | "print" expression ";"
  function statement() {
    if (peek().type === "LET") {
      next();
      const name = expect("IDENT").value;
      expect("EQUALS");
      const value = expression();
      expect("SEMI");
      return { kind: "Let", name, value };
    }
    if (peek().type === "PRINT") {
      next();
      const value = expression();
      expect("SEMI");
      return { kind: "Print", value };
    }
    throw new Error(`Unexpected statement start: ${peek().type}`);
  }

  const statements = [];
  while (peek().type !== "EOF") statements.push(statement());
  return { kind: "Program", statements };
}

Why precedence works. Parsing 2 + 3 * 4, expression() calls term(), which parses 2 and — seeing + rather than * — returns immediately. Back in expression(), we consume + and call term() again; that call parses 3, sees *, and greedily consumes 3 * 4 into a Binary node before returning. So the multiplication ends up as a child of the addition, and since evaluation is bottom-up, it happens first. Precedence is encoded in the shape of the call hierarchy, and therefore in the shape of the tree — exactly 3.1's claim, now demonstrated in code.

Parentheses work by recursion: factor() sees ( and calls expression() again, restarting at the lowest precedence inside the brackets. That recursion is precisely the stack that makes the parser a pushdown automaton and puts this grammar in the context-free class (1.7) — a finite automaton could never match nested parentheses.

4. The interpreter: walking the tree

The final stage evaluates the AST. It's a recursive function that switches on node kind — the tree-walking interpreter of 3.2:

function interpret(ast) {
  const env = new Map();      // the environment: variable name → value

  function evaluate(node) {
    switch (node.kind) {
      case "Number":
        return node.value;

      case "Variable": {
        if (!env.has(node.name)) throw new Error(`Undefined variable: ${node.name}`);
        return env.get(node.name);
      }

      case "Binary": {
        const l = evaluate(node.left);     // recurse into children first…
        const r = evaluate(node.right);
        switch (node.op) {                 // …then combine
          case "PLUS":  return l + r;
          case "MINUS": return l - r;
          case "STAR":  return l * r;
          case "SLASH":
            if (r === 0) throw new Error("Division by zero");
            return l / r;
        }
      }
    }
  }

  for (const stmt of ast.statements) {
    if (stmt.kind === "Let")   env.set(stmt.name, evaluate(stmt.value));
    if (stmt.kind === "Print") console.log(evaluate(stmt.value));
  }
}

// Put it together:
const source = "let x = 2 + 3 * 4; print x; let y = (x + 1) / 3; print y;";
interpret(parse(lex(source)));      // prints 14, then 5

That env Map is a symbol table (3.1) in its simplest form — and the "Undefined variable" check is semantic analysis, catching a meaning error that parsing alone cannot. Notice the evaluation order in Binary: we recurse to the leaves first and combine on the way back up, which is why the tree's shape determines arithmetic order. And notice that this interpreter re-examines every node on every execution — precisely the repeated work that 3.2 identified as the reason interpreters are slow, and that a JIT eliminates.

5. Where to take it next

Each extension teaches a specific concept, in rough order of difficulty:

• Booleans and comparison operators, then if/else — introduces control flow: the interpreter conditionally evaluates a branch rather than always both.
• while loops — makes the language Turing-complete (1.7): with unbounded iteration and conditionals, Toy can now compute anything computable. (Note how little it took — this is why config languages are deliberately kept without loops, 1.7's drill.)
• Functions with parameters — the biggest leap: you need a call stack of environments (3.6.1), each with a link to its enclosing scope, which is precisely how scope chains and closures are implemented.
• Better errors — track line and column numbers in each token and report them, and you'll immediately appreciate why good compiler diagnostics are hard.
• A bytecode VM — instead of walking the tree, compile the AST to a flat instruction list and write a loop that executes it (3.2). Usually several times faster, and it makes the bytecode chapter concrete.
• Static type checking — annotate variables and verify types before execution, implementing 3.3's semantic-analysis stage yourself.

6. The expert lens

Parsers are everywhere once you can see them, and that recognition is the real prize. The lexer-plus-parser pattern you just built is not a niche compiler skill — it is the machinery inside an enormous share of everyday tools. Every one of these is the same three stages: a JSON or YAML parser (3.10); a Markdown renderer; a template engine; a SQL query planner (Part 7); an ORM (a library that lets you read and write database rows as if they were ordinary objects) turning method chains into SQL; a regular-expression engine; a linter or formatter (3.1); a bundler tracing import statements (3.6.5); a search-query syntax; a spreadsheet formula bar; a log-filter expression. When you next need to accept structured user input more complex than a form field, you'll recognise it as a parsing problem and reach for a grammar rather than a pile of regular expressions and string splitting — which is exactly the difference between a fragile hack and a maintainable feature.

Know when to build a DSL and when not to. Because building a small language is now within reach, the temptation is to build one whenever configuration gets complicated. Resist it by default. A domain-specific language is justified when non-programmers must express logic (spreadsheet formulas, business rules), when the domain has genuine structure that a general language obscures (SQL for queries, regex for patterns), or when you need to restrict what's expressible for safety — recall 1.7: a deliberately non-Turing-complete language can guarantee termination, which is exactly why config formats omit loops and why sandboxed rule engines exist. It is not justified when an existing format (TOML, JSON) plus a library would do, because a custom language means you now own its parser, error messages, editor support, documentation, and every future feature request — a permanent maintenance cost most teams underestimate.

Building the thing is what converts knowledge into understanding. You have now personally implemented the pipeline that Part 3 spent ten chapters describing: text became tokens, tokens became a tree whose shape encodes precedence, a symbol table resolved names, and a recursive evaluator produced answers. The theory of 1.7 stopped being abstract the moment your factor() function recursed on a parenthesis — that was a pushdown automaton using its stack. This is the general lesson worth carrying past Part 3: for any concept you want to hold permanently — a hash table, a garbage collector, a virtual machine, a database index, a TCP handshake, a toy neural network — build the smallest possible working version. A weekend spent implementing something teaches more than a month of reading about it, because a program that doesn't work forces you to confront exactly the parts you didn't really understand.

Part 3 complete. From how source becomes execution, through types, memory, paradigms, the JavaScript/TypeScript/Node stack, a comparative tour, tooling, and now a language you built yourself — you own the layer between the operating system of Part 2 and the algorithms of Part 4. Part 4 takes up data structures and algorithms: the problem-solving spine, and the heart of technical interviews.

Recall

• A working language needs three stages, exactly as 3.1 described: lexer (characters → tokens, discarding whitespace; a finite automaton), parser (tokens → AST), and an evaluator.
• Recursive descent parsing writes one function per grammar rule; precedence is encoded in the call hierarchy (expression → term → factor), so tighter-binding operators land deeper in the tree and evaluate first. Parentheses work by recursing back to the lowest-precedence rule — the stack that makes a parser a pushdown automaton (1.7).
• A tree-walking interpreter recurses to the leaves and combines upward; an environment Map is a symbol table, and checking for undefined variables is semantic analysis. Re-examining every node per execution is exactly the waste a JIT removes (3.2).
• Extensions map to concepts: if/while → control flow and Turing completeness; functions → a call stack of scoped environments (closures); bytecode VM → 3.2; type annotations → 3.3.
• The pattern recurs everywhere (JSON/YAML parsers, Markdown, SQL, ORMs, regex engines, linters, bundlers, template engines). Build a DSL only when non-programmers must express logic, the domain has real structure, or you must restrict expressiveness for safety — otherwise use an existing format.

Self-test: What does the lexer discard and why doesn't it matter? Explain precisely how recursive descent makes 2 + 3 * 4 evaluate correctly. Which part of the parser makes it a pushdown rather than a finite automaton? What does the env Map correspond to in a real compiler? Name three everyday tools that are secretly parsers.

Quiz Bank

FoundationalWhat are the three stages of a minimal language implementation, and what does each produce?

Lexer — scans raw characters and groups them into tokens (NUMBER, IDENT, PLUS, …), discarding whitespace and comments since they carry no execution meaning; it needs no memory beyond position, making it a finite automaton (1.7). Parser — consumes the flat token list and produces an Abstract Syntax Tree capturing structure and precedence; it needs a stack (via recursion) to handle nesting, making it a pushdown automaton. Interpreter (or code generator) — walks the AST and performs the operations, using an environment for variables. A compiler would add IR generation, optimisation, and code generation (3.1) instead of the final step.

AppliedHow does recursive descent parsing produce correct operator precedence?

By encoding precedence in the call hierarchy: one function per grammar level, with the lowest-precedence rule calling the next-tighter one — expression (handles +/-) calls term (handles *//) which calls factor (literals, names, parentheses). Parsing 2 + 3 * 4: expression calls term, which parses 2, sees + (not its operator) and returns; expression consumes + and calls term again, and that call greedily consumes 3 * 4 into a Binary node before returning. So the multiplication becomes a child of the addition. Since evaluation recurses to the leaves and combines upward, deeper nodes evaluate first — hence 3 * 4 happens before the addition. Precedence is the tree's shape, fixed at parse time, not a runtime rule.

AppliedIn the toy interpreter, what does the environment Map correspond to in a real compiler, and what error does it enable?

It is a symbol table (3.1) in its simplest form — the structure mapping declared names to their values (in a compiler, to their types, storage locations, and scope information). It enables semantic analysis errors that parsing alone cannot catch: print z; is syntactically perfect (it produces a valid AST) but semantically wrong if z was never declared, and the environment lookup is what detects it — producing the familiar "undefined variable" error. Extending the toy language with functions would turn this single Map into a chain of environments, each linked to its enclosing scope, which is exactly how scope chains and closures are implemented (3.6.1).

InterviewWhich part of a recursive-descent parser makes it more powerful than a lexer, in formal terms?

The recursion — specifically, factor() calling expression() when it encounters an opening parenthesis. A lexer is a finite automaton: it has a fixed set of states and no memory beyond its current position, so it can recognise regular languages (identifiers, numbers, symbols) but cannot count — it can never verify balanced parentheses to arbitrary depth (1.7). The parser's recursion uses the call stack as unbounded memory of "how deep am I," making it a pushdown automaton, which recognises context-free languages — exactly the class containing nested expressions, blocks, and brackets. This is why programming-language syntax is context-free and why you famously cannot parse nested structures (like HTML) with regular expressions.

StaffWhen is building a domain-specific language the right decision, and when is it a mistake?

Justified when: (1) non-programmers must express logic — business rules, spreadsheet formulas, alerting conditions — where a constrained syntax is far safer and more learnable than a general language; (2) the domain has genuine structure a general-purpose language obscures, so a specialised notation is dramatically clearer (SQL for relational queries, regex for patterns, a query DSL for search); (3) you need to restrict what is expressible for safety — this is the strongest reason and rests on 1.7: a deliberately non-Turing-complete language (no unbounded loops) can guarantee termination, so untrusted rules cannot hang your system, which is precisely why config formats omit loops and why sandboxed rule engines exist.

A mistake when: an existing format (TOML/JSON/YAML — 3.10) plus a small library would suffice; the "language" is really just configuration that grew organically; or the team underestimates the permanent ownership cost — you now own the grammar, the parser, error messages good enough for users, editor/syntax support, documentation, versioning and backward compatibility (3.6.1's lesson that published interfaces freeze their mistakes), plus every future feature request. The staff heuristic: prefer a well-known format with a schema; escalate to an embedded DSL in an existing language (a fluent API) before inventing syntax; invent a real language only when constrained expressiveness or non-programmer authorship is the actual requirement.

Flashcards

FlashThree stages of a toy language

Lexer (text → tokens), parser (tokens → AST), interpreter (walk the AST and evaluate).

FlashRecursive descent

One function per grammar rule, lowest precedence calling the next tighter (expression → term → factor); precedence emerges from the call hierarchy and thus the tree shape.

FlashWhy the parser needs recursion

To handle nesting (parentheses/blocks) — the call stack is the memory that makes it a pushdown automaton, recognising context-free languages a lexer never could.

FlashThe environment Map = ?

A symbol table — name → value; looking up a missing name is semantic analysis producing "undefined variable."

FlashWhat adding while loops does

Makes the language Turing-complete (unbounded iteration + conditionals) — which is why safe config languages deliberately omit loops.

FlashEveryday tools that are parsers

JSON/YAML parsers, Markdown renderers, template engines, SQL planners, ORMs, regex engines, linters, formatters, bundlers.

FlashWhen to build a DSL

When non-programmers must author logic, the domain has real structure, or you must restrict expressiveness (e.g. guarantee termination). Otherwise use an existing format.

Scenario Drill

DrillYour product needs users to write filter rules like `status = active AND (age > 30 OR country = IN)`. A colleague proposes parsing them with regular expressions and string splitting. Evaluate, and design a better approach.

The regex/split approach will fail, and this chapter says exactly why: the requirement contains nested parentheses, which are context-free, and regular expressions are finite automata that cannot count nesting depth (1.7). It may appear to work on flat examples and then break on the first nested rule, on an operator inside a quoted string (country = "AND"), or on unbalanced input — and each patch makes the regex more unmaintainable. It's also unable to produce good error messages ("unexpected ) at column 24"), which matters because users are authoring these.

Better approach — treat it as the parsing problem it is, using this chapter's pipeline: (1) Lexer — scan the rule into tokens: IDENT, OPERATOR (=, >, <), VALUE (string/number), AND/OR/NOT, (, ), tracking line/column for diagnostics. (2)

Parser (recursive descent) — a grammar where precedence falls out of the call hierarchy exactly as in section 3: orExpr → andExpr ("OR" andExpr)*, andExpr → comparison ("AND" comparison)*, comparison → IDENT op VALUE | "(" orExpr ")". The parenthesis case recurses back to the top, handling arbitrary nesting correctly and giving AND tighter binding than OR for free. (3)

Semantic analysis — validate against a schema of allowed fields, operators, and value types (rejecting unknown fields or age = "hello" before execution) — the symbol table idea. (4) Evaluate or compile — either walk the AST per record, or, better, compile the AST into a database query (a parameterised WHERE clause) so the database does the filtering — and note this also eliminates injection risk (3.10/Part 8), because user text is never concatenated into SQL; only validated, structured nodes become parameterised predicates.

Also consider: a mature expression-parser library (or a parser generator) rather than hand-rolling, and — deliberately — keeping the language non-Turing-complete (no loops or recursion) so every user rule is guaranteed to terminate, which is a real safety property you get by restricting expressiveness. The judgment to state: structured user input with nesting is a grammar problem; reaching for regexes is the standard way teams accumulate an unfixable parser.