Source code --> Lexer --> tokens --> Parser --> AST --> Evaluator --> value
^^^^^
you are here
The lexer (also called a tokenizer or scanner) takes Monkey source code as a string and breaks it into a sequence of tokens, each being the smallest meaningful unit of the language. This step separates meaningless things from the meaningful, so the next step (the parsing) can have an easier time not needing to worry about whitespaces or other things that don’t matter in Monkey.
In practice, here’s what lexical analysis looks like.
Source: let five = 5 ;
| | | | |
v v v v v
Token: [let_] [ident] [assign] [int] [semicolon]
"let" "five" "=" "5" ";"
Each meaningful unit is mapped to a token with a type and a literal. The type is what the parser cares about (is this a keyword? an operator?) and the literal is the actual text, which we need for things like identifier names and integer values.
Our lexer hands back one token each time you call nextToken. The parser pulls tokens as it needs them, and as you’ll see in chapter 2, it never needs to look more than one token ahead. This keeps the lexer tiny and means we never hold more than the source string and a couple of positions in memory.
We’ll build the lexer across two files: token.zig for the token definitions and keyword lookup, and lexer.zig for the lexer itself.
Token definition (token.zig)
#
We’ll declare each token type as a variant in an enum. Comparing two enum values compiles down to an integer comparison instead of a string comparison. In the source I’ve grouped the tokens into categories using comments to make it easier to read.
const std = @import("std");
pub const TokenType = enum {
// Special.
illegal,
eof,
// Identifiers and literals.
ident,
int,
string,
// Operators.
assign,
plus,
minus,
bang,
asterisk,
slash,
lt,
gt,
eq,
not_eq,
// Delimiters.
comma,
semicolon,
colon,
lparen,
rparen,
lbrace,
rbrace,
lbracket,
rbracket,
// Keywords.
function,
let_,
true_,
false_,
if_,
else_,
return_,
};
pub const Token = struct {
type: TokenType,
literal: []const u8,
};
The
literalis a slice into the original source string, not a copy. The lexer never allocates, but that means the source string has to outlive every token, and later every AST node, that points into it. Keep that in the back of your mind, it comes up again in chapter 4.
Keyword lookup with lookupIdent
#
When the lexer reads your source and encounters a word like let or return or foo, it needs to make a decision. Is this a keyword or an identifier? The lexer can’t tell by looking at the characters, let and foo are both just letters. So we keep a map of the reserved words. This function builds that map at compile time, looks up the word the lexer found, and returns either the keyword’s token type or .ident to say it’s a user-defined name.
pub fn lookupIdent(ident: []const u8) TokenType {
const keywords = std.StaticStringMap(TokenType).initComptime(.{
.{ "fn", .function },
.{ "let", .let_ },
.{ "true", .true_ },
.{ "false", .false_ },
.{ "if", .if_ },
.{ "else", .else_ },
.{ "return", .return_ },
});
return keywords.get(ident) orelse .ident;
}
Trailing underscores:
let,true,false,if,else,returnwe append_to avoid conflicts with Zig keywords and primitives, and althoughletisn’t a Zig keyword I’m adding here for consistency.
Complete token.zig
#
const std = @import("std");
pub const TokenType = enum {
// Special.
illegal,
eof,
// Identifiers and literals.
ident,
int,
string,
// Operators.
assign,
plus,
minus,
bang,
asterisk,
slash,
lt,
gt,
eq,
not_eq,
// Delimiters.
comma,
semicolon,
colon,
lparen,
rparen,
lbrace,
rbrace,
lbracket,
rbracket,
// Keywords.
function,
let_,
true_,
false_,
if_,
else_,
return_,
};
pub const Token = struct {
type: TokenType,
literal: []const u8,
};
pub fn lookupIdent(ident: []const u8) TokenType {
const keywords = std.StaticStringMap(TokenType).initComptime(.{
.{ "fn", .function },
.{ "let", .let_ },
.{ "true", .true_ },
.{ "false", .false_ },
.{ "if", .if_ },
.{ "else", .else_ },
.{ "return", .return_ },
});
return keywords.get(ident) orelse .ident;
}
test "lookupIdent keywords" {
try std.testing.expectEqual(TokenType.let_, lookupIdent("let"));
try std.testing.expectEqual(TokenType.function, lookupIdent("fn"));
try std.testing.expectEqual(TokenType.return_, lookupIdent("return"));
try std.testing.expectEqual(TokenType.ident, lookupIdent("foobar"));
try std.testing.expectEqual(TokenType.ident, lookupIdent("x"));
}
Lexer (lexer.zig)
#
The lexer needs to hold a reference to the input string and track its position as it scans through characters of your Monkey source. The core of the lexer is a function called nextToken, which we’ll write in a bit, but before we start writing code let’s examine what decisions take place each time we call nextToken.
read char <------+
| |
v |
whitespace? --yes-+
|
no
v
end of input (0)? --yes--> emit eof
|
no
v
known symbol? ----yes--> emit token
| (for = and !, peek ahead
no to check for == or !=)
v
double quote? ----yes--> read until closing quote,
| emit string
no
v
letter? -------yes--> read full word, check keywords,
| emit ident or keyword
no
v
digit? --------yes--> read full number, emit int
|
no
v
emit illegal
Okay let’s build it.
Lexer struct, init and readChar
#
const std = @import("std");
const token = @import("token.zig");
pub const Lexer = struct {
input: []const u8,
position: usize,
read_position: usize,
ch: u8,
pub fn init(input: []const u8) Lexer {
var l = Lexer{
.input = input,
.position = 0,
.read_position = 0,
.ch = 0,
};
l.readChar();
return l;
}
fn readChar(self: *Lexer) void {
if (self.read_position >= self.input.len) {
self.ch = 0;
} else {
self.ch = self.input[self.read_position];
}
self.position = self.read_position;
self.read_position += 1;
}
Let’s talk about the positions we track, position and read_position. position points to the current character (stored in ch) and read_position points to the next character we’re about to read. This lookahead helps us handle two-character tokens like ==. When we see = we can lookahead at what’s coming up before deciding whether to emit assign or eq.
When we run past the end of the input we set ch to 0. That’s the NUL byte, and since it never shows up in real Monkey source it makes a handy “we’re done” marker. The nextToken switch we’ll write soon turns it into the eof token. The lexer only understands ASCII to keep the scope simple for this book.
Looking ahead with peekChar
#
fn peekChar(self: *Lexer) u8 {
if (self.read_position >= self.input.len) {
return 0;
}
return self.input[self.read_position];
}
This function looks at the next character without advancing the lexer position. This is the function we need to handle the lookahead described above.
The nextToken
#
There’s a lot going in this function so I’ll show you the code first and we’ll break this up in to 3 sections.
pub fn nextToken(self: *Lexer) token.Token {
self.skipWhitespace();
const tok: token.Token = switch (self.ch) {
// Section 1 =================================================================================
'=' => blk: {
if (self.peekChar() == '=') {
const start = self.position;
self.readChar();
break :blk .{ .type = .eq, .literal = self.input[start .. self.position + 1] };
}
break :blk .{ .type = .assign, .literal = "=" };
},
'+' => .{ .type = .plus, .literal = "+" },
'-' => .{ .type = .minus, .literal = "-" },
'!' => blk: {
if (self.peekChar() == '=') {
const start = self.position;
self.readChar();
break :blk .{ .type = .not_eq, .literal = self.input[start .. self.position + 1] };
}
break :blk .{ .type = .bang, .literal = "!" };
},
// Section 2 =================================================================================
'*' => .{ .type = .asterisk, .literal = "*" },
'/' => .{ .type = .slash, .literal = "/" },
'<' => .{ .type = .lt, .literal = "<" },
'>' => .{ .type = .gt, .literal = ">" },
',' => .{ .type = .comma, .literal = "," },
';' => .{ .type = .semicolon, .literal = ";" },
':' => .{ .type = .colon, .literal = ":" },
'(' => .{ .type = .lparen, .literal = "(" },
')' => .{ .type = .rparen, .literal = ")" },
'{' => .{ .type = .lbrace, .literal = "{" },
'}' => .{ .type = .rbrace, .literal = "}" },
'[' => .{ .type = .lbracket, .literal = "[" },
']' => .{ .type = .rbracket, .literal = "]" },
// Section 3 =================================================================================
'"' => .{ .type = .string, .literal = self.readString() },
0 => .{ .type = .eof, .literal = "" },
else => {
if (isLetter(self.ch)) {
const literal = self.readIdentifier();
return .{ .type = token.lookupIdent(literal), .literal = literal };
} else if (isDigit(self.ch)) {
return .{ .type = .int, .literal = self.readNumber() };
} else {
return .{ .type = .illegal, .literal = self.input[self.position .. self.position + 1] };
}
},
};
self.readChar();
return tok;
}
Section 1: This is where lookahead starts to make sense. When we see = we peek, if the next character is also = we consume both and emit eq, otherwise it must be assign.
Section 2: The simplest part of this function, this section simply maps a known character to its token.
Section 3: Everything that’s more than one character wide. Strings, identifiers, keywords, numbers, and whatever’s left over is illegal.
After the switch near the bottom, we call self.readChar() and then return the token. Every single-character case relies on that call to move past the character it just handled. But the identifier and number branches return directly from inside the switch and skip it. We do this because readIdentifier and readNumber loop with readChar until they hit a character that isn’t part of the word, which means they’ve already stopped on the first character after the token. If we fell through to the trailing readChar we’d skip that character entirely and let x would lose its x. The string case is different again, readString stops on the closing quote, so it falls through and the trailing readChar is what moves us past the ".
The helpers readIdentifier readNumber readString
#
fn readIdentifier(self: *Lexer) []const u8 {
const start = self.position;
while (isLetter(self.ch)) {
self.readChar();
}
return self.input[start..self.position];
}
fn readNumber(self: *Lexer) []const u8 {
const start = self.position;
while (isDigit(self.ch)) {
self.readChar();
}
return self.input[start..self.position];
}
fn readString(self: *Lexer) []const u8 {
const start = self.position + 1; // skip opening quote
while (true) {
self.readChar();
if (self.ch == '"' or self.ch == 0) break;
}
return self.input[start..self.position];
}
These functions each read a specific type of token and all follow the same pattern. They remember the starting position, advance the position while a condition is true, and return the slice when the condition is false. The readString helper has one additional step in that it skips the opening " and scans until the closing ". It also stops at 0, so an unterminated string gives you everything up to the end of input instead of running off the end of the slice. There are no escape sequences, "\n" is a backslash followed by an n.
Whitespace and characters #
fn skipWhitespace(self: *Lexer) void {
while (self.ch == ' ' or self.ch == '\t' or self.ch == '\n' or self.ch == '\r') {
self.readChar();
}
}
};
fn isLetter(ch: u8) bool {
return (ch >= 'a' and ch <= 'z') or (ch >= 'A' and ch <= 'Z') or ch == '_';
}
fn isDigit(ch: u8) bool {
return ch >= '0' and ch <= '9';
}
Complete lexer.zig
#
const std = @import("std");
const token = @import("token.zig");
pub const Lexer = struct {
input: []const u8,
position: usize,
read_position: usize,
ch: u8,
pub fn init(input: []const u8) Lexer {
var l = Lexer{
.input = input,
.position = 0,
.read_position = 0,
.ch = 0,
};
l.readChar();
return l;
}
fn readChar(self: *Lexer) void {
if (self.read_position >= self.input.len) {
self.ch = 0;
} else {
self.ch = self.input[self.read_position];
}
self.position = self.read_position;
self.read_position += 1;
}
fn peekChar(self: *Lexer) u8 {
if (self.read_position >= self.input.len) {
return 0;
}
return self.input[self.read_position];
}
pub fn nextToken(self: *Lexer) token.Token {
self.skipWhitespace();
const tok: token.Token = switch (self.ch) {
'=' => blk: {
if (self.peekChar() == '=') {
const start = self.position;
self.readChar();
break :blk .{ .type = .eq, .literal = self.input[start .. self.position + 1] };
}
break :blk .{ .type = .assign, .literal = "=" };
},
'+' => .{ .type = .plus, .literal = "+" },
'-' => .{ .type = .minus, .literal = "-" },
'!' => blk: {
if (self.peekChar() == '=') {
const start = self.position;
self.readChar();
break :blk .{ .type = .not_eq, .literal = self.input[start .. self.position + 1] };
}
break :blk .{ .type = .bang, .literal = "!" };
},
'*' => .{ .type = .asterisk, .literal = "*" },
'/' => .{ .type = .slash, .literal = "/" },
'<' => .{ .type = .lt, .literal = "<" },
'>' => .{ .type = .gt, .literal = ">" },
',' => .{ .type = .comma, .literal = "," },
';' => .{ .type = .semicolon, .literal = ";" },
':' => .{ .type = .colon, .literal = ":" },
'(' => .{ .type = .lparen, .literal = "(" },
')' => .{ .type = .rparen, .literal = ")" },
'{' => .{ .type = .lbrace, .literal = "{" },
'}' => .{ .type = .rbrace, .literal = "}" },
'[' => .{ .type = .lbracket, .literal = "[" },
']' => .{ .type = .rbracket, .literal = "]" },
'"' => .{ .type = .string, .literal = self.readString() },
0 => .{ .type = .eof, .literal = "" },
else => {
if (isLetter(self.ch)) {
const literal = self.readIdentifier();
return .{ .type = token.lookupIdent(literal), .literal = literal };
} else if (isDigit(self.ch)) {
return .{ .type = .int, .literal = self.readNumber() };
} else {
return .{ .type = .illegal, .literal = self.input[self.position .. self.position + 1] };
}
},
};
self.readChar();
return tok;
}
fn readIdentifier(self: *Lexer) []const u8 {
const start = self.position;
while (isLetter(self.ch)) {
self.readChar();
}
return self.input[start..self.position];
}
fn readNumber(self: *Lexer) []const u8 {
const start = self.position;
while (isDigit(self.ch)) {
self.readChar();
}
return self.input[start..self.position];
}
fn readString(self: *Lexer) []const u8 {
const start = self.position + 1; // skip opening quote
while (true) {
self.readChar();
if (self.ch == '"' or self.ch == 0) break;
}
return self.input[start..self.position];
}
fn skipWhitespace(self: *Lexer) void {
while (self.ch == ' ' or self.ch == '\t' or self.ch == '\n' or self.ch == '\r') {
self.readChar();
}
}
};
fn isLetter(ch: u8) bool {
return (ch >= 'a' and ch <= 'z') or (ch >= 'A' and ch <= 'Z') or ch == '_';
}
fn isDigit(ch: u8) bool {
return ch >= '0' and ch <= '9';
}
Tests #
Basic token test #
test "next token, basic symbols" {
const input = "=+(){},;";
var l = Lexer.init(input);
const expected = [_]struct { expected_type: token.TokenType, expected_literal: []const u8 }{
.{ .expected_type = .assign, .expected_literal = "=" },
.{ .expected_type = .plus, .expected_literal = "+" },
.{ .expected_type = .lparen, .expected_literal = "(" },
.{ .expected_type = .rparen, .expected_literal = ")" },
.{ .expected_type = .lbrace, .expected_literal = "{" },
.{ .expected_type = .rbrace, .expected_literal = "}" },
.{ .expected_type = .comma, .expected_literal = "," },
.{ .expected_type = .semicolon, .expected_literal = ";" },
.{ .expected_type = .eof, .expected_literal = "" },
};
for (expected) |tt| {
const tok = l.nextToken();
try std.testing.expectEqual(tt.expected_type, tok.type);
try std.testing.expectEqualStrings(tt.expected_literal, tok.literal);
}
}
Full program test #
This is the main lexer test from Thorsten Ball’s book. It tokenizes a complete Monkey program and verifies every token.
test "next token, complete program" {
const input =
\\let five = 5;
\\let ten = 10;
\\
\\let add = fn(x, y) {
\\ x + y;
\\};
\\
\\let result = add(five, ten);
\\!-/*5;
\\5 < 10 > 5;
\\
\\if (5 < 10) {
\\ return true;
\\} else {
\\ return false;
\\}
\\
\\10 == 10;
\\10 != 9;
\\"foobar"
\\"foo bar"
\\[1, 2];
\\{"foo": "bar"}
;
var l = Lexer.init(input);
// comments show which line of source is being scanned
const expected = [_]struct { expected_type: token.TokenType, expected_literal: []const u8 }{
// let five = 5 ====================================================
.{ .expected_type = .let_, .expected_literal = "let" },
.{ .expected_type = .ident, .expected_literal = "five" },
.{ .expected_type = .assign, .expected_literal = "=" },
.{ .expected_type = .int, .expected_literal = "5" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// let ten = 10 ====================================================
.{ .expected_type = .let_, .expected_literal = "let" },
.{ .expected_type = .ident, .expected_literal = "ten" },
.{ .expected_type = .assign, .expected_literal = "=" },
.{ .expected_type = .int, .expected_literal = "10" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// let add = fn(x, y) { x + y; } ===================================
.{ .expected_type = .let_, .expected_literal = "let" },
.{ .expected_type = .ident, .expected_literal = "add" },
.{ .expected_type = .assign, .expected_literal = "=" },
.{ .expected_type = .function, .expected_literal = "fn" },
.{ .expected_type = .lparen, .expected_literal = "(" },
.{ .expected_type = .ident, .expected_literal = "x" },
.{ .expected_type = .comma, .expected_literal = "," },
.{ .expected_type = .ident, .expected_literal = "y" },
.{ .expected_type = .rparen, .expected_literal = ")" },
.{ .expected_type = .lbrace, .expected_literal = "{" },
.{ .expected_type = .ident, .expected_literal = "x" },
.{ .expected_type = .plus, .expected_literal = "+" },
.{ .expected_type = .ident, .expected_literal = "y" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
.{ .expected_type = .rbrace, .expected_literal = "}" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// let result = add(five, ten) =====================================
.{ .expected_type = .let_, .expected_literal = "let" },
.{ .expected_type = .ident, .expected_literal = "result" },
.{ .expected_type = .assign, .expected_literal = "=" },
.{ .expected_type = .ident, .expected_literal = "add" },
.{ .expected_type = .lparen, .expected_literal = "(" },
.{ .expected_type = .ident, .expected_literal = "five" },
.{ .expected_type = .comma, .expected_literal = "," },
.{ .expected_type = .ident, .expected_literal = "ten" },
.{ .expected_type = .rparen, .expected_literal = ")" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// !-/*5 ===========================================================
.{ .expected_type = .bang, .expected_literal = "!" },
.{ .expected_type = .minus, .expected_literal = "-" },
.{ .expected_type = .slash, .expected_literal = "/" },
.{ .expected_type = .asterisk, .expected_literal = "*" },
.{ .expected_type = .int, .expected_literal = "5" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// 5 < 10 > 5 ======================================================
.{ .expected_type = .int, .expected_literal = "5" },
.{ .expected_type = .lt, .expected_literal = "<" },
.{ .expected_type = .int, .expected_literal = "10" },
.{ .expected_type = .gt, .expected_literal = ">" },
.{ .expected_type = .int, .expected_literal = "5" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// if (5 < 10) { return true; } else { return false; } =============
.{ .expected_type = .if_, .expected_literal = "if" },
.{ .expected_type = .lparen, .expected_literal = "(" },
.{ .expected_type = .int, .expected_literal = "5" },
.{ .expected_type = .lt, .expected_literal = "<" },
.{ .expected_type = .int, .expected_literal = "10" },
.{ .expected_type = .rparen, .expected_literal = ")" },
.{ .expected_type = .lbrace, .expected_literal = "{" },
.{ .expected_type = .return_, .expected_literal = "return" },
.{ .expected_type = .true_, .expected_literal = "true" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
.{ .expected_type = .rbrace, .expected_literal = "}" },
.{ .expected_type = .else_, .expected_literal = "else" },
.{ .expected_type = .lbrace, .expected_literal = "{" },
.{ .expected_type = .return_, .expected_literal = "return" },
.{ .expected_type = .false_, .expected_literal = "false" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
.{ .expected_type = .rbrace, .expected_literal = "}" },
// 10 == 10 ========================================================
.{ .expected_type = .int, .expected_literal = "10" },
.{ .expected_type = .eq, .expected_literal = "==" },
.{ .expected_type = .int, .expected_literal = "10" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// 10 != 9 =========================================================
.{ .expected_type = .int, .expected_literal = "10" },
.{ .expected_type = .not_eq, .expected_literal = "!=" },
.{ .expected_type = .int, .expected_literal = "9" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// "foobar" ========================================================
.{ .expected_type = .string, .expected_literal = "foobar" },
// "foo bar" =======================================================
.{ .expected_type = .string, .expected_literal = "foo bar" },
// [1, 2] ==========================================================
.{ .expected_type = .lbracket, .expected_literal = "[" },
.{ .expected_type = .int, .expected_literal = "1" },
.{ .expected_type = .comma, .expected_literal = "," },
.{ .expected_type = .int, .expected_literal = "2" },
.{ .expected_type = .rbracket, .expected_literal = "]" },
.{ .expected_type = .semicolon, .expected_literal = ";" },
// {"foo": "bar"} ==================================================
.{ .expected_type = .lbrace, .expected_literal = "{" },
.{ .expected_type = .string, .expected_literal = "foo" },
.{ .expected_type = .colon, .expected_literal = ":" },
.{ .expected_type = .string, .expected_literal = "bar" },
.{ .expected_type = .rbrace, .expected_literal = "}" },
// EOF =============================================================
.{ .expected_type = .eof, .expected_literal = "" },
};
for (expected) |tt| {
const tok = l.nextToken();
try std.testing.expectEqual(tt.expected_type, tok.type);
try std.testing.expectEqualStrings(tt.expected_literal, tok.literal);
}
}
Verify it works #
Run zig build test. No output means all tests passed.
What we built #
We have a lexer that turns a Monkey source string into tokens, one at a time, whenever the parser asks for the next one. Each token has a type for the parser and a literal with the actual text. Keywords are identifiers the language reserved, so we read the word first and then check the keyword table. One character of lookahead is enough to handle == and !=. The part I’d keep in mind going forward is where each read loop stops. Words and numbers stop on the character after the token so we return right away, strings stop on the closing quote so we advance once more before returning.
The tokens don’t mean anything yet, let 5 = x; lexes just fine. Deciding what’s valid Monkey is the parser’s job, and that’s chapter 2.