From Interpreter To Compiler In Zig

This book is heavily inspired by the Intepreter and Compiler books written by Thorsten Ball.

• Writing An Interpreter In Go
• Writing A Compiler In Go

My most significant learning of general programming concepts came from these two books. They’ve been invaluable to me in my career. I’ve personally purchased several copies of both books (for myself and friends) and implore you to do the same if you are programming in Go. This book is a work in progress and I’ll continue updating it as I learn more and as the Zig programming language changes.

In this Zig book we’ll be borrowing Thorsten’s Monkey Language and break the project into two parts. First you’ll build the interpreter in part 1, then you’ll use what we learned in part 1 to write the compiler for Monkey Language in part 2. You can read part 1 and stop at the end if you only want to learn about interpreters, but you need to complete part 1 in order to start part 2 since the compiler builds on the interpreter.

As you read through the book please try to write the code blocks instead of copy/pasting, it’ll help build muscle memory for the Zig language but also it’ll force you to think about each line as you write it and understand what the code is doing.

In the current state I felt it’s good enough to release, but if you find bugs or have issues following along please feel free to reach out on my socials and I’ll do the best I can to improve. I’m making this book free because the concept and the structure are not entirely mine, it’s borrowing from Thorsten’s books. I felt the Zig community could use a version of those books.

How to Use This Guide

#

1. Follow chapters in order. Each builds on the previous.
2. Write the code yourself. Type it out. Don’t copy/paste. You’ll learn better by doing.
3. Run zig build test in the root of your project after each section to verify your implementation.
4. Read the original books for deeper conceptual explanations. For this early release we’ll focus on how to do this in Zig.

What We Build

#

Part 1: The Interpreter (Chapters 1–4)

#

A fully working Monkey interpreter. Lexer, parser, evaluator, REPL. Self-contained and testable on its own.

Part 2: The Compiler (Chapters 5–13)

#

Replaces the tree-walking interpreter with a bytecode compiler and stack-based virtual machine.

Planned file layout

#

Part 1 builds the interpreter files. Part 2 adds the compiler and VM files to the interpreter project.

monkey/
├── build.zig
├── build.zig.zon
└── src/
    ├── main.zig           # REPL entry point.
    ├── token.zig          # Token types and keyword lookup.
    ├── lexer.zig          # Lexical analysis.
    ├── ast.zig            # Abstract Syntax Tree nodes.
    ├── parser.zig         # Pratt parser.
    ├── object.zig         # Runtime object system.
    ├── environment.zig    # Variable binding environments.
    ├── evaluator.zig      # Tree-walking evaluator.
    ├── builtins.zig       # Built-in functions.
    ├── code.zig           # Bytecode opcodes and encoding.
    ├── compiler.zig       # AST-to-bytecode compiler.
    ├── symbol_table.zig   # Compiler symbol table.
    ├── vm.zig             # Stack-based virtual machine.
    ├── parser_test.zig    # Parser tests.
    ├── evaluator_test.zig # Evaluator tests.
    ├── compiler_test.zig  # Compiler bytecode tests.
    └── vm_test.zig        # VM integration tests.

Project Setup

#

Create the project:

mkdir monkey && cd monkey
zig init
rm src/main.zig src/root.zig

zig init creates boilerplate src/main.zig and src/root.zig files. Delete both, we won’t need those where we’re going. We build every file from scratch.

build.zig

#

Replace the boilerplate build.zig with this code block below. We’ll update this file as we make progress through the book.

const std = @import("std");

pub fn build(b: *std.Build) void {
    const target = b.standardTargetOptions(.{});
    const optimize = b.standardOptimizeOption(.{});

    // REPL executable (Chapter 4)
    const exe = b.addExecutable(.{
        .name = "monkey",
        .root_module = b.createModule(.{
            .root_source_file = b.path("src/main.zig"),
            .target = target,
            .optimize = optimize,
        }),
    });
    b.installArtifact(exe);

    const run_cmd = b.addRunArtifact(exe);
    run_cmd.step.dependOn(b.getInstallStep());
    const run_step = b.step("run", "Run the Monkey REPL");
    run_step.dependOn(&run_cmd.step);

    // Tests — uncomment entries as you create files in later chapters
    const test_files = [_][]const u8{
        "src/token.zig",
        "src/lexer.zig",
        // "src/parser_test.zig", // Chapter 2.
        // "src/evaluator_test.zig", // Chapter 3.
        // "src/code.zig", // Chapter 6.
        // "src/vm_test.zig", // Chapter 6.
        // "src/compiler_test.zig", // Chapter 8.
        // "src/symbol_table.zig", // Chapter 9.
    };

    const test_step = b.step("test", "Run all tests");
    for (test_files) |file| {
        const t = b.addTest(.{
            .root_module = b.createModule(.{
                .root_source_file = b.path(file),
                .target = target,
                .optimize = optimize,
            }),
        });
        const run_t = b.addRunArtifact(t);
        test_step.dependOn(&run_t.step);
    }
}

Where tests go

#

In this book tests will be both inline and separate _test.zig files. Tests that require importing other files/modules will go in a separate file to avoid circular imports. All other tests will be written inline. I’ll make note of these in the chapters.

The Monkey Language

#

// Variable bindings.
let name = "Monkey";
let age = 1;

// Integer arithmetic.
let result = (5 + 10 * 2 + 15 / 3) * 2 + -10;  // => 50

// Boolean expressions.
let isTrue = 1 < 2;       // => true
let isFalse = 1 > 2;      // => false
let isEqual = 10 == 10;    // => true
let isNotEqual = 10 != 9;  // => true

// String concatenation.
let greeting = "Hello" + " " + "World!";

// If/else expressions (they return values).
let max = fn(a, b) {
  if (a > b) { a } else { b }
};
max(5, 10);  // => 10

// Functions are first-class.
let add = fn(x, y) { x + y; };
add(1, 2);  // => 3

// Closures.
let newAdder = fn(x) {
  fn(y) { x + y; };
};
let addTwo = newAdder(2);
addTwo(3);  // => 5

// Implicit return.
let fibonacci = fn(x) {
  if (x == 0) {
    0
  } else {
    if (x == 1) {
      return 1;
    } else {
      fibonacci(x - 1) + fibonacci(x - 2);
    }
  }
};
fibonacci(10);  // => 55

// No loops.
let map = fn(arr, f) {
  let iter = fn(arr, accumulated) {
    if (len(arr) == 0) {
      accumulated
    } else {
      iter(rest(arr), push(accumulated, f(first(arr))));
    }
  };
  iter(arr, []);
};

// Arrays.
let numbers = [1, 2, 3, 4, 5];
let doubled = map(numbers, fn(x) { x * 2; });
// => [2, 4, 6, 8, 10]

// Hashes.
let people = {"name": "Monkey", "age": 1};
people["name"];  // => "Monkey"

// Built-in functions: len, first, last, rest, push, puts.
len("hello");        // => 5
len([1, 2, 3]);      // => 3
first([1, 2, 3]);    // => 1
last([1, 2, 3]);     // => 3
rest([1, 2, 3]);     // => [2, 3]
push([1, 2], 3);     // => [1, 2, 3]
puts("hello world"); // prints to stdout