src/Parser.zig

   1 const std = @import("std");
   2 const ArenaAllocator = std.heap.ArenaAllocator;
   3 const Allocator = std.mem.Allocator;
   4 const ArrayList = std.ArrayList;
   5 const Token = @import("Token.zig");
   6 const Parser = @This();
   7 const Stmt = @import("stmt.zig").Stmt;
   8 const Expr = @import("expr.zig").Expr;
   9 const TokenType = @import("token_type.zig").TokenType;
  10 const lox = @import("main.zig");
  11
  12 arena: ArenaAllocator,
  13 allocator: Allocator,
  14 tokens: []const Token,
  15 current: u32 = 0,
  16
  17 pub fn init(child_allocator: Allocator, tokens: []const Token) !Parser {
  18     return .{
  19         .arena = .init(child_allocator),
  20         .allocator = undefined,
  21         .tokens = tokens,
  22     };
  23 }
  24
  25 pub fn deinit(self: *Parser) void {
  26     self.arena.deinit();
  27 }
  28
  29 pub fn parse(self: *Parser) ![]const *const Stmt {
  30     self.allocator = self.arena.allocator();
  31
  32     var statements: ArrayList(*const Stmt) = .empty;
  33
  34     while (!self.isAtEnd()) {
  35         try statements.append(self.allocator, try self.statement());
  36     }
  37
  38     return statements.toOwnedSlice(self.allocator);
  39 }
  40
  41 fn expression(self: *Parser) (Allocator.Error || std.Io.Writer.Error || error{ParseError})!*const Expr {
  42     return self.equality();
  43 }
  44
  45 fn statement(self: *Parser) !*const Stmt {
  46     if (self.match(&.{.print})) {
  47         return self.printStatement();
  48     }
  49
  50     return self.expressionStatement();
  51 }
  52
  53 fn printStatement(self: *Parser) !*const Stmt {
  54     const value = try self.expression();
  55     _ = try self.consume(.semicolon, "Expect ';' after value.");
  56     const stmt = try self.allocator.create(Stmt);
  57     stmt.* = .{ .print = .init(value) };
  58     return stmt;
  59 }
  60
  61 fn expressionStatement(self: *Parser) !*const Stmt {
  62     const expr = try self.expression();
  63     _ = try self.consume(.semicolon, "Expect ';' after expression.");
  64     const stmt = try self.allocator.create(Stmt);
  65     stmt.* = .{ .expression = .init(expr) };
  66     return stmt;
  67 }
  68
  69 fn equality(self: *Parser) !*const Expr {
  70     var expr = try self.comparison();
  71
  72     while (self.match(&.{ .bang_equal, .equal_equal })) {
  73         const operator = self.previous();
  74         const right = try self.comparison();
  75         const binary = try self.allocator.create(Expr);
  76         binary.* = .{ .binary = .init(expr, operator, right) };
  77         expr = binary;
  78     }
  79
  80     return expr;
  81 }
  82
  83 fn comparison(self: *Parser) !*const Expr {
  84     var expr = try self.term();
  85
  86     while (self.match(&.{ .greater, .greater_equal, .less, .less_equal })) {
  87         const operator = self.previous();
  88         const right = try self.term();
  89         const binary = try self.allocator.create(Expr);
  90         binary.* = .{ .binary = .init(expr, operator, right) };
  91         expr = binary;
  92     }
  93
  94     return expr;
  95 }
  96
  97 fn term(self: *Parser) !*const Expr {
  98     var expr = try self.factor();
  99
 100     while (self.match(&.{ .plus, .minus })) {
 101         const operator = self.previous();
 102         const right = try self.factor();
 103         const binary = try self.allocator.create(Expr);
 104         binary.* = .{ .binary = .init(expr, operator, right) };
 105         expr = binary;
 106     }
 107
 108     return expr;
 109 }
 110
 111 fn factor(self: *Parser) !*const Expr {
 112     var expr = try self.unary();
 113
 114     while (self.match(&.{ .slash, .star })) {
 115         const operator = self.previous();
 116         const right = try self.unary();
 117         const binary = try self.allocator.create(Expr);
 118         binary.* = .{ .binary = .init(expr, operator, right) };
 119         expr = binary;
 120     }
 121
 122     return expr;
 123 }
 124
 125 fn unary(self: *Parser) !*const Expr {
 126     if (self.match(&.{ .bang, .minus })) {
 127         const operator = self.previous();
 128         const right = try self.unary();
 129         const expr = try self.allocator.create(Expr);
 130         expr.* = .{ .unary = .init(operator, right) };
 131         return expr;
 132     }
 133
 134     return self.primary();
 135 }
 136
 137 fn primary(self: *Parser) !*const Expr {
 138     if (self.match(&.{.false})) {
 139         const expr = try self.allocator.create(Expr);
 140         expr.* = .{ .literal = .init(.{ .boolean = false }) };
 141         return expr;
 142     }
 143
 144     if (self.match(&.{.true})) {
 145         const expr = try self.allocator.create(Expr);
 146         expr.* = .{ .literal = .init(.{ .boolean = true }) };
 147         return expr;
 148     }
 149
 150     if (self.match(&.{.nil})) {
 151         const expr = try self.allocator.create(Expr);
 152         expr.* = .{ .literal = .init(.{ .nil = {} }) };
 153         return expr;
 154     }
 155
 156     if (self.match(&.{ .number, .string })) {
 157         const expr = try self.allocator.create(Expr);
 158         expr.* = .{ .literal = .init(self.previous().literal.?) };
 159         return expr;
 160     }
 161
 162     if (self.match(&.{.left_paren})) {
 163         const expr = try self.expression();
 164         _ = try self.consume(.right_paren, "Expect ')' after expression.");
 165         const grouping = try self.allocator.create(Expr);
 166         grouping.* = .{ .grouping = .init(expr) };
 167         return grouping;
 168     }
 169
 170     try self.err(self.peek(), "Expect expression.");
 171 }
 172
 173 fn match(self: *Parser, types: []const TokenType) bool {
 174     for (types) |@"type"| {
 175         if (self.check(@"type")) {
 176             _ = self.advance();
 177             return true;
 178         }
 179     }
 180
 181     return false;
 182 }
 183
 184 fn consume(self: *Parser, @"type": TokenType, message: []const u8) !Token {
 185     if (self.check(@"type")) return self.advance();
 186
 187     try self.err(self.peek(), message);
 188 }
 189
 190 fn check(self: *Parser, @"type": TokenType) bool {
 191     if (self.isAtEnd()) return false;
 192     return self.peek().type == @"type";
 193 }
 194
 195 fn advance(self: *Parser) Token {
 196     if (!self.isAtEnd()) self.current += 1;
 197     return self.previous();
 198 }
 199
 200 fn isAtEnd(self: *Parser) bool {
 201     return self.peek().type == .eof;
 202 }
 203
 204 fn peek(self: *Parser) Token {
 205     return self.tokens[self.current];
 206 }
 207
 208 fn previous(self: *Parser) Token {
 209     return self.tokens[self.current - 1];
 210 }
 211
 212 fn err(self: *Parser, token: Token, message: []const u8) !noreturn {
 213     try lox.parseError(self.allocator, token, message);
 214     return error.ParseError;
 215 }
 216
 217 fn synchronize(self: *Parser) !void {
 218     _ = self.advance();
 219
 220     while (!self.isAtEnd()) {
 221         if (self.previous().type == .semicolon) return;
 222
 223         switch (self.peek().type) {
 224             .class,
 225             .fun,
 226             .@"var",
 227             .@"for",
 228             .@"if",
 229             .@"while",
 230             .print,
 231             .@"return",
 232             => return,
 233         }
 234
 235         _ = self.advance();
 236     }
 237 }