1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
|
const std = @import("std");
const Grammar = @import("grammar.zig");
pub fn Generator(T: type) type {
const GenError = error { MaxDepth } || std.mem.Allocator.Error;
return struct {
const Self = @This();
inner: T = .{},
pub fn sentential_from_grammar(
self: *Self,
grammar: *Grammar,
max_depth: usize,
allocator: std.mem.Allocator
) GenError![]u8 {
var string = std.ArrayList(u8).init(allocator);
while (true) {
self.generate_sentential_recursive(
grammar,
&string,
grammar.entry_point().id,
max_depth
) catch |err| switch (err) {
error.MaxDepth => {
string.clearAndFree();
continue;
},
else => return err,
};
break;
}
return string.toOwnedSlice();
}
fn generate_sentential_recursive(
self: *Self,
grammar: *Grammar,
string: *std.ArrayList(u8),
id: usize,
max_depth: usize
) GenError!void {
if (max_depth == 0) {
return error.MaxDepth;
}
const rules = grammar.non_terminal_by_id(id).rules();
const index = self.inner.next(rules.len);
const rule = rules[index];
const success = blk: {
for (rule) |character| {
switch (character) {
.terminal => |t| try string.append(t),
.non_terminal => |next_n| {
self.generate_sentential_recursive(
grammar,
string,
next_n,
max_depth - 1
) catch |err| switch (err) {
error.MaxDepth => break :blk false,
else => return err,
};
},
else => {},
}
}
break :blk true;
};
if (success) return;
return error.MaxDepth;
}
};
}
|
