Compiler — JavaScript Project

1. The Problem

Build a compiler for arithmetic expressions. The front end tokenizes and parses the expression, emitting a list of stack-machine instructions (bytecode) like PUSH 2, PUSH 3, MUL. The back end is a virtual machine that runs that bytecode to produce the answer.

Why this project? The difference between an interpreter (evaluate directly) and a compiler (emit code to run later) is one of the deepest ideas in CS. Building both a bytecode emitter and a stack VM makes it concrete — and it is how the JVM, Python, and WebAssembly all work.

2. How to Think About This

The front end is a recursive-descent parser like the interpreter's, but instead of computing values it emits instructions: a number emits PUSH n; after parsing both sides of a + it emits ADD. This naturally produces postfix (reverse-Polish) bytecode. The back end is a stack machine: PUSH pushes a number; an operator pops two operands, combines them, and pushes the result. When the program ends, the single value left on the stack is the answer.

3. The Build

compiler.mjs

// ---- FRONT END: tokenize + parse, emitting bytecode ----
function tokenize(text) {
  const tokens = [];
  for (const part of text.match(/\d+|[+\-*/()]/g) || []) {
    tokens.push(/^\d+$/.test(part) ? ["NUM", parseInt(part, 10)] : [part, part]);
  }
  return tokens;
}

class Compiler {
  constructor(tokens) { this.tokens = tokens; this.pos = 0; this.code = []; }
  peek() { return this.pos < this.tokens.length ? this.tokens[this.pos] : [null, null]; }
  eat()  { return this.tokens[this.pos++]; }

  expr() {
    this.term();
    while (this.peek()[0] === "+" || this.peek()[0] === "-") {
      const op = this.eat()[0];
      this.term();
      this.code.push(op === "+" ? "ADD" : "SUB");
    }
  }
  term() {
    this.factor();
    while (this.peek()[0] === "*" || this.peek()[0] === "/") {
      const op = this.eat()[0];
      this.factor();
      this.code.push(op === "*" ? "MUL" : "DIV");
    }
  }
  factor() {
    const [type, value] = this.eat();
    if (type === "NUM") this.code.push(["PUSH", value]);
    else if (type === "(") { this.expr(); this.eat(); }   // consume ")"
  }
}

export function compile(text) {
  const c = new Compiler(tokenize(text));
  c.expr();
  return c.code;
}

// ---- BACK END: a stack-based virtual machine ----
export function run(bytecode) {
  const stack = [];
  for (const instr of bytecode) {
    if (Array.isArray(instr)) {           // ["PUSH", n]
      stack.push(instr[1]);
    } else {
      const b = stack.pop(), a = stack.pop();
      if (instr === "ADD") stack.push(a + b);
      else if (instr === "SUB") stack.push(a - b);
      else if (instr === "MUL") stack.push(a * b);
      else if (instr === "DIV") stack.push(a / b);
    }
  }
  return stack[0];
}

// Demo
const code = compile("2 + 3 * 4");
console.log("Bytecode:", JSON.stringify(code));
console.log("Result:", run(code));   // 14

4. Test & Prove

compiler.test.mjs

import { compile, run } from "./compiler.mjs";

let pass = 0, fail = 0;
function test(desc, fn) {
  try { fn(); console.log("  \u2713", desc); pass++; }
  catch (e) { console.log("  \u2717", desc, "\u2014", e.message); fail++; }
}
function assert(cond, msg) { if (!cond) throw new Error(msg || "assertion failed"); }

test("compiles a number to a single PUSH", () => {
  assert(JSON.stringify(compile("5")) === JSON.stringify([["PUSH", 5]]));
});
test("emits postfix bytecode for +", () => {
  assert(JSON.stringify(compile("1 + 2")) === JSON.stringify([["PUSH",1],["PUSH",2],"ADD"]));
});
test("the VM runs bytecode to the right answer", () => {
  assert(run(compile("2 + 3 * 4")) === 14);
});
test("precedence is baked into the emitted code", () => {
  assert(run(compile("2 + 3 * 4")) === 14);
  assert(run(compile("(2 + 3) * 4")) === 20);
});
test("compile and run are separate stages", () => {
  const code = compile("10 - 2 - 3");   // left-associative
  assert(run(code) === 5);
});

console.log(`\n${pass} passed, ${fail} failed`);

5. The Interface

node compiler.mjs

Bytecode: [["PUSH",2],["PUSH",3],["PUSH",4],"MUL","ADD"]
Result: 14

6. Run It

node compiler.mjs
node compiler.test.mjs

🎯 Try this next

Add a DISASSEMBLE step that prints the bytecode in human-readable form
Add variables: a STORE/LOAD instruction pair and a variables slot
Constant-fold: if both operands are PUSH, compute at compile time
Target real output: emit WebAssembly text (WAT) instead of custom bytecode

What you practised

The compiler front-end/back-end split, emitting stack-machine (postfix) bytecode from a recursive-descent parser, and running it on a virtual machine — the model behind the JVM, CPython, and WebAssembly.

Reference: Recursion · Interpreter (related) · Stacks