Source code --> Lexer --> tokens --> Parser --> AST --> Evaluator --> value
^^^^^^
you are here
In chapter 1 we wrote a lexer to break our source code into tokens. In this chapter we’ll write the parser that’ll take the tokens and build an Abstract Syntax Tree (AST), a tree representation of your source code structure.
Let’s look at an example AST for let result = 5 + 3 * 4;.
LetStatement
/ \
name: "result" value:
Infix (+)
/ \
Int(5) Infix (*)
/ \
Int(3) Int(4)
Look at the shape of it. The * ended up deeper in the tree than the +, which is what makes 5 + 3 * 4 mean 5 + (3 * 4) and not (5 + 3) * 4. Building that shape correctly is the whole job of the parser, and the technique we’ll use to do it is called Pratt parsing (after Vaughan Pratt, who described it in 1973). A Pratt parser handles prefix operators (at the start of an expression, like -5 or !true) and infix operators (between two expressions, like 5 + 3) using one relatively simple idea. Every token type gets a numeric precedence, and the parser uses that number to decide how much of what follows belongs to the expression it’s currently building. The higher the number, the tighter the operator binds. I’ll walk through exactly how this works, with a trace, when we get to parseExpression. For now just remember that the tree shape falls out of the precedence numbers.
Statements and expressions #
Two words you’ll see constantly from here on. An expression produces a value: 5, x + y, add(1, 2), fn(x) { x }. A statement doesn’t: let x = 5; binds a name, return x; leaves a function. Monkey has exactly three kinds of statements, let, return, and the expression statement, which is just an expression sitting on its own line, like x + 10; typed into the REPL. A block statement is a { ... } full of statements, it’s what goes inside an if or a function body. A Monkey program is a list of statements.
One thing that makes Monkey a little unusual is that if and fn are expressions, not statements. let max = if (a > b) { a } else { b }; is valid Monkey. That decision makes the parser and the evaluator simpler, since there’s one fewer category to handle, and it’s why you’ll see IfExpression and FunctionLiteral living next to IntegerLiteral in the AST.
A word on memory #
This is the first place our Zig version has to make a decision the Go version never did. An AST is a tree, tree nodes point at other tree nodes, so somebody has to allocate them. The parser takes an allocator in init and uses it for every node, every list of statements, and every error message. What we never do is free any of it one piece at a time. A tree is only useful as a whole, and once we’re done with a program we’re done with all of it. So every caller in this book (the tests, and the REPL in chapter 4) hands the parser an arena and frees everything in one shot. The same strategy carries over to the runtime values in chapter 3. A language meant for long-running programs would need a garbage collector or reference counting here, and that’s a big enough topic to be its own book. For Monkey, arenas are the right tool and they let us focus on the interpreter.
We’ll be building the parser across two files: ast.zig for AST node types, and parser.zig for the Pratt parser itself.
AST (ast.zig)
#
In this source we’ll define every kind of node that can appear in a Monkey source program. We’ll build it in layers start with leaf nodes, then compound expressions, then statements.
Leaf nodes #
These are the simplest Monkey expressions, they carry a single value and have no children.
const std = @import("std");
pub const Identifier = struct { value: []const u8 };
pub const IntegerLiteral = struct { value: i64 };
pub const Boolean = struct { value: bool };
pub const StringLiteral = struct { value: []const u8 };
An Identifier holds a name like "foo" or "bar" and an IntegerLiteral holds a parsed number. These are the leaves of our tree.
Compound expressions #
These nodes contain other expressions and form the tree.
Notice that some children are *const Expression pointers and some aren’t. Expression is going to be a tagged union that includes InfixExpression, and InfixExpression contains an Expression. A type can’t contain itself by value, the compiler would have no way to know how big it is, so recursive children have to go behind a pointer. BlockStatement and the slices are fine by value because a slice is only a pointer and a length. This is the same reason a linked list node holds a pointer to the next node and not the next node itself.
pub const PrefixExpression = struct {
operator: []const u8,
right: *const Expression,
};
pub const InfixExpression = struct {
left: *const Expression,
operator: []const u8,
right: *const Expression,
};
pub const IfExpression = struct {
condition: *const Expression,
consequence: BlockStatement,
alternative: ?BlockStatement,
};
pub const FunctionLiteral = struct {
parameters: []const Identifier,
body: BlockStatement,
};
pub const CallExpression = struct {
function: *const Expression,
arguments: []const Expression,
};
pub const IndexExpression = struct {
left: *const Expression,
index: *const Expression,
};
An InfixExpression like 5 + 3 has a left pointing to Int(5) and a right pointing to Int(3). This is how our tree is nesting 5 + 3 * 4, the right of the + node points to an entire InfixExpression for 3 * 4.
We store the operator as a string ("+", "==") rather than a token type. It’s slightly wasteful, the evaluator ends up comparing strings, but it keeps the AST readable and it’s what the Go book does. Swapping it for the TokenType enum is an easy change if it bothers you.
Collection literals #
Arrays are a list of expressions, [1, 2 * 2, add(3, 4)]. Hashes are a list of key/value pairs where both sides are expressions, {"one": 1, x + 1: "two"}. At parse time we don’t care whether a key is something you can actually hash, that’s a runtime question and the evaluator will answer it in chapter 3.
pub const ArrayLiteral = struct { elements: []const Expression };
pub const HashLiteral = struct { pairs: []const HashPair };
pub const HashPair = struct {
key: Expression,
value: Expression,
};
The Expression union
#
To return “any kind of expression” from a single function we gather all our expression types into a single tagged union. The union isn’t closed yet in the snippet below, writeTo and string in the next section live inside it.
pub const Expression = union(enum) {
identifier: Identifier,
integer_literal: IntegerLiteral,
boolean: Boolean,
string_literal: StringLiteral,
prefix: PrefixExpression,
infix: InfixExpression,
if_expression: IfExpression,
function_literal: FunctionLiteral,
call: CallExpression,
array_literal: ArrayLiteral,
index_expression: IndexExpression,
hash_literal: HashLiteral,
Printing with writeTo
#
In order to test/debug we need a way to print an expression as a string. The writeTo function recursively walks the tree and writes the representation, allowing us to assert things like 5 + 3 * 4 parses as "(5 + (3 * 4))". Every infix and prefix expression gets wrapped in parentheses, so the string tells you the exact tree shape. That’s the whole point, it makes precedence bugs visible.
pub fn writeTo(self: Expression, writer: *std.Io.Writer) !void {
switch (self) {
.identifier => |id| try writer.writeAll(id.value),
.integer_literal => |il| try writer.print("{d}", .{il.value}),
.boolean => |b| try writer.writeAll(if (b.value) "true" else "false"),
.string_literal => |s| try writer.writeAll(s.value),
.prefix => |p| {
try writer.writeAll("(");
try writer.writeAll(p.operator);
try p.right.writeTo(writer);
try writer.writeAll(")");
},
.infix => |i| {
try writer.writeAll("(");
try i.left.writeTo(writer);
try writer.writeAll(" ");
try writer.writeAll(i.operator);
try writer.writeAll(" ");
try i.right.writeTo(writer);
try writer.writeAll(")");
},
.if_expression => |ie| {
try writer.writeAll("if ");
try ie.condition.writeTo(writer);
try writer.writeAll(" { ... }");
if (ie.alternative != null) {
try writer.writeAll(" else { ... }");
}
},
.function_literal => |fl| {
try writer.writeAll("fn(");
for (fl.parameters, 0..) |param, idx| {
if (idx > 0) try writer.writeAll(", ");
try writer.writeAll(param.value);
}
try writer.writeAll(") { ... }");
},
.call => |c| {
try c.function.writeTo(writer);
try writer.writeAll("(");
for (c.arguments, 0..) |arg, idx| {
if (idx > 0) try writer.writeAll(", ");
try arg.writeTo(writer);
}
try writer.writeAll(")");
},
.array_literal => |a| {
try writer.writeAll("[");
for (a.elements, 0..) |elem, idx| {
if (idx > 0) try writer.writeAll(", ");
try elem.writeTo(writer);
}
try writer.writeAll("]");
},
.index_expression => |ie| {
try writer.writeAll("(");
try ie.left.writeTo(writer);
try writer.writeAll("[");
try ie.index.writeTo(writer);
try writer.writeAll("])");
},
.hash_literal => |h| {
try writer.writeAll("{");
for (h.pairs, 0..) |pair, idx| {
if (idx > 0) try writer.writeAll(", ");
try pair.key.writeTo(writer);
try writer.writeAll(": ");
try pair.value.writeTo(writer);
}
try writer.writeAll("}");
},
}
}
pub fn string(self: Expression, allocator: std.mem.Allocator) ![]const u8 {
var out: std.Io.Writer.Allocating = .init(allocator);
try self.writeTo(&out.writer);
return out.toOwnedSlice();
}
};
Statements #
Monkey programs are a list of statements, they’re the top-level building blocks. As covered above, there are only three kinds: let bindings, return statements, and expression statements.
pub const ReturnStatement = struct { value: Expression };
pub const ExpressionStatement = struct { expression: Expression };
pub const BlockStatement = struct { statements: []const Statement };
pub const Statement = union(enum) {
let_statement: LetStatement,
return_statement: ReturnStatement,
expression_statement: ExpressionStatement,
};
pub const LetStatement = struct {
name: []const u8,
value: Expression,
};
pub const Program = struct { statements: []const Statement };
Complete ast.zig
#
const std = @import("std");
pub const Identifier = struct { value: []const u8 };
pub const IntegerLiteral = struct { value: i64 };
pub const Boolean = struct { value: bool };
pub const StringLiteral = struct { value: []const u8 };
pub const PrefixExpression = struct {
operator: []const u8,
right: *const Expression,
};
pub const InfixExpression = struct {
left: *const Expression,
operator: []const u8,
right: *const Expression,
};
pub const IfExpression = struct {
condition: *const Expression,
consequence: BlockStatement,
alternative: ?BlockStatement,
};
pub const FunctionLiteral = struct {
parameters: []const Identifier,
body: BlockStatement,
};
pub const CallExpression = struct {
function: *const Expression,
arguments: []const Expression,
};
pub const IndexExpression = struct {
left: *const Expression,
index: *const Expression,
};
pub const ArrayLiteral = struct { elements: []const Expression };
pub const HashLiteral = struct { pairs: []const HashPair };
pub const HashPair = struct {
key: Expression,
value: Expression,
};
pub const Expression = union(enum) {
identifier: Identifier,
integer_literal: IntegerLiteral,
boolean: Boolean,
string_literal: StringLiteral,
prefix: PrefixExpression,
infix: InfixExpression,
if_expression: IfExpression,
function_literal: FunctionLiteral,
call: CallExpression,
array_literal: ArrayLiteral,
index_expression: IndexExpression,
hash_literal: HashLiteral,
pub fn writeTo(self: Expression, writer: *std.Io.Writer) !void {
switch (self) {
.identifier => |id| try writer.writeAll(id.value),
.integer_literal => |il| try writer.print("{d}", .{il.value}),
.boolean => |b| try writer.writeAll(if (b.value) "true" else "false"),
.string_literal => |s| try writer.writeAll(s.value),
.prefix => |p| {
try writer.writeAll("(");
try writer.writeAll(p.operator);
try p.right.writeTo(writer);
try writer.writeAll(")");
},
.infix => |i| {
try writer.writeAll("(");
try i.left.writeTo(writer);
try writer.writeAll(" ");
try writer.writeAll(i.operator);
try writer.writeAll(" ");
try i.right.writeTo(writer);
try writer.writeAll(")");
},
.if_expression => |ie| {
try writer.writeAll("if ");
try ie.condition.writeTo(writer);
try writer.writeAll(" { ... }");
if (ie.alternative != null) {
try writer.writeAll(" else { ... }");
}
},
.function_literal => |fl| {
try writer.writeAll("fn(");
for (fl.parameters, 0..) |param, idx| {
if (idx > 0) try writer.writeAll(", ");
try writer.writeAll(param.value);
}
try writer.writeAll(") { ... }");
},
.call => |c| {
try c.function.writeTo(writer);
try writer.writeAll("(");
for (c.arguments, 0..) |arg, idx| {
if (idx > 0) try writer.writeAll(", ");
try arg.writeTo(writer);
}
try writer.writeAll(")");
},
.array_literal => |a| {
try writer.writeAll("[");
for (a.elements, 0..) |elem, idx| {
if (idx > 0) try writer.writeAll(", ");
try elem.writeTo(writer);
}
try writer.writeAll("]");
},
.index_expression => |ie| {
try writer.writeAll("(");
try ie.left.writeTo(writer);
try writer.writeAll("[");
try ie.index.writeTo(writer);
try writer.writeAll("])");
},
.hash_literal => |h| {
try writer.writeAll("{");
for (h.pairs, 0..) |pair, idx| {
if (idx > 0) try writer.writeAll(", ");
try pair.key.writeTo(writer);
try writer.writeAll(": ");
try pair.value.writeTo(writer);
}
try writer.writeAll("}");
},
}
}
pub fn string(self: Expression, allocator: std.mem.Allocator) ![]const u8 {
var out: std.Io.Writer.Allocating = .init(allocator);
try self.writeTo(&out.writer);
return out.toOwnedSlice();
}
};
pub const ReturnStatement = struct { value: Expression };
pub const ExpressionStatement = struct { expression: Expression };
pub const BlockStatement = struct { statements: []const Statement };
pub const Statement = union(enum) {
let_statement: LetStatement,
return_statement: ReturnStatement,
expression_statement: ExpressionStatement,
};
pub const LetStatement = struct {
name: []const u8,
value: Expression,
};
pub const Program = struct { statements: []const Statement };
Parser (parser.zig)
#
Precedence levels #
To set precedence we use an enum backed by u8 where the integer value determines the precedence. The names are the ones from the Go book. lowest is the floor, it’s what we pass when we want “parse a whole expression, whatever it is”.
const Precedence = enum(u8) {
lowest = 1,
equals = 2, // ==
less_greater = 3, // > or <
sum = 4, // +
product = 5, // *
prefix = 6, // -X or !X
call = 7, // myFunction(X)
index = 8, // array[index]
};
fn getPrecedence(token_type: token.TokenType) Precedence {
return switch (token_type) {
.eq, .not_eq => .equals,
.lt, .gt => .less_greater,
.plus, .minus => .sum,
.slash, .asterisk => .product,
.lparen => .call,
.lbracket => .index,
else => .lowest,
};
}
Two entries in that table might look odd. Why do ( and [ have a precedence? Because in a Pratt parser a function call is treated as an infix operator. In add(1, 2) the ( sits between add and the arguments the same way + sits between 1 and 2. Same story for myArray[0]. Giving them the highest precedences means they bind tighter than anything else, which is what you want: -add(1, 2) should negate the result of the call, not call the negation. Hold that thought, it’ll click when we get to the infix loop.
Parser struct and init
#
const std = @import("std");
const token = @import("token.zig");
const ast = @import("ast.zig");
const Lexer = @import("lexer.zig").Lexer;
pub const Parser = struct {
const Error = std.mem.Allocator.Error || error{ParseError};
lexer: *Lexer,
cur_token: token.Token,
peek_token: token.Token,
errors: std.ArrayList([]const u8),
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator, lexer: *Lexer) Parser {
var p = Parser{
.lexer = lexer,
.cur_token = undefined,
.peek_token = undefined,
.errors = .empty,
.allocator = allocator,
};
p.nextToken();
p.nextToken();
return p;
}
In the init we prime both cur_token and peek_token by calling nextToken twice to make sure the parser always has one token lookahead. That’s the whole window the parser ever gets to see, two tokens sliding left to right over the stream the lexer produces on demand.
tokens: let five = 5 ; eof
^ ^
cur peek
after nextToken():
tokens: let five = 5 ; eof
^ ^
cur peek
Every decision the parser makes comes down to “what is cur_token, and what is peek_token?” That turns out to be enough for Monkey, and for a lot of real languages too.
Token navigation helpers #
fn nextToken(self: *Parser) void {
self.cur_token = self.peek_token;
self.peek_token = self.lexer.nextToken();
}
fn curPrecedence(self: *Parser) Precedence {
return getPrecedence(self.cur_token.type);
}
fn peekPrecedence(self: *Parser) Precedence {
return getPrecedence(self.peek_token.type);
}
fn expectPeek(self: *Parser, t: token.TokenType) Error!bool {
if (self.peek_token.type == t) {
self.nextToken();
return true;
}
try self.peekError(t);
return false;
}
fn peekError(self: *Parser, t: token.TokenType) Error!void {
const msg = try std.fmt.allocPrint(
self.allocator,
"expected next token to be {t}, got {t} instead",
.{ t, self.peek_token.type },
);
try self.errors.append(self.allocator, msg);
}
The expectPeek helper is how we assert the next token is what the grammar demands. If it is, we advance onto it and return true. If not, we record an error and return false, and it’s up to the caller to decide what to do. This is where nearly every parser error message comes from, “expected next token to be rparen, got eof instead” and friends.
Which brings up how this parser handles errors, because it uses two mechanisms and it helps to know why. At the statement level, when a let is malformed we record the message and return null. parseProgram skips that statement, moves on, and keeps collecting errors, so a user gets all their mistakes reported at once instead of one per run. Deeper down, inside an expression, it’s not safe to keep guessing, half an if expression isn’t something we can recover from, so those helpers return error.ParseError and unwind all the way out. In both cases the human-readable message has already been appended to errors before we bail, so whoever called parseProgram can print it.
Statement dispatch and parseProgram
#
pub fn parseProgram(self: *Parser) Error!ast.Program {
var statements: std.ArrayList(ast.Statement) = .empty;
while (self.cur_token.type != .eof) {
if (try self.parseStatement()) |stmt| try statements.append(self.allocator, stmt);
self.nextToken();
}
return .{ .statements = try statements.toOwnedSlice(self.allocator) };
}
fn parseStatement(self: *Parser) Error!?ast.Statement {
return switch (self.cur_token.type) {
.let_ => try self.parseLetStatement(),
.return_ => try self.parseReturnStatement(),
else => try self.parseExpressionStatement(),
};
}
parseProgram is the entry point. It loops until eof, asks parseStatement for the next statement, and collects the results. parseStatement only needs to look at cur_token. If it’s let or return we know what we’re parsing. Anything else must be the start of an expression, so it becomes an expression statement.
Parsing let and return
#
A let statement is let <ident> = <expression>;. Read the function top to bottom and you can see the grammar in the calls: expect an identifier, expect an =, step past it, parse an expression. The semicolon at the end is optional in our Monkey, which is what makes typing let x = 5 without one into the REPL work.
parseBlockStatement is the same loop as parseProgram with a different stopping condition. It reads statements until it hits the closing } (or runs out of input).
fn parseLetStatement(self: *Parser) Error!?ast.Statement {
if (!try self.expectPeek(.ident)) return null;
const name = self.cur_token.literal;
if (!try self.expectPeek(.assign)) return null;
self.nextToken();
const value = try self.parseExpression(.lowest) orelse return null;
if (self.peek_token.type == .semicolon) self.nextToken();
return .{ .let_statement = .{ .name = name, .value = value } };
}
fn parseReturnStatement(self: *Parser) Error!?ast.Statement {
self.nextToken();
const value = try self.parseExpression(.lowest) orelse return null;
if (self.peek_token.type == .semicolon) self.nextToken();
return .{ .return_statement = .{ .value = value } };
}
fn parseExpressionStatement(self: *Parser) Error!?ast.Statement {
const expr = try self.parseExpression(.lowest) orelse return null;
if (self.peek_token.type == .semicolon) self.nextToken();
return .{ .expression_statement = .{ .expression = expr } };
}
fn parseBlockStatement(self: *Parser) Error!ast.BlockStatement {
self.nextToken(); // skip the {
var statements: std.ArrayList(ast.Statement) = .empty;
while (self.cur_token.type != .rbrace and self.cur_token.type != .eof) {
if (try self.parseStatement()) |stmt| try statements.append(self.allocator, stmt);
self.nextToken();
}
return .{ .statements = try statements.toOwnedSlice(self.allocator) };
}
parseExpression
#
This is the meat and potato of the parser, and the one function in the book I’d ask you to slow down on. It has two halves. First we look at cur_token and build the leftmost piece of the expression from it, that’s the prefix half. Then we loop, and on each pass we ask “does the operator in peek_token bind tighter than the precedence I was called with?” If it does, whatever we’ve built so far becomes the left side of that operator and we keep going. If it doesn’t, we return what we have and let our caller deal with the operator.
fn parseExpression(self: *Parser, precedence: Precedence) Error!?ast.Expression {
// Half 1: build the left side from the current token.
var left: ast.Expression = switch (self.cur_token.type) {
.ident => .{ .identifier = .{ .value = self.cur_token.literal } },
.int => blk: {
const value = std.fmt.parseInt(i64, self.cur_token.literal, 10) catch {
try self.errors.append(
self.allocator,
try std.fmt.allocPrint(self.allocator, "could not parse '{s}' as integer", .{self.cur_token.literal}),
);
return null;
};
break :blk .{ .integer_literal = .{ .value = value } };
},
.string => .{ .string_literal = .{ .value = self.cur_token.literal } },
.true_ => .{ .boolean = .{ .value = true } },
.false_ => .{ .boolean = .{ .value = false } },
.bang, .minus => try self.parsePrefixExpression(),
.lparen => try self.parseGroupedExpression() orelse return null,
.if_ => try self.parseIfExpression(),
.function => try self.parseFunctionLiteral(),
.lbracket => try self.parseArrayLiteral(),
.lbrace => try self.parseHashLiteral(),
else => {
try self.errors.append(
self.allocator,
try std.fmt.allocPrint(self.allocator, "no prefix parse function for {t}", .{self.cur_token.type}),
);
return null;
},
};
// Half 2: keep absorbing infix operators while they bind tighter than we do.
while (self.peek_token.type != .semicolon and
@intFromEnum(precedence) < @intFromEnum(self.peekPrecedence()))
{
switch (self.peek_token.type) {
.plus, .minus, .slash, .asterisk, .eq, .not_eq, .lt, .gt => {
self.nextToken();
left = try self.parseInfixExpression(left);
},
.lparen => {
self.nextToken();
left = try self.parseCallExpression(left);
},
.lbracket => {
self.nextToken();
left = try self.parseIndexExpression(left);
},
else => return left,
}
}
return left;
}
How the precedence argument works #
The precedence parameter is best read as “how hard is the thing on my left holding on to me?” When parseProgram wants a whole expression it passes lowest, nobody is holding on. When parseInfixExpression is building the right side of a +, it passes sum, meaning “the + on your left is holding on with strength 4, only give me operators stronger than that.”
Let’s trace 5 + 3 * 4. The numbers are the enum values: lowest is 1, sum is 4, product is 5, and eof has no entry so it’s lowest.
parseExpression(lowest=1) cur: 5 peek: +
half 1: left = Int(5)
half 2: is 1 < prec(+)=4? yes, absorb it
parseInfixExpression(left=Int(5)) cur: + peek: 3
operator "+", prec = 4, advance cur: 3 peek: *
parseExpression(sum=4)
half 1: left = Int(3)
half 2: is 4 < prec(*)=5? yes, absorb it
parseInfixExpression(left=Int(3)) cur: * peek: 4
operator "*", prec = 5, advance cur: 4 peek: eof
parseExpression(product=5)
half 1: left = Int(4)
half 2: is 5 < prec(eof)=1? no, return Int(4)
returns Infix(3 * 4)
half 2: is 4 < prec(eof)=1? no, return Infix(3 * 4)
returns Infix(5 + (3 * 4))
half 2: is 1 < prec(eof)=1? no, return
result: (5 + (3 * 4))
The 3 got absorbed by the * because when we were parsing the right side of + (with precedence 4) the * (precedence 5) was stronger. Now flip the operators, 5 * 3 + 4:
parseExpression(lowest=1) cur: 5 peek: *
half 1: left = Int(5)
half 2: is 1 < prec(*)=5? yes, absorb it
parseInfixExpression(left=Int(5)) cur: * peek: 3
operator "*", prec = 5, advance cur: 3 peek: +
parseExpression(product=5)
half 1: left = Int(3)
half 2: is 5 < prec(+)=4? no, return Int(3)
returns Infix(5 * 3)
half 2: is 1 < prec(+)=4? yes, absorb it
parseInfixExpression(left=Infix(5 * 3)) cur: + peek: 4
operator "+", prec = 4, advance cur: 4 peek: eof
parseExpression(sum=4) -> Int(4)
returns Infix((5 * 3) + 4)
half 2: is 1 < prec(eof)=1? no, return
result: ((5 * 3) + 4)
This time the 3 was not absorbed by the +, because we were inside the right side of * (precedence 5) and + is only 4. So parseExpression(product) returned just Int(3), the * finished with (5 * 3), and control went back up to the outer loop, which was running with lowest and was happy to absorb the +. Same code, different tree, and the only thing that changed was the number.
Here’s the AST from the top of the chapter again with the precedences written in. Higher numbers sit lower in the tree.
Infix(+) prec 4
/ \
Int(5) Infix(*) prec 5
/ \
Int(3) Int(4)
A few things fall out of this design that I want to spell out.
Left associativity comes from the <
#
Trace a + b + c. After the first + we call parseExpression(sum), which parses b and then asks “is 4 < prec(+)=4?” No, strictly less than fails, so it returns just b. The first + finishes as (a + b), and the outer loop picks up the second +, giving ((a + b) + c). If that comparison were <= you’d get (a + (b + c)) instead, so that one character is what decides associativity.
Prefix operators use the prefix precedence
#
parsePrefixExpression calls parseExpression(.prefix), and prefix is 6, higher than every arithmetic operator. So in -a * b the right side of - is asked “is 6 < prec(*)=5?”, says no, and returns just a. Result: ((-a) * b). If it passed lowest you’d get (-(a * b)), which is wrong.
Calls and indexing are infix operators #
Now the odd entries in the precedence table make sense. In add(1, 2), half 1 builds Identifier(add), then half 2 sees ( in peek_token, checks 1 < prec(lparen)=7, and hands add to parseCallExpression as the left side. There’s no special case for “is this identifier a function?”, anything can be called, which is why fn(x) { x }(5) works without any extra code. Indexing is the same trick with [. And since index (8) is higher than call (7), a[0](1) parses as ((a[0])(1)), which is what you’d expect.
Grouped expressions reset the precedence #
parseGroupedExpression just calls parseExpression(.lowest) and then expects a ). That’s all parentheses are, a way to say “nobody is holding on to what’s in here”. We don’t even need a node type for them, the tree shape does the work.
Once this clicks, you can add a new operator to Monkey in two lines: a precedence in the table and a case in the infix loop.
Prefix and infix expression builders #
parsePrefixExpression records the operator, steps onto the operand, and parses it with prefix precedence, for the reason above. parseInfixExpression receives the already-built left side, records the operator and its precedence, steps onto the right side, and parses that with the operator’s own precedence. Both heap-allocate their children because, as covered in the AST section, a union can’t contain itself by value.
fn parsePrefixExpression(self: *Parser) Error!ast.Expression {
const operator = self.cur_token.literal;
self.nextToken();
const right = try self.parseExpression(.prefix) orelse
return error.ParseError;
const right_ptr = try self.allocator.create(ast.Expression);
right_ptr.* = right;
return .{ .prefix = .{ .operator = operator, .right = right_ptr } };
}
fn parseInfixExpression(self: *Parser, left: ast.Expression) Error!ast.Expression {
const operator = self.cur_token.literal;
const prec = self.curPrecedence();
self.nextToken();
const right = try self.parseExpression(prec) orelse
return error.ParseError;
const left_ptr = try self.allocator.create(ast.Expression);
left_ptr.* = left;
const right_ptr = try self.allocator.create(ast.Expression);
right_ptr.* = right;
return .{ .infix = .{
.left = left_ptr,
.operator = operator,
.right = right_ptr,
} };
}
Grouped expressions, if/else and functions #
These three all follow the same shape: use expectPeek to walk through the fixed parts of the syntax ((, ), {, else) and call parseExpression or parseBlockStatement for the variable parts. If you can read parseIfExpression top to bottom you can read the grammar of an if off of it. Also, a function literal parses to an AST node and nothing more. There’s no function object yet and no environment, that’s all runtime, and runtime is chapter 3.
fn parseGroupedExpression(self: *Parser) Error!?ast.Expression {
self.nextToken();
const expr = try self.parseExpression(.lowest);
if (!try self.expectPeek(.rparen)) return null;
return expr;
}
fn parseIfExpression(self: *Parser) Error!ast.Expression {
if (!try self.expectPeek(.lparen)) return error.ParseError;
self.nextToken();
const condition = try self.parseExpression(.lowest) orelse return error.ParseError;
const condition_ptr = try self.allocator.create(ast.Expression);
condition_ptr.* = condition;
if (!try self.expectPeek(.rparen)) return error.ParseError;
if (!try self.expectPeek(.lbrace)) return error.ParseError;
const consequence = try self.parseBlockStatement();
var alternative: ?ast.BlockStatement = null;
if (self.peek_token.type == .else_) {
self.nextToken();
if (!try self.expectPeek(.lbrace)) return error.ParseError;
alternative = try self.parseBlockStatement();
}
return .{ .if_expression = .{
.condition = condition_ptr,
.consequence = consequence,
.alternative = alternative,
} };
}
fn parseFunctionLiteral(self: *Parser) Error!ast.Expression {
if (!try self.expectPeek(.lparen)) return error.ParseError;
const parameters = try self.parseFunctionParameters();
if (!try self.expectPeek(.lbrace)) return error.ParseError;
const body = try self.parseBlockStatement();
return .{ .function_literal = .{
.parameters = parameters,
.body = body,
} };
}
fn parseFunctionParameters(self: *Parser) Error![]const ast.Identifier {
var params: std.ArrayList(ast.Identifier) = .empty;
if (self.peek_token.type == .rparen) {
self.nextToken();
return params.toOwnedSlice(self.allocator);
}
if (!try self.expectPeek(.ident)) return error.ParseError;
try params.append(self.allocator, .{ .value = self.cur_token.literal });
while (self.peek_token.type == .comma) {
self.nextToken(); // skip comma
if (!try self.expectPeek(.ident)) return error.ParseError;
try params.append(self.allocator, .{ .value = self.cur_token.literal });
}
if (!try self.expectPeek(.rparen)) return error.ParseError;
return params.toOwnedSlice(self.allocator);
}
Calls, arrays, indexing and hashes #
Call arguments and array elements have the same shape, a comma-separated list of expressions with a closing token, so they share parseExpressionList and just pass a different terminator. parseIndexExpression is another infix builder: it receives the left side, parses the index expression with lowest (anything goes inside the brackets), and expects a ]. Hashes are the fiddliest of the bunch only because each entry has three parts, key, colon, value, and the loop has to handle the trailing } with and without a comma before it.
fn parseCallExpression(self: *Parser, function: ast.Expression) Error!ast.Expression {
const func_ptr = try self.allocator.create(ast.Expression);
func_ptr.* = function;
const arguments = try self.parseExpressionList(.rparen);
return .{ .call = .{
.function = func_ptr,
.arguments = arguments,
} };
}
fn parseArrayLiteral(self: *Parser) Error!ast.Expression {
const elements = try self.parseExpressionList(.rbracket);
return .{ .array_literal = .{ .elements = elements } };
}
fn parseExpressionList(self: *Parser, end: token.TokenType) Error![]const ast.Expression {
var list: std.ArrayList(ast.Expression) = .empty;
if (self.peek_token.type == end) {
self.nextToken();
return list.toOwnedSlice(self.allocator);
}
self.nextToken();
try list.append(self.allocator, try self.parseExpression(.lowest) orelse return error.ParseError);
while (self.peek_token.type == .comma) {
self.nextToken(); // skip comma
self.nextToken(); // move to expression
try list.append(self.allocator, try self.parseExpression(.lowest) orelse return error.ParseError);
}
if (!try self.expectPeek(end)) return error.ParseError;
return list.toOwnedSlice(self.allocator);
}
fn parseIndexExpression(self: *Parser, left: ast.Expression) Error!ast.Expression {
self.nextToken();
const index = try self.parseExpression(.lowest) orelse return error.ParseError;
if (!try self.expectPeek(.rbracket)) return error.ParseError;
const left_ptr = try self.allocator.create(ast.Expression);
left_ptr.* = left;
const index_ptr = try self.allocator.create(ast.Expression);
index_ptr.* = index;
return .{ .index_expression = .{
.left = left_ptr,
.index = index_ptr,
} };
}
fn parseHashLiteral(self: *Parser) Error!ast.Expression {
var pairs: std.ArrayList(ast.HashPair) = .empty;
while (self.peek_token.type != .rbrace) {
self.nextToken();
const key = try self.parseExpression(.lowest) orelse return error.ParseError;
if (!try self.expectPeek(.colon)) return error.ParseError;
self.nextToken();
const value = try self.parseExpression(.lowest) orelse return error.ParseError;
try pairs.append(self.allocator, .{ .key = key, .value = value });
if (self.peek_token.type != .rbrace) {
if (!try self.expectPeek(.comma)) return error.ParseError;
}
}
if (!try self.expectPeek(.rbrace)) return error.ParseError;
return .{ .hash_literal = .{ .pairs = try pairs.toOwnedSlice(self.allocator) } };
}
};
Complete parser.zig
#
const std = @import("std");
const token = @import("token.zig");
const ast = @import("ast.zig");
const Lexer = @import("lexer.zig").Lexer;
const Precedence = enum(u8) {
lowest = 1,
equals = 2, // ==
less_greater = 3, // > or <
sum = 4, // +
product = 5, // *
prefix = 6, // -X or !X
call = 7, // myFunction(X)
index = 8, // array[index]
};
fn getPrecedence(token_type: token.TokenType) Precedence {
return switch (token_type) {
.eq, .not_eq => .equals,
.lt, .gt => .less_greater,
.plus, .minus => .sum,
.slash, .asterisk => .product,
.lparen => .call,
.lbracket => .index,
else => .lowest,
};
}
pub const Parser = struct {
const Error = std.mem.Allocator.Error || error{ParseError};
lexer: *Lexer,
cur_token: token.Token,
peek_token: token.Token,
errors: std.ArrayList([]const u8),
allocator: std.mem.Allocator,
pub fn init(allocator: std.mem.Allocator, lexer: *Lexer) Parser {
var p = Parser{
.lexer = lexer,
.cur_token = undefined,
.peek_token = undefined,
.errors = .empty,
.allocator = allocator,
};
p.nextToken();
p.nextToken();
return p;
}
fn nextToken(self: *Parser) void {
self.cur_token = self.peek_token;
self.peek_token = self.lexer.nextToken();
}
fn curPrecedence(self: *Parser) Precedence {
return getPrecedence(self.cur_token.type);
}
fn peekPrecedence(self: *Parser) Precedence {
return getPrecedence(self.peek_token.type);
}
fn expectPeek(self: *Parser, t: token.TokenType) Error!bool {
if (self.peek_token.type == t) {
self.nextToken();
return true;
}
try self.peekError(t);
return false;
}
fn peekError(self: *Parser, t: token.TokenType) Error!void {
const msg = try std.fmt.allocPrint(
self.allocator,
"expected next token to be {t}, got {t} instead",
.{ t, self.peek_token.type },
);
try self.errors.append(self.allocator, msg);
}
pub fn parseProgram(self: *Parser) Error!ast.Program {
var statements: std.ArrayList(ast.Statement) = .empty;
while (self.cur_token.type != .eof) {
if (try self.parseStatement()) |stmt| try statements.append(self.allocator, stmt);
self.nextToken();
}
return .{ .statements = try statements.toOwnedSlice(self.allocator) };
}
fn parseStatement(self: *Parser) Error!?ast.Statement {
return switch (self.cur_token.type) {
.let_ => try self.parseLetStatement(),
.return_ => try self.parseReturnStatement(),
else => try self.parseExpressionStatement(),
};
}
fn parseLetStatement(self: *Parser) Error!?ast.Statement {
if (!try self.expectPeek(.ident)) return null;
const name = self.cur_token.literal;
if (!try self.expectPeek(.assign)) return null;
self.nextToken();
const value = try self.parseExpression(.lowest) orelse return null;
if (self.peek_token.type == .semicolon) self.nextToken();
return .{ .let_statement = .{ .name = name, .value = value } };
}
fn parseReturnStatement(self: *Parser) Error!?ast.Statement {
self.nextToken();
const value = try self.parseExpression(.lowest) orelse return null;
if (self.peek_token.type == .semicolon) self.nextToken();
return .{ .return_statement = .{ .value = value } };
}
fn parseExpressionStatement(self: *Parser) Error!?ast.Statement {
const expr = try self.parseExpression(.lowest) orelse return null;
if (self.peek_token.type == .semicolon) self.nextToken();
return .{ .expression_statement = .{ .expression = expr } };
}
fn parseBlockStatement(self: *Parser) Error!ast.BlockStatement {
self.nextToken(); // skip the {
var statements: std.ArrayList(ast.Statement) = .empty;
while (self.cur_token.type != .rbrace and self.cur_token.type != .eof) {
if (try self.parseStatement()) |stmt| try statements.append(self.allocator, stmt);
self.nextToken();
}
return .{ .statements = try statements.toOwnedSlice(self.allocator) };
}
fn parseExpression(self: *Parser, precedence: Precedence) Error!?ast.Expression {
// Half 1: build the left side from the current token.
var left: ast.Expression = switch (self.cur_token.type) {
.ident => .{ .identifier = .{ .value = self.cur_token.literal } },
.int => blk: {
const value = std.fmt.parseInt(i64, self.cur_token.literal, 10) catch {
try self.errors.append(
self.allocator,
try std.fmt.allocPrint(self.allocator, "could not parse '{s}' as integer", .{self.cur_token.literal}),
);
return null;
};
break :blk .{ .integer_literal = .{ .value = value } };
},
.string => .{ .string_literal = .{ .value = self.cur_token.literal } },
.true_ => .{ .boolean = .{ .value = true } },
.false_ => .{ .boolean = .{ .value = false } },
.bang, .minus => try self.parsePrefixExpression(),
.lparen => try self.parseGroupedExpression() orelse return null,
.if_ => try self.parseIfExpression(),
.function => try self.parseFunctionLiteral(),
.lbracket => try self.parseArrayLiteral(),
.lbrace => try self.parseHashLiteral(),
else => {
try self.errors.append(
self.allocator,
try std.fmt.allocPrint(self.allocator, "no prefix parse function for {t}", .{self.cur_token.type}),
);
return null;
},
};
// Half 2: keep absorbing infix operators while they bind tighter than we do.
while (self.peek_token.type != .semicolon and
@intFromEnum(precedence) < @intFromEnum(self.peekPrecedence()))
{
switch (self.peek_token.type) {
.plus, .minus, .slash, .asterisk, .eq, .not_eq, .lt, .gt => {
self.nextToken();
left = try self.parseInfixExpression(left);
},
.lparen => {
self.nextToken();
left = try self.parseCallExpression(left);
},
.lbracket => {
self.nextToken();
left = try self.parseIndexExpression(left);
},
else => return left,
}
}
return left;
}
fn parsePrefixExpression(self: *Parser) Error!ast.Expression {
const operator = self.cur_token.literal;
self.nextToken();
const right = try self.parseExpression(.prefix) orelse
return error.ParseError;
const right_ptr = try self.allocator.create(ast.Expression);
right_ptr.* = right;
return .{ .prefix = .{ .operator = operator, .right = right_ptr } };
}
fn parseInfixExpression(self: *Parser, left: ast.Expression) Error!ast.Expression {
const operator = self.cur_token.literal;
const prec = self.curPrecedence();
self.nextToken();
const right = try self.parseExpression(prec) orelse
return error.ParseError;
const left_ptr = try self.allocator.create(ast.Expression);
left_ptr.* = left;
const right_ptr = try self.allocator.create(ast.Expression);
right_ptr.* = right;
return .{ .infix = .{
.left = left_ptr,
.operator = operator,
.right = right_ptr,
} };
}
fn parseGroupedExpression(self: *Parser) Error!?ast.Expression {
self.nextToken();
const expr = try self.parseExpression(.lowest);
if (!try self.expectPeek(.rparen)) return null;
return expr;
}
fn parseIfExpression(self: *Parser) Error!ast.Expression {
if (!try self.expectPeek(.lparen)) return error.ParseError;
self.nextToken();
const condition = try self.parseExpression(.lowest) orelse return error.ParseError;
const condition_ptr = try self.allocator.create(ast.Expression);
condition_ptr.* = condition;
if (!try self.expectPeek(.rparen)) return error.ParseError;
if (!try self.expectPeek(.lbrace)) return error.ParseError;
const consequence = try self.parseBlockStatement();
var alternative: ?ast.BlockStatement = null;
if (self.peek_token.type == .else_) {
self.nextToken();
if (!try self.expectPeek(.lbrace)) return error.ParseError;
alternative = try self.parseBlockStatement();
}
return .{ .if_expression = .{
.condition = condition_ptr,
.consequence = consequence,
.alternative = alternative,
} };
}
fn parseFunctionLiteral(self: *Parser) Error!ast.Expression {
if (!try self.expectPeek(.lparen)) return error.ParseError;
const parameters = try self.parseFunctionParameters();
if (!try self.expectPeek(.lbrace)) return error.ParseError;
const body = try self.parseBlockStatement();
return .{ .function_literal = .{
.parameters = parameters,
.body = body,
} };
}
fn parseFunctionParameters(self: *Parser) Error![]const ast.Identifier {
var params: std.ArrayList(ast.Identifier) = .empty;
if (self.peek_token.type == .rparen) {
self.nextToken();
return params.toOwnedSlice(self.allocator);
}
if (!try self.expectPeek(.ident)) return error.ParseError;
try params.append(self.allocator, .{ .value = self.cur_token.literal });
while (self.peek_token.type == .comma) {
self.nextToken(); // skip comma
if (!try self.expectPeek(.ident)) return error.ParseError;
try params.append(self.allocator, .{ .value = self.cur_token.literal });
}
if (!try self.expectPeek(.rparen)) return error.ParseError;
return params.toOwnedSlice(self.allocator);
}
fn parseCallExpression(self: *Parser, function: ast.Expression) Error!ast.Expression {
const func_ptr = try self.allocator.create(ast.Expression);
func_ptr.* = function;
const arguments = try self.parseExpressionList(.rparen);
return .{ .call = .{
.function = func_ptr,
.arguments = arguments,
} };
}
fn parseArrayLiteral(self: *Parser) Error!ast.Expression {
const elements = try self.parseExpressionList(.rbracket);
return .{ .array_literal = .{ .elements = elements } };
}
fn parseExpressionList(self: *Parser, end: token.TokenType) Error![]const ast.Expression {
var list: std.ArrayList(ast.Expression) = .empty;
if (self.peek_token.type == end) {
self.nextToken();
return list.toOwnedSlice(self.allocator);
}
self.nextToken();
try list.append(self.allocator, try self.parseExpression(.lowest) orelse return error.ParseError);
while (self.peek_token.type == .comma) {
self.nextToken(); // skip comma
self.nextToken(); // move to expression
try list.append(self.allocator, try self.parseExpression(.lowest) orelse return error.ParseError);
}
if (!try self.expectPeek(end)) return error.ParseError;
return list.toOwnedSlice(self.allocator);
}
fn parseIndexExpression(self: *Parser, left: ast.Expression) Error!ast.Expression {
self.nextToken();
const index = try self.parseExpression(.lowest) orelse return error.ParseError;
if (!try self.expectPeek(.rbracket)) return error.ParseError;
const left_ptr = try self.allocator.create(ast.Expression);
left_ptr.* = left;
const index_ptr = try self.allocator.create(ast.Expression);
index_ptr.* = index;
return .{ .index_expression = .{
.left = left_ptr,
.index = index_ptr,
} };
}
fn parseHashLiteral(self: *Parser) Error!ast.Expression {
var pairs: std.ArrayList(ast.HashPair) = .empty;
while (self.peek_token.type != .rbrace) {
self.nextToken();
const key = try self.parseExpression(.lowest) orelse return error.ParseError;
if (!try self.expectPeek(.colon)) return error.ParseError;
self.nextToken();
const value = try self.parseExpression(.lowest) orelse return error.ParseError;
try pairs.append(self.allocator, .{ .key = key, .value = value });
if (self.peek_token.type != .rbrace) {
if (!try self.expectPeek(.comma)) return error.ParseError;
}
}
if (!try self.expectPeek(.rbrace)) return error.ParseError;
return .{ .hash_literal = .{ .pairs = try pairs.toOwnedSlice(self.allocator) } };
}
};
Tests #
Create src/parser_test.zig. Two helpers do most of the work. parseProgram runs the lexer and parser and fails loudly if any errors were recorded, printing them so you can see what went wrong. parseExpressionString parses a one-statement program and gives you back the string form of the expression, which is how we check tree shapes.
const std = @import("std");
const Lexer = @import("lexer.zig").Lexer;
const Parser = @import("parser.zig").Parser;
const ast = @import("ast.zig");
fn parseProgram(allocator: std.mem.Allocator, input: []const u8) !ast.Program {
var l = Lexer.init(input);
var p = Parser.init(allocator, &l);
const program = try p.parseProgram();
if (p.errors.items.len > 0) {
for (p.errors.items) |msg| std.debug.print("parser error: {s}\n", .{msg});
return error.TestUnexpectedResult;
}
return program;
}
fn parseExpressionString(allocator: std.mem.Allocator, input: []const u8) ![]const u8 {
const program = try parseProgram(allocator, input);
try std.testing.expectEqual(@as(usize, 1), program.statements.len);
return program.statements[0].expression_statement.expression.string(allocator);
}
test "operator precedence parsing" {
const tests = [_]struct { input: []const u8, expected: []const u8 }{
.{ .input = "-a * b", .expected = "((-a) * b)" },
.{ .input = "!-a", .expected = "(!(-a))" },
.{ .input = "a + b + c", .expected = "((a + b) + c)" },
.{ .input = "a + b - c", .expected = "((a + b) - c)" },
.{ .input = "a * b * c", .expected = "((a * b) * c)" },
.{ .input = "a * b / c", .expected = "((a * b) / c)" },
.{ .input = "a + b / c", .expected = "(a + (b / c))" },
.{ .input = "a + b * c + d / e - f", .expected = "(((a + (b * c)) + (d / e)) - f)" },
.{ .input = "5 > 4 == 3 < 4", .expected = "((5 > 4) == (3 < 4))" },
.{ .input = "true", .expected = "true" },
.{ .input = "false", .expected = "false" },
.{ .input = "3 > 5 == false", .expected = "((3 > 5) == false)" },
.{ .input = "3 < 5 == true", .expected = "((3 < 5) == true)" },
.{ .input = "1 + (2 + 3) + 4", .expected = "((1 + (2 + 3)) + 4)" },
.{ .input = "(5 + 5) * 2", .expected = "((5 + 5) * 2)" },
.{ .input = "2 / (5 + 5)", .expected = "(2 / (5 + 5))" },
.{ .input = "-(5 + 5)", .expected = "(-(5 + 5))" },
.{ .input = "a + add(b * c) + d", .expected = "((a + add((b * c))) + d)" },
.{ .input = "add(a, b, 1, 2 * 3, 4 + 5, add(6, 7 * 8))", .expected = "add(a, b, 1, (2 * 3), (4 + 5), add(6, (7 * 8)))" },
.{ .input = "a * [1, 2, 3, 4][b * c] * d", .expected = "((a * ([1, 2, 3, 4][(b * c)])) * d)" },
.{ .input = "add(a * b[2], b[1], 2 * [1, 2][1])", .expected = "add((a * (b[2])), (b[1]), (2 * ([1, 2][1])))" },
};
for (tests) |tt| {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const result = try parseExpressionString(arena.allocator(), tt.input);
try std.testing.expectEqualStrings(tt.expected, result);
}
}
test "let statements" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const program = try parseProgram(arena.allocator(), "let x = 5; let y = true; let foobar = y;");
try std.testing.expectEqual(@as(usize, 3), program.statements.len);
const expected = [_]struct { name: []const u8, value: []const u8 }{
.{ .name = "x", .value = "5" },
.{ .name = "y", .value = "true" },
.{ .name = "foobar", .value = "y" },
};
for (expected, 0..) |tt, i| {
const stmt = program.statements[i].let_statement;
try std.testing.expectEqualStrings(tt.name, stmt.name);
try std.testing.expectEqualStrings(tt.value, try stmt.value.string(arena.allocator()));
}
}
test "return statements" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const program = try parseProgram(arena.allocator(), "return 5; return true; return add(1, 2);");
try std.testing.expectEqual(@as(usize, 3), program.statements.len);
const expected = [_][]const u8{ "5", "true", "add(1, 2)" };
for (expected, 0..) |value, i| {
const stmt = program.statements[i].return_statement;
try std.testing.expectEqualStrings(value, try stmt.value.string(arena.allocator()));
}
}
test "if expression" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
var program = try parseProgram(arena.allocator(), "if (x < y) { x } else { y }");
var ie = program.statements[0].expression_statement.expression.if_expression;
try std.testing.expectEqualStrings("(x < y)", try ie.condition.string(arena.allocator()));
try std.testing.expectEqual(@as(usize, 1), ie.consequence.statements.len);
try std.testing.expect(ie.alternative != null);
try std.testing.expectEqual(@as(usize, 1), ie.alternative.?.statements.len);
program = try parseProgram(arena.allocator(), "if (x < y) { x }");
ie = program.statements[0].expression_statement.expression.if_expression;
try std.testing.expect(ie.alternative == null);
}
test "function literal parsing" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const program = try parseProgram(arena.allocator(), "fn(x, y) { x + y; }");
const func = program.statements[0].expression_statement.expression.function_literal;
try std.testing.expectEqual(@as(usize, 2), func.parameters.len);
try std.testing.expectEqualStrings("x", func.parameters[0].value);
try std.testing.expectEqualStrings("y", func.parameters[1].value);
try std.testing.expectEqual(@as(usize, 1), func.body.statements.len);
const body = func.body.statements[0].expression_statement.expression;
try std.testing.expectEqualStrings("(x + y)", try body.string(arena.allocator()));
}
test "call expression parsing" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const program = try parseProgram(arena.allocator(), "add(1, 2 * 3, 4 + 5);");
const call = program.statements[0].expression_statement.expression.call;
try std.testing.expectEqualStrings("add", try call.function.string(arena.allocator()));
try std.testing.expectEqual(@as(usize, 3), call.arguments.len);
const expected = [_][]const u8{ "1", "(2 * 3)", "(4 + 5)" };
for (expected, 0..) |arg, i| {
try std.testing.expectEqualStrings(arg, try call.arguments[i].string(arena.allocator()));
}
}
test "strings arrays and hashes" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
const allocator = arena.allocator();
var program = try parseProgram(allocator, "\"hello world\"");
try std.testing.expectEqualStrings("hello world", program.statements[0].expression_statement.expression.string_literal.value);
program = try parseProgram(allocator, "[1, 2 * 2, 3 + 3]");
const array = program.statements[0].expression_statement.expression.array_literal;
try std.testing.expectEqual(@as(usize, 3), array.elements.len);
try std.testing.expectEqualStrings("(2 * 2)", try array.elements[1].string(allocator));
try std.testing.expectEqualStrings("(myArray[(1 + 1)])", try parseExpressionString(allocator, "myArray[1 + 1]"));
program = try parseProgram(allocator, "{\"one\": 1, \"two\": 2, \"three\": 3}");
const hash = program.statements[0].expression_statement.expression.hash_literal;
try std.testing.expectEqual(@as(usize, 3), hash.pairs.len);
try std.testing.expectEqualStrings("one", hash.pairs[0].key.string_literal.value);
try std.testing.expectEqualStrings("1", try hash.pairs[0].value.string(allocator));
program = try parseProgram(allocator, "{}");
try std.testing.expectEqual(@as(usize, 0), program.statements[0].expression_statement.expression.hash_literal.pairs.len);
}
test "parser errors" {
var arena = std.heap.ArenaAllocator.init(std.testing.allocator);
defer arena.deinit();
// a bad let statement gets recorded and skipped, parsing keeps going.
var l = Lexer.init("let x 5; let y = 10;");
var p = Parser.init(arena.allocator(), &l);
const program = try p.parseProgram();
try std.testing.expectEqual(@as(usize, 1), p.errors.items.len);
try std.testing.expectEqualStrings("expected next token to be assign, got int instead", p.errors.items[0]);
try std.testing.expectEqual(@as(usize, 2), program.statements.len); // the stray `5` and the good let
// a bad expression returns ParseError, the message is still in the list.
var l2 = Lexer.init("if (x");
var p2 = Parser.init(arena.allocator(), &l2);
try std.testing.expectError(error.ParseError, p2.parseProgram());
try std.testing.expectEqual(@as(usize, 1), p2.errors.items.len);
try std.testing.expectEqualStrings("expected next token to be rparen, got eof instead", p2.errors.items[0]);
}
Verify it works #
Make sure you’ve uncommented "src/parser_test.zig" in build.zig, then run zig build test. No output means all tests passed.
If the precedence test fails, the string it prints is your friend. Compare the parentheses you got against the ones you expected and you can usually spot which precedence number or which < is wrong.
What we built #
We have a parser that turns the token stream into a tree, with operator precedence handled correctly and useful error messages when the input isn’t valid Monkey. The things to carry forward:
- The parser only ever sees two tokens,
cur_tokenandpeek_token, and pulls them from the lexer on demand. - Statements are handled by plain recursive descent: look at the current token, call the function for that kind of statement.
- Expressions are handled by Pratt parsing. Build the left side from the current token, then absorb infix operators for as long as they bind tighter than the precedence you were called with. The tree shape is a direct consequence of the precedence numbers and the
<in the loop. - Calls and indexing are infix operators on their left operand. A function name is just an identifier.
- The AST is allocated from an arena and freed all at once. We never free a node on its own.
The tree still doesn’t do anything though. In chapter 3 we build the evaluator, which walks the tree and produces values.