diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/compile.zig | 88 | ||||
| -rw-r--r-- | src/lexer.zig | 49 | ||||
| -rw-r--r-- | src/main.zig | 26 | ||||
| -rw-r--r-- | src/parse.zig | 76 |
4 files changed, 186 insertions, 53 deletions
diff --git a/src/compile.zig b/src/compile.zig new file mode 100644 index 0000000..b9e1a86 --- /dev/null +++ b/src/compile.zig @@ -0,0 +1,88 @@ +const std = @import("std"); +const Allocator = std.mem.Allocator; +const root = @import("root"); +const Token = root.Lexer.Token; +const Expr = root.Expr; +const Location = root.Lexer.Location; + +pub const Reg = enum(u32) { _ }; + +pub const Instr = union(enum) { + constant: Constant, + bin_op: BinOp, + + const Constant = struct { + dest: Reg, + value: Location, + }; + + const BinOp = struct { + dest: Reg, + lhs: Reg, + rhs: Reg, + op: Op, + + const Op = enum { + add, + }; + }; +}; + +pub const Block = struct { + // arguments: []Reg, + instrs: []Instr, +}; + +pub fn compile(allocator: Allocator, expr: *const Expr) !Block { + const instrs: std.ArrayListUnmanaged(Instr) = try .initCapacity(allocator, 0); + var ctx: CompileContext = .{ + .allocator = allocator, + .register_counter = 0, + .instrs = instrs, + }; + _ = try ctx.compileExpr(expr); + return .{ .instrs = ctx.instrs.items }; +} + +const CompileContext = struct { + allocator: Allocator, + register_counter: u32, + instrs: std.ArrayListUnmanaged(Instr), + + const Self = @This(); + + fn addInstr(self: *Self, instr: Instr) !void { + try self.instrs.append(self.allocator, instr); + } + + fn compileExpr(self: *Self, expr: *const Expr) !Reg { + const dest = self.register(); + switch (expr.type) { + .integer_literal => try addInstr(self, .{ + .constant = .{ .dest = dest, .value = expr.loc }, + }), + .bin_op => |binop| { + const lhs = try self.compileExpr(binop.lhs); + const rhs = try self.compileExpr(binop.rhs); + try addInstr(self, .{ + .bin_op = .{ + .dest = dest, + .lhs = lhs, + .rhs = rhs, + .op = switch (binop.op) { + .plus => .add, + }, + }, + }); + }, + .invalid => return error.CantCompileInvalidExpr, + } + return dest; + } + + fn register(self: *Self) Reg { + const reg: Reg = @enumFromInt(self.register_counter); + self.register_counter += 1; + return reg; + } +}; diff --git a/src/lexer.zig b/src/lexer.zig index 93ed6cc..67beec9 100644 --- a/src/lexer.zig +++ b/src/lexer.zig @@ -1,49 +1,56 @@ pub const Token = struct { - start: usize, - end: usize, + loc: Location, type: Type, pub const Type = union(enum) { - LeftParen, - RightParen, - IntegerLiteral: usize, - Plus, - Invalid, - Eof, + left_paren, + right_paren, + integer_literal, + plus, + invalid, + eof, }; }; +pub const Location = struct { + start: usize, + end: usize, + + pub fn combine(a: Location, b: Location) Location { + if (a.end > b.start) unreachable; + return .{ .start = @min(a.start, b.start), .end = @max(a.end, b.end) }; + } +}; + source: []const u8, last_end: usize = 0, pos: usize = 0, pub fn next(self: *Self) ?Token { - return s: switch (self.eat() orelse return self.create(.Eof)) { - '(' => self.create(.LeftParen), - ')' => self.create(.RightParen), - '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' => |d| self.integerLiteral(d), - '+' => self.create(.Plus), + return s: switch (self.eat() orelse return self.create(.eof)) { + '(' => self.create(.left_paren), + ')' => self.create(.right_paren), + '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' => self.integerLiteral(), + '+' => self.create(.plus), ' ' => { self.last_end = self.pos; - continue :s (self.eat() orelse return self.create(.Eof)); + continue :s (self.eat() orelse return self.create(.eof)); }, - else => self.create(.Invalid), + else => self.create(.invalid), }; } -fn integerLiteral(self: *Self, first: u8) Token { - var value: usize = @intCast(digitValue(first).?); - while (digitValue(self.peek())) |d| { +fn integerLiteral(self: *Self) Token { + while (digitValue(self.peek()) != null) { _ = self.eat(); - value = value *| 10 +| d; } - return self.create(.{ .IntegerLiteral = value }); + return self.create(.{ .integer_literal = {} }); } fn create(self: *Self, tajp: Token.Type) Token { const start = self.last_end; self.last_end = self.pos; - return .{ .start = start, .end = self.pos, .type = tajp }; + return .{ .loc = .{ .start = start, .end = self.pos }, .type = tajp }; } fn eat(self: *Self) ?u8 { diff --git a/src/main.zig b/src/main.zig index e897d41..d938d9b 100644 --- a/src/main.zig +++ b/src/main.zig @@ -1,5 +1,12 @@ +const std = @import("std"); +const parse = @import("./parse.zig"); +const peek = @import("./peek.zig"); +const compile = @import("./compile.zig"); + pub const peekable = peek.peekable; pub const Peekable = peek.Peekable; +pub const Expr = parse.Expr; +pub const Lexer = @import("./lexer.zig"); pub fn main() !void { var arena: std.heap.ArenaAllocator = .init(std.heap.smp_allocator); @@ -22,7 +29,7 @@ pub fn main() !void { // try stdout.print("{s}\n", .{line.items}); // } - const source = "69 + (32 + 1) + 2"; + const source = "1 + 2 + 3"; // var lexer = Lexer{ .source = source }; // while (true) { // const token = lexer.next().?; @@ -30,17 +37,20 @@ pub fn main() !void { // if (token.type == .Eof) break; // } // try stdout.print("\n", .{}); - var lexer2 = peekable(Lexer{ .source = source }); - try stdout.print("{}\n", .{try parse.expression(allocator, &lexer2)}); + var lexer = peekable(Lexer{ .source = source }); + const expr = try parse.expression(allocator, &lexer); + try stdout.print("{}\n", .{expr}); + if (lexer.next()) |token| if (token.type != .eof) { + try stdout.print("Unexpected token {}, expected end of file\n", .{token}); + }; + const block = try compile.compile(allocator, expr); + for (block.instrs) |instr| { + try stdout.print("{}\n", .{instr}); + } try bw.flush(); // Don't forget to flush! } -const std = @import("std"); -const Lexer = @import("./lexer.zig"); -const parse = @import("./parse.zig"); -const peek = @import("./peek.zig"); - test { _ = peek; } diff --git a/src/parse.zig b/src/parse.zig index 8ceabeb..2149cd7 100644 --- a/src/parse.zig +++ b/src/parse.zig @@ -1,7 +1,31 @@ -pub const Expr = union(enum) { - IntegerLiteral: Token, - BinOp: struct { lhs: *const Expr, op: Token, rhs: *const Expr }, - Invalid: Token, +const std = @import("std"); +const Allocator = std.mem.Allocator; + +const root = @import("root"); +const Lexer = root.Lexer; +const Token = root.Lexer.Token; +const Peekable = root.Peekable; +const peekable = root.peekable; + +pub const Expr = struct { + loc: Lexer.Location, + type: Type, + + pub const Type = union(enum) { + integer_literal, + bin_op: BinOp, + invalid: Token, + + pub const BinOp = struct { + lhs: *const Expr, + rhs: *const Expr, + op: Op, + + const Op = enum { + plus, + }; + }; + }; }; pub fn expression(allocator: Allocator, lexer: *Peekable(Lexer)) error{OutOfMemory}!*Expr { @@ -9,28 +33,41 @@ pub fn expression(allocator: Allocator, lexer: *Peekable(Lexer)) error{OutOfMemo } pub fn addExpr(allocator: Allocator, lexer: *Peekable(Lexer)) !*Expr { - const lhs = try primaryExpr(allocator, lexer); - const token: ?Lexer.Token = lexer.peek(); - const op = (if (token) |t| if (t.type == .Plus) t else null else null) orelse return lhs; - _ = lexer.next(); + var lhs = try primaryExpr(allocator, lexer); + while (true) { + const token: Lexer.Token = if (lexer.peek()) |t| t else break; + const op: Expr.Type.BinOp.Op = switch (token.type) { + .plus => .plus, + else => break, + }; + + _ = lexer.next(); - const rhs = try primaryExpr(allocator, lexer); - return allocate(allocator, .{ .BinOp = .{ .lhs = lhs, .op = op, .rhs = rhs } }); + const rhs = try primaryExpr(allocator, lexer); + lhs = try allocate(allocator, .{ + .loc = lhs.loc.combine(rhs.loc), + .type = .{ .bin_op = .{ .lhs = lhs, .op = op, .rhs = rhs } }, + }); + } + return lhs; } pub fn primaryExpr(allocator: Allocator, lexer: *Peekable(Lexer)) !*Expr { const token = lexer.next().?; // std.debug.print("term {}\n", .{token}); return allocate(allocator, switch (token.type) { - .LeftParen => { + .left_paren => { const res = expression(allocator, lexer); const right_paren = lexer.next().?; - if (right_paren.type != .RightParen) - return allocate(allocator, .{ .Invalid = right_paren }); + if (right_paren.type != .right_paren) + return allocate(allocator, .{ + .loc = right_paren.loc, + .type = .{ .invalid = right_paren }, + }); return res; }, - .IntegerLiteral => .{ .IntegerLiteral = token }, - else => .{ .Invalid = token }, + .integer_literal => .{ .loc = token.loc, .type = .integer_literal }, + else => .{ .loc = token.loc, .type = .{ .invalid = token } }, }); } @@ -39,12 +76,3 @@ fn allocate(allocator: Allocator, expr: Expr) !*Expr { res.* = expr; return res; } - -const std = @import("std"); -const Allocator = std.mem.Allocator; - -const Lexer = @import("./lexer.zig"); -const Token = Lexer.Token; -const root = @import("root"); -const Peekable = root.Peekable; -const peekable = root.peekable; |