Implement parser

diff --git a/src/Parser.zig b/src/Parser.zig
new file mode 100644 (file)
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 96f83784835e5abe25555d7215d48f76867ad3fb..596b1baefc7d8052d306c75a2dbf7433ca745360 100644 (file)
--- a/src/Token.zig
+++ b/src/Token.zig
@@ -7,9 +7,11 @@ lexeme: []const u8,
 literal: ?Literal,
 line: u32,
 
 literal: ?Literal,
 line: u32,
 

-pub const Literal = union {
+pub const Literal = union(enum) {

     string: []const u8,
     number: f64,
     string: []const u8,
     number: f64,

+    boolean: bool,
+    nil: void,

 };
 
 pub fn init(@"type": TokenType, lexeme: []const u8, literal: ?Literal, line: u32) Token {
 };
 
 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 (file)
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 (file)
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 590511401fe84de62c615f9d2c73cf4fe57393eb..0e41f10eef16372fddbe6e825628bd0146a8f167 100644 (file)
--- 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 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;
 
 
 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 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 {
 }
 
 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;
 }
     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);
+    }
+}