Build a Compiler for a Tiny Language

Overview

Compilers and interpreters are not magic — they're just programs that read text and do something structured with it. In this tutorial, you'll build a complete interpreter for a small language called Tiny in TypeScript. You'll implement every stage: lexing (raw text → tokens), parsing (tokens → AST), and evaluation (AST → result). Then you'll extend Tiny with variables, functions, and if/else control flow.

What you'll learn:

How lexers tokenize raw source text
Recursive descent parsing and operator precedence
Abstract Syntax Tree (AST) design and node types
Tree-walking interpretation
Scope chains and environment management
Extending a language with new features

The language we'll build supports arithmetic, comparisons, variables, functions, and conditionals:

Step 1: Project Setup

Create tsconfig.json:

Step 2: Token Types

Create src/tokens.ts. Every meaningful piece of source code maps to a token type:

Step 3: The Lexer

Create src/lexer.ts. The lexer scans raw source text character by character and produces a stream of tokens:

Step 4: AST Node Types

Create src/ast.ts. The AST represents the structure of the program as a tree:

Each node type carries exactly the data needed to evaluate it. BinaryExpr has an operator and two children. FunctionLiteral has parameter names and a body. This is the key insight of compilers: source text is messy and ambiguous, but an AST is precise and structured.

Step 5: The Parser

Create src/parser.ts. This recursive descent parser converts tokens into an AST, handling operator precedence correctly:

Operator precedence is encoded in the call hierarchy: parseComparison calls parseAddition, which calls parseMultiplication. Lower-precedence operators are parsed at higher levels, so 2 + 3 * 4 correctly produces 2 + (3 * 4).

Step 6: The Environment

Create src/environment.ts. The environment tracks variable bindings with lexical scoping:

The scope chain works by parent pointers. When looking up a variable, we check the current scope first, then walk up to parent scopes. Functions capture their defining environment (closure), enabling lexical scoping.

Step 7: The Interpreter

Create src/interpreter.ts:

Step 8: Wiring It Together

Create src/tiny.ts:

Create src/index.ts as a REPL:

Run it:

Step 9: Test the Language

Step 10: Add Higher-Order Functions

The function implementation already supports closures, which means higher-order functions work automatically:

This works because fn(x) { x + n } captures the environment where n is defined (the closure of makeAdder's call). When add5(10) executes, it looks up n in the captured closure and finds 5.

Step 11: Add More Built-ins

Extend the interpreter constructor in src/interpreter.ts with useful built-in functions:

Then handle built-ins in evalCall:

Step 12: What Comes Next

You've built a working interpreter with:

Lexer: raw text → tokens (handles numbers, strings, operators, keywords)
Parser: tokens → AST (recursive descent with operator precedence)
Interpreter: AST → values (tree-walking evaluation with closures)

To extend Tiny further, consider:

Arrays and objects: add [1, 2, 3] syntax and {key: value} literals
Loops: add while (condition) { body } — requires adding a WhileExpr AST node
Error handling: add try/catch with a TinyError value type
Code generation: instead of interpreting the AST, emit JavaScript or WebAssembly
Optimization: add constant folding (evaluate 2 + 3 at compile time) and dead code elimination

The concepts scale directly. Every real language — JavaScript, Python, Rust — has these same stages. The lexer, parser, and evaluator you built are the foundation that V8, CPython, and rustc all share. The difference is complexity of the language grammar and sophistication of the optimization passes, not the fundamental architecture.