Tokens, Trees, and Scope: Building a Small Interpreter to Understand Languages

Interpreters can feel like infrastructure reserved for compiler teams. In practice, a small interpreter is one of the most direct ways to understand what a programming language does with your code. This tutorial builds a compact interpreter in JavaScript for a language we will call Lumen. It supports numbers, arithmetic, variables, functions, closures, and recursion in roughly 500 lines. The target is not production performance. The target is a precise mental model that makes scope, call frames, and recursion less mysterious.

Why Build One Instead of Reading About One

Most developers use several languages every day, yet the boundary between syntax and runtime behavior remains blurry. A tokenizer, parser, and evaluator make that boundary explicit. You see where a name is resolved, when an environment is created, and why a closure retains access to an outer variable. For US developers who work across TypeScript, Python, and JavaScript, this model pays off in debugging and design reviews. When a callback captures the wrong value or a recursive function exhausts the stack, the failure becomes a concrete consequence of a small set of rules.

The Architecture in Five Pieces

Lumen needs five components: a tokenizer, a parser, an AST, an evaluator, and an environment. The tokenizer turns text into tokens. The parser turns tokens into an abstract syntax tree. The evaluator walks that tree. The environment maps names to values and points to a parent environment. Functions are values that store parameters, a body, and the environment in which they were created. That last detail is the closure.

A useful constraint is to keep the grammar small. Lumen supports let bindings, function definitions, return statements, arithmetic, comparisons, and calls. The parser is recursive descent, which means each grammar rule becomes a function. This is slower to write than a parser generator but far easier to inspect.

Tokenizing Without Ceremony

The tokenizer scans characters and emits objects with a type and a value. Whitespace is skipped. Numbers become number tokens, identifiers become identifier tokens, and punctuation becomes its own token. A final end-of-file token simplifies the parser loop.

function tokenize(source) {
  const tokens = [];
  let i = 0;
  const isDigit = ch => ch >= '0' && ch <= '9';
  const isAlpha = ch => (ch >= 'a' && ch <= 'z') ||
    (ch >= 'A' && ch <= 'Z') || ch === '_';
  while (i < source.length) {
    const ch = source[i];
    const whitespace = ch === ' ' || ch === String.fromCharCode(10) || ch === String.fromCharCode(9);
    if (whitespace) { i++; continue; }
    if (isDigit(ch)) {
      let start = i;
      while (i < source.length && isDigit(source[i])) i++;
      tokens.push({ type: 'number', value: Number(source.slice(start, i)) });
      continue;
    }
    if (isAlpha(ch)) {
      let start = i;
      while (i < source.length && (isAlpha(source[i]) || isDigit(source[i]))) i++;
      tokens.push({ type: 'identifier', value: source.slice(start, i) });
      continue;
    }
    if ('+-*/=(){}<>,;'.includes(ch)) {
      tokens.push({ type: ch, value: ch });
      i++;
      continue;
    }
    throw new Error('Unexpected character: ' + ch);
  }
  tokens.push({ type: 'eof' });
  return tokens;
}

The important design choice is that the tokenizer knows nothing about grammar. It does not decide whether a plus sign is binary addition or part of an assignment. That belongs to the parser.

Parsing and the AST

The parser consumes tokens and returns nodes such as Number, Identifier, Binary, Let, Def, Call, Return, and Block. Recursive descent mirrors the grammar: parseExpression calls parseTerm, which calls parseFactor. A call expression is recognized when an identifier is followed by an opening parenthesis.

function parseExpression() {
  let left = parseTerm();
  while (match('+') || match('-')) {
    const op = previous().type;
    const right = parseTerm();
    left = { type: 'Binary', op, left, right };
  }
  return left;
}

The AST is deliberately boring. It contains no behavior. This separation matters because the evaluator can change without rewriting the parser, and the parser can be tested with snapshots before any runtime behavior exists.

Evaluation, Environments, and Scope

The evaluator is a recursive function over AST nodes. For a number, return its value. For a binary expression, evaluate both sides and apply the operator. For a let statement, evaluate the initializer, define the name in the current environment, and return the value. The Environment class is a chain:

class Environment {
  constructor(parent = null) {
    this.parent = parent;
    this.values = new Map();
  }
  define(name, value) { this.values.set(name, value); }
  get(name) {
    if (this.values.has(name)) return this.values.get(name);
    if (this.parent) return this.parent.get(name);
    throw new Error('Undefined variable: ' + name);
  }
}

Scope becomes visible here. A block creates a child environment. A lookup walks outward until it finds a binding. That is lexical scope in its simplest form.

Functions and Closures

A function definition creates an object with parameters, a body, and a reference to the current environment. When called, the evaluator creates a new environment whose parent is the function's captured environment, binds the arguments, evaluates the body, and returns the result. The captured environment is why this works:

def makeAdder(x) {
  def add(y) { return x + y; }
  return add;
}
let addFive = makeAdder(5);
addFive(3);

The inner function retains access to x after makeAdder returns. No special closure syntax is required; the environment chain does the work. Recursion works for the same reason. When a function calls its own name, the name is resolved in the environment where the function was defined. Because that environment contains the function binding, the call succeeds.

Testing and Extending the Language

Test the interpreter at three levels. Tokenizer tests assert token sequences. Parser tests assert AST shape. Evaluator tests assert program results. Add a small suite for scoping errors, arity mismatches, and return behavior. Then extend Lumen with if statements, arrays, or string concatenation. Each extension touches the same five pieces, which is the lesson: language features are coordinated changes across syntax, representation, and runtime rules.

The completed project is modest, but the model is not. Once you have built a tokenizer, parser, and evaluator, the behavior of real languages becomes easier to reason about. You stop seeing scope as a keyword and start seeing it as a chain of environments. That is the practical value of a 500-line interpreter.