From: Ayo Reis <hey@ayoreis.com>
Date: Wed, 18 Feb 2026 16:33:34 +0000 (+0000)
Subject: Implement parser
X-Git-Url: https://git.ayoreis.com/zlox.git/commitdiff_plain/6d286699938880d7a1482be65e5e4771788c6b6f?hp=abb953787c9ce7a2eb0459ecbf7b1b9a7000b0c1

Implement parser
---

diff --git a/src/Parser.zig b/src/Parser.zig
new file mode 100644
index 0000000..a584c3f
--- /dev/null
+++ b/src/Parser.zig
@@ -0,0 +1,208 @@
+const std = @import("std");
+const ArenaAllocator = std.heap.ArenaAllocator;
+const Allocator = std.mem.Allocator;
+const Token = @import("Token.zig");
+const Parser = @This();
+const Expr = @import("expr.zig").Expr;
+const TokenType = @import("token_type.zig").TokenType;
+const lox = @import("main.zig");
+
+arena: ArenaAllocator,
+allocator: Allocator,
+tokens: []const Token,
+current: u32 = 0,
+
+pub fn init(child_allocator: Allocator, tokens: []const Token) !Parser {
+    return .{
+        .arena = .init(child_allocator),
+        .allocator = undefined,
+        .tokens = tokens,
+    };
+}
+
+pub fn deinit(self: *Parser) void {
+    self.arena.deinit();
+}
+
+pub fn parse(self: *Parser) !?*Expr {
+    self.allocator = self.arena.allocator();
+
+    return self.expression() catch |err| switch (err) {
+        error.ParseError => return null,
+        else => return err,
+    };
+}
+
+fn expression(self: *Parser) (Allocator.Error || std.Io.Writer.Error || error{ParseError})!*Expr {
+    return self.equality();
+}
+
+fn equality(self: *Parser) !*Expr {
+    var expr = try self.comparison();
+
+    while (self.match(&.{ .bang_equal, .equal_equal })) {
+        const operator = self.previous();
+        const right = try self.comparison();
+        const binary = try self.allocator.create(Expr);
+        binary.* = .{ .binary = .init(expr, operator, right) };
+        expr = binary;
+    }
+
+    return expr;
+}
+
+fn comparison(self: *Parser) !*Expr {
+    var expr = try self.term();
+
+    while (self.match(&.{ .greater, .greater_equal, .less, .less_equal })) {
+        const operator = self.previous();
+        const right = try self.term();
+        const binary = try self.allocator.create(Expr);
+        binary.* = .{ .binary = .init(expr, operator, right) };
+        expr = binary;
+    }
+
+    return expr;
+}
+
+fn term(self: *Parser) !*Expr {
+    var expr = try self.factor();
+
+    while (self.match(&.{ .plus, .minus })) {
+        const operator = self.previous();
+        const right = try self.factor();
+        const binary = try self.allocator.create(Expr);
+        binary.* = .{ .binary = .init(expr, operator, right) };
+        expr = binary;
+    }
+
+    return expr;
+}
+
+fn factor(self: *Parser) !*Expr {
+    var expr = try self.unary();
+
+    while (self.match(&.{ .slash, .star })) {
+        const operator = self.previous();
+        const right = try self.unary();
+        const binary = try self.allocator.create(Expr);
+        binary.* = .{ .binary = .init(expr, operator, right) };
+        expr = binary;
+    }
+
+    return expr;
+}
+
+fn unary(self: *Parser) !*Expr {
+    if (self.match(&.{ .bang, .minus })) {
+        const operator = self.previous();
+        const right = try self.unary();
+        const expr = try self.allocator.create(Expr);
+        expr.* = .{ .unary = .init(operator, right) };
+        return expr;
+    }
+
+    return try self.primary();
+}
+
+fn primary(self: *Parser) !*Expr {
+    if (self.match(&.{.false})) {
+        const expr = try self.allocator.create(Expr);
+        expr.* = .{ .literal = .init(.{ .boolean = false }) };
+        return expr;
+    }
+
+    if (self.match(&.{.true})) {
+        const expr = try self.allocator.create(Expr);
+        expr.* = .{ .literal = .init(.{ .boolean = true }) };
+        return expr;
+    }
+
+    if (self.match(&.{.nil})) {
+        const expr = try self.allocator.create(Expr);
+        expr.* = .{ .literal = .init(.{ .nil = {} }) };
+        return expr;
+    }
+
+    if (self.match(&.{ .number, .string })) {
+        const expr = try self.allocator.create(Expr);
+        expr.* = .{ .literal = .init(self.previous().literal.?) };
+        return expr;
+    }
+
+    if (self.match(&.{.left_paren})) {
+        const expr = try self.expression();
+        _ = try self.consume(.right_paren, "Expect ')' after expression.");
+        const grouping = try self.allocator.create(Expr);
+        grouping.* = .{ .grouping = .init(expr) };
+        return grouping;
+    }
+
+    try self.@"error"(self.peek(), "Expect expression.");
+}
+
+fn match(self: *Parser, types: []const TokenType) bool {
+    for (types) |@"type"| {
+        if (self.check(@"type")) {
+            _ = self.advance();
+            return true;
+        }
+    }
+
+    return false;
+}
+
+fn consume(self: *Parser, @"type": TokenType, message: []const u8) !Token {
+    if (self.check(@"type")) return self.advance();
+
+    try self.@"error"(self.peek(), message);
+}
+
+fn check(self: *Parser, @"type": TokenType) bool {
+    if (self.isAtEnd()) return false;
+    return self.peek().type == @"type";
+}
+
+fn advance(self: *Parser) Token {
+    if (!self.isAtEnd()) self.current += 1;
+    return self.previous();
+}
+
+fn isAtEnd(self: *Parser) bool {
+    return self.peek().type == .eof;
+}
+
+fn peek(self: *Parser) Token {
+    return self.tokens[self.current];
+}
+
+fn previous(self: *Parser) Token {
+    return self.tokens[self.current - 1];
+}
+
+fn @"error"(self: *Parser, token: Token, message: []const u8) !noreturn {
+    try lox.parse_error(self.allocator, token, message);
+    return error.ParseError;
+}
+
+fn synchronize(self: *Parser) !void {
+    _ = self.advance();
+
+    while (!self.isAtEnd()) {
+        if (self.previous().type == .semicolon) return;
+
+        switch (self.peek().type) {
+            .class,
+            .fun,
+            .@"var",
+            .@"for",
+            .@"if",
+            .@"while",
+            .print,
+            .@"return",
+            => return,
+        }
+
+        _ = self.advance();
+    }
+}
diff --git a/src/Token.zig b/src/Token.zig
index 96f8378..596b1ba 100644
--- a/src/Token.zig
+++ b/src/Token.zig
@@ -7,9 +7,11 @@ lexeme: []const u8,
 literal: ?Literal,
 line: u32,
 
-pub const Literal = union {
+pub const Literal = union(enum) {
     string: []const u8,
     number: f64,
+    boolean: bool,
+    nil: void,
 };
 
 pub fn init(@"type": TokenType, lexeme: []const u8, literal: ?Literal, line: u32) Token {
diff --git a/src/ast_printer.zig b/src/ast_printer.zig
new file mode 100644
index 0000000..21c8702
--- /dev/null
+++ b/src/ast_printer.zig
@@ -0,0 +1,34 @@
+const std = @import("std");
+const Allocator = std.mem.Allocator;
+const Expr = @import("expr.zig").Expr;
+const Token = @import("Token.zig");
+
+pub fn print(allocator: Allocator, expr: *const Expr) Allocator.Error![]const u8 {
+    return switch (expr.*) {
+        .binary => |binary| try parenthesize(allocator, binary.operator.lexeme, &.{ binary.left, binary.right }),
+        .grouping => |grouping| try parenthesize(allocator, "group", &.{grouping.expression}),
+        .literal => |literal| switch (literal.value) {
+            .nil => "nil",
+            .boolean => |boolean| if (boolean) "true" else "false",
+            .string => |string| string,
+            .number => |number| try std.fmt.allocPrint(allocator, "{}", .{number}),
+        },
+        .unary => |unary| try parenthesize(allocator, unary.operator.lexeme, &.{unary.right}),
+    };
+}
+
+fn parenthesize(allocator: Allocator, name: []const u8, exprs: []const *const Expr) ![]const u8 {
+    var builder: std.ArrayList(u8) = .empty;
+
+    try builder.append(allocator, '(');
+    try builder.appendSlice(allocator, name);
+    for (exprs) |expr| {
+        try builder.append(allocator, ' ');
+        const printed = try print(allocator, expr);
+        defer allocator.free(printed);
+        try builder.appendSlice(allocator, printed);
+    }
+    try builder.append(allocator, ')');
+
+    return try builder.toOwnedSlice(allocator);
+}
diff --git a/src/expr.zig b/src/expr.zig
new file mode 100644
index 0000000..e862131
--- /dev/null
+++ b/src/expr.zig
@@ -0,0 +1,54 @@
+const Token = @import("Token.zig");
+
+pub const Expr = union(enum) {
+    binary: Binary,
+    grouping: Grouping,
+    literal: Literal,
+    unary: Unary,
+
+    const Binary = struct {
+        left: *const Expr,
+        operator: Token,
+        right: *const Expr,
+
+        pub fn init(left: *const Expr, operator: Token, right: *const Expr) Binary {
+            return .{
+                .left = left,
+                .operator = operator,
+                .right = right,
+            };
+        }
+    };
+
+    const Grouping = struct {
+        expression: *const Expr,
+
+        pub fn init(expression: *const Expr) Grouping {
+            return .{
+                .expression = expression,
+            };
+        }
+    };
+
+    const Literal = struct {
+        value: Token.Literal,
+
+        pub fn init(value: Token.Literal) Literal {
+            return .{
+                .value = value,
+            };
+        }
+    };
+
+    const Unary = struct {
+        operator: Token,
+        right: *const Expr,
+
+        pub fn init(operator: Token, right: *const Expr) Unary {
+            return Unary{
+                .operator = operator,
+                .right = right,
+            };
+        }
+    };
+};
diff --git a/src/main.zig b/src/main.zig
index 5905114..0e41f10 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -1,6 +1,9 @@
 const std = @import("std");
 const Allocator = std.mem.Allocator;
 const Scanner = @import("Scanner.zig");
+const Token = @import("Token.zig");
+const Parser = @import("Parser.zig");
+const ast_printer = @import("ast_printer.zig");
 
 var hadError = false;
 
@@ -56,11 +59,16 @@ fn run(allocator: Allocator, source: []const u8) !void {
     var scanner = Scanner.init(allocator, source);
     const tokens = try scanner.scanTokens();
     defer allocator.free(tokens);
+    var parser = try Parser.init(allocator, tokens);
+    defer parser.deinit();
+    const expression = try parser.parse();
 
-    // For now, just print the tokens.
-    for (tokens) |token| {
-        std.debug.print("{f}\n", .{token});
-    }
+    // Stop if there was a syntax error.
+    if (hadError) return;
+
+    const printed = try ast_printer.print(allocator, expression.?);
+    defer allocator.free(printed);
+    std.debug.print("{s}\n", .{printed});
 }
 
 pub fn @"error"(line: u32, message: []const u8) !void {
@@ -76,3 +84,11 @@ fn report(line: u32, where: []const u8, message: []const u8) !void {
     try stderr.flush();
     hadError = true;
 }
+
+pub fn parse_error(allocator: Allocator, token: Token, message: []const u8) !void {
+    if (token.type == .eof) {
+        try report(token.line, " at end", message);
+    } else {
+        try report(token.line, try std.fmt.allocPrint(allocator, " at '{s}'", .{token.lexeme}), message);
+    }
+}