#LL(1) parsing for Zig

1 messages · Page 1 of 1 (latest)

fathom crest
#

https://github.com/aquapi/zll1
I'm trying to write a LL(1) parser generator for Zig, similar to https://github.com/sinclairzx81/parsebox

I'm not sure how to implement recursive parsing and type inference with a similar DSL to Parsebox

Something like

const Parser = Module(.{
  .Root = Union(.{
    .end = Const(.end, "end"),
    .next = Tuple(.{
      Union(.{
        .x = Const(.x, "x"),
        .y = Const(.y, "y")
      }),
      Ref("Root")
    })
  })
}, "Root");

// Expected output type
const Root = union(enum) {
  .end: @EnumLiteral(),
  .next: struct { 
    union(enum) {
      .x: @EnumLiteral(),
      .y: @EnumLiteral()
    },
    *Root
  }
}

I have tried and it only works if the output type is acyclic which is kinda useless for parsing purposes
Please suggest as many changes as u guys can (even rewriting the whole codebase is fine)
Not using a similar DSL is fine too as long as it is composable

ionic pulsar
fathom crest
fathom crest
#

@ionic pulsar i got the DSL working tho u can check how i did it

ionic pulsar
# 
const Root = union(enum) {
    end: void,
    next: struct {
        union(enum) {
            x,
            y,
        },
        *Root,
    },
};

const ParseError = error{ OutOfMemory, NoMatch };

fn ParseResult(comptime T: type) type {
    return struct { value: T, rest: std.mem.TokenIterator(u8, .any) };
}
# 
fn parse(comptime T: type, arena: std.mem.Allocator, input: std.mem.TokenIterator(u8, .any)) ParseError!ParseResult(T) {
    switch (@typeInfo(T)) {
        .@"union" => |info| {
            inline for (info.fields) |field| switch (field.type) {
                void => {
                    var it = input;
                    if (it.next()) |tok| {
                        if (std.mem.eql(u8, tok, field.name)) {
                            return .{
                                .value = @unionInit(T, field.name, {}),
                                .rest = it,
                            };
                        }
                    }
                },
                else => {
                    if (parse(field.type, arena, input)) |res| {
                        return .{
                            .value = @unionInit(T, field.name, res.value),
                            .rest = res.rest,
                        };
                    } else |_| {}
                },
            };
            return error.NoMatch;
        },
        .@"struct" => |info| {
            var value: T = undefined;
            var rest = input;
            inline for (info.fields) |field| {
                const result = try parse(field.type, arena, rest);
                @field(value, field.name) = result.value;
                rest = result.rest;
            }
            return .{ .value = value, .rest = rest };
        },
        .pointer => |info| {
            const res = try parse(info.child, arena, input);
            const boxed = try arena.create(info.child);
            boxed.* = res.value;
            return .{ .value = boxed, .rest = res.rest };
        },
        else => @compileError("unsupported parser type: " ++ @typeName(T)),
    }
}
# 
pub fn main(init: std.process.Init) !void {
    const arena = init.arena.allocator();

    const result = try parse(Root, arena, std.mem.tokenizeAny(u8, "x y x end", &std.ascii.whitespace));
    std.debug.print("rest = '{any}'\n", .{result.value});
}
#

custom parser would be with a specifically named method like format for the std lib format functions

fathom crest
#

If u have a
const T = struct { value: u8, next: ?*Node }
It will error because parse(Node, …) is called recursively

ionic pulsar