commit e065976bc7633261152b211d79f6f94d232e33f5
parent bd613c13f14151295f4d05f1d2e74b3fdd38dd8b
Author: Ashymad <szymon.mikulicz@posteo.net>
Date: Wed, 6 Mar 2024 23:37:28 +0100
Compiling
Diffstat:
7 files changed, 330 insertions(+), 40 deletions(-)
diff --git a/zlox/.gitignore b/zlox/.gitignore
@@ -1,2 +1,5 @@
zig-cache/
zig-out/
+.cache/
+.envrc
+.tool-versions
diff --git a/zlox/src/chunk.zig b/zlox/src/chunk.zig
@@ -13,26 +13,27 @@ pub const OP = enum(u8) {
DIVIDE,
};
+pub const ChunkError = error{OutOfMemory};
+
pub const Chunk = struct {
- pub fn init(allocator: std.mem.Allocator) !@This() {
+ pub fn init(allocator: std.mem.Allocator) ChunkError!@This() {
return @This(){
.code = try array.Array(u8, usize, 8).init(allocator),
.constants = try ValueArray.init(allocator),
- .lines = try array.RLEArray(u32, 8).init(allocator),
+ .lines = try array.RLEArray(i32, 8).init(allocator),
};
}
- pub fn write(self: *@This(), byte: u8, line: u32) !void {
+ pub fn write(self: *@This(), byte: u8, line: i32) ChunkError!void {
try self.code.add(byte);
try self.lines.add(line);
}
- pub fn writeOP(self: *@This(), op: OP, line: u32) !void {
- try self.code.add(@intFromEnum(op));
- try self.lines.add(line);
+ pub fn writeOP(self: *@This(), op: OP, line: i32) ChunkError!void {
+ try self.write(@intFromEnum(op), line);
}
- pub fn addConstant(self: *@This(), val: value.Value) !u8 {
+ pub fn addConstant(self: *@This(), val: value.Value) ChunkError!u8 {
try self.constants.add(val);
return self.constants.len - 1;
}
@@ -45,5 +46,5 @@ pub const Chunk = struct {
code: array.Array(u8, usize, 8),
constants: ValueArray,
- lines: array.RLEArray(u32, 8),
+ lines: array.RLEArray(i32, 8),
};
diff --git a/zlox/src/compiler.zig b/zlox/src/compiler.zig
@@ -1,23 +1,269 @@
const std = @import("std");
const scanner = @import("scanner.zig");
+const chunk = @import("chunk.zig");
+const value = @import("value.zig");
+const debug = @import("debug.zig");
-pub const CompilerError = scanner.ScannerError;
+pub const CompilerError = scanner.ScannerError || chunk.ChunkError || value.ParseValueError || error{ UnexpectedToken, NotAnExpression };
-pub fn compile(source: []const u8) !void {
- var Scanner = try scanner.Scanner.init(source);
+const Precedence = enum {
+ NONE,
+ ASSIGNMENT, // =
+ OR, // or
+ AND, // and
+ EQUALITY, // == !=
+ COMPARISON, // < > <= >=
+ TERM, // + -
+ FACTOR, // * /
+ UNARY, // ! -
+ CALL, // . ()
+ PRIMARY,
- var line: i32 = -1;
+ pub fn inc(self: @This()) @This() {
+ return @enumFromInt(@intFromEnum(self) + 1);
+ }
+
+ pub fn lessOrEq(self: @This(), rhs: @This()) bool {
+ return @intFromEnum(self) <= @intFromEnum(rhs);
+ }
+};
+
+pub const Compiler = struct {
+ current: scanner.Token,
+ previous: scanner.Token,
+ scanner: scanner.Scanner,
+ lastError: CompilerError,
+ hadError: bool,
+ panicMode: bool,
+ compilingChunk: *chunk.Chunk,
+
+ const ParseFn = *const fn (*@This()) void;
+
+ const ParseRule = struct { prefix: ?ParseFn, infix: ?ParseFn, precedence: Precedence };
+
+ const rules = init: {
+ var new: [@typeInfo(scanner.TokenType).Enum.fields.len]ParseRule = undefined;
+ for (&new, 0..) |*v, i| {
+ const tok: scanner.TokenType = @enumFromInt(i);
+ const T = scanner.TokenType;
+ v.* = switch (tok) {
+ // zig fmt: off
+ T.LEFT_PAREN => ParseRule{ .prefix = @This().grouping, .infix = null, .precedence = Precedence.NONE },
+ T.RIGHT_PAREN => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.LEFT_BRACE => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.RIGHT_BRACE => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.COMMA => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.DOT => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.MINUS => ParseRule{ .prefix = @This().unary, .infix = @This().binary, .precedence = Precedence.TERM },
+ T.PLUS => ParseRule{ .prefix = null, .infix = @This().binary, .precedence = Precedence.TERM },
+ T.SEMICOLON => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.SLASH => ParseRule{ .prefix = null, .infix = @This().binary, .precedence = Precedence.FACTOR },
+ T.STAR => ParseRule{ .prefix = null, .infix = @This().binary, .precedence = Precedence.FACTOR },
+ T.BANG => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.BANG_EQUAL => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.EQUAL => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.EQUAL_EQUAL => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.GREATER => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.GREATER_EQUAL => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.LESS => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.LESS_EQUAL => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.IDENTIFIER => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.STRING => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.NUMBER => ParseRule{ .prefix = @This().number, .infix = null, .precedence = Precedence.NONE },
+ T.AND => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.CLASS => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.ELSE => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.FALSE => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.FOR => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.FUN => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.IF => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.NIL => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.OR => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.PRINT => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.RETURN => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.SUPER => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.THIS => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.TRUE => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.VAR => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.WHILE => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ T.EOF => ParseRule{ .prefix = null, .infix = null, .precedence = Precedence.NONE },
+ // zig fmt: on
+ };
+ }
+ break :init new;
+ };
+
+ fn getRule(tok: scanner.TokenType) *const ParseRule {
+ return &Compiler.rules[@intFromEnum(tok)];
+ }
+
+ fn advance(self: *@This()) void {
+ self.previous = self.current;
+
+ while (true) {
+ self.current = self.scanner.scanToken();
+
+ if (self.current.type) |_| {
+ break;
+ } else |err| {
+ self.lastError = err;
+ self.errorAtCurrent(scanner.ScannerErrorString(err));
+ }
+ }
+ }
+
+ fn currentChunk(self: *@This()) *chunk.Chunk {
+ return self.compilingChunk;
+ }
+
+ fn emitByte(self: *@This(), byte: u8) void {
+ self.currentChunk().write(byte, self.previous.line) catch |err| {
+ self.lastError = err;
+ self.errorAtCurrent("Out of Memory");
+ };
+ }
+
+ fn emitOP(self: *@This(), op: chunk.OP) void {
+ self.currentChunk().writeOP(op, self.previous.line) catch |err| {
+ self.lastError = err;
+ self.errorAtCurrent("Out of Memory");
+ };
+ }
+
+ fn emit(self: *@This(), op: chunk.OP, byte: u8) void {
+ self.emitOP(op);
+ self.emitByte(byte);
+ }
+
+ fn endCompiler(self: *@This()) void {
+ self.emitReturn();
+ if (!self.hadError) {
+ debug.disassembleChunk(self.currentChunk().*, "code") catch {
+ std.debug.print("Unable to disassemble chunk\n", .{});
+ };
+ }
+ }
+
+ fn emitReturn(self: *@This()) void {
+ self.emitOP(chunk.OP.RETURN);
+ }
+
+ fn errorAtCurrent(self: *@This(), message: []const u8) void {
+ self.errorAt(self.current, message);
+ }
- while (true) {
- const token = try Scanner.scanToken();
- if (token.line != line) {
- std.debug.print("{d:4} ", .{token.line});
- line = token.line;
+ fn errorAtPrevious(self: *@This(), message: []const u8) void {
+ self.errorAt(self.previous, message);
+ }
+
+ fn expression(self: *@This()) void {
+ self.parsePrecedence(Precedence.ASSIGNMENT);
+ }
+
+ fn parsePrecedence(self: *@This(), precedence: Precedence) void {
+ self.advance();
+ if (getRule(self.previous.type catch unreachable).prefix) |prefixRule| {
+ prefixRule(self);
} else {
- std.debug.print(" | ", .{});
+ self.lastError = CompilerError.NotAnExpression;
+ self.errorAtPrevious("Expect expression.");
+ return;
}
- std.debug.print("{s:15} '{s}'\n", .{ @tagName(token.type), token.lexeme });
- if (token.type == scanner.TokenType.EOF) break;
+ while (precedence.lessOrEq(getRule(self.current.type catch unreachable).precedence)) {
+ self.advance();
+ if (getRule(self.previous.type catch unreachable).infix) |infixRule| {
+ infixRule(self);
+ } else {
+ self.lastError = CompilerError.NotAnExpression;
+ self.errorAtPrevious("Expect expression.");
+ return;
+ }
+ }
+ }
+
+ fn errorAt(self: *@This(), token: scanner.Token, message: []const u8) void {
+ if (self.panicMode) return;
+ self.panicMode = true;
+ std.debug.print("[{d}:{d}] Error", .{ token.line, token.column });
+ if (token.type) |tpe| {
+ if (tpe == scanner.TokenType.EOF) {
+ std.debug.print(" at end", .{});
+ } else {
+ std.debug.print(" at {s}", .{token.lexeme});
+ }
+ } else |_| {}
+ std.debug.print(": {s}\n", .{message});
+ self.hadError = true;
+ }
+
+ fn consume(self: *@This(), tok: scanner.TokenType, message: []const u8) void {
+ if (self.current.type) |tpe| {
+ if (tpe == tok) {
+ self.advance();
+ return;
+ }
+ } else |_| {}
+ self.lastError = CompilerError.UnexpectedToken;
+ self.errorAtCurrent(message);
+ }
+
+ fn number(self: *@This()) void {
+ self.emitConstant(value.parseValue(self.previous.lexeme) catch |err| {
+ self.lastError = err;
+ self.errorAtPrevious("Invalid numeric literal");
+ return;
+ });
+ }
+
+ fn emitConstant(self: *@This(), val: value.Value) void {
+ self.emit(chunk.OP.CONSTANT, self.makeConstant(val));
+ }
+
+ fn makeConstant(self: *@This(), val: value.Value) u8 {
+ return self.currentChunk().addConstant(val) catch |err| {
+ self.lastError = err;
+ self.errorAtPrevious("Too many constants in one chunk");
+ return 0;
+ };
+ }
+
+ fn grouping(self: *@This()) void {
+ self.expression();
+ self.consume(scanner.TokenType.RIGHT_PAREN, "Expected ')' after expression");
+ }
+
+ fn unary(self: *@This()) void {
+ const operatorType = self.previous.type catch unreachable;
+
+ self.parsePrecedence(Precedence.UNARY);
+
+ switch (operatorType) {
+ scanner.TokenType.MINUS => self.emitOP(chunk.OP.NEGATE),
+ else => unreachable,
+ }
+ }
+
+ fn binary(self: *@This()) void {
+ const operatorType = self.previous.type catch unreachable;
+ self.parsePrecedence(getRule(operatorType).precedence.inc());
+
+ switch (operatorType) {
+ scanner.TokenType.PLUS => self.emitOP(chunk.OP.ADD),
+ scanner.TokenType.MINUS => self.emitOP(chunk.OP.SUBTRACT),
+ scanner.TokenType.STAR => self.emitOP(chunk.OP.MULTIPLY),
+ scanner.TokenType.SLASH => self.emitOP(chunk.OP.DIVIDE),
+ else => unreachable,
+ }
+ }
+
+ pub fn compile(source: []const u8, ch: *chunk.Chunk) CompilerError!void {
+ var self = @This(){ .scanner = try scanner.Scanner.init(source), .current = scanner.Token.Empty, .previous = scanner.Token.Empty, .panicMode = false, .hadError = false, .lastError = scanner.ScannerError.EmptyToken, .compilingChunk = ch };
+ self.advance();
+ self.expression();
+ self.consume(scanner.TokenType.EOF, "Expected end of expression.");
+ self.endCompiler();
+
+ if (self.hadError) return self.lastError;
}
-}
+};
diff --git a/zlox/src/main.zig b/zlox/src/main.zig
@@ -15,7 +15,7 @@ pub fn main() anyerror!u8 {
defer std.process.argsFree(allocator, args);
if (args.len == 1) {
- try repl();
+ try repl(allocator);
} else if (args.len == 2) {
try runFile(allocator, args[1]);
} else {
@@ -34,7 +34,7 @@ pub fn runFile(allocator: std.mem.Allocator, path: []const u8) anyerror!void {
defer allocator.free(text);
}
-pub fn repl() anyerror!void {
+pub fn repl(allocator: std.mem.Allocator) anyerror!void {
var VM = vm.VM.init();
defer VM.deinit();
@@ -42,7 +42,9 @@ pub fn repl() anyerror!void {
while (Linenoise.linenoise("lox> ")) |line| {
defer Linenoise.linenoiseFree(line);
- try VM.interpret(std.mem.span(line));
+ VM.interpret(std.mem.span(line), allocator) catch |err| {
+ std.debug.print("Error: {}\n", .{err});
+ };
_ = Linenoise.linenoiseHistoryAdd(line);
}
}
diff --git a/zlox/src/scanner.zig b/zlox/src/scanner.zig
@@ -47,12 +47,24 @@ pub const TokenType = enum {
EOF,
};
-pub const ScannerError = error{ UnexpectedCharacter, UnknownCharacter, UnterminatedString };
+pub const ScannerError = error{ UnexpectedCharacter, UnknownCharacter, UnterminatedString, EmptyToken };
+
+pub fn ScannerErrorString(err: ScannerError) []const u8 {
+ return switch (err) {
+ ScannerError.UnknownCharacter => "Unknown Character",
+ ScannerError.UnexpectedCharacter => "Unexpected Character",
+ ScannerError.UnterminatedString => "Unterminated String",
+ ScannerError.EmptyToken => "Empty Token",
+ };
+}
pub const Token = struct {
- type: TokenType,
+ type: ScannerError!TokenType,
lexeme: []const u8,
line: i32,
+ column: usize,
+
+ pub const Empty = @This(){ .type = ScannerError.EmptyToken, .lexeme = "", .line = -1, .column = 0 };
};
pub const Scanner = struct {
@@ -76,16 +88,16 @@ pub const Scanner = struct {
});
pub fn init(source: []const u8) !@This() {
- return @This(){ .start = source.ptr, .current = source.ptr, .end = source.ptr + source.len, .line = 0 };
+ return @This(){ .start = source.ptr, .current = source.ptr, .end = source.ptr + source.len, .line_ptr = source.ptr, .line = 0 };
}
- pub fn scanToken(self: *@This()) ScannerError!Token {
+ pub fn scanToken(self: *@This()) Token {
+ self.skipWhitespace();
+
self.start = self.current;
if (self.isAtEnd()) return self.makeToken(TokenType.EOF);
- self.skipWhitespace();
-
switch (self.advance()) {
'(' => return self.makeToken(TokenType.LEFT_PAREN),
')' => return self.makeToken(TokenType.RIGHT_PAREN),
@@ -105,19 +117,19 @@ pub const Scanner = struct {
'"' => return self.string(),
'0'...'9' => return self.number(),
'a'...'z', 'A'...'Z', '_' => return self.identifier(),
- else => return ScannerError.UnknownCharacter,
+ else => return self.makeToken(ScannerError.UnknownCharacter),
}
- return ScannerError.UnexpectedCharacter;
+ return self.makeToken(ScannerError.UnexpectedCharacter);
}
- fn string(self: *@This()) ScannerError!Token {
+ fn string(self: *@This()) Token {
while (self.peek() != '"' and !self.isAtEnd()) {
if (self.peek() == '\n') self.line += 1;
_ = self.advance();
}
- if (self.isAtEnd()) return ScannerError.UnterminatedString;
+ if (self.isAtEnd()) return self.makeToken(ScannerError.UnterminatedString);
_ = self.advance();
@@ -131,6 +143,7 @@ pub const Scanner = struct {
'\n' => {
self.line += 1;
_ = self.advance();
+ self.line_ptr = self.current;
},
'/' => {
if (self.peekNext() == '/') {
@@ -159,7 +172,7 @@ pub const Scanner = struct {
}
fn identifierType(self: *const @This()) TokenType {
- if (identifiers.get(self.start[0..(@intFromPtr(self.current) - @intFromPtr(self.start))])) |tok| {
+ if (identifiers.get(self.lexeme())) |tok| {
return tok;
} else {
return TokenType.IDENTIFIER;
@@ -198,12 +211,25 @@ pub const Scanner = struct {
return self.current == self.end;
}
- fn makeToken(self: *const @This(), tokentype: TokenType) Token {
- return Token{ .type = tokentype, .lexeme = self.start[0..(@intFromPtr(self.current) - @intFromPtr(self.start))], .line = self.line };
+ fn makeToken(self: *const @This(), tokentype: ScannerError!TokenType) Token {
+ return Token{ .type = tokentype, .lexeme = self.lexeme(), .line = self.line, .column = self.column() };
+ }
+
+ fn lexeme_len(self: *const @This()) usize {
+ return @intFromPtr(self.current) - @intFromPtr(self.start);
+ }
+
+ fn column(self: *const @This()) usize {
+ return @intFromPtr(self.start) - @intFromPtr(self.line_ptr);
+ }
+
+ fn lexeme(self: *const @This()) []const u8 {
+ return self.start[0..self.lexeme_len()];
}
start: [*]const u8,
current: [*]const u8,
end: [*]const u8,
+ line_ptr: [*]const u8,
line: i32,
};
diff --git a/zlox/src/value.zig b/zlox/src/value.zig
@@ -3,8 +3,14 @@ const array = @import("array.zig");
pub const Value = f64;
+pub const ParseValueError = std.fmt.ParseFloatError;
+
pub fn printValue(value: Value) void {
std.debug.print("{d}", .{value});
}
+pub fn parseValue(str: []const u8) ParseValueError!Value {
+ return std.fmt.parseFloat(Value, str);
+}
+
pub const ValueArray = array.Array(Value, u8, 8);
diff --git a/zlox/src/vm.zig b/zlox/src/vm.zig
@@ -6,7 +6,7 @@ const debug = @import("debug.zig");
const wrp = @import("wrap.zig");
const compiler = @import("compiler.zig");
-pub const InterpreterError = compiler.CompilerError || error{ CompileError, RuntimeError, IndexOutOfBounds, Overflow, DivisionByZero };
+pub const InterpreterError = compiler.CompilerError || error{ OutOfMemory, CompileError, RuntimeError, IndexOutOfBounds, Overflow, DivisionByZero };
pub const VM = struct {
ip: [*]const u8,
@@ -35,8 +35,13 @@ pub const VM = struct {
try self.run(true);
}
- pub fn interpret(self: *@This(), source: []const u8) !void {
- try compiler.compile(source);
+ pub fn interpret(self: *@This(), source: []const u8, allocator: std.mem.Allocator) InterpreterError!void {
+ var chunk = try Chunk.init(allocator);
+ defer chunk.deinit();
+
+ try compiler.Compiler.compile(source, &chunk);
+
+ try self.interpretChunk(&chunk);
self.resetStack();
}
@@ -86,6 +91,7 @@ pub const VM = struct {
const instruction: u8 = self.read_byte();
switch (instruction) {
@intFromEnum(OP.RETURN) => {
+ std.debug.print("{d}\n", .{self.pop()});
return;
},
@intFromEnum(OP.CONSTANT) => {
