Keeping Track of Names

On this page

Table of Contents

This chapter we add let statement support to the compiler/VM. This requires a symbol table that tracks variable names and their scopes, two new opcodes for storing and loading global variables, and a globals store in the VM.

Step 1: add new opcodes
#

Add these two variants to the Opcode enum in code.zig:

op_set_global = 16,  // operand: u16 index
op_get_global = 17,  // operand: u16 index

Add these entries to the lookup function in code.zig:

.op_set_global => .{ .name = "OpSetGlobal", .operand_widths = &[_]u8{2} },
.op_get_global => .{ .name = "OpGetGlobal", .operand_widths = &[_]u8{2} },

OpSetGlobal: Pops a value from the stack and stores it in globals[index]. OpGetGlobal: Pushes globals[index] onto the stack.

Step 2: create `symbol_table.zig`
#

Create src/symbol_table.zig. The symbol table maps identifier names to Symbol structs. Each symbol has a scope and an index (its position in the relevant store). For this chapter, the only scope is global.

Complete `symbol_table.zig`
#

const std = @import("std");

pub const SymbolScope = enum {
    global,
};

pub const Symbol = struct {
    name: []const u8,
    scope: SymbolScope,
    index: usize,
};

pub const SymbolTable = struct {
    store: std.StringHashMap(Symbol),
    num_definitions: usize,
    allocator: std.mem.Allocator,

    pub fn init(allocator: std.mem.Allocator) SymbolTable {
        return .{
            .store = std.StringHashMap(Symbol).init(allocator),
            .num_definitions = 0,
            .allocator = allocator,
        };
    }

    /// Defines a new symbol in the current scope.
    /// Returns the created symbol with its assigned index.
    pub fn define(self: *SymbolTable, name: []const u8) !Symbol {
        const symbol = Symbol{
            .name = name,
            .scope = .global,
            .index = self.num_definitions,
        };
        try self.store.put(name, symbol);
        self.num_definitions += 1;
        return symbol;
    }

    /// Resolves a symbol by name.
    /// Returns the symbol if found, null otherwise.
    pub fn resolve(self: *SymbolTable, name: []const u8) ?Symbol return self.store.get(name);
};

How symbol resolution works
#

  Symbol Table (global scope)
  ┌──────────┬────────────┬───────┐
  │  Name    │   Scope    │ Index │
  ├──────────┼────────────┼───────┤
  │  "x"     │  global    │   0   │
  │  "y"     │  global    │   1   │
  └──────────┴────────────┴───────┘

  resolve("x") ──▶ ✓ Symbol{ scope: .global, index: 0 }
  resolve("z") ──▶ ✗ null (not found)

All symbols defined in this chapter are global. Later chapters add local, builtin, free, and function scopes along with an outer pointer for scope chaining.

Step 3: update `compiler.zig`
#

Add symbol table to compiler
#

Add these imports to the top of compiler.zig:

const SymbolTable = @import("symbol_table.zig").SymbolTable;
const Symbol = @import("symbol_table.zig").Symbol;

Then make three changes to the Compiler struct.

Add this field alongside the existing fields:

symbol_table: SymbolTable,

Update init to initialize the symbol table:

pub fn init(allocator: std.mem.Allocator) Compiler {
    return .{
        .instructions = .empty,
        .constants = .empty,
        .allocator = allocator,
        .last_instruction = null,
        .previous_instruction = null,
        .symbol_table = SymbolTable.init(allocator),
    };
}

Update deinit to clean up the symbol table’s store:

pub fn deinit(self: *Compiler) void {
    self.instructions.deinit(self.allocator);
    self.constants.deinit(self.allocator);
    self.symbol_table.store.deinit();
}

Compile let statements
#

Add this case to compileStatement in compiler.zig:

.let_statement => |ls| {
    try self.compileExpression(ls.value);
    const symbol = try self.symbol_table.define(ls.name);
    _ = try self.emit(.op_set_global, &[_]usize{symbol.index});
},

Compile identifiers
#

Add this case to compileExpression in compiler.zig:

.identifier => |id| {
    const symbol = self.symbol_table.resolve(id.value) orelse
        return error.UndefinedVariable;
    try self.loadSymbol(symbol);
},

Load symbol helper
#

Add this method to the Compiler struct. For now it only handles global scope. Later chapters add more cases:

fn loadSymbol(self: *Compiler, sym: Symbol) CompileError!void {
    switch (sym.scope) {
        .global => _ = try self.emit(.op_get_global, &[_]usize{sym.index}),
    }
}

For now, only .global is handled. Later chapters add more scopes and corresponding cases here.

Step 4: update `vm.zig`
#

Globals store
#

Add GLOBALS_SIZE as a module-level constant and globals as a new field on the VM struct. Initialize it in init:

const GLOBALS_SIZE = 65536;

pub const VM = struct {
    // ... existing fields (constants, instructions, stack, sp) ...
    globals: [GLOBALS_SIZE]?object.Object,

    pub fn init(bc: compiler.Bytecode) VM {
        return .{
            // ... existing field initializers ...
            .globals = [_]?object.Object{null} ** GLOBALS_SIZE,
        };
    }
};

65536 globals because the index is a u16 (max value 65535).

Handle new opcodes
#

Add these cases to the switch (op) in the run method on the VM struct:

.op_set_global => {
    const global_idx = std.mem.readInt(u16, self.instructions[ip + 1 ..][0..2], .big);
    ip += 3;
    self.globals[global_idx] = self.pop();
},
.op_get_global => {
    const global_idx = std.mem.readInt(u16, self.instructions[ip + 1 ..][0..2], .big);
    ip += 3;
    try self.push(self.globals[global_idx].?);
},

Worked example
#

Input: let one = 1; let two = 2; one + two;

Symbol table after compilation:

one: global, index 0
two: global, index 1

Bytecode:

0000 OpConstant 0         // push 1
0003 OpSetGlobal 0        // globals[0] = pop() → 1
0006 OpConstant 1         // push 2
0009 OpSetGlobal 1        // globals[1] = pop() → 2
0012 OpGetGlobal 0        // push globals[0] → 1
0015 OpGetGlobal 1        // push globals[1] → 2
0018 OpAdd                // pop both, push 3
0019 OpPop                // expression statement cleanup

Tests
#

Symbol table tests
#

Add this test at the bottom of symbol_table.zig. It only uses internal types so it goes inline:

test "define and resolve global" {
    const allocator = std.testing.allocator;
    var st = SymbolTable.init(allocator);
    defer st.store.deinit();

    const a = try st.define("a");
    try std.testing.expectEqual(SymbolScope.global, a.scope);
    try std.testing.expectEqual(@as(usize, 0), a.index);

    const b = try st.define("b");
    try std.testing.expectEqual(SymbolScope.global, b.scope);
    try std.testing.expectEqual(@as(usize, 1), b.index);

    const resolved_a = st.resolve("a").?;
    try std.testing.expectEqual(SymbolScope.global, resolved_a.scope);
    try std.testing.expectEqual(@as(usize, 0), resolved_a.index);

    try std.testing.expect(st.resolve("c") == null);
}

VM integration tests
#

Add this test to vm_test.zig.

test "global let statements" {
    const allocator = std.testing.allocator;

    const tests = [_]struct { input: []const u8, expected: i64 }{
        .{ .input = "let one = 1; one", .expected = 1 },
        .{ .input = "let one = 1; let two = 2; one + two", .expected = 3 },
        .{ .input = "let one = 1; let two = one + one; one + two", .expected = 3 },
    };

    for (tests) |tt| {
        var arena = std.heap.ArenaAllocator.init(allocator);
        defer arena.deinit();
        const result = try testVMRun(&arena, tt.input);
        try std.testing.expectEqual(tt.expected, result.integer.value);
    }
}

Verify it works
#

Make sure you’ve uncommented "src/symbol_table.zig" in build.zig, then run zig build test. No output means all tests passed.

In chapter 10 we add strings, arrays, and hashes to the compiler and VM.

Step 1: add new opcodes #

Step 2: create symbol_table.zig #

Complete symbol_table.zig #

How symbol resolution works #

Step 3: update compiler.zig #

Add symbol table to compiler #

Compile let statements #

Compile identifiers #

Load symbol helper #

Step 4: update vm.zig #

Globals store #

Handle new opcodes #

Worked example #

Tests #

Symbol table tests #

VM integration tests #

Verify it works #