aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/argument.zig341
-rw-r--r--src/command/benchmark.zig272
-rw-r--r--src/gss.zig134
-rw-r--r--src/main.zig1
-rw-r--r--src/pex/block.zig90
-rw-r--r--src/pex/instruction.zig9
-rw-r--r--src/pex/node.zig36
-rw-r--r--src/pex/optimizer/root.zig38
-rw-r--r--src/pex/root.zig163
-rw-r--r--src/recognizer.zig456
10 files changed, 959 insertions, 581 deletions
diff --git a/src/argument.zig b/src/argument.zig
index 7912397..81172fb 100644
--- a/src/argument.zig
+++ b/src/argument.zig
@@ -2,223 +2,230 @@ const std = @import("std");
pub const Grammar = @import("grammar.zig");
fn help(err: ?anyerror) noreturn {
- const stderr = std.io.getStdErr().writer();
+ const stderr = std.io.getStdErr().writer();
- if (err) |e| {
- stderr.print("error: {s}\n", .{@errorName(e)}) catch unreachable;
- }
+ if (err) |e| {
+ stderr.print("error: {s}\n", .{@errorName(e)}) catch unreachable;
+ }
- stderr.writeAll(
- \\mry [command] [options]
- \\
- \\Commands:
- \\
- \\ generate [grammar] [options]
- \\ Options:
- \\ -e, --entry label Name of the entry point. (default: main)
- \\
- \\ -o, --output entry Output string to file
- \\ By default stdout will be used.
- \\
- \\ -c, --count n Number of texts to generate. (default: 1)
- \\
- \\ -n, --non-empty Only output texts which are non-empty.
- \\
- \\ -m, --min-length n Minimum length of sentential string.
- \\
- \\ benchmark [grammar] [options]
- \\ Options:
- \\ -e, --entry label Name of the entry point. (default: main)
- \\
- \\ -i, --input entry Specify input source, if the path
- \\ points to a directory it will scan
- \\ all files in it. By default stdin will
- \\ be used as input.
- \\
- \\General Options
- \\ -h, --help Print usage
- \\
- ) catch unreachable;
- std.process.exit(@intFromBool(err != null));
+ stderr.writeAll(
+ \\mry [command] [options]
+ \\
+ \\Commands:
+ \\
+ \\ generate [grammar] [options]
+ \\ Options:
+ \\ -e, --entry label Name of the entry point. (default: main)
+ \\
+ \\ -o, --output entry Output string to file
+ \\ By default stdout will be used.
+ \\
+ \\ -c, --count n Number of texts to generate. (default: 1)
+ \\
+ \\ -n, --non-empty Only output texts which are non-empty.
+ \\
+ \\ -m, --min-length n Minimum length of sentential string.
+ \\
+ \\ benchmark [grammar] [options]
+ \\ Options:
+ \\ -e, --entry label Name of the entry point. (default: main)
+ \\
+ \\ -i, --input entry Specify input source, if the path
+ \\ points to a directory it will scan
+ \\ all files in it. By default stdin will
+ \\ be used as input.
+ \\
+ \\ --csv output in CSV format.
+ \\
+ \\General Options
+ \\ -h, --help Print usage
+ \\
+ ) catch unreachable;
+ std.process.exit(@intFromBool(err != null));
}
fn check(arg_or_null: ?[]const u8) []const u8 {
- const arg = arg_or_null orelse help(error.MissingArgument);
+ const arg = arg_or_null orelse help(error.MissingArgument);
- if (std.mem.eql(u8, arg, "-h") or std.mem.eql(u8, arg, "--help")) {
- help(null);
- }
- return arg;
+ if (std.mem.eql(u8, arg, "-h") or std.mem.eql(u8, arg, "--help")) {
+ help(null);
+ }
+ return arg;
}
fn parse_enum(T: type, arg: []const u8) T {
- return std.meta.stringToEnum(T, arg) orelse help(error.InvalidArgument);
+ return std.meta.stringToEnum(T, arg) orelse help(error.InvalidArgument);
}
fn parse_int(n: []const u8) usize {
- return std.fmt.parseInt(usize, n, 10) catch |e| help(e);
+ return std.fmt.parseInt(usize, n, 10) catch |e| help(e);
}
fn check_flags(arg: []const u8, comptime flags: []const []const u8) bool {
- inline for (flags) |flag| {
- if (std.mem.eql(u8, arg, flag)) {
- return true;
- }
- }
+ inline for (flags) |flag| {
+ if (std.mem.eql(u8, arg, flag)) {
+ return true;
+ }
+ }
- return false;
+ return false;
}
pub const Mode = enum {
- benchmark,
- generate,
+ benchmark,
+ generate,
};
pub const Entry = struct {
- const Self = @This();
+ const Self = @This();
- name: []const u8,
- file: std.fs.File,
+ name: []const u8,
+ file: std.fs.File,
- pub fn open(path: []const u8, writer: bool) Self {
- var cwd = std.fs.cwd();
+ pub fn open(path: []const u8, writer: bool) Self {
+ var cwd = std.fs.cwd();
- return Self {
- .name = path,
- .file = (if (writer) cwd.createFile(path, .{})
- else cwd.openFile(path, .{})) catch |e| help(e)
- };
- }
+ return Self {
+ .name = path,
+ .file = (if (writer) cwd.createFile(path, .{})
+ else cwd.openFile(path, .{})) catch |e| help(e)
+ };
+ }
- pub fn read_file(path: []const u8, allocator: std.mem.Allocator) []const u8 {
- var cwd = std.fs.cwd();
+ pub fn read_file(path: []const u8, allocator: std.mem.Allocator) []const u8 {
+ var cwd = std.fs.cwd();
- var file = cwd.openFile(path, .{}) catch |e| help(e);
- defer file.close();
- const stat = file.stat() catch |e| help(e);
+ var file = cwd.openFile(path, .{}) catch |e| help(e);
+ defer file.close();
+ const stat = file.stat() catch |e| help(e);
- return file.readToEndAlloc(allocator, stat.size) catch |e| help(e);
- }
+ return file.readToEndAlloc(allocator, stat.size) catch |e| help(e);
+ }
- pub fn stdin() Self {
- return Self {
- .name = "[stdin]",
- .file = std.io.getStdIn(),
- };
- }
+ pub fn stdin() Self {
+ return Self {
+ .name = "[stdin]",
+ .file = std.io.getStdIn(),
+ };
+ }
- pub fn stdout() Self {
- return Self {
- .name = "[stdout]",
- .file = std.io.getStdOut(),
- };
- }
+ pub fn stdout() Self {
+ return Self {
+ .name = "[stdout]",
+ .file = std.io.getStdOut(),
+ };
+ }
};
pub const BenchmarkArgs = struct {
- input: Entry,
- grammar: Grammar,
- entry: []const u8,
+ input: Entry,
+ grammar: Grammar,
+ entry: []const u8,
+ csv: bool,
};
pub const GenerateArgs = struct {
- count: usize,
- min_length: usize,
- output: Entry,
- grammar: Grammar,
- entry: []const u8,
+ count: usize,
+ min_length: usize,
+ output: Entry,
+ grammar: Grammar,
+ entry: []const u8,
};
pub const Args = union(Mode) {
- const Self = @This();
+ const Self = @This();
- benchmark: BenchmarkArgs,
- generate: GenerateArgs,
+ benchmark: BenchmarkArgs,
+ generate: GenerateArgs,
- pub fn parse(allocator: std.mem.Allocator) Self {
- var args = std.process.args();
- _ = args.next();
+ pub fn parse(allocator: std.mem.Allocator) Self {
+ var args = std.process.args();
+ _ = args.next();
- const mode = parse_enum(Mode, check(args.next()));
+ const mode = parse_enum(Mode, check(args.next()));
- const text = Entry.read_file(check(args.next()), allocator);
- defer allocator.free(text);
+ const text = Entry.read_file(check(args.next()), allocator);
+ defer allocator.free(text);
- switch (mode) {
- .benchmark => {
- var input: ?Entry = null;
- var entry: []const u8 = "main";
+ switch (mode) {
+ .benchmark => {
+ var input: ?Entry = null;
+ var entry: []const u8 = "main";
+ var csv = false;
- while (args.next()) |arg| {
- if (check_flags(arg, &[_][]const u8 { "-i", "--input" })) {
- input = Entry.open(check(args.next()), false);
- } else if (check_flags(arg, &[_][]const u8 { "-e", "--entry" })) {
- entry = check(args.next());
- } else help(error.InvalidArgument);
- }
+ while (args.next()) |arg| {
+ if (check_flags(arg, &[_][]const u8 { "-i", "--input" })) {
+ input = Entry.open(check(args.next()), false);
+ } else if (check_flags(arg, &[_][]const u8 { "-e", "--entry" })) {
+ entry = check(args.next());
+ } else if (check_flags(arg, &[_][]const u8 { "--csv" })) {
+ csv = true;
+ } else help(error.InvalidArgument);
+ }
- const grammar = Grammar.parse(
- entry,
- text,
- allocator
- ) catch |e| help(e);
+ const grammar = Grammar.parse(
+ entry,
+ text,
+ allocator
+ ) catch |e| help(e);
- return Self {
- .benchmark = .{
- .input = input orelse Entry.stdin(),
- .grammar = grammar,
- .entry = entry,
- },
- };
- },
+ return Self {
+ .benchmark = .{
+ .input = input orelse Entry.stdin(),
+ .grammar = grammar,
+ .entry = entry,
+ .csv = csv,
+ },
+ };
+ },
- .generate => {
- var count: usize = 1;
- var output: ?Entry = null;
- var min_length: usize = 0;
- var entry: []const u8 = "main";
+ .generate => {
+ var count: usize = 1;
+ var output: ?Entry = null;
+ var min_length: usize = 0;
+ var entry: []const u8 = "main";
- while (args.next()) |arg| {
- if (check_flags(arg, &[_][]const u8 { "-o", "--output" })) {
- output = Entry.open(check(args.next()), true);
- } 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" })) {
- min_length = 1;
- } else if (check_flags(arg, &[_][]const u8 { "-m", "--min-length" })) {
- min_length = parse_int(check(args.next()));
- } else if (check_flags(arg, &[_][]const u8 { "-e", "--entry" })) {
- entry = check(args.next());
- } else help(error.InvalidArgument);
- }
+ while (args.next()) |arg| {
+ if (check_flags(arg, &[_][]const u8 { "-o", "--output" })) {
+ output = Entry.open(check(args.next()), true);
+ } 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" })) {
+ min_length = 1;
+ } else if (check_flags(arg, &[_][]const u8 { "-m", "--min-length" })) {
+ min_length = parse_int(check(args.next()));
+ } else if (check_flags(arg, &[_][]const u8 { "-e", "--entry" })) {
+ entry = check(args.next());
+ } else help(error.InvalidArgument);
+ }
- const grammar = Grammar.parse(
- entry,
- text,
- allocator
- ) catch |e| help(e);
+ const grammar = Grammar.parse(
+ entry,
+ text,
+ allocator
+ ) catch |e| help(e);
- return Self {
- .generate = .{
- .count = count,
- .min_length = min_length,
- .output = output orelse Entry.stdout(),
- .grammar = grammar,
- .entry = entry,
- },
- };
- },
- }
- }
+ return Self {
+ .generate = .{
+ .count = count,
+ .min_length = min_length,
+ .output = output orelse Entry.stdout(),
+ .grammar = grammar,
+ .entry = entry,
+ },
+ };
+ },
+ }
+ }
- pub fn deinit(self: *Self) void {
- switch (self.*) {
- .benchmark => |*rec| {
- rec.grammar.deinit();
- },
- .generate => |*gen| {
- gen.grammar.deinit();
- }
- }
- }
+ pub fn deinit(self: *Self) void {
+ switch (self.*) {
+ .benchmark => |*rec| {
+ rec.grammar.deinit();
+ },
+ .generate => |*gen| {
+ gen.grammar.deinit();
+ }
+ }
+ }
};
diff --git a/src/command/benchmark.zig b/src/command/benchmark.zig
index 98ec49f..bbb8cb7 100644
--- a/src/command/benchmark.zig
+++ b/src/command/benchmark.zig
@@ -2,149 +2,189 @@ const std = @import("std");
const root = @import("../main.zig");
const BenchmarkArgs = root.argument.BenchmarkArgs;
const recognizer = root.recognizer;
+const Pex = @import("../pex/root.zig");
fn write_result(
- writer: anytype,
- is_tty: bool,
- name: []const u8,
- index: usize,
- accepted: bool,
- elapsed: u64,
- throughput: f64,
+ writer: anytype,
+ is_tty: bool,
+ name: []const u8,
+ index: usize,
+ result: recognizer.Result,
+ elapsed: u64,
+ throughput: f64,
) !void {
- if (is_tty) {
- try writer.print("{s}[{}] {s}\x1b[0m ({}, {d:.2} tps)\n", .{
- name,
- index,
- if (accepted) "\x1b[32maccept"
- else "\x1b[31mreject",
- std.fmt.fmtDuration(elapsed),
- throughput,
- });
- } else {
- try writer.print("{s}[{}] {s} ({}, {d:.2} tps)\n", .{
- name,
- index,
- if (accepted) "accept"
- else "reject",
- std.fmt.fmtDuration(elapsed),
- throughput,
- });
- }
+ if (is_tty) {
+ try writer.print("{s}[{}] {s}\x1b[0m ({:.2}, {d:.2} tps, {})\n", .{
+ name,
+ index,
+ if (result.is_accepted) "\x1b[32maccept"
+ else "\x1b[31mreject",
+ std.fmt.fmtDuration(elapsed),
+ throughput,
+ result.info,
+ });
+ } else {
+ try writer.print("{s}[{}] {s} ({:.2}, {d:.2} tps, {})\n", .{
+ name,
+ index,
+ if (result.is_accepted) "accept"
+ else "reject",
+ std.fmt.fmtDuration(elapsed),
+ throughput,
+ result.info,
+ });
+ }
+}
+
+fn write_result_as_csv(
+ writer: anytype,
+ index: usize,
+ input_length: usize,
+ result: recognizer.Result,
+ elapsed: u64,
+ throughput: f64,
+) !void {
+ try writer.print("{},{},{d:.2},{d:.2},{:.2},{}\n", .{
+ index,
+ input_length,
+ elapsed,
+ throughput,
+ result.info.max_heap_size,
+ result.info.number_of_nodes,
+ });
}
fn write_summary(
- writer: anytype,
- is_tty: bool,
- total: usize,
- accepted: usize,
- total_time: u64,
- throughput: struct { f64, f64, f64 },
+ writer: anytype,
+ is_tty: bool,
+ total: usize,
+ accepted: usize,
+ total_time: u64,
+ throughput: struct { f64, f64, f64 },
) !void {
- const min, const max, const avg = throughput;
+ const min, const max, const avg = throughput;
- if (is_tty) {
- try writer.print("finished {} ({} \x1b[32maccepted\x1b[0m {d:.2} \x1b[31mrejected\x1b[0m)", .{
- total,
- accepted,
- total - accepted,
- });
- } else {
- try writer.print("finished {} ({} accepted {} rejected)", .{
- total,
- accepted,
- total - accepted,
- });
- }
+ if (is_tty) {
+ try writer.print("finished {} ({} \x1b[32maccepted\x1b[0m {} \x1b[31mrejected\x1b[0m)", .{
+ total,
+ accepted,
+ total - accepted,
+ });
+ } else {
+ try writer.print("finished {} ({} accepted {} rejected)", .{
+ total,
+ accepted,
+ total - accepted,
+ });
+ }
- try writer.print(" in {} (min: {d:.5} tps, max: {d:.2} tps, average: {d:.2} tps)\n", .{
- std.fmt.fmtDuration(total_time),
- min,
- max,
- avg,
- });
+ try writer.print(" in {} (min: {d:.5} tps, max: {d:.2} tps, average: {d:.2} tps)\n", .{
+ std.fmt.fmtDuration(total_time),
+ min,
+ max,
+ avg,
+ });
}
fn min_max_avg(values: []f64) struct { f64, f64, f64 } {
- var min: f64 = -1;
- var max: f64 = 0;
- var sum: f64 = 0;
+ var min: f64 = -1;
+ var max: f64 = 0;
+ var sum: f64 = 0;
- for (values) |value| {
- min = if (min < 0) value else @min(min, value);
- max = @max(max, value);
- sum += value;
- }
+ for (values) |value| {
+ min = if (min < 0) value else @min(min, value);
+ max = @max(max, value);
+ sum += value;
+ }
- return .{ min, max, sum / @as(f64, @floatFromInt(values.len)) };
+ return .{ min, max, sum / @as(f64, @floatFromInt(values.len)) };
}
pub fn benchmark(args: *BenchmarkArgs, allocator: std.mem.Allocator) !void {
- const stdout = std.io.getStdOut();
- const writer = stdout.writer();
+ const stdout = std.io.getStdOut();
+ const writer = stdout.writer();
+
+ if (args.csv) {
+ try writer.print("index,input length,duration [ns],throughput,max heap size [bytes],number of nodes\n", .{});
+ }
+
+ var bufreader = std.io.bufferedReader(args.input.file.reader());
+ var reader = bufreader.reader();
+ var index: usize = 0;
+ const stderr = std.io.getStdErr();
- var bufreader = std.io.bufferedReader(args.input.file.reader());
- var reader = bufreader.reader();
- var index: usize = 0;
- const stderr = std.io.getStdErr();
+ var throughputs = std.ArrayList(f64).init(allocator);
+ defer throughputs.deinit();
- var throughputs = std.ArrayList(f64).init(allocator);
- defer throughputs.deinit();
+ if (args.input.file.isTty()) {
+ try stderr.writeAll("> ");
+ }
- if (args.input.file.isTty()) {
- try stderr.writeAll("> ");
- }
+ var read_arena = std.heap.ArenaAllocator.init(allocator);
+ defer read_arena.deinit();
+ var number_of_accepted: usize = 0;
+ var total_time: u64 = 0;
+ var timer = try std.time.Timer.start();
- var read_arena = std.heap.ArenaAllocator.init(allocator);
- defer read_arena.deinit();
- var number_of_accepted: usize = 0;
- var total_time: u64 = 0;
- var timer = try std.time.Timer.start();
+ const pex: Pex = try .compile(&args.grammar, allocator);
- while (try reader.readUntilDelimiterOrEofAlloc(
- read_arena.allocator(),
- '\n',
- std.math.maxInt(usize)
- )) |buffer| {
+ while (try reader.readUntilDelimiterOrEofAlloc(
+ read_arena.allocator(),
+ '\n',
+ std.math.maxInt(usize)
+ )) |buffer| {
- const trimmed = std.mem.trim(u8, buffer, &std.ascii.whitespace);
+ const trimmed = std.mem.trim(u8, buffer, &std.ascii.whitespace);
- timer.reset();
- const accepted = try recognizer.check(
- &args.grammar,
- trimmed,
- allocator
- );
+ timer.reset();
+ const result = try recognizer.check(
+ &pex,
+ trimmed,
+ allocator
+ );
- const elapsed = timer.read();
- const throughput = @as(f64, @floatFromInt(trimmed.len)) / (@as(f64, @floatFromInt(elapsed)) / std.time.ns_per_s);
- try throughputs.append(throughput);
+ const elapsed = timer.read();
+ const throughput = @as(f64, @floatFromInt(trimmed.len)) / (@as(f64, @floatFromInt(elapsed)) / std.time.ns_per_s);
+ try throughputs.append(throughput);
- try write_result(
- writer,
- stdout.isTty(),
- args.input.name,
- index,
- accepted,
- elapsed,
- throughput,
- );
+ if (args.csv) {
+ try write_result_as_csv(
+ writer,
+ index,
+ trimmed.len,
+ result,
+ elapsed,
+ throughput,
+ );
+ } else {
+ try write_result(
+ writer,
+ stdout.isTty(),
+ args.input.name,
+ index,
+ result,
+ elapsed,
+ throughput,
+ );
+ }
- index += 1;
- number_of_accepted += @intFromBool(accepted);
- total_time += elapsed;
+ index += 1;
+ number_of_accepted += @intFromBool(result.is_accepted);
+ total_time += elapsed;
- if (args.input.file.isTty()) {
- try stderr.writeAll("> ");
- }
- }
+ if (args.input.file.isTty()) {
+ try stderr.writeAll("> ");
+ }
+ }
- try write_summary(
- writer,
- stdout.isTty(),
- index,
- number_of_accepted,
- total_time,
- min_max_avg(throughputs.items)
- );
+ if (!args.csv) {
+ try write_summary(
+ writer,
+ stdout.isTty(),
+ index,
+ number_of_accepted,
+ total_time,
+ min_max_avg(throughputs.items)
+ );
+ }
}
diff --git a/src/gss.zig b/src/gss.zig
index 12b3b46..aa638a9 100644
--- a/src/gss.zig
+++ b/src/gss.zig
@@ -1,88 +1,88 @@
const std = @import("std");
pub fn Node(T: type) type {
- return struct {
- const Self = @This();
+ return struct {
+ const Self = @This();
- parents: *std.ArrayList(*Self),
- state: T,
+ parents: *std.ArrayList(*Self),
+ state: T,
- pub fn init(state: T, allocator: std.mem.Allocator) !Self {
- const parents = try allocator.create(std.ArrayList(*Self));
- parents.* = std.ArrayList(*Self).init(allocator);
+ pub fn init(state: T, allocator: std.mem.Allocator) !Self {
+ const parents = try allocator.create(std.ArrayList(*Self));
+ parents.* = std.ArrayList(*Self).init(allocator);
- return Self {
- .state = state,
- .parents = parents,
- };
- }
+ return Self {
+ .state = state,
+ .parents = parents,
+ };
+ }
- pub fn clone(self: *Self, state: T) !Self {
- return Self {
- .parents = self.parents,
- .state = state,
- };
- }
+ pub fn clone(self: *Self, state: T) !Self {
+ return Self {
+ .parents = self.parents,
+ .state = state,
+ };
+ }
- pub fn push(self: *Self, state: T) !Self {
- const parents = try self.parents.allocator.create(std.ArrayList(*Self));
- parents.* = std.ArrayList(*Self).init(self.parents.allocator);
- var other = Self {
- .parents = parents,
- .state = state,
- };
+ pub fn push(self: *Self, state: T) !Self {
+ const parents = try self.parents.allocator.create(std.ArrayList(*Self));
+ parents.* = std.ArrayList(*Self).init(self.parents.allocator);
+ var other = Self {
+ .parents = parents,
+ .state = state,
+ };
- try other.parents.append(self);
+ try other.parents.append(self);
- return other;
- }
+ return other;
+ }
- pub fn format(
- self: *const Self,
- comptime fmt: []const u8,
- options: std.fmt.FormatOptions,
- writer: anytype,
- ) !void {
- _ = fmt;
- _ = options;
+ 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});
- }
- };
+ try writer.print("Node {{ {} }}", .{self.state});
+ }
+ };
}
pub fn Graph(T: type) type {
- return struct {
- const Self = @This();
+ return struct {
+ const Self = @This();
- allocator: std.mem.Allocator,
- number_of_nodes: usize = 0,
- number_of_clones: usize = 0,
+ 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 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 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);
- return node;
- }
+ 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);
+ return node;
+ }
- 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;
- }
- };
+ 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/main.zig b/src/main.zig
index d9aee77..5f35d8f 100644
--- a/src/main.zig
+++ b/src/main.zig
@@ -32,4 +32,5 @@ pub fn main() !void {
test {
std.testing.refAllDecls(@This());
+ std.testing.refAllDecls(@import("pex/root.zig"));
}
diff --git a/src/pex/block.zig b/src/pex/block.zig
new file mode 100644
index 0000000..3ae690e
--- /dev/null
+++ b/src/pex/block.zig
@@ -0,0 +1,90 @@
+const std = @import("std");
+const NonTerminal = @import("../non-terminal.zig");
+const Rule = @import("../rule.zig");
+const Node = @import("node.zig");
+
+const Self = @This();
+
+id: usize,
+heads: std.ArrayListUnmanaged(*Node) = .empty,
+
+pub fn compile(
+ non_terminal: *NonTerminal,
+ node_pool: *std.heap.MemoryPool(Node),
+ allocator: std.mem.Allocator
+) !Self {
+ var self: Self = .{ .id = non_terminal.id };
+
+ for (non_terminal.rules()) |*rule| {
+ try self.heads.append(allocator, try compile_variant(rule, node_pool));
+ }
+
+ return self;
+}
+
+pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {
+ for (self.heads.items) |head| {
+ head.deinit();
+ }
+ self.heads.deinit(allocator);
+ self.* = undefined;
+}
+
+pub fn clone(
+ self: *const Self,
+ allocator: std.mem.Allocator,
+ node_pool: *std.heap.MemoryPool(Node),
+) !Self {
+ var self_clone = Self{
+ .id = self.id,
+ .heads = try .initCapacity(allocator, self.heads.items.len),
+ };
+ errdefer self_clone.deinit(allocator);
+
+ for (self.heads.items) |head| {
+ try self_clone.heads.append(allocator, try head.clone(node_pool));
+ }
+
+ return self_clone;
+}
+
+fn compile_variant(
+ rule: *Rule,
+ node_pool: *std.heap.MemoryPool(Node),
+) !*Node {
+ const first = blk: {
+ for (rule.items, 0..) |item, index| {
+ switch (item) {
+ .terminal, .non_terminal => break :blk index,
+ .epsilon => {},
+ }
+ }
+
+ break :blk rule.items.len;
+ };
+
+ if (first == rule.items.len) {
+ return try Node.create(.{ .@"return" = void{} }, node_pool);
+ }
+
+ const head = switch (rule.items[0]) {
+ .terminal => |c| try Node.create(.{ .@"check" = c }, node_pool),
+ .non_terminal => |id| try Node.create(.{ .@"call" = id }, node_pool),
+ .epsilon => unreachable,
+ };
+
+ var current = head;
+ for (rule.items[1..]) |item| {
+ const node = switch (item) {
+ .terminal => |c| try Node.create(.{ .@"check" = c }, node_pool),
+ .non_terminal => |id| try Node.create(.{ .@"call" = id }, node_pool),
+ .epsilon => continue,
+ };
+ current.next = node;
+ current = node;
+ }
+
+ current.next = try Node.create(.{ .@"return" = void{} }, node_pool);
+
+ return head;
+}
diff --git a/src/pex/instruction.zig b/src/pex/instruction.zig
new file mode 100644
index 0000000..5edffef
--- /dev/null
+++ b/src/pex/instruction.zig
@@ -0,0 +1,9 @@
+const std = @import("std");
+const Node = @import("node.zig");
+
+pub const Instruction = union(enum) {
+ check: u8,
+ call: usize,
+ jump: *std.ArrayListUnmanaged(*Node),
+ @"return": void,
+};
diff --git a/src/pex/node.zig b/src/pex/node.zig
new file mode 100644
index 0000000..7abb274
--- /dev/null
+++ b/src/pex/node.zig
@@ -0,0 +1,36 @@
+const std = @import("std");
+const Instruction = @import("instruction.zig").Instruction;
+
+const Self = @This();
+
+instruction: Instruction,
+next: ?*Self = null,
+
+pub fn create(instruction: Instruction, node_pool: *std.heap.MemoryPool(Self)) !*Self {
+ const node = try node_pool.create();
+ node.* = .{ .instruction = instruction };
+ return node;
+}
+
+pub fn deinit(self: *Self) void {
+ if (self.next) |next| {
+ next.deinit();
+ }
+ self.* = undefined;
+}
+
+pub fn clone(
+ self: *Self,
+ node_pool: *std.heap.MemoryPool(Self),
+) !*Self {
+ const self_clone = try node_pool.create();
+ self_clone.instruction = self.instruction;
+
+ if (self.next) |next| {
+ self_clone.next = try next.clone(node_pool);
+ } else {
+ self_clone.next = null;
+ }
+
+ return self_clone;
+}
diff --git a/src/pex/optimizer/root.zig b/src/pex/optimizer/root.zig
new file mode 100644
index 0000000..68ce968
--- /dev/null
+++ b/src/pex/optimizer/root.zig
@@ -0,0 +1,38 @@
+const std = @import("std");
+const Block = @import("../block.zig");
+const Node = @import("../node.zig");
+const Rule = @import("../../rule.zig");
+
+pub fn optimize_block(
+ blocks: []Block,
+ raw: *Block,
+ target: *Block,
+ node_pool: *std.heap.MemoryPool(Node),
+ allocator: std.mem.Allocator,
+) !void {
+ target.* = try raw.clone(allocator, node_pool);
+ _ = blocks;
+
+ for (target.heads.items) |head| {
+ try hard_link_right_recursion(target, head);
+ }
+}
+
+pub fn hard_link_right_recursion(
+ block: *Block,
+ current: *Node,
+) !void {
+ switch (current.instruction) {
+ .call => |id| if (id == block.id) {
+ if (current.next.?.instruction == .@"return") {
+ current.instruction = .{ .jump = &block.heads };
+ return;
+ }
+ },
+ else => {},
+ }
+
+ if (current.next) |next| {
+ try hard_link_right_recursion(block, next);
+ }
+}
diff --git a/src/pex/root.zig b/src/pex/root.zig
new file mode 100644
index 0000000..c653ca5
--- /dev/null
+++ b/src/pex/root.zig
@@ -0,0 +1,163 @@
+const std = @import("std");
+pub const Block = @import("block.zig");
+pub const Instruction = @import("instruction.zig").Instruction;
+pub const Node = @import("node.zig");
+pub const Grammar = @import("../grammar.zig");
+const optimizer = @import("optimizer/root.zig");
+
+const Self = @This();
+
+grammar: *Grammar,
+blocks: []Block,
+node_pool: std.heap.MemoryPool(Node),
+
+pub fn compile(grammar: *Grammar, allocator: std.mem.Allocator) !Self {
+ const raw_blocks = try allocator.alloc(Block, grammar.non_terminals.len);
+ defer {
+ for (raw_blocks) |*block| {
+ block.deinit(allocator);
+ }
+ allocator.free(raw_blocks);
+ }
+
+ var raw_node_pool: std.heap.MemoryPool(Node) = .init(allocator);
+ defer raw_node_pool.deinit();
+
+ for (raw_blocks, grammar.non_terminals) |*block, *non_terminal| {
+ block.* = try .compile(non_terminal, &raw_node_pool, allocator);
+ }
+
+ var self: Self = .{
+ .grammar = grammar,
+ .blocks = try allocator.alloc(Block, grammar.non_terminals.len),
+ .node_pool = .init(allocator),
+ };
+
+ for (self.blocks, raw_blocks) |*optimized, *raw| {
+ try optimizer.optimize_block(raw_blocks, raw, optimized, &self.node_pool, allocator);
+ }
+
+ return self;
+}
+
+pub fn deinit(self: *Self, allocator: std.mem.Allocator) void {
+ for (self.blocks) |*block| {
+ block.deinit(allocator);
+ }
+
+ allocator.free(self.blocks);
+ self.node_pool.deinit();
+ self.* = undefined;
+}
+
+pub fn entry_point(self: *const Self) *Block {
+ return &self.blocks[0];
+}
+
+test "terminals-single" {
+ const allocator = std.testing.allocator;
+
+ var grammar = try Grammar.parse("S", "S -> 'a'", allocator);
+ defer grammar.deinit();
+
+ var pex = try Self.compile(&grammar, allocator);
+ defer pex.deinit(allocator);
+
+ try std.testing.expectEqual(2, pex.blocks.len);
+ try std.testing.expectEqual(1, pex.blocks[1].heads.items.len);
+ try std.testing.expectEqual(
+ Instruction{ .check = 'a' },
+ pex.blocks[1].heads.items[0].instruction
+ );
+ try std.testing.expectEqual(1, pex.blocks[1].heads.items[0].next.items.len);
+ try std.testing.expectEqual(
+ Instruction{ .@"return" = void{} },
+ pex.blocks[1].heads.items[0].next.items[0].instruction
+ );
+}
+
+test "terminals-single-thread" {
+ const allocator = std.testing.allocator;
+
+ var grammar = try Grammar.parse("S", "S -> 'abc'", allocator);
+ defer grammar.deinit();
+
+ var pex = try Self.compile(&grammar, allocator);
+ defer pex.deinit(allocator);
+
+ try std.testing.expectEqual(2, pex.blocks.len);
+ try std.testing.expectEqual(1, pex.blocks[1].heads.items.len);
+
+ var current = pex.blocks[1].heads.items[0];
+ for ("abc") |c| {
+ try std.testing.expectEqual(
+ Instruction{ .check = c },
+ current.instruction,
+ );
+ try std.testing.expectEqual(1, current.next.items.len);
+ current = current.next.items[0];
+ }
+
+ try std.testing.expectEqual(
+ Instruction{ .@"return" = void{} },
+ current.instruction,
+ );
+}
+
+test "direct-left-recursion" {
+ const allocator = std.testing.allocator;
+
+ var grammar = try Grammar.parse("S", "S -> 'a' | S 'a'", allocator);
+ defer grammar.deinit();
+
+ var pex = try Self.compile(&grammar, allocator);
+ defer pex.deinit(allocator);
+
+ try std.testing.expectEqual(2, pex.blocks.len);
+ try std.testing.expectEqual(1, pex.blocks[1].heads.items.len);
+
+ try std.testing.expectEqual(
+ Instruction{ .check = 'a' },
+ pex.blocks[1].heads.items[0].instruction,
+ );
+
+ try std.testing.expectEqual(
+ Instruction{ .@"return" = void{} },
+ pex.blocks[1].heads.items[0].next.items[0].instruction,
+ );
+
+ try std.testing.expectEqual(
+ Instruction{ .check = 'a' },
+ pex.blocks[1].heads.items[0].next.items[1].next.items[0].instruction,
+ );
+
+ try std.testing.expectEqual(
+ Instruction{ .@"return" = void{} },
+ pex.blocks[1]
+ .heads.items[0]
+ .next.items[1]
+ .next.items[0]
+ .next.items[0]
+ .instruction,
+ );
+
+ try std.testing.expect(
+ pex.blocks[1]
+ .heads.items[0]
+ .next.items[1]
+ .next.items[0]
+ .next.items[1]
+ .instruction == .jump
+ );
+
+ try std.testing.expectEqual(
+ Instruction{ .@"return" = void{} },
+ pex.blocks[1]
+ .heads.items[0]
+ .next.items[1]
+ .next.items[0]
+ .next.items[1]
+ .next.items[0]
+ .instruction,
+ );
+}
diff --git a/src/recognizer.zig b/src/recognizer.zig
index 1934750..6af7de1 100644
--- a/src/recognizer.zig
+++ b/src/recognizer.zig
@@ -5,295 +5,289 @@ const Rule = @import("rule.zig");
const Character = @import("character.zig").Character;
const Generator = @import("generator.zig").Generator;
const gss = @import("gss.zig");
+const Pex = @import("pex/root.zig");
-const State = struct {
- const Self = @This();
+pub const Result = struct {
+ const Info = struct {
+ const Self = @This();
- pub const Context = struct {
- pub fn hash(_: @This(), s: Self) u64 {
- return std.hash.Wyhash.hash(0, std.mem.asBytes(&s));
- }
+ max_heap_size: usize,
+ number_of_nodes: usize,
- pub fn eql(_: @This(), a: Self, b: Self) bool {
- return a.id == b.id
- and a.rule_index == b.rule_index
- and a.inner_position == b.inner_position;
- }
- };
+ pub fn format(
+ self: *const Self,
+ comptime fmt: []const u8,
+ options: std.fmt.FormatOptions,
+ writer: anytype,
+ ) !void {
+ _ = fmt;
+ _ = options;
- id: usize,
- rule_index: usize,
- inner_position: usize,
+ try writer.print("{:.2}, {} nodes", .{
+ std.fmt.fmtIntSizeBin(self.max_heap_size),
+ self.number_of_nodes,
+ });
+ }
+ };
- pub inline fn next(self: *const Self) Self {
- var other = self.*;
- other .inner_position += 1;
- return other;
- }
-
- pub inline fn is_at_end_of_rule(self: *Self, rule: Rule) bool {
- return self.inner_position == rule.items.len;
- }
-
- pub fn format(
- self: *const Self,
- comptime fmt: []const u8,
- options: std.fmt.FormatOptions,
- writer: anytype,
- ) !void {
- _ = fmt;
- _ = options;
-
- try writer.print("[ {}, {}, {} ]", .{
- self.id,
- self.rule_index,
- self.inner_position,
- });
- }
-
- pub fn debug(self: *const Self, grammar: *Grammar) void {
- const rule = grammar.non_terminal_by_id(self.id).rules()[self.rule_index];
- std.debug.print("{*} state (", .{ self });
-
- for (rule.items, 0..) |char, index| {
- if (index == self.inner_position) {
- std.debug.print("○", .{});
- }
-
- std.debug.print("{}", .{char});
- }
-
- if (rule.items.len == self.inner_position) {
- std.debug.print("○", .{});
- }
- std.debug.print(")\n", .{});
- }
+ is_accepted: bool,
+ info: Info,
};
-pub fn reaches_end_of_entry(grammar: *Grammar, node: *gss.Node(State)) bool {
- const rule = grammar.non_terminal_by_id(node.state.id).rules()[node.state.rule_index];
+fn OpaqueContext(T: type) type {
+ return struct {
+ pub fn hash(_: @This(), h: T) u64 {
+ return @intFromPtr(h);
+ }
- if (node.parents.items.len == 0) {
- return true;
- }
+ pub fn eql(_: @This(), a: T, b: T) bool {
+ return a == b;
+ }
+ };
+}
- for (rule.items[node.state.inner_position..]) |character| {
- switch (character) {
- .terminal => return false,
- .non_terminal => |n| {
- if (!grammar.non_terminal_by_id(n).first.is_set(Character.EPSILON)) {
- return false;
- }
- },
- else => {}
- }
- }
- for (node.parents.items) |parent| {
- parent.state = parent.state.next();
- if (reaches_end_of_entry(grammar, parent)) {
- return true;
- }
- }
+pub fn reaches_end_of_entry(grammar: *Grammar, node: *gss.Node(*Pex.Node)) bool {
+ if (node.parents.items.len == 0) {
+ return true;
+ }
- return false;
-}
+ var pex_node = node.state;
+ while (pex_node.next) |next| : (pex_node = next) {
+ switch (pex_node.instruction) {
+ .check => return false,
+ .call => |n| {
+ if (!grammar.non_terminal_by_id(n).first.is_set(Character.EPSILON)) {
+ return false;
+ }
+ },
+ else => {},
+ }
+ }
-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();
+ for (node.parents.items) |parent| {
+ if (parent.state.next) |next| {
+ parent.state = next;
- 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];
+ if (reaches_end_of_entry(grammar, parent)) {
+ return true;
+ }
+ }
+ }
- var graph = gss.Graph(State).init(allocator);
+ return false;
+}
- for (0..entry.rules().len) |index| {
- const id = try graph.add_toplevel(State {
- .id = entry.id,
- .rule_index = index,
- .inner_position = 0,
- });
+pub fn check(
+ pex: *const Pex,
+ input: []const u8,
+ inner_allocator: std.mem.Allocator
+) !Result {
+ var arena = std.heap.ArenaAllocator.init(inner_allocator);
+ defer arena.deinit();
+ const allocator = arena.allocator();
- try processing_queue.append(id);
- }
+ var queues = [2]std.ArrayList(*gss.Node(*Pex.Node)) {
+ std.ArrayList(*gss.Node(*Pex.Node)).init(allocator),
+ std.ArrayList(*gss.Node(*Pex.Node)).init(allocator),
+ };
+ defer for (queues) |queue| queue.deinit();
+ var processing_queue = &queues[0];
- var node_cache = std.HashMap(State, *gss.Node(State), State.Context, 80).init(allocator);
- var forward_queue = std.ArrayList(struct { State, *gss.Node(State) }).init(allocator);
+ var graph = gss.Graph(*Pex.Node).init(allocator);
- var next_processing_queue = &queues[1];
+ for (pex.entry_point().heads.items) |head| {
+ try processing_queue.append(try graph.add_toplevel(head));
+ }
- for (input) |character| {
- for (processing_queue.items) |base| {
- try forward_queue.append(.{ base.state, base });
+ var node_cache = std.HashMap(
+ *Pex.Node,
+ *gss.Node(*Pex.Node),
+ OpaqueContext(*Pex.Node),
+ 80
+ ).init(allocator);
- while (forward_queue.pop()) |checkpoint| {
- const last_state, const last_node = checkpoint;
- const rule = grammar.non_terminal_by_id(last_state.id).rules()[last_state.rule_index];
+ var forward_queue = std.ArrayList(struct { *Pex.Node, *gss.Node(*Pex.Node) }).init(allocator);
+ var next_processing_queue = &queues[1];
- if (last_state.inner_position == rule.items.len) {
- for (last_node.parents.items) |parent| {
- try forward_queue.append(.{parent.state.next(), parent});
- }
+ for (input) |character| {
+ for (processing_queue.items) |base| {
+ try forward_queue.append(.{ base.state, base });
+ try node_cache.put(base.state, base);
- continue;
- }
+ while (forward_queue.pop()) |checkpoint| {
+ const pex_node, const last_node = checkpoint;
- switch (rule.items[last_state.inner_position]) {
- .terminal => |t| if (t == character) {
- const node = try graph.clone(last_node, last_state.next());
- try next_processing_queue.append(node);
- },
- .non_terminal => |n| {
- const non_terminal = grammar.non_terminal_by_id(n);
- for (grammar.non_terminal_by_id(n).rules(), 0..) |child_rule, rule_index| {
- if (
- child_rule.first.is_set(character) or
- (child_rule.first.is_set(Character.EPSILON) and non_terminal.follows.is_set(character))
- ) {
+ switch (pex_node.instruction) {
+ .check => |t| if (t == character) {
+ if (pex_node.next) |next| {
+ const node = try graph.clone(last_node, next);
+ try next_processing_queue.append(node);
+ }
+ },
+ .@"return" => {
+ for (last_node.parents.items) |parent| {
+ if (parent.state.next) |next| {
+ try forward_queue.append(.{next, parent});
+ }
+ }
+ },
+ .call => |id| {
+ const non_terminal = pex.grammar.non_terminal_by_id(id);
+ for (non_terminal.rules(), pex.blocks[id].heads.items) |child_rule, head| {
+ if (
+ child_rule.first.is_set(character) or
+ (child_rule.first.is_set(Character.EPSILON) and non_terminal.follows.is_set(character))
+ ) {
- const state = State {
- .id = n,
- .rule_index = rule_index,
- .inner_position = 0,
- };
+ if (node_cache.get(head)) |parent| {
+ try parent.parents.append(last_node);
+ } else {
+ const parent = try graph.clone(last_node, pex_node);
+ const next = try graph.push(parent, head);
+ try node_cache.put(head, next);
+ try forward_queue.append(.{head, next});
+ }
+ }
+ }
+ },
+ .jump => |jump_next| {
+ if (pex_node.next) |next| {
+ try forward_queue.append(.{next, last_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 => {
- try forward_queue.append(.{last_state.next(), last_node});
- },
- }
- }
+ for (jump_next.items) |next| {
+ try forward_queue.append(.{next, last_node});
+ }
+ },
+ }
+ }
- node_cache.clearRetainingCapacity();
- forward_queue.clearRetainingCapacity();
- }
+ node_cache.clearRetainingCapacity();
+ forward_queue.clearRetainingCapacity();
+ }
- const swap = processing_queue;
- processing_queue = next_processing_queue;
- next_processing_queue = swap;
- next_processing_queue.clearRetainingCapacity();
- }
+ const swap = processing_queue;
+ processing_queue = next_processing_queue;
+ next_processing_queue = swap;
+ next_processing_queue.clearRetainingCapacity();
+ }
- for (processing_queue.items) |node| {
- if (reaches_end_of_entry(grammar, node)) {
- return true;
- }
- }
+ for (processing_queue.items) |node| {
+ if (reaches_end_of_entry(pex.grammar, node)) {
+ return .{
+ .is_accepted = true,
+ .info = .{
+ .max_heap_size = arena.queryCapacity(),
+ .number_of_nodes = graph.number_of_nodes,
+ },
+ };
+ }
+ }
- return false;
+ return .{
+ .is_accepted = false,
+ .info = .{
+ .max_heap_size = arena.queryCapacity(),
+ .number_of_nodes = graph.number_of_nodes,
+ },
+ };
}
test "expr" {
- const text =
- \\S -> B A
- \\A -> '+' B A
- \\A -> ''
- \\B -> D C
- \\C -> '*' D C
- \\C -> ''
- \\D -> '(' S ')'
- \\D -> 'a'
- \\D -> 'b'
- ;
+ const text =
+ \\S -> B A
+ \\A -> '+' B A
+ \\A -> ''
+ \\B -> D C
+ \\C -> '*' D C
+ \\C -> ''
+ \\D -> '(' S ')'
+ \\D -> 'a'
+ \\D -> 'b'
+ ;
- const input = "b+a*b";
+ const input = "b+a*b";
- const allocator = std.testing.allocator;
+ const allocator = std.testing.allocator;
- var grammar = try Grammar.parse("S", text, allocator);
- defer grammar.deinit();
+ var grammar = try Grammar.parse("S", text, allocator);
+ defer grammar.deinit();
- try std.testing.expect(try check(&grammar, input, allocator));
+ try std.testing.expect(try check(&grammar, input, allocator));
}
test "simple 0 - success" {
- const text =
- \\S -> A S 'd'
- \\S -> B S
- \\S -> ''
- \\A -> 'a'
- \\A -> 'c'
- \\B -> 'a'
- \\B -> 'b'
- ;
+ const text =
+ \\S -> A S 'd'
+ \\S -> B S
+ \\S -> ''
+ \\A -> 'a'
+ \\A -> 'c'
+ \\B -> 'a'
+ \\B -> 'b'
+ ;
- const input = "aad";
+ const input = "aad";
- const allocator = std.testing.allocator;
+ const allocator = std.testing.allocator;
- var grammar = try Grammar.parse("S", text, allocator);
- defer grammar.deinit();
+ var grammar = try Grammar.parse("S", text, allocator);
+ defer grammar.deinit();
- try std.testing.expect(try check(&grammar, input, allocator));
+ try std.testing.expect(try check(&grammar, input, allocator));
}
test "simple 0 - fail" {
- const text =
- \\S -> A S 'd'
- \\S -> B S
- \\S -> ''
- \\A -> 'a'
- \\A -> 'c'
- \\B -> 'a'
- \\B -> 'b'
- ;
+ const text =
+ \\S -> A S 'd'
+ \\S -> B S
+ \\S -> ''
+ \\A -> 'a'
+ \\A -> 'c'
+ \\B -> 'a'
+ \\B -> 'b'
+ ;
- const input = "accd";
+ const input = "accd";
- const allocator = std.testing.allocator;
+ const allocator = std.testing.allocator;
- var grammar = try Grammar.parse("S", text, allocator);
- defer grammar.deinit();
+ var grammar = try Grammar.parse("S", text, allocator);
+ defer grammar.deinit();
- try std.testing.expect(!try check(&grammar, input, allocator));
+ try std.testing.expect(!try check(&grammar, input, allocator));
}
test "simple 0 - fuzzy" {
- const text =
- \\S -> A S 'd'
- \\S -> B S
- \\S -> ''
- \\A -> 'a'
- \\A -> 'c'
- \\B -> 'a'
- \\B -> 'b'
- ;
+ const text =
+ \\S -> A S 'd'
+ \\S -> B S
+ \\S -> ''
+ \\A -> 'a'
+ \\A -> 'c'
+ \\B -> 'a'
+ \\B -> 'b'
+ ;
- const allocator = std.testing.allocator;
+ const allocator = std.testing.allocator;
- var grammar = try Grammar.parse("S", text, allocator);
- defer grammar.deinit();
+ var grammar = try Grammar.parse("S", text, allocator);
+ defer grammar.deinit();
- var generator = Generator(struct {
- const Self = @This();
+ var generator = Generator(struct {
+ const Self = @This();
- pub fn next(_: *Self, n: usize) usize {
- return std.crypto.random.uintLessThan(usize, n);
- }
- }){};
+ pub fn next(_: *Self, n: usize) usize {
+ return std.crypto.random.uintLessThan(usize, n);
+ }
+ }){};
- for (0..100) |_| {
- const input = try generator.sentential_from_grammar(&grammar, 1000, allocator);
- defer allocator.free(input);
+ for (0..100) |_| {
+ const input = try generator.sentential_from_grammar(&grammar, 1000, allocator);
+ defer allocator.free(input);
- try std.testing.expect(try check(&grammar, input, allocator));
- }
+ try std.testing.expect(try check(&grammar, input, allocator));
+ }
}
generated by cgit v1.2.3-70-g09d2 (git 2.53.0) at 2026-05-12 17:08:33 +0000