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)
We’re going to walk this tree to evaluate the instructions with a Pratt parser, which handles prefix (at the start of an expression) and infix (between two expressions) expressions with different precedence levels.
So 5 + 3 * 4 parses as (5 + (3 * 4)) because * has higher precedence than +. The parser we’ll write will build this tree using a relatively simple concept, every token type has a numeric precedence level, and the parser uses that number to decide how to consume tokens. The higher the number the tighter the binding (meaning that it refuses to let go). I’ll explain in more detail when we write the function to parse expressions.
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 #
This is the simplest Monkey expression, 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 pointers to other expressions and form the tree.
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.
Collection literals #
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.
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))".
pub fn writeTo(self: Expression, writer: anytype) !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 buf: std.ArrayList(u8) = .empty;
try self.writeTo(buf.writer(allocator));
return buf.toOwnedSlice(allocator);
}
};
Statements #
Monkey programs are a list of statements, they’re the top-level building blocks. Monkey only has three kinds of statements let bindings, return statements, and expression statements (an expression used as a statement).
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 ArrayLiteral = struct { elements: []const Expression };
pub const HashLiteral = struct { pairs: []const HashPair };
pub const IfExpression = struct {
condition: *const Expression,
consequence: BlockStatement,
alternative: ?BlockStatement,
};
pub const InfixExpression = struct {
left: *const Expression,
operator: []const u8,
right: *const Expression,
};
pub const PrefixExpression = struct {
operator: []const u8,
right: *const Expression,
};
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 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: anytype) !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 buf: std.ArrayList(u8) = .empty;
try self.writeTo(buf.writer(allocator));
return buf.toOwnedSlice(allocator);
}
};
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.
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,
};
}
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.
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 {}, got {} instead",
.{ t, self.peek_token.type },
);
try self.errors.append(self.allocator, msg);
}
The expectPeek helper is how we assert the next token is valid Monkey. It reports problems like a missing ) or }.
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(),
};
}
Parsing let and return
#
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 .{ .return_statement = .{ .value = .{ .integer_literal = .{ .value = 0 } } } };
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 where we dispatch the prefix handler and loop through infix handlers.
fn parseExpression(self: *Parser, precedence: Precedence) Error!?ast.Expression {
// Step 1: prefix dispatch
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 {}", .{self.cur_token.type}),
);
return null;
},
};
// Step 2: infix loop -- keep going while the next token binds tighter
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;
}
Prefix and infix expression builders #
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 #
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);
}
self.nextToken();
try params.append(self.allocator, .{ .value = self.cur_token.literal });
while (self.peek_token.type == .comma) {
self.nextToken(); // skip comma
self.nextToken(); // move to param
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 #
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,
sum = 4,
product = 5,
prefix = 6,
call = 7,
index = 8,
};
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 {}, got {} 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 .{ .return_statement = .{ .value = .{ .integer_literal = .{ .value = 0 } } } };
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 {
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 {}", .{self.cur_token.type}),
);
return null;
},
};
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);
}
self.nextToken();
try params.append(self.allocator, .{ .value = self.cur_token.literal });
while (self.peek_token.type == .comma) {
self.nextToken(); // skip comma
self.nextToken(); // move to param
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.
const std = @import("std");
const Parser = @import("parser.zig").Parser;
test "operator precedence parsing" {
const allocator = std.testing.allocator;
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 * [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(allocator);
defer arena.deinit();
var l = @import("lexer.zig").Lexer.init(tt.input);
var p = Parser.init(arena.allocator(), &l);
const program = try p.parseProgram();
try std.testing.expectEqual(@as(usize, 0), p.errors.items.len);
try std.testing.expectEqual(@as(usize, 1), program.statements.len);
const expr = program.statements[0].expression_statement.expression;
const result = try expr.string(arena.allocator());
try std.testing.expectEqualStrings(tt.expected, result);
}
}
test "let statements" {
const allocator = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(allocator);
defer arena.deinit();
const input = "let x = 5; let y = true; let foobar = y;";
var l = @import("lexer.zig").Lexer.init(input);
var p = Parser.init(arena.allocator(), &l);
const program = try p.parseProgram();
try std.testing.expectEqual(@as(usize, 0), p.errors.items.len);
try std.testing.expectEqual(@as(usize, 3), program.statements.len);
const expected_names = [_][]const u8{ "x", "y", "foobar" };
for (expected_names, 0..) |name, i| {
const stmt = program.statements[i];
try std.testing.expectEqualStrings(name, stmt.let_statement.name);
}
}
test "function literal parsing" {
const allocator = std.testing.allocator;
var arena = std.heap.ArenaAllocator.init(allocator);
defer arena.deinit();
const input = "fn(x, y) { x + y; }";
var l = @import("lexer.zig").Lexer.init(input);
var p = Parser.init(arena.allocator(), &l);
const program = try p.parseProgram();
try std.testing.expectEqual(@as(usize, 0), p.errors.items.len);
try std.testing.expectEqual(@as(usize, 1), program.statements.len);
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);
}
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.
In chapter 3 we build the evaluator, a tree-walking interpreter that traverses the AST and produces values.