Part 3 · 2 chapters · ~22 min

M3: Compiler

A compiler and VM for a small typed language: a lexer with positions, Pratt parsing with binding powers, a type checker with scopes, constant folding, stack bytecode with patched jumps and short-circuit logic, and a fetch-decode-execute virtual machine.

The pipeline

each stage makes the next one easy

Lexer: tokens that carry their positions.
Pratt parser: binding powers decide precedence and associativity.
Type checker: scopes, types, and errors that point at the source.
Constant folding as a tree-to-tree rewrite.
Codegen: a post-order walk to stack code, with patched jumps.
The VM: fetch, decode and execute against an operand stack and frames.

code

// Mini, the language tiny-compiler compiles
fn isPrime(n: int): bool {
  if (n < 2) { return false; }
  let d: int = 2;
  while (d * d <= n) { if (n % d == 0) { return false; } d = d + 1; }
  return true;
}
let i: int = 0; let count: int = 0;
while (i < 50) { if (isPrime(i)) { count = count + 1; } i = i + 1; }
print(count);                  // 15

where this connects

The JavaScript course parts 1 to 4 cover V8's real pipeline: a lazy parser, Ignition bytecode with feedback slots, then the Sparkplug, Maglev and TurboFan tiers. tiny-compiler is Ignition without the feedback and the JITs. The Algorithms course part 8 covers the parsing and code generation algorithms in general.

TINY-COMPILER: SOURCE TO EXECUTION

one expression followed through every stage: tokens, a tree, types, a fold, bytecode and a running stack machine

swipe the figure sideways, or tap expand for full screen

1/6

lex

Lexing: characters become tokens: kw(print) punct(() num(2) op(*) num(3) op(+) ident(x) punct()) punct(;). Whitespace and comments vanish; each token keeps its line and column so every later error can point at the source.

Building it: tiny-compiler

Repo: repos/compiler. Six files, one per stage, about 550 lines.

code

// src/parser.ts: the whole of Pratt parsing for binary operators
const BP: Record<string, number> = { '||': 1, '&&': 2, '==': 3, '!=': 3, '<': 4, '<=': 4, '>': 4, '>=': 4, '+': 5, '-': 5, '*': 6, '/': 6, '%': 6 };

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

code

// src/codegen.ts: short-circuit && and ||, and a while loop with a patched exit jump
if (e.op === '&&' || e.op === '||') {
  expr(e.l);
  const j = emit([e.op === '&&' ? 'JZ' : 'JNZ', -1]);         // left decides: skip the right side
  expr(e.r);
  const end = emit(['JMP', -1]);
  patch(j, code.length); emit(['PUSH', e.op === '&&' ? 0 : 1]);
  patch(end, code.length);
}
// …
case 'while': {
  const top = code.length;
  expr(s.cond);
  const jz = emit(['JZ', -1]);                          // target unknown until the body is emitted
  genBody(s.body, [...slots, new Map()], counter);
  emit(['JMP', top]);
  patch(jz, code.length);
}

code

$ npm run fib          # node src/index.ts examples/fib.mini --asm
fib:
   31  LOAD 0
   32  PUSH 2
   33  LT
   34  JZ 37
   35  LOAD 0
   36  RET
   37  LOAD 0
   38  PUSH 1
   39  SUB
   40  CALL fib 1
   …

Run it. In repos/compiler: npm test, then npm run fib to see the bytecode and the output. Introduce type errors on purpose (let x: int = true;) and read the positioned messages. Then delete the <= in the parser's loop condition, change it to <, and watch the associativity test fail.

exercises

1. Strings and a heap, with a reference-counted or mark-and-sweep collector. 2. Closures via upvalues, as in Lua. 3. A register IR with liveness analysis and a simple register allocator. 4. Tail calls: reuse the frame for return f(x). 5. Emit WebAssembly text instead of custom bytecode and run it with WebAssembly.instantiate.