Let and let differently while SQL did not;==, !=, <= and >= are single two-character tokens instead of two glued-together one-character ones;// line comments as trivia the parser never has to see;next() loop that hands back one token at a time, allocation-free, ready for the parser we build next.Learn Zig Series):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!
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 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 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.
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.
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".
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.
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.
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.
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.
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.
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.
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. ;-)
Hexadecimal literals. Extend number so that a 0x prefix introduces a hexadecimal integer, scanning hex digits (0-9, a-f, A-F) after the x. Keep the token kind .int; the parser can decide the base later from the text. Make sure a bare 0 followed by a non-x character still lexes as a normal decimal integer.
Block comments. Add support for /* ... */ comments in skipTrivia, remembering that they can span multiple lines (so they must still go through bump to 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's error.UnexpectedChar path (and string'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 lexes let 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! ;-)
@scipio