1 files changed, 82 insertions, 0 deletions
diff --git a/src/generator.zig b/src/generator.zig
new file mode 100644
index 0000000..8d0c888
--- /dev/null
+++ b/src/generator.zig
@@ -0,0 +1,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().name,
+					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),
+			n: u8,
+			max_depth: usize
+		) GenError!void {
+			if (max_depth == 0) {
+				return error.MaxDepth;
+			}
+
+			const rules = grammar.non_terminal_by_name(n).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;
+		}
+	};
+}