aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/argument.zig8
-rw-r--r--src/gss.zig23
-rw-r--r--src/main.zig12
-rw-r--r--src/recognizer.zig161
4 files changed, 113 insertions, 91 deletions
diff --git a/src/argument.zig b/src/argument.zig
index fa9612d..37d9045 100644
--- a/src/argument.zig
+++ b/src/argument.zig
@@ -74,12 +74,12 @@ pub const Entry = struct {
name: []const u8,
file: std.fs.File,
- pub fn open(path: []const u8) Self {
+ pub fn open(path: []const u8, flags: std.fs.File.OpenFlags) Self {
var cwd = std.fs.cwd();
return Self {
.name = path,
- .file = cwd.openFile(path, .{}) catch |e| help(e)
+ .file = cwd.openFile(path, flags) catch |e| help(e)
};
}
@@ -145,7 +145,7 @@ pub const Args = union(Mode) {
while (args.next()) |arg| {
if (check_flags(arg, &[_][]const u8 { "-i", "--input" })) {
- input = Entry.open(check(args.next()));
+ input = Entry.open(check(args.next()), .{});
} else help(error.InvalidArgument);
}
@@ -164,7 +164,7 @@ pub const Args = union(Mode) {
while (args.next()) |arg| {
if (check_flags(arg, &[_][]const u8 { "-o", "--output" })) {
- output = Entry.open(check(args.next()));
+ output = Entry.open(check(args.next()), .{ .mode = .write_only });
} else if (check_flags(arg, &[_][]const u8 { "-c", "--count" })) {
count = parse_int(check(args.next()));
} else if (check_flags(arg, &[_][]const u8 { "-n", "--non-empty" })) {
diff --git a/src/gss.zig b/src/gss.zig
index ba8542d..8f81d80 100644
--- a/src/gss.zig
+++ b/src/gss.zig
@@ -4,7 +4,7 @@ pub fn Node(T: type) type {
return struct {
const Self = @This();
- parent: ?*Node = null,
+ parent: ?*Self = null,
state: T,
pub fn init(state: T) Self {
@@ -18,7 +18,14 @@ pub fn Node(T: type) type {
return node;
}
- pub fn pop(self: *Self, allocator: std.mem.Allocator) struct { T, *Self } {
+ pub fn clone(self: *Self, state: T, allocator: std.mem.Allocator) !*Self {
+ const node = try allocator.create(Self);
+ node.parent = self.parent;
+ node.state = state;
+ return node;
+ }
+
+ pub fn pop(self: *Self, allocator: std.mem.Allocator) struct { T, ?*Self } {
const parent = self.parent;
const state = self.state;
@@ -26,5 +33,17 @@ pub fn Node(T: type) type {
return .{ state, parent };
}
+
+ pub fn format(
+ self: *const Self,
+ comptime fmt: []const u8,
+ options: std.fmt.FormatOptions,
+ writer: anytype,
+ ) !void {
+ _ = fmt;
+ _ = options;
+
+ try writer.print("Node {{ {} }}", .{ self.state });
+ }
};
}
diff --git a/src/main.zig b/src/main.zig
index 4dec1f1..c1d63c0 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -38,9 +38,11 @@ fn write_result(
fn recognize(args: *RecognizeArgs, allocator: std.mem.Allocator) !void {
const stdout = std.io.getStdOut();
- const writer = std.io.getStdOut().writer();
+ var bufwriter = std.io.bufferedWriter(stdout.writer());
+ const writer = bufwriter.writer();
- var reader = args.input.file.reader();
+ var bufreader = std.io.bufferedReader(args.input.file.reader());
+ var reader = bufreader.reader();
var index: usize = 0;
const stderr = std.io.getStdErr();
@@ -58,8 +60,6 @@ fn recognize(args: *RecognizeArgs, allocator: std.mem.Allocator) !void {
)) |buffer| {
const trimmed = std.mem.trim(u8, buffer, &std.ascii.whitespace);
- var arena = std.heap.ArenaAllocator.init(allocator);
- defer arena.deinit();
try write_result(
writer,
@@ -70,7 +70,7 @@ fn recognize(args: *RecognizeArgs, allocator: std.mem.Allocator) !void {
try recognizer.check(
&args.grammar,
trimmed,
- arena.allocator()
+ allocator
));
index += 1;
@@ -79,6 +79,8 @@ fn recognize(args: *RecognizeArgs, allocator: std.mem.Allocator) !void {
try stderr.writeAll("> ");
}
}
+
+ try bufwriter.flush();
}
fn generate(args: *GenerateArgs, allocator: std.mem.Allocator) !void {
diff --git a/src/recognizer.zig b/src/recognizer.zig
index 3adb7a4..1783db1 100644
--- a/src/recognizer.zig
+++ b/src/recognizer.zig
@@ -31,111 +31,112 @@ const State = struct {
}
};
-pub fn check(grammar: *Grammar, input: []const u8, allocator: std.mem.Allocator) !bool {
- var stacks = std.ArrayList(std.ArrayList(State)).init(allocator);
- defer {
- for (stacks.items) |stack| {
- stack.deinit();
- }
- stacks.deinit();
- }
+pub fn check(grammar: *Grammar, input: []const u8, inner_allocator: std.mem.Allocator) !bool {
+ var arena = std.heap.ArenaAllocator.init(inner_allocator);
+ defer arena.deinit();
+ const allocator = arena.allocator();
const entry = grammar.entry_point();
+ var queues = [2]std.ArrayList(*gss.Node(State)) {
+ std.ArrayList(*gss.Node(State)).init(allocator),
+ std.ArrayList(*gss.Node(State)).init(allocator),
+ };
+ defer for (queues) |queue| queue.deinit();
+ var processing_queue = &queues[0];
for (entry.rules()) |rule| {
- const state = State {
+ const node = try allocator.create(gss.Node(State));
+ node.* = gss.Node(State).init(State {
.name = entry.name,
.rule = rule,
.inner_position = 0,
.input_position = 0,
- };
+ });
- var stack = std.ArrayList(State).init(allocator);
- try stack.append(state);
- try stacks.append(stack);
+ try processing_queue.append(node);
}
- var remove_queue = std.ArrayList(usize).init(allocator);
- defer remove_queue.deinit();
- var add_queue = std.ArrayList(std.ArrayList(State)).init(allocator);
- defer add_queue.deinit();
+ var next_processing_queue = &queues[1];
- while (stacks.items.len > 0) {
- for (stacks.items, 0..) |*stack, stack_index| {
- var state: *State = &stack.items[stack.items.len - 1];
-
- if (state.inner_position == state.rule.len) {
+ while (processing_queue.items.len > 0) {
+ for (processing_queue.items) |node| {
+ if (node.state.inner_position == node.state.rule.len) {
if (
- stack.items.len == 1 and
- state.name == entry.name and
- state.input_position == input.len
+ node.parent == null and
+ node.state.name == entry.name and
+ node.state.input_position == input.len
) {
return true;
}
- const old_state = stack.pop();
- if (stack.items.len > 0) {
- state = &stack.items[stack.items.len - 1];
- state.inner_position += 1;
- state.input_position = old_state.input_position;
- } else {
- try remove_queue.append(stack_index);
+ const old_state, const parent_node = node.pop(allocator);
+ if (parent_node) |parent| {
+ const sibling = try parent.clone(State {
+ .name = parent.state.name,
+ .rule = parent.state.rule,
+ .inner_position = parent.state.inner_position + 1,
+ .input_position = old_state.input_position,
+ }, allocator);
+ try next_processing_queue.append(sibling);
}
- continue;
- }
-
- const epsilon_only = state.input_position == input.len;
+ } else {
+ const epsilon_only = node.state.input_position == input.len;
- switch (state.rule[state.inner_position]) {
- .terminal => |t| {
- if (!epsilon_only and input[state.input_position] == t) {
- state.inner_position += 1;
- state.input_position += 1;
- } else {
- try remove_queue.append(stack_index);
- }
- },
- .non_terminal => |n| {
- const non_terminal = grammar.non_terminal_by_name(n);
- const rules = non_terminal.rules();
+ switch (node.state.rule[node.state.inner_position]) {
+ .terminal => |t| {
+ if (!epsilon_only and input[node.state.input_position] == t) {
+ const sibling = try node.clone(State {
+ .name = node.state.name,
+ .rule = node.state.rule,
+ .inner_position = node.state.inner_position + 1,
+ .input_position = node.state.input_position + 1,
+ }, allocator);
+ try next_processing_queue.append(sibling);
+ }
+ },
+ .non_terminal => |n| {
+ const non_terminal = grammar.non_terminal_by_name(n);
+ const rules = non_terminal.rules();
- if (!epsilon_only and non_terminal.first.is_set(input[state.input_position])) {
- for (rules) |rule| {
- const next_state = State {
- .name = non_terminal.name,
- .rule = rule,
- .inner_position = 0,
- .input_position = state.input_position,
- };
- var new_stack = try stack.clone();
- try new_stack.append(next_state);
- try add_queue.append(new_stack);
+ if (!epsilon_only and non_terminal.first.is_set(input[node.state.input_position])) {
+ for (rules) |rule| {
+ const child = try node.push(State {
+ .name = non_terminal.name,
+ .rule = rule,
+ .inner_position = 0,
+ .input_position = node.state.input_position,
+ }, allocator);
+ try next_processing_queue.append(child);
+ }
}
- }
- if (non_terminal.first.is_set(Character.EPSILON)) {
- state.inner_position += 1;
- } else {
- try remove_queue.append(stack_index);
- }
- },
- .epsilon => {
- state.inner_position += 1;
- },
+ if (non_terminal.first.is_set(Character.EPSILON)) {
+ const sibling = try node.clone(State {
+ .name = node.state.name,
+ .rule = node.state.rule,
+ .inner_position = node.state.inner_position + 1,
+ .input_position = node.state.input_position
+ }, allocator);
+ try next_processing_queue.append(sibling);
+ }
+ },
+ .epsilon => {
+ const sibling = try node.clone(State {
+ .name = node.state.name,
+ .rule = node.state.rule,
+ .inner_position = node.state.inner_position + 1,
+ .input_position = node.state.input_position
+ }, allocator);
+ try next_processing_queue.append(sibling);
+ },
+ }
}
}
- for (remove_queue.items, 0..) |index, offset| {
- const stack = stacks.orderedRemove(index - offset);
- stack.deinit();
- }
-
- for (add_queue.items) |stack| {
- try stacks.append(stack);
- }
-
- remove_queue.clearAndFree();
- add_queue.clearAndFree();
+ const swap = processing_queue;
+ processing_queue = next_processing_queue;
+ next_processing_queue = swap;
+ next_processing_queue.clearRetainingCapacity();
}
return false;
generated by cgit v1.2.3-70-g09d2 (git 2.53.0) at 2026-05-12 17:50:09 +0000