Build a tiny JavaScript interpreter

import { run } from "./evaluator.js";

run(`
function factorial(n) {
  if (n <= 1) {
    return 1;
  }
  return n * factorial(n - 1);
}
let price = 4;
print("total", price * 3 + 1);
print("5! =", factorial(5));
`);

const pattern = /(\d+(?:\.\d+)?)|("[^"]*")|([A-Za-z_]\w*)|(===|!==|<=|>=|[-+*/<>=(){},;])/y;
const keywords = new Set(["let", "function", "return", "if", "else"]);

export function tokenize(source) {
  const tokens = [];
  let position = 0;
  while (position < source.length) {
    if (/\s/.test(source[position])) {
      position += 1;
      continue;
    }
    pattern.lastIndex = position;
    const match = pattern.exec(source);
    if (!match) throw new SyntaxError(`Unexpected "${source[position]}" at ${position}`);
    const [text, number, string, name] = match;
    if (number) tokens.push({ type: "number", value: Number(number) });
    else if (string) tokens.push({ type: "string", value: string.slice(1, -1) });
    else if (name) tokens.push({ type: keywords.has(name) ? "keyword" : "name", value: name });
    else tokens.push({ type: "punct", value: text });
    position = pattern.lastIndex;
  }
  return tokens;
}

import { tokenize } from "./tokenizer.js";

const tokens = tokenize("let total = price * 2;");
console.log(tokens.map((token) => token.type + ":" + token.value).join(" "));

import { tokenize } from "./tokenizer.js";

export function parse(source) {
  const tokens = tokenize(source);
  let index = 0;
  let functionDepth = 0;
  const peek = () => tokens[index];
  const next = () => tokens[index++];
  const isNext = (value) => peek()?.type !== "string" && peek()?.value === value;
  const found = () => (peek() ? `"${peek().value}"` : "the end");
  function expect(value) {
    if (!isNext(value)) throw new SyntaxError(`Expected "${value}" but found ${found()}`);
    next();
  }
  function name() {
    if (peek()?.type !== "name") throw new SyntaxError(`Expected a name but found ${found()}`);
    return next().value;
  }
  function list(item) {
    expect("(");
    const items = [];
    while (!isNext(")")) {
      items.push(item());
      if (!isNext(")")) expect(",");
    }
    expect(")");
    return items;
  }
  function block() {
    expect("{");
    const body = [];
    while (!isNext("}")) body.push(statement());
    expect("}");
    return body;
  }

  function statement() {
    if (isNext("let")) {
      next();
      const target = name();
      expect("=");
      const value = expression();
      expect(";");
      return { type: "Let", name: target, value };
    }
    if (isNext("function")) {
      next();
      const target = name();
      const params = list(name);
      functionDepth += 1;
      const body = block();
      functionDepth -= 1;
      return { type: "Function", name: target, params, body };
    }
    if (isNext("return")) {
      if (functionDepth === 0) throw new SyntaxError("return is only allowed inside a function");
      next();
      const value = expression();
      expect(";");
      return { type: "Return", value };
    }
    if (isNext("if")) {
      next();
      expect("(");
      const test = expression();
      expect(")");
      const then = block();
      const otherwise = isNext("else") ? (next(), block()) : null;
      return { type: "If", test, then, otherwise };
    }
    const value = expression();
    expect(";");
    return { type: "Expression", value };
  }

  function expression() {
    const left = binary(0);
    if (isNext("=") && left.type === "Name") {
      next();
      return { type: "Assign", name: left.name, value: expression() };
    }
    return left;
  }
  const levels = [["===", "!==", "<", ">", "<=", ">="], ["+", "-"], ["*", "/"]];
  function binary(level) {
    if (level === levels.length) return call();
    let left = binary(level + 1);
    while (peek() && peek().type === "punct" && levels[level].includes(peek().value)) {
      const operator = next().value;
      left = { type: "Binary", operator, left, right: binary(level + 1) };
    }
    return left;
  }
  function call() {
    let callee = primary();
    while (isNext("(")) callee = { type: "Call", callee, args: list(expression) };
    return callee;
  }
  function primary() {
    const token = next();
    if (!token) throw new SyntaxError("Unexpected end of input");
    if (token.type === "number" || token.type === "string") return { type: "Literal", value: token.value };
    if (token.type === "name") return { type: "Name", name: token.value };
    if (token.value === "(") {
      const value = expression();
      expect(")");
      return value;
    }
    throw new SyntaxError(`Unexpected "${token.value}"`);
  }

  const body = [];
  while (index < tokens.length) body.push(statement());
  return { type: "Program", body };
}

import { parse } from "./parser.js";

function show(node) {
  if (node.type === "Binary") return "(" + node.operator + " " + show(node.left) + " " + show(node.right) + ")";
  if (node.type === "Call") return "(call " + show(node.callee) + " " + node.args.map(show).join(" ") + ")";
  if (node.type === "Name") return node.name;
  return String(node.value);
}

const program = parse("print(1 + 2 * 3);\nlet total = (1 + 2) * 3;\nlet left = 10 - 3 - 2;");
for (const statement of program.body) console.log(statement.type, show(statement.value));

import { parse } from "./parser.js";

class Scope {
  constructor(parent = null) {
    this.vars = new Map();
    this.parent = parent;
  }
  declare(name, value) {
    this.vars.set(name, value);
  }
  find(name) {
    for (let scope = this; scope; scope = scope.parent) if (scope.vars.has(name)) return scope;
    throw new ReferenceError(`${name} is not defined`);
  }
}

class ReturnSignal {
  constructor(value) {
    this.value = value;
  }
}

export function run(source, print = console.log) {
  const globals = new Scope();
  globals.declare("print", print);
  execBlock(parse(source).body, globals);
}

function execBlock(statements, scope) {
  for (const statement of statements) exec(statement, scope);
}

function exec(node, scope) {
  if (node.type === "Let") scope.declare(node.name, evaluate(node.value, scope));
  else if (node.type === "Function") scope.declare(node.name, makeFunction(node, scope));
  else if (node.type === "Return") throw new ReturnSignal(evaluate(node.value, scope));
  else if (node.type === "If") {
    if (evaluate(node.test, scope)) execBlock(node.then, new Scope(scope));
    else if (node.otherwise) execBlock(node.otherwise, new Scope(scope));
  } else evaluate(node.value, scope);
}

function makeFunction(node, closure) {
  return (...args) => {
    const scope = new Scope(closure);
    node.params.forEach((param, i) => scope.declare(param, args[i]));
    try {
      execBlock(node.body, scope);
    } catch (signal) {
      if (signal instanceof ReturnSignal) return signal.value;
      throw signal;
    }
    return undefined;
  };
}

function evaluate(node, scope) {
  if (node.type === "Literal") return node.value;
  if (node.type === "Name") return scope.find(node.name).vars.get(node.name);
  if (node.type === "Assign") {
    const value = evaluate(node.value, scope);
    scope.find(node.name).vars.set(node.name, value);
    return value;
  }
  if (node.type === "Call") {
    const fn = evaluate(node.callee, scope);
    if (typeof fn !== "function") throw new TypeError(`${fn} is not a function`);
    return fn(...node.args.map((arg) => evaluate(arg, scope)));
  }
  const left = evaluate(node.left, scope);
  const right = evaluate(node.right, scope);
  const operations = {
    "+": () => left + right, "-": () => left - right, "*": () => left * right, "/": () => left / right,
    "<": () => left < right, ">": () => left > right, "<=": () => left <= right, ">=": () => left >= right,
    "===": () => left === right, "!==": () => left !== right,
  };
  return operations[node.operator]();
}

import { run } from "./evaluator.js";

for (const program of ["let a = 5 # 2;", "let = 5;", "print(price);", "print(1 + 2)"]) {
  try {
    run(program);
  } catch (error) {
    console.log(error.name + ": " + error.message);
  }
}

import { run } from "./evaluator.js";

run(`
function makeCounter() {
  let count = 0;
  function add() {
    count = count + 1;
    return count;
  }
  return add;
}
let counter = makeCounter();
print(counter());
print(counter());
let other = makeCounter();
print(other());
`);

import { run } from "./evaluator.js";

run(`
let x = "outer";
function show() {
  return x;
}
function test() {
  let x = "inner";
  return show();
}
print(test());
`);