Lexer 1

lexer_1.md

To understand Tree-sitter using Zig, we start with the absolute atom of parsing: the Lexer.

In a traditional compiler, the Lexer (or Scanner) turns a string of characters into a stream of Tokens. In an incremental system like Tree-sitter, the lexer must be able to start at any byte offset, but for our first step, we will build a linear Lexer in Zig.

---

1. The Core Data Structures

First, we define what our "Tokens" look like. Using a Zig enum is perfect for this because we can use tagged unions later for more complex metadata.

const std = @import("std");

pub const TokenType = enum {
    keyword_fn,
    identifier,
    l_paren,
    r_paren,
    l_brace,
    r_brace,
    punctuation,
    eof,
    invalid,
};

pub const Token = struct {
    tag: TokenType,
    loc: Loc,
};

pub const Loc = struct {
    start: usize,
    end: usize,
};

---

2. Building a Basic Lexer in Zig

A Tree-sitter-style lexer is essentially a Deterministic Finite Automaton (DFA). It reads a character, checks the current state, and decides whether to transition to a new state or emit a token.

Here is a simplified implementation in Zig that recognizes a few basic patterns:

pub const Lexer = struct {
    buffer: []const u8,
    pos: usize,

    pub fn init(buffer: []const u8) Lexer {
        return .{
            .buffer = buffer,
            .pos = 0,
        };
    }

    pub fn next(self: *Lexer) Token {
        self.skipWhitespace();

        if (self.pos >= self.buffer.len) {
            return .{ .tag = .eof, .loc = .{ .start = self.pos, .end = self.pos } };
        }

        const start = self.pos;
        const c = self.buffer[self.pos];

        return switch (c) {
            '(' => self.emit(.l_paren, 1),
            ')' => self.emit(.r_paren, 1),
            '{' => self.emit(.l_brace, 1),
            '}' => self.emit(.r_brace, 1),
            'a'...'z', 'A'...'Z', '_' => self.lexIdentifier(start),
            else => self.emit(.invalid, 1),
        };
    }

    fn lexIdentifier(self: *Lexer, start: usize) Token {
        while (self.pos < self.buffer.len and isAlphaNumeric(self.buffer[self.pos])) {
            self.pos += 1;
        }
        const text = self.buffer[start..self.pos];
        if (std.mem.eql(u8, text, "fn")) {
            return .{ .tag = .keyword_fn, .loc = .{ .start = start, .end = self.pos } };
        }
        return .{ .tag = .identifier, .loc = .{ .start = start, .end = self.pos } };
    }

    fn skipWhitespace(self: *Lexer) void {
        while (self.pos < self.buffer.len and std.ascii.isWhitespace(self.buffer[self.pos])) {
            self.pos += 1;
        }
    }

    fn emit(self: *Lexer, tag: TokenType, len: usize) Token {
        const start = self.pos;
        self.pos += len;
        return .{ .tag = tag, .loc = .{ .start = start, .end = self.pos } };
    }
};

fn isAlphaNumeric(c: u8) bool {
    return std.ascii.isAlphanumeric(c) or c == '_';
}

---

3. Why this matters for Tree-sitter

In a standard parser, you just call lexer.next() until you hit EOF. However, Tree-sitter's algorithm requires the Lexer to be restartable.

The Concept of "Lookahead"

When Tree-sitter parses, it records how many characters the lexer looked at before deciding on a token.

• If you have the code var x = 10; and you change 10 to 20, Tree-sitter knows that the var and x tokens are still valid.
• It only re-runs the lexer on the "dirty" range.

Your First Exercise

To start thinking like the Tree-sitter engineers, try to modify the Lexer above in a Zig scratchpad:

1. Add a peek() function: In Zig, this would return u8 without advancing self.pos. This is how parsers "look ahead" to decide between two rules.
2. Implement a LexerState: Imagine you stop the lexer halfway through. What data would you need to save to resume it later? (Hint: In Tree-sitter, this is often just the byte offset, but for languages like Python, it includes an indentation stack).

---

Next Step

Once you are comfortable turning a string like fn main() into [.keyword_fn, .identifier, .l_paren, .r_paren], we will move to the Syntax Tree—defining how these tokens nest inside each other using Zig's MultiArrayList for high-performance memory layout.

Does the DFA (Switch-case) approach to lexing make sense, or would you like to dive deeper into how Zig handles the memory for these tokens?