diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.zig | 20 | ||||
| -rw-r--r-- | src/parser.zig | 115 |
2 files changed, 106 insertions, 29 deletions
diff --git a/src/main.zig b/src/main.zig index f28ab18..8741cd7 100644 --- a/src/main.zig +++ b/src/main.zig @@ -8,24 +8,16 @@ pub fn main() !void { defer _ = gpa.deinit(); - const lexer = try allocator.create(Regex.Lexer); + var lexer = Regex.Lexer.init("bz*[a-z](l)", &allocator); - lexer.* = Regex.Lexer.init("abc|123[a-Z]()+", &allocator); + _ = try lexer.scan(); - const tl = try lexer.scan(); + var parser = Regex.Parser.init(&lexer.tokens, &allocator); - var it = tl.first; - while (it) |node| : (it = node.next) { - try stdio.print("{}\n", .{&(node.data)}); - } + const pt = try parser.parse(); - const parser = try allocator.create(Regex.Parser); - - parser.* = Regex.Parser.init(&lexer.tokens, &allocator); - - _ = try parser.parseRe(); + try stdio.print("{}\n", .{pt}); + parser.deinit(); lexer.deinit(); - allocator.destroy(lexer); - allocator.destroy(parser); } diff --git a/src/parser.zig b/src/parser.zig index 49fcdb6..80522da 100644 --- a/src/parser.zig +++ b/src/parser.zig @@ -24,6 +24,21 @@ pub const ParseTree = struct { return t; } + pub fn deinit(self: *ParseTree, allocator: *std.mem.Allocator) void { + const child = self.child; + const sibling = self.sibling; + + allocator.destroy(self); + + if (child) |c| { + c.deinit(allocator); + } + + if (sibling) |s| { + s.deinit(allocator); + } + } + pub fn appendChild(self: *ParseTree, child: *ParseTree) void { if (self.child) |c| { var p = c; @@ -35,9 +50,51 @@ pub const ParseTree = struct { self.child = child; } } + + pub fn format(self: *const ParseTree, comptime fmt: []const u8, _: std.fmt.FormatOptions, writer: anytype) !void { + var arena = std.heap.ArenaAllocator.init(std.heap.page_allocator); + defer arena.deinit(); + const allocator = arena.allocator(); + + if (fmt.len != 0) { + return std.invalidFmtError(fmt, self); + } + + const Queue = std.DoublyLinkedList(struct { *const ParseTree, u32 }); + + var q: Queue = .{}; + + const root = try allocator.create(Queue.Node); + root.* = .{ .data = .{ self, 0 } }; + + q.append(root); + + var level: u32 = 0; + while (q.len != 0) { + const cur: *Queue.Node = q.popFirst().?; + + const tree = cur.data[0]; + const l = cur.data[1]; + + if (l != level) { + try writer.print("\n", .{}); + level = l; + } + + try writer.print("{s} ", .{@tagName(tree.rule)}); + + var p: ?*ParseTree = tree.child; + while (p) |child| : (p = child.sibling) { + const node = try allocator.create(Queue.Node); + node.* = .{ .data = .{ child, l + 1 } }; + q.append(node); + } + } + } }; pub const Parser = struct { + parse_tree: ?*ParseTree, tokens: *const TokenList, itr: ?*TokenList.Node, allocator: *std.mem.Allocator, @@ -45,7 +102,13 @@ pub const Parser = struct { pub const Error = error{ UnexpectedToken, ExpectedToken }; pub fn init(tl: *const TokenList, allocator: *std.mem.Allocator) Parser { - return .{ .tokens = tl, .allocator = allocator, .itr = tl.first.? }; + return .{ .tokens = tl, .allocator = allocator, .itr = tl.first.?, .parse_tree = null }; + } + + pub fn deinit(self: *Parser) void { + if (self.parse_tree) |pt| { + pt.deinit(self.allocator); + } } pub fn expectToken(self: *Parser, kind: Token.Kind) !*ParseTree { @@ -68,8 +131,19 @@ pub const Parser = struct { } } - pub fn parseRe(self: *Parser) error{ ExpectedToken, UnexpectedToken, OutOfMemory }!*ParseTree { + pub fn parse(self: *Parser) !*ParseTree { + if (self.parse_tree) |pt| { + return pt; + } + + self.parse_tree = try self.parseRe(); + + return self.parse_tree.?; + } + + fn parseRe(self: *Parser) error{ ExpectedToken, UnexpectedToken, OutOfMemory }!*ParseTree { const t = try ParseTree.init(Rule.Re, self.allocator); + errdefer t.deinit(self.allocator); t.appendChild(try self.parseCat()); t.appendChild(try self.parseRer()); @@ -77,19 +151,23 @@ pub const Parser = struct { return t; } - pub fn parseRer(self: *Parser) !*ParseTree { + fn parseRer(self: *Parser) !*ParseTree { const t = try ParseTree.init(Rule.Rer, self.allocator); + errdefer t.deinit(self.allocator); - if (self.itr) |_| { - t.appendChild(try self.expectToken(Token.Kind.Or)); - t.appendChild(try self.parseCat()); + if (self.itr) |node| { + if (node.data.kind == Token.Kind.Or) { + t.appendChild(try self.expectToken(Token.Kind.Or)); + t.appendChild(try self.parseCat()); + } } // else -> epsilon return t; } - pub fn parseCat(self: *Parser) !*ParseTree { + fn parseCat(self: *Parser) !*ParseTree { const t = try ParseTree.init(Rule.Cat, self.allocator); + errdefer t.deinit(self.allocator); t.appendChild(try self.parseE()); t.appendChild(try self.parseCatr()); @@ -97,19 +175,26 @@ pub const Parser = struct { return t; } - pub fn parseCatr(self: *Parser) !*ParseTree { + fn parseCatr(self: *Parser) !*ParseTree { const t = try ParseTree.init(Rule.Catr, self.allocator); + errdefer t.deinit(self.allocator); - if (self.itr) |_| { - t.appendChild(try self.parseE()); - t.appendChild(try self.parseCatr()); + if (self.itr) |node| { + switch (node.data.kind) { + .RParen, .Or => {}, // also cases where the null production should be chosen + else => { + t.appendChild(try self.parseE()); + t.appendChild(try self.parseCatr()); + }, + } } return t; } - pub fn parseE(self: *Parser) !*ParseTree { + fn parseE(self: *Parser) !*ParseTree { const t = try ParseTree.init(Rule.E, self.allocator); + errdefer t.deinit(self.allocator); t.appendChild(try self.parseL()); @@ -120,15 +205,14 @@ pub const Parser = struct { }, else => {}, } - } else { - return Error.ExpectedToken; } return t; } - pub fn parseL(self: *Parser) !*ParseTree { + fn parseL(self: *Parser) !*ParseTree { const t = try ParseTree.init(Rule.L, self.allocator); + errdefer t.deinit(self.allocator); if (self.itr) |node| { switch (node.data.kind) { @@ -141,6 +225,7 @@ pub const Parser = struct { t.appendChild(try self.expectToken(Token.Kind.RParen)); }, else => { + std.debug.print("unexpected token of type {s}\n", .{@tagName(node.data.kind)}); return Error.UnexpectedToken; }, } |