diff options
| -rw-r--r-- | src/gss.zig | 6 | ||||
| -rw-r--r-- | src/recognizer.zig | 89 |
2 files changed, 51 insertions, 44 deletions
diff --git a/src/gss.zig b/src/gss.zig index ef5d221..9201ca6 100644 --- a/src/gss.zig +++ b/src/gss.zig @@ -58,18 +58,22 @@ pub fn Graph(T: type) type { const Self = @This(); allocator: std.mem.Allocator, + number_of_nodes: usize = 0, + number_of_clones: usize = 0, pub fn init(allocator: std.mem.Allocator) Self { return Self { .allocator = allocator }; } pub fn push(self: *Self, node: *Node(T), state: T) !*Node(T) { + self.number_of_nodes += 1; const child = try self.allocator.create(Node(T)); child.* = try node.push(state); return child; } pub fn add_toplevel(self: *Self, state: T) !*Node(T) { + self.number_of_nodes += 1; const node = try self.allocator.create(Node(T)); node.* = try Node(T).init(state, self.allocator); node.is_toplevel = true; @@ -77,6 +81,8 @@ pub fn Graph(T: type) type { } pub fn clone(self: *Self, node: *Node(T), state: T) !*Node(T) { + self.number_of_nodes += 1; + self.number_of_clones += 1; const sibling = try self.allocator.create(Node(T)); sibling.* = try node.clone(state); return sibling; diff --git a/src/recognizer.zig b/src/recognizer.zig index 3c284d1..2eeae0d 100644 --- a/src/recognizer.zig +++ b/src/recognizer.zig @@ -69,65 +69,65 @@ const State = struct { } }; -// NOTE: Since I can't remember shit: -// -// if (grammar.is_next_char( -// non_terminal.rules()[node.state.rule_index][node.state.inner_position..], -// node.state.id, -// input[node.state.input_position], -// )) - pub fn forward_and_consume( grammar: *Grammar, - node: *gss.Node(State), + base: *gss.Node(State), graph: *gss.Graph(State), terminal: u8, queue: *std.ArrayList(*gss.Node(State)), node_cache: *std.HashMap(State, *gss.Node(State), State.Context, 80), + allocator: std.mem.Allocator, ) !void { - const rule = grammar.non_terminal_by_id(node.state.id).rules()[node.state.rule_index]; + var forward_queue = std.ArrayList(struct { State, *gss.Node(State) }).init(allocator); + try forward_queue.append(.{ base.state, base }); - if (node.state.inner_position == rule.len) { - for (node.parents.items) |parent| { - const next = try graph.clone(parent, parent.state.next()); - try forward_and_consume(grammar, next, graph, terminal, queue, node_cache); - } + while (forward_queue.popOrNull()) |checkpoint| { + const last_state, const last_node = checkpoint; + const rule = grammar.non_terminal_by_id(last_state.id).rules()[last_state.rule_index]; - return; - } + if (last_state.inner_position == rule.len) { + for (last_node.parents.items) |parent| { + try forward_queue.append(.{parent.state.next(), parent}); + } - switch (rule[node.state.inner_position]) { - .terminal => |t| if (t == terminal) try queue.append(try graph.clone(node, node.state.next())), - .non_terminal => |n| { - const non_terminal = grammar.non_terminal_by_id(n); - for (0..grammar.non_terminal_by_id(n).rules().len) |rule_index| { - if (grammar.is_next_char( - non_terminal.rules()[rule_index], - n, - terminal, - )) { + continue; + } - const state = State { - .id = n, - .rule_index = rule_index, - .inner_position = 0, - }; + switch (rule[last_state.inner_position]) { + .terminal => |t| if (t == terminal) { + const node = try graph.clone(last_node, last_state.next()); + try queue.append(node); + }, + .non_terminal => |n| { + const non_terminal = grammar.non_terminal_by_id(n); + for (0..grammar.non_terminal_by_id(n).rules().len) |rule_index| { + if (grammar.is_next_char( + non_terminal.rules()[rule_index], + n, + terminal, + )) { - const result = try node_cache.getOrPut(state); + const state = State { + .id = n, + .rule_index = rule_index, + .inner_position = 0, + }; - if (!result.found_existing) { - result.value_ptr.* = try graph.push(node, state); - try forward_and_consume(grammar, result.value_ptr.*, graph, terminal, queue, node_cache); - } else { - try result.value_ptr.*.parents.append(node); + if (node_cache.get(state)) |parent| { + try parent.parents.append(last_node); + } else { + const parent = try graph.clone(last_node, last_state); + const next = try graph.push(parent, state); + try node_cache.put(state, next); + try forward_queue.append(.{state, next}); + } } } - } - }, - .epsilon => { - const next = try graph.clone(node, node.state.next()); - try forward_and_consume(grammar, next, graph, terminal, queue, node_cache); - }, + }, + .epsilon => { + try forward_queue.append(.{last_state.next(), last_node}); + }, + } } } @@ -193,6 +193,7 @@ pub fn check(grammar: *Grammar, input: []const u8, inner_allocator: std.mem.Allo character, next_processing_queue, &node_cache, + allocator, ); node_cache.clearRetainingCapacity(); |