src/Parser.zig

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