Learn Zig Series (#131) - Lexing a Simple Language
Learn Zig Series (#131) - Lexing a Simple Language
What will I learn?
- Why the tokenizer we wrote for SQL last episode is the exact same tool we need to build a whole programming language, and what changes when the language gets bigger;
- How to design a token that carries a source position (line and column), so that when something goes wrong we can point at the precise character instead of shrugging;
- Reading integer and floating-point numbers with one shared scanning loop, and deciding which one you have by looking for a single dot;
- Recognising identifiers and keywords with case-sensitive matching -- and why a programming language treats
Letandletdifferently while SQL did not; - Maximal munch on operators, so that
==,!=,<=and>=are single two-character tokens instead of two glued-together one-character ones; - Scanning string literals with escape sequences, and turning an unterminated string into a typed error rather than a walk off the end of the buffer;
- Skipping whitespace and
//line comments as trivia the parser never has to see; - Wrapping the whole thing in a
next()loop that hands back one token at a time, allocation-free, ready for the parser we build next.
Requirements
- A working modern computer running macOS, Windows or Ubuntu;
- An installed Zig 0.14+ distribution (download from ziglang.org);
- The SQL lexer from episode 130 fresh in mind -- today we take that same two-stage split and point it at a real programming language;
- Tagged unions and enums from episode 6, slices from episode 5, and Zig's error handling from episode 4;
- The ambition to learn Zig programming.
Difficulty
- Advanced
Curriculum (of the Learn Zig Series):
- Zig Programming Tutorial - ep001 - Intro
- Learn Zig Series (#2) - Hello Zig, Variables and Types
- Learn Zig Series (#3) - Functions and Control Flow
- Learn Zig Series (#4) - Error Handling (Zig's Best Feature)
- Learn Zig Series (#5) - Arrays, Slices, and Strings
- Learn Zig Series (#6) - Structs, Enums, and Tagged Unions
- Learn Zig Series (#7) - Memory Management and Allocators
- Learn Zig Series (#8) - Pointers and Memory Layout
- Learn Zig Series (#9) - Comptime (Zig's Superpower)
- Learn Zig Series (#10) - Project Structure, Modules, and File I/O
- Learn Zig Series (#11) - Mini Project: Building a Step Sequencer
- Learn Zig Series (#12) - Testing and Test-Driven Development
- Learn Zig Series (#13) - Interfaces via Type Erasure
- Learn Zig Series (#14) - Generics with Comptime Parameters
- Learn Zig Series (#15) - The Build System (build.zig)
- Learn Zig Series (#16) - Sentinel-Terminated Types and C Strings
- Learn Zig Series (#17) - Packed Structs and Bit Manipulation
- Learn Zig Series (#18b) - Addendum: Async Returns in Zig 0.16
- Learn Zig Series (#19) - SIMD with @Vector
- Learn Zig Series (#20) - Working with JSON
- Learn Zig Series (#21) - Networking and TCP Sockets
- Learn Zig Series (#22) - Hash Maps and Data Structures
- Learn Zig Series (#23) - Iterators and Lazy Evaluation
- Learn Zig Series (#24) - Logging, Formatting, and Debug Output
- Learn Zig Series (#25) - Mini Project: HTTP Status Checker
- Learn Zig Series (#26) - Writing a Custom Allocator
- Learn Zig Series (#27) - C Interop: Calling C from Zig
- Learn Zig Series (#28) - C Interop: Exposing Zig to C
- Learn Zig Series (#29) - Inline Assembly and Low-Level Control
- Learn Zig Series (#30) - Thread Safety and Atomics
- Learn Zig Series (#31) - Memory-Mapped I/O and Files
- Learn Zig Series (#32) - Compile-Time Reflection with @typeInfo
- Learn Zig Series (#33) - Building a State Machine with Tagged Unions
- Learn Zig Series (#34) - Performance Profiling and Optimization
- Learn Zig Series (#35) - Cross-Compilation and Target Triples
- Learn Zig Series (#36) - Mini Project: CLI Task Runner
- Learn Zig Series (#37) - Markdown to HTML: Tokenizer and Lexer
- Learn Zig Series (#38) - Markdown to HTML: Parser and AST
- Learn Zig Series (#39) - Markdown to HTML: Renderer and CLI
- Learn Zig Series (#40) - Key-Value Store: In-Memory Store
- Learn Zig Series (#41) - Key-Value Store: Write-Ahead Log
- Learn Zig Series (#42) - Key-Value Store: TCP Server
- Learn Zig Series (#43) - Key-Value Store: Client Library and Benchmarks
- Learn Zig Series (#44) - Image Tool: Reading and Writing PPM/BMP
- Learn Zig Series (#45) - Image Tool: Pixel Operations
- Learn Zig Series (#46) - Image Tool: CLI Pipeline
- Learn Zig Series (#47) - Build a Shell: Parsing Commands
- Learn Zig Series (#48) - Build a Shell: Process Spawning
- Learn Zig Series (#49) - Build a Shell: Built-in Commands
- Learn Zig Series (#50) - Build a Shell: Job Control and Signals
- Learn Zig Series (#51) - HTTP Server: Accept Loop and Parsing
- Learn Zig Series (#52) - HTTP Server: Router and Responses
- Learn Zig Series (#53) - HTTP Server: Static Files and MIME
- Learn Zig Series (#54) - HTTP Server: Middleware and Logging
- Learn Zig Series (#55) - ECS Game Engine: Architecture
- Learn Zig Series (#56) - ECS Game Engine: Component Storage
- Learn Zig Series (#57) - ECS Game Engine: Systems and Queries
- Learn Zig Series (#58) - ECS Game Engine: Terminal Rendering
- Learn Zig Series (#59) - Assembler: Instruction Encoding
- Learn Zig Series (#60) - Assembler: Two-Pass Assembly
- Learn Zig Series (#61) - Assembler: Disassembler and Binary Inspector
- Learn Zig Series (#62) - File Systems: Reading Directories and Metadata
- Learn Zig Series (#63) - File Watching: Detecting Changes
- Learn Zig Series (#64) - Process Management: Fork, Exec, Wait
- Learn Zig Series (#65) - Pipes and Inter-Process Communication
- Learn Zig Series (#66) - Shared Memory and Semaphores
- Learn Zig Series (#67) - Signal Handling Deep Dive
- Learn Zig Series (#68) - Unix Domain Sockets
- Learn Zig Series (#69) - Daemonization: Background Services
- Learn Zig Series (#70) - Timers and Scheduling
- Learn Zig Series (#71) - Resource Limits and Capabilities
- Learn Zig Series (#72) - System Call Wrappers
- Learn Zig Series (#73) - seccomp and Sandboxing
- Learn Zig Series (#74) - ptrace: Process Tracing
- Learn Zig Series (#75) - Reading Kernel State from /proc and /sys
- Learn Zig Series (#76) - Mini Project: Process Monitor
- Learn Zig Series (#77) - Mini Project: File Sync Tool - Part 1
- Learn Zig Series (#78) - Mini Project: File Sync Tool - Part 2: Delta Transfer
- Learn Zig Series (#79) - Mini Project: File Sync Tool - Part 3: Network Protocol
- Learn Zig Series (#80) - Mini Project: File Sync Tool - Part 4: Polish
- Learn Zig Series (#81) - UDP Sockets and Datagrams
- Learn Zig Series (#82) - DNS Resolver from Scratch
- Learn Zig Series (#83) - DNS Server Implementation
- Learn Zig Series (#84) - HTTP/1.1 Deep Dive
- Learn Zig Series (#85) - HTTP/2 Frames and Streams
- Learn Zig Series (#86) - TLS via C Interop
- Learn Zig Series (#87) - WebSocket Protocol
- Learn Zig Series (#88) - WebSocket Server
- Learn Zig Series (#89) - MQTT Messaging Protocol
- Learn Zig Series (#90) - Protocol Buffers Serialization
- Learn Zig Series (#91) - MessagePack Format
- Learn Zig Series (#92) - gRPC Service in Zig
- Learn Zig Series (#93) - SOCKS5 Proxy
- Learn Zig Series (#94) - NAT Traversal and Hole Punching
- Learn Zig Series (#95) - Mini Project: Chat Server - Protocol Design
- Learn Zig Series (#96) - Mini Project: Chat Server - Server Core
- Learn Zig Series (#97) - Mini Project: Chat Server - Client TUI
- Learn Zig Series (#98) - Mini Project: Chat Server - Rooms and History
- Learn Zig Series (#99) - Mini Project: DNS-over-HTTPS Proxy
- Learn Zig Series (#100) - Mini Project: Port Scanner
- Learn Zig Series (#101) - Mini Project: HTTP Load Tester - Part 1
- Learn Zig Series (#102) - Mini Project: HTTP Load Tester - Part 2
- Learn Zig Series (#103) - Mini Project: Reverse Proxy - Routing
- Learn Zig Series (#104) - Mini Project: Reverse Proxy - Load Balancing
- Learn Zig Series (#105) - Mini Project: Reverse Proxy - Health Checks
- Learn Zig Series (#106) - Linked Lists: Singly and Doubly
- Learn Zig Series (#107) - Skip Lists
- Learn Zig Series (#108) - B-Trees
- Learn Zig Series (#109) - Red-Black Trees
- Learn Zig Series (#110) - Tries: Prefix Trees
- Learn Zig Series (#111) - Bloom Filters
- Learn Zig Series (#112) - Cuckoo Filters
- Learn Zig Series (#113) - Ring Buffers: Lock-Free
- Learn Zig Series (#114) - Memory Pools
- Learn Zig Series (#115) - Slab Allocators
- Learn Zig Series (#116) - Sorting Algorithms in Zig
- Learn Zig Series (#117) - Binary Search Variations
- Learn Zig Series (#118) - Graph Representation
- Learn Zig Series (#119) - BFS and DFS
- Learn Zig Series (#120) - Dijkstra and A*
- Learn Zig Series (#121) - Topological Sort
- Learn Zig Series (#122) - Union-Find
- Learn Zig Series (#123) - LRU Cache
- Learn Zig Series (#124) - Consistent Hashing
- Learn Zig Series (#125) - Mini Project: Search Engine - Inverted Index
- Learn Zig Series (#126) - Mini Project: Search Engine - TF-IDF
- Learn Zig Series (#127) - Mini Project: Search Engine - Query Parser
- Learn Zig Series (#128) - Mini Project: Database Engine - Page Storage
- Learn Zig Series (#129) - Mini Project: Database Engine - B-Tree Index
- Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser
- Learn Zig Series (#131) - Lexing a Simple Language (this post)
Learn Zig Series (#131) - Lexing a Simple Language
Last episode we ended the database mini-project by writing a lexer and a recursive-descent parser for a tiny slice of SQL, and I made a promise in passing: that the technique we used there -- characters into tokens, tokens into a typed tree -- is not a database technique at all. It is the technique, the one that turns any text a human writes into structure a machine can act on. Today we cash that promise in. We are starting a new arc, and the thing we are building over the next stretch of episodes is a small programming language of our own -- a real one, with variables, functions, arithmetic, conditionals and loops, that reads a line of source and actually runs it.
Every language, without exception, starts at the same place we started with SQL: the lexer. Before a compiler or an interpreter can reason about what your code means, it has to chop the flat river of characters into meaningful atoms -- the word let, the number 42, the operator ==, the string "hello". Those atoms are called tokens, and the job of turning let x = 42; into the token sequence let, x, =, 42, ; is lexing, also called tokenizing or scanning. It is the least glamorous stage of a language and, done badly, the one that produces the worst error messages you have ever sworn at. Done well, it is invisible -- and that is what we are aiming for. Let's dive right in!
From a SQL toy to a real language
The SQL lexer from episode 130 was deliberately minimal. It knew eight keywords, a handful of single-character punctuation symbols, identifiers and integers, and that was the whole alphabet. It matched keywords case-insensitively because SQL does, it borrowed each token's text as a slice into the source instead of copying, and it produced one token at a time from a next method. All three of those decisions were right, and we keep every one of them today. But a programming language asks for more, and the differences are exactly what this episode is about.
Here is the language we are going to lex. It has no official name -- call it our little language -- and a fragment of it looks like this:
// compute a factorial the slow, honest way
let n = 5;
fn fact(x) {
if x <= 1 {
return 1;
}
return x * fact(x - 1);
}
let answer = fact(n);
let greeting = "fact of 5 is";
Look at what that fragment demands that our SQL toy never did. There are comments (// to end of line) that the parser should never even see. There are string literals with real content inside quotes. There are two-character operators like <= sitting right next to single-character ones like <. There are keywords (let, fn, if, return) that must be case-sensitive, because in a programming language Return is a variable name and return is a statement and confusing the two is a catastrophe. And when a human is going to type thousands of lines of this, we cannot report an error as "something is wrong somewhere" -- we need to say line 7, column 12. That last one, source position tracking, is the single biggest upgrade, so let us build it into the very first type we write.
A token that knows where it came from
A token is still a tiny value -- a kind plus the slice of source it came from -- but now it also carries a position, the line and column where it starts. That position costs us two integers per token and buys us every good error message we will ever print. First the full catalogue of token kinds our grammar can produce, one variant per keyword, one per literal category, one per operator, one per punctuation mark, and the eof sentinel so the parser always has something to look at:
const std = @import("std");
const TokenKind = enum {
// keywords
kw_let, kw_fn, kw_if, kw_else, kw_while, kw_return,
kw_true, kw_false, kw_and, kw_or,
// literals and names
identifier, int, float, string,
// operators
plus, minus, star, slash, percent,
assign, eq, neq, lt, lte, gt, gte, bang,
// punctuation
lparen, rparen, lbrace, rbrace, comma, semicolon,
eof,
};
const Token = struct {
kind: TokenKind,
text: []const u8, // a slice pointing straight into the source
line: usize,
col: usize,
};
// the lexer has exactly two ways to fail, and both are typed
const LexError = error{ UnexpectedChar, UnterminatedString };
The LexError set names the only two things that can go wrong while scanning -- an unrecognised character, or a string with no closing quote -- and every scanning method that can hit them returns LexError!Token so the caller is forced to handle both. Notice the two categories that did not exist in the SQL lexer: float (a number with a decimal point) as distinct from int, and string for quoted text. Notice also that the operators come in pairs that share a first character -- assign (=) versus eq (==), lt (<) versus lte (<=) -- which is precisely the thing that will force us to look one character ahead. And as before, text is a borrowed slice into the original source, not an owned copy. The lexer allocates nothing. Every token just remembers where in the input it lives, so the source string has to outlive the tokens -- which, for a program we lex in one pass, is trivially true. No allocator, no frees, no lifetime headaches, exactly the discipline from episode 5.
The lexer, and the art of the cursor
The lexer holds the source, a cursor position, and -- this is new -- the current line and column, so that every token it emits can be stamped with where it began. The interesting part is that we cannot just advance pos and call it a day anymore, because we have to notice when we cross a newline and reset the column. So every character we consume goes through one method, bump, which is the only place pos, line and col change together. Centralising that is what keeps the position bookkeeping honest:
const Lexer = struct {
src: []const u8,
pos: usize = 0,
line: usize = 1,
col: usize = 1,
fn peek(self: *Lexer) u8 {
if (self.pos >= self.src.len) return 0;
return self.src[self.pos];
}
fn peekNext(self: *Lexer) u8 {
if (self.pos + 1 >= self.src.len) return 0;
return self.src[self.pos + 1];
}
fn bump(self: *Lexer) u8 {
const c = self.src[self.pos];
self.pos += 1;
if (c == '\n') {
self.line += 1;
self.col = 1;
} else {
self.col += 1;
}
return c;
}
peek looks at the current character without consuming it, and returns 0 at end of input so callers never have to special-case the boundary in the middle of a scanning loop -- 0 is not a character any of our loops accept, so they all stop naturally. peekNext looks one further, which is exactly the one-character lookahead we need to tell < from <=. And bump is the workhorse: it reads the current character, advances the cursor, and updates the line and column -- a newline bumps the line and resets the column to 1, anything else just moves the column along. Every other method in the lexer is written in terms of these three, and none of them ever touches pos directly. That is the discipline that makes line-and-column tracking reliable in stead of a source of off-by-one misery.
Trivia: whitespace and comments the parser never sees
Before scanning a token we have to get past the stuff between tokens -- whitespace and comments. This is often called trivia, because it is real text in the file but carries no meaning the parser cares about (a code formatter cares, which is why formatters keep trivia around, but our interpreter does not). A // comment runs to the end of the line, so we swallow characters until we hit a newline or run out of input. Whitespace we simply skip. The loop keeps going until it sees a character that starts a real token:
fn skipTrivia(self: *Lexer) void {
while (self.pos < self.src.len) {
const c = self.src[self.pos];
if (std.ascii.isWhitespace(c)) {
_ = self.bump();
} else if (c == '/' and self.peekNext() == '/') {
// line comment: consume through end of line
while (self.pos < self.src.len and self.src[self.pos] != '\n') {
_ = self.bump();
}
} else {
break;
}
}
}
The subtle bit is the ordering. We check for // before we would ever treat / as a division operator, so a comment always wins over division -- which is correct, because // can only mean a comment, never "divide by the start of a comment". Note also that we route the comment-skipping through bump too, so that a comment spanning to a newline still advances the line counter properly. Trivia may be meaningless to the parser, but it still occupies real lines and columns, and if we skipped it without counting we would mis-locate every token after the first comment.
Numbers: one loop, two kinds
Now the real tokens. Numbers first, because they show off a nice trick. An integer and a float scan almost identically -- a run of digits -- and they only diverge when a decimal point appears with a digit after it. So we scan the integer part, then peek: if the next character is a . and the one after that is a digit, we have a float, so we consume the dot and scan the fractional digits too. That "digit after the dot" check matters, because otherwise 5.method() (if our language ever grows method calls) would wrongly eat the dot:
fn number(self: *Lexer, line: usize, col: usize) Token {
const start = self.pos;
while (std.ascii.isDigit(self.peek())) {
_ = self.bump();
}
var kind: TokenKind = .int;
if (self.peek() == '.' and std.ascii.isDigit(self.peekNext())) {
kind = .float;
_ = self.bump(); // consume the '.'
while (std.ascii.isDigit(self.peek())) {
_ = self.bump();
}
}
return Token{
.kind = kind,
.text = self.src[start..self.pos],
.line = line,
.col = col,
};
}
This is the same maximal munch idea from the Markdown and SQL lexers: mark the start, walk forward as long as the character still belongs to this token, and slice from start to the new position. What is new is that the token's kind is decided during the scan, not before it. We do not know whether 3 is an int or the start of 3.14 until we have looked past the digits -- and the one character of lookahead peekNext gives us is exactly enough to decide. The token's text is still just a borrowed slice; we do not convert it to an actual number here. Turning "3.14" into the f64 value 3.14 is a job for later, with std.fmt.parseFloat, once the parser knows it wants a number in that position. The lexer's only job is to say "these five characters are one float token, starting at line L, column C".
Identifiers, keywords, and case that matters
A word -- a run of letters, digits and underscores that starts with a letter or underscore -- is either an identifier (a variable or function name) or a keyword (let, if, fn). To the scanning loop they look identical, so we scan the whole word first and then ask a lookup table what it is. The difference from SQL is that our lookup is case-sensitive: std.mem.eql compares the bytes exactly, so let is the keyword but Let and LET are ordinary identifiers, which is how nearly every real programming language behaves:
fn isIdentChar(c: u8) bool {
return std.ascii.isAlphanumeric(c) or c == '_';
}
fn identifierOrKeyword(self: *Lexer, line: usize, col: usize) Token {
const start = self.pos;
while (isIdentChar(self.peek())) {
_ = self.bump();
}
const word = self.src[start..self.pos];
return Token{ .kind = keywordKind(word), .text = word, .line = line, .col = col };
}
The keyword lookup itself is a small table walked linearly -- the same shape as episode 130, just case-sensitive and with our language's reserved words. Ten keywords is far too few to bother with a hash map or a sorted binary search; a straight loop is faster than the machinery you would build to avoid it, and it reads clearly:
fn keywordKind(word: []const u8) TokenKind {
const keywords = [_]struct { text: []const u8, kind: TokenKind }{
.{ .text = "let", .kind = .kw_let },
.{ .text = "fn", .kind = .kw_fn },
.{ .text = "if", .kind = .kw_if },
.{ .text = "else", .kind = .kw_else },
.{ .text = "while", .kind = .kw_while },
.{ .text = "return", .kind = .kw_return },
.{ .text = "true", .kind = .kw_true },
.{ .text = "false", .kind = .kw_false },
.{ .text = "and", .kind = .kw_and },
.{ .text = "or", .kind = .kw_or },
};
for (keywords) |kw| {
if (std.mem.eql(u8, word, kw.text)) return kw.kind;
}
return .identifier;
}
Any word that matches nothing in the table falls through to .identifier -- the default that lets n, fact, answer and greeting through as names. That default is what makes the whole approach extensible: to add a keyword later you add one row to the table and one variant to the enum, and every word that used to be an identifier keeps being one.
Operators and maximal munch, the two-character way
Here is the genuinely new mechanism of this episode. Our language has operators that share a first character: = means assignment but == means equality, ! means logical-not but != means not-equal, < is less-than but <= is less-than-or-equal. When the lexer sees a =, it cannot decide which token it has until it looks at the next character. The rule that resolves this is called maximal munch: always take the longest token that matches. If = is followed by another =, take ==; otherwise take the lone =.
We express that with a little helper, match, that consumes the next character only if it is the one we hoped for -- a conditional bump. Then the operator scanner is a switch over the first character, and the two-character cases ask match whether to upgrade themselves:
fn match(self: *Lexer, expected: u8) bool {
if (self.peek() == expected) {
_ = self.bump();
return true;
}
return false;
}
fn operator(self: *Lexer, line: usize, col: usize) LexError!Token {
const start = self.pos;
const c = self.bump();
const kind: TokenKind = switch (c) {
'+' => .plus,
'-' => .minus,
'*' => .star,
'/' => .slash,
'%' => .percent,
',' => .comma,
';' => .semicolon,
'(' => .lparen,
')' => .rparen,
'{' => .lbrace,
'}' => .rbrace,
'=' => if (self.match('=')) .eq else .assign,
'!' => if (self.match('=')) .neq else .bang,
'<' => if (self.match('=')) .lte else .lt,
'>' => if (self.match('=')) .gte else .gt,
else => return error.UnexpectedChar,
};
return Token{
.kind = kind,
.text = self.src[start..self.pos],
.line = line,
.col = col,
};
}
Trace <= through it. We bump the <, landing in the '<' arm; match('=') peeks, sees the =, bumps it, and returns true, so the kind is .lte. Now self.pos has moved past both characters, so self.src[start..self.pos] is the two-byte slice "<=" -- the token's text spans exactly the operator, one character or two, without us tracking the length by hand. Trace a bare < instead: match('=') peeks, sees something else, returns false without consuming, and the kind is .lt with a one-byte slice. And anything the switch does not recognise -- a stray @ or $ -- falls through to error.UnexpectedChar, a typed failure rather than a silently swallowed mystery character. That is the episode-4 error philosophy again: the lexer produces a token or an error, never garbage.
Strings and the danger of running off the end
The last token kind is the string literal, and it hides the classic lexer bug: the unterminated string. When we see an opening ", we scan forward until we find the closing " -- but what if there isn't one? A naive loop would run straight off the end of the buffer. So the loop guards on self.pos < self.src.len at every step, and if we reach the end without finding a closing quote, we return a typed error.UnterminatedString in stead of crashing:
fn string(self: *Lexer, line: usize, col: usize) LexError!Token {
_ = self.bump(); // consume the opening quote
const start = self.pos;
while (self.pos < self.src.len and self.peek() != '"') {
// a backslash escapes the next character, so skip both
if (self.peek() == '\\') {
_ = self.bump();
if (self.pos >= self.src.len) break;
}
_ = self.bump();
}
if (self.pos >= self.src.len) return error.UnterminatedString;
const text = self.src[start..self.pos];
_ = self.bump(); // consume the closing quote
return Token{ .kind = .string, .text = text, .line = line, .col = col };
}
There is a real subtlety in the escape handling. Inside the string, a backslash means "the next character is literal, whatever it is" -- so "she said \"hi\"" contains two quote characters that must not end the string. When we see a \, we bump past it and past the character it escapes, so an escaped " never trips the loop's terminating condition. Note carefully what text holds: it is the raw slice between the quotes, escapes and all -- she said \"hi\", backslashes still in it. We deliberately do not decode the escapes here. Turning \" into " and \n into a real newline is a separate concern that needs a fresh buffer (and therefore an allocator), and it belongs in the parser or a later pass, not in the allocation-free lexer. The lexer's job is only to find the boundaries of the token and prove it is well-formed. Keeping that boundary clean -- scanning here, decoding later -- is the kind of separation that keeps each stage small enough to hold in your head.
Tying it off: next(), and a loop over a whole program
Everything above are the branches; next is the trunk that chooses among them. It skips trivia, records the starting line and column, handles end-of-input, and then dispatches on the first character -- a digit starts a number, a letter or underscore starts a word, a quote starts a string, and anything else goes to the operator scanner:
fn next(self: *Lexer) LexError!Token {
self.skipTrivia();
const line = self.line;
const col = self.col;
if (self.pos >= self.src.len) {
return Token{ .kind = .eof, .text = "", .line = line, .col = col };
}
const c = self.peek();
if (std.ascii.isDigit(c)) return self.number(line, col);
if (std.ascii.isAlphabetic(c) or c == '_') return self.identifierOrKeyword(line, col);
if (c == '"') return self.string(line, col);
return self.operator(line, col);
}
};
We capture line and col after skipping trivia and before scanning, so the position points at the first real character of the token, not at the whitespace in front of it. That closing }; ends the Lexer struct -- everything we wrote is a method on it, driven by peek, peekNext and bump. Now driving the lexer over an entire program is a five-line loop: call next until it hands back eof, doing whatever you like with each token in between. Here we simply print them, which is the single most useful debugging tool you can have while building a language -- being able to see exactly how your source was tokenized:
pub fn main() !void {
const source =
\\let n = 5;
\\fn fact(x) {
\\ if x <= 1 { return 1; }
\\ return x * fact(x - 1);
\\}
;
var lexer = Lexer{ .src = source };
while (true) {
const tok = try lexer.next();
std.debug.print("{d}:{d}\t{s}\t'{s}'\n", .{
tok.line, tok.col, @tagName(tok.kind), tok.text,
});
if (tok.kind == .eof) break;
}
}
@tagName turns the enum variant into its name string for printing, so you get a readable dump: 1:1 kw_let 'let', 1:5 identifier 'n', 1:7 assign '=', and so on down to the final eof. The moment you can print that table, debugging a language stops being guesswork -- when the parser later complains, you dump the token stream and see whether the lexer or the parser is at fault. As we saw with the SQL parser last episode, keeping stages separate means you can also test them separately, so let us do exactly that.
Proving it, token by token
A test is worth more than my say-so. I feed the lexer a full statement and assert the exact sequence of kinds it produces, ending in eof. This is the same test shape as episode 130, now exercising keywords, an identifier, a two-character operator, a number and punctuation all in one line:
test "lexer tokenizes a statement into the right kinds" {
var lx = Lexer{ .src = "let x = 42 <= y;" };
const expected = [_]TokenKind{
.kw_let, .identifier, .assign, .int, .lte, .identifier, .semicolon, .eof,
};
for (expected) |kind| {
const tok = try lx.next();
try std.testing.expectEqual(kind, tok.kind);
}
}
Eight tokens in order: let, x, =, 42, <=, y, ;, and the sentinel. The <= arriving as a single .lte rather than a .lt followed by an .assign is the maximal-munch rule working. Next, prove the number classifier and the position stamping -- that a dotted number becomes a .float, that the string's text is the raw content without the quotes, and that a token on the second line reports line == 2:
test "floats, strings, and positions are recorded correctly" {
var lx = Lexer{ .src = "3.14\n\"hi\"" };
const num = try lx.next();
try std.testing.expectEqual(TokenKind.float, num.kind);
try std.testing.expectEqualStrings("3.14", num.text);
try std.testing.expectEqual(@as(usize, 1), num.line);
const str = try lx.next();
try std.testing.expectEqual(TokenKind.string, str.kind);
try std.testing.expectEqualStrings("hi", str.text); // quotes stripped, content borrowed
try std.testing.expectEqual(@as(usize, 2), str.line); // second line
}
And the part that separates a toy from a tool -- proving that bad input fails cleanly rather than crashing. A stray character and an unterminated string should each produce their own typed error, caught and asserted with expectError:
test "malformed input produces typed errors, never a crash" {
var lx1 = Lexer{ .src = "let x = @;" };
_ = try lx1.next(); // let
_ = try lx1.next(); // x
_ = try lx1.next(); // =
try std.testing.expectError(error.UnexpectedChar, lx1.next());
var lx2 = Lexer{ .src = "\"no closing quote" };
try std.testing.expectError(error.UnterminatedString, lx2.next());
}
The first case walks up to the @, which no branch of operator recognises, so it returns error.UnexpectedChar. The second opens a string and never finds its closing quote, so string runs to the end of input and returns error.UnterminatedString. Both funnel into the same handled, typed, non-crashing path -- the caller gets an error value it can attach a line and column to and print as a real diagnostic, in stead of a segfault or a silently wrong token. That, more than anything, is what Zig's error handling buys a language front-end: there is no malformed input that becomes undefined behaviour, only inputs that become errors you are forced to deal with.
How C, Rust, and Go do it
The shape you just wrote is not a teaching simplification -- it is how production language front-ends are built, scaled up. The reference C implementation of Lua hand-writes its lexer (llex.c) as almost exactly this: a struct holding the source and current position, a next that switches on the current character, maximal munch for its two-character operators like == and ~=, and a keyword table checked after scanning a word. The famous book Crafting Interpreters builds its C and Java scanners with this identical structure -- start and current pointers, a match helper for two-character operators, line tracking on every newline -- which is a good sign we are on the well-trodden path and not inventing something strange.
In Rust, the compiler's own lexer (rustc_lexer) is a hand-written scanner producing tokens with lengths rather than copied strings, the same borrowing idea as our slices, and the logos crate lets you generate a very fast lexer from an enum of patterns -- different ergonomics, same two-stage pipeline underneath. In Go, the standard library's text/scanner and the compiler's own cmd/compile/internal/syntax scanner are both hand-written state machines that track line and column for diagnostics exactly as we do; Go's designers are famously allergic to parser generators and hand-write the whole front-end. Rob Pike's well-known talk on Go's template lexer models it as concurrent state functions, a lovely variation, but the atoms it produces are the same tokens.
Zig's own compiler, fittingly, has a hand-written Tokenizer in lib/std/zig/tokenizer.zig that is startlingly close in spirit to what we built -- a state machine over bytes, keywords in a comptime map, tokens carrying source offsets rather than copied text. So the technique is not just a way to lex; across C, Rust, Go and Zig itself, hand-written scanning into borrowed-slice tokens with maximal munch and a keyword table is the way, and generators are the exception reserved for grammars far larger than a hobby language. You have written the real thing, at real-language scale, minus a few hundred more keywords.
Where this is heading
Step back and look at what we have. A stream of typed tokens, each stamped with a line and column, each borrowing its text straight from the source, produced one at a time by an allocation-free next that turns unexpected characters and unterminated strings into errors rather than crashes. That is the raw material of every stage that follows. Right now those tokens are still a flat list -- let, x, =, 42, ; -- with no structure, no notion that x is being bound to 42, no tree. Giving them structure, turning that flat stream into a shape that captures what the program means, is the next brick, and it is the one that finally lets us stop thinking in characters and start thinking in expressions and statements.
If the two-stage split from the SQL parser is fresh in your mind, you already know the outline of what comes next -- one small function per grammar rule, each consuming exactly the tokens it expects. The difference is that our little language has real nesting: expressions inside expressions, x * fact(x - 1), precedence between * and +, function calls, blocks inside if. That is a richer parsing problem than a flat SQL statement, and it is where recursive descent starts to show its full power. Build the lexer, dump its tokens over the factorial program above until the table looks exactly right, and you will have the foundation the whole arc stands on -- because a parser is only ever as trustworthy as the tokens you feed it. ;-)
Exercises
Hexadecimal literals. Extend
numberso that a0xprefix introduces a hexadecimal integer, scanning hex digits (0-9,a-f,A-F) after thex. Keep the token kind.int; the parser can decide the base later from the text. Make sure a bare0followed by a non-xcharacter still lexes as a normal decimal integer.Block comments. Add support for
/* ... */comments inskipTrivia, remembering that they can span multiple lines (so they must still go throughbumpto keep the line counter correct). As a stretch, make them nest, so that/* outer /* inner */ still a comment */is handled correctly -- which C famously does not do, but Rust and Zig do.A column-precise error. Change
operator'serror.UnexpectedCharpath (andstring's unterminated case) so the lexer stores the offending line and column in a field on the struct before returning the error, then write a test that lexeslet x = @;and asserts the recorded position points exactly at the@. This is the groundwork for the human-readable diagnostics every good compiler prints.
Go dump some tokens over that factorial program until the table reads exactly right -- thanks for reading, and see you in the next one! ;-)
Leave Learn Zig Series (#131) - Lexing a Simple Language to:
Read more #stem posts
Best Posts From scipio
We have not curated any of scipio's posts yet. But you can encourage our curation team to review posts by visiting them regularly and by referring other readers. Because we give priority to frequently read content.
More Posts From scipio
- Learn Zig Series (#131) - Lexing a Simple Language
- Learn Rust Series (#20) - Drop & Deterministic Destruction (RAII)
- Learn AI Series (#150) - Emerging Frontiers
- Learn Zig Series (#130) - Mini Project: Database Engine - SQL Parser
- Learn Rust Series (#19) - Deref, DerefMut & Deref Coercion
- Learn AI Series (#149) - AI Ethics in Practice
- Learn Zig Series (#129) - Mini Project: Database Engine - B-Tree Index
- Learn Rust Series (#18) - Operator Overloading with std::ops
- Learn AI Series (#148) - The Economics of AI
- Learn Zig Series (#128) - Mini Project: Database Engine - Page Storage