From 8f55e2fa7059ef215a1b8369300f0a85103b079b Mon Sep 17 00:00:00 2001 From: Nic Gaffney Date: Thu, 18 Jul 2024 19:26:06 -0500 Subject: ASt progress --- src/ast.zig | 156 ++++++++++++++++++++++++++++++++++++++++++++----------- src/main.zig | 12 ++--- src/tokenize.zig | 65 +++++++++++++++++------ 3 files changed, 176 insertions(+), 57 deletions(-) (limited to 'src') diff --git a/src/ast.zig b/src/ast.zig index 2f8f209..e8f3a8e 100644 --- a/src/ast.zig +++ b/src/ast.zig @@ -4,64 +4,158 @@ const tok = @import("tokenize.zig"); const SyntaxError = error{SyntaxError}; const expectedToken = error{ExpectedToken}; -pub const BinOp = enum { - Add, - Sub, - Mul, - Div, +pub const BinOp = enum(u32) { + Add = 0b000, + Sub = 0b001, + Mul = 0b100, + Div = 0b101, + Mod = 0b110, + + fn init(typ: tok.TokenType) ?BinOp { + return switch (typ) { + .plus => .Add, + .minus => .Sub, + .star => .Mul, + .slash => .Div, + else => null, + }; + } + + fn greater(self: BinOp, other: ?BinOp) bool { + if (other == null) return true; + return (@intFromEnum(self) >> 2) > (@intFromEnum(other.?) >> 2); + } }; pub const Literal = union(enum) { Int: i32, }; +pub const AstExpr = struct { + kind: ExprKind, + allocator: std.mem.Allocator, + pub fn init(allocator: std.mem.Allocator) !*AstExpr { + const value = try allocator.create(AstExpr); + value.* = .{ + .kind = .Void, + .allocator = allocator, + }; + return value; + } + pub fn deinit(self: *AstExpr) void { + self.allocator.free(self); + } +}; + +pub const AstStmt = struct { + kind: StmtKind, + allocator: std.mem.Allocator, + pub fn init(allocator: std.mem.Allocator) !*AstStmt { + const value = try allocator.create(AstStmt); + value.* = .{ + .kind = .Void, + .allocator = allocator, + }; + return value; + } + pub fn deinit(self: *AstStmt) void { + self.allocator.free(self); + } +}; + pub const Ast = union(enum) { - Expr: struct { - kind: ExprKind, - }, - Stmt: struct { - kind: StmtKind, - }, + Expr: AstExpr, + Stmt: AstStmt, }; const StmtKind = union(enum) { - exit: Ast.Expr, + exit: AstExpr, + Void, }; const ExprKind = union(enum) { Literal: Literal, BinaryOp: struct { op: BinOp, - left: Ast.Expr, - right: Ast.Expr, + left: *AstExpr, + right: *AstExpr, }, + Void, }; -fn checkType(token: tok.Token, typ: tok.TokenType) bool { - return switch (token) { - typ => true, - else => false, - }; -} - const AstParser = struct { tokens: tok.Iterator(tok.Token), - fn parseStmt(self: *AstParser) !Ast.Stmt { - return switch (self.tokens.peek().?) { - .ret => try self.exitStmt(), + arena: std.heap.ArenaAllocator, + allocator: std.mem.Allocator, + + fn init(allocator: *std.heap.ArenaAllocator, tokens: tok.Iterator(tok.Token)) AstParser { + return AstParser{ + .tokens = tokens, + .arena = allocator.*, + .allocator = allocator.allocator(), }; } - fn parseExpr(self: *AstParser) !Ast.Expr { + fn deinit(self: *AstParser) void { + self.arena.deinit(); + } + fn parseStmt(self: *AstParser) !AstStmt { + return switch (self.tokens.peek().?) { + .ret => self.exitStmt(), + else => error.SyntaxError, + }; } - fn exitStmt(self: *AstParser) !Ast.Stmt { - if (!checkType(self.tokens.consume().?, tok.TokenType.ret)) return expectedToken; - const value = self.parseExpr(); + fn parseExpr(self: *AstParser, lastOp: ?BinOp) !*AstExpr { + if (!tok.checkType(self.tokens.peek().?, tok.TokenType.intLit)) return error.ExpectedToken; + const kind = ExprKind{ .Literal = .{ .Int = self.tokens.consume().?.intLit } }; + var lhs = try AstExpr.init(self.allocator); + lhs.*.kind = kind; + while (self.tokens.peek()) |tokn| { + const op = BinOp.init(tokn); + if (op != null and op.?.greater(lastOp)) { + self.tokens.skip(); + const rhs = try self.parseExpr(op); + const newkind = ExprKind{ .BinaryOp = .{ + .op = op.?, + .left = lhs, + .right = rhs, + } }; + lhs = try AstExpr.init(self.allocator); + lhs.*.kind = newkind; + } + return lhs; + } + return lhs; + } - if (!checkType(self.tokens.consume().?, tok.TokenType.semiCol)) return expectedToken; - const kind = StmtKind{ .exit = value }; - return Ast.Stmt{ .kind = kind }; + fn exitStmt(self: *AstParser) !AstStmt { + if (!tok.checkType(self.tokens.consume().?, tok.TokenType.ret)) + return error.ExpectedToken; + const value = try self.parseExpr(null); + + if (!tok.checkType(self.tokens.consume().?, tok.TokenType.semiCol)) return error.ExpectedToken; + const kind = StmtKind{ .exit = value.* }; + const stmt = try AstStmt.init(self.allocator); + stmt.kind = kind; + return stmt.*; } }; + +test "AstParse" { + std.testing.log_level = std.log.Level.info; + const expect = std.testing.expect; + const testSource: []const u8 = "exit 120 + 150;"; + var toks = tok.Tokenizer.init(std.testing.allocator, testSource); + defer toks.deinit(); + var arrtoks = try toks.tokenize(); + const slice = try arrtoks.toOwnedSlice(); + const iter = tok.Iterator(tok.Token).init(slice); + var arena = std.heap.ArenaAllocator.init(std.testing.allocator); + var parser = AstParser.init(&arena, iter); + defer parser.deinit(); + const stmt = try parser.parseStmt(); + _ = stmt; + _ = expect; +} diff --git a/src/main.zig b/src/main.zig index 4a0bbca..2ca0b68 100644 --- a/src/main.zig +++ b/src/main.zig @@ -45,21 +45,15 @@ pub fn main() !void { switch (t) { .ret => { const num = tokIter.next(); - switch (num.?) { - .intLit => {}, - else => break, - } - switch (tokIter.next().?) { - .semiCol => {}, - else => break, - } + if (!tok.checkType(num.?, tok.TokenType.intLit)) return error.SyntaxError; + + if (!tok.checkType(tokIter.next().?, tok.TokenType.semiCol)) return error.SyntaxError; try outWriter.print( \\ mov rax, 60 \\ mov rdi, {} \\ syscall \\ , .{num.?.intLit}); - gpa.allocator().free(t.ret); }, // No other commands else => {}, diff --git a/src/tokenize.zig b/src/tokenize.zig index 93a3ac9..40a7d00 100644 --- a/src/tokenize.zig +++ b/src/tokenize.zig @@ -1,22 +1,37 @@ const std = @import("std"); const TokenError = error{UnknownToken}; -const TokenType = enum { - ret, +pub const TokenType = enum { + ident, intLit, - binaryOp, + ret, + plus, + minus, + star, + slash, semiCol, nil, }; pub const Token = union(TokenType) { - ret: []const u8, + ident: []const u8, intLit: i32, - binaryOp: u8, + ret, + plus, + minus, + star, + slash, semiCol, nil, }; +pub fn checkType(tok: Token, comptime typ: TokenType) bool { + return switch (tok) { + typ => true, + else => false, + }; +} + /// Creates a tokenizer over a slice of typ pub fn Iterator(comptime typ: type) type { return struct { @@ -91,7 +106,8 @@ pub const Tokenizer = struct { while (std.ascii.isAlphanumeric(self.src.peek().?)) try str.append(self.src.consume().?); - try self.toks.append(.{ .ret = try str.toOwnedSlice() }); + if (std.mem.eql(u8, "exit", str.items)) + try self.toks.append(.ret); str.deinit(); str = std.ArrayList(u8).init(self.allocator); }, @@ -99,7 +115,22 @@ pub const Tokenizer = struct { self.src.skip(); try self.toks.append(.semiCol); }, - '+', '-', '*', '/' => try self.toks.append(.{ .binaryOp = self.src.consume().? }), + '+' => { + self.src.skip(); + try self.toks.append(.plus); + }, + '-' => { + self.src.skip(); + try self.toks.append(.minus); + }, + '*' => { + self.src.skip(); + try self.toks.append(.star); + }, + '/' => { + self.src.skip(); + try self.toks.append(.slash); + }, else => {}, } } @@ -115,27 +146,27 @@ test "Tokenize" { defer toks.deinit(); const arrtoks = try toks.tokenize(); const expected = &[_]Token{ - .{ .ret = "exit" }, + .ret, .{ .intLit = 120 }, - .{ .binaryOp = '+' }, + .plus, .{ .intLit = 150 }, - .{ .binaryOp = '-' }, + .minus, .{ .intLit = 260 }, - .{ .binaryOp = '*' }, + .star, .{ .intLit = 12 }, - .{ .binaryOp = '/' }, + .slash, .{ .intLit = 5 }, .semiCol, }; for (arrtoks.items, expected) |act, exp| { switch (act) { - .ret => |v| { - try expect(std.mem.eql(u8, v, exp.ret)); - std.testing.allocator.free(v); - }, + .ret => |v| try expect(v == exp.ret), .intLit => |v| try expect(v == exp.intLit), .semiCol => |v| try expect(v == exp.semiCol), - .binaryOp => |v| try expect(v == exp.binaryOp), + .plus => |v| try expect(v == exp.plus), + .minus => |v| try expect(v == exp.minus), + .star => |v| try expect(v == exp.star), + .slash => |v| try expect(v == exp.slash), else => {}, } } -- cgit v1.2.3