Zen言語でパーサコンビネータ(1)

はじめに

Java パーサコンビネータ 超入門を読んで、やりたくなったので、やってみました。

コードはこちらです。

(1)としましたが、続くかどうかは知りません。

overview

文字列に対して、u8もしくはBuffer (u8の可変長配列) を返すパーサを実装しています。 次のような感じで使えます。

const std = @import("std");
const Buffer = std.container.Buffer;
usingnamespace @import("comzen.zen");

pub fn main() anyerror!void {
    var source = String.init("abc123");
    // `Many(alpha)` は `Parser(Buffer)` インタフェースを実装するパーサです
    const parser: Parser(Buffer) = Many(alpha){};

    var result = try parser.parse(&source);
    defer result.deinit();
    std.debug.warn("result = {}\n", .{result.toSlice()});
}
$ zen build run
result = abc

次のパーサインスタンスを実装しています。

  • any_char
  • digit
  • upper
  • lower
  • alpha
  • alphaNum
  • letter

また、次のパーサ型を返す関数を定義しています。

  • Satisfy
  • Char
  • Many
  • Sequence
  • Count

実装

インタフェース

1文字 (u8) を返すパーサと複数文字 (Buffer) を返すパーサとがあるので、ジェネリックインタフェースを定義します。 ジェネリックインタフェースは、任意の型 (T) に対応するインタフェース型を返す関数です。 これはコンパイル時にだけ機能します。

// A generic interface for parser which returns `ParserError!T`.
pub fn Parser(comptime T: type) type {
    return interface {
        fn parse(*String) ParserError!T;
    };
}

エラー型もパーサごとに定義しようかとも考えたのですが、面倒なので、エラー型は一括定義することにしました。

/// All parsers return this Error or its subset.
pub const ParserError = String.Error || AllocError || error {
    NotSatisfy,
};

パース対象

それほど重要ではないのですが、パース対象の文字列を包む型を定義しました。 1文字ずつ順番に読み込んでいくだけの、特に面白みのない型です。 これは、標準ライブラリのstd.ioに定義されているBufferedInStreamあたりを使っても良い気がしました。

/// A pair of string parsed and its position whicn indicates
/// next character.
pub const String = struct {
    const Self = @This();

    const Error = error {
        IndexOutOfBounds,
    };

    str: []const u8,
    pos: usize = 0,

    /// Initializes `String` source.
    /// `str` must live long enough than this instance.
    pub fn init(str: []const u8) Self {
        return Self {
            .str = str,
        };
    }

    /// Tries to get the next character if exists.
    pub fn peek(self: Self) Error!u8 {
         if (self.pos >= self.str.len) {
            return error.IndexOutOfBounds;
        }
        return self.str[self.pos];
    }

    /// Advances position.
    pub fn next(self: *Self) void {
        self.pos += 1;
    }
};

Satisfy

指定した条件を満たす場合にパースが成功するパーサです。 何やらトリッキーになってしまいました。

pub fn Satisfy(predicate: fn (u8) bool) type {
    const _Satisfy = struct {
        fn parse(self: @This(), str: *String) ParserError!u8 {
            const ch = try str.peek();
            if (!predicate(ch)) {
                return error.NotSatisfy;
            }
            str.next();
            return ch;
        }
    };

    _ = @is(Parser(u8), _Satisfy{});
    return _Satisfy;
}

test "satisfy" {
    testing.err(error.NotSatisfy, parseTest(u8, Satisfy(ascii.isDigit){}, "abc"));
    testing.equal(@is(u8, '1'), try parseTest(u8, Satisfy(ascii.isDigit){}, "123"));
}

というのも、Zenにはクロージャを作る機能がないため、素直にパーサ関数を返すことができません。 そこで、Parserインタフェースを実装する型を返すようにしました。

利用する時は、Satisfy(条件を指定する関数ポインタ)型のインスタンスを作成して、parse()メソッドを呼び出します。 引数で与えた関数ポインタを呼び出す新たな型を返すことで、あたかも関数ポインタをキャプチャした型として使えます。

Char

指定した文字と一致する場合だけ、パースが成功するパーサです。 Satisfyを使います。

Zenにはクロージャはないのですが、似たようなことができます。 次のChar()関数内では、無名struct名前空間として利用して、関数f()を定義しています。 この関数f()内では、Char()関数の引数cを使用した処理が書けます。 まるで環境をキャプチャしているようですね。 そして、構造体名.関数名つまりstruct { ... }.fで関数ポインタを取得できるわけですね。 構造体の型は名前をconstでバインドしなくても無名のまま使えるので、これで良いわけです。

pub fn Char(c: u8) type {
    const C = Satisfy( struct { fn f(src: u8) bool { return src == c; } }.f );

    _ = @is(Parser(u8), C{});
    return C;
}

Satisfyを使った頻出パターン

Satisfyを使った頻出パターンをえいやっと定義します。 これらは環境をキャプチャする必要がないため、インスタンス化してしまいます。

pub const digit = Satisfy(ascii.isDigit){};
pub const upper = Satisfy(ascii.isUpper){};
pub const lower = Satisfy(ascii.isLower){};
pub const alpha = Satisfy(ascii.isAlpha){};
pub const alphaNum = Satisfy(ascii.isAlNum){};
pub const letter = Satisfy(ascii.isAlpha){};

Count

あるパーサを指定回数適用します。 ここでは、ちょっと型を手抜きして、Parser(u8)インタフェースを実装するパーサを受け取り、count回適用して、Bufferを返すパーサとして定義しました。 このCountParser(Buffer)インタフェースします。

pub fn Count(comptime count: usize, parser: Parser(u8)) type {
    const _Count = struct {
        fn parse(self: @This(), str: *String) ParserError!Buffer {
            var buf: [count]u8 = undefined;
            for (buf) |*c| {
                c.* = try parser.parse(str);
            }
            return try Buffer.init(&heap.page_allocator, &buf);
        }
    };

    comptime _ = @is(Parser(Buffer), _Count{});
    return _Count;
}

Sequence

任意の個数のパーサを受け取り、順番に適用します。 今回、一番苦労したやつです。色々、逃げつつ、まぁなんとかしました。

先に使い方を見ておくと、「アルファベット->数字->数字」をパースするパーサはSequenceを使って次のように書けます。 ここで、letterParser(u8)インタフェースを実装するパーサ、CountParser(Buffer)インタフェースを実装するパーサです。 異なる型のパーサを複数受け取ることができるようになっています。

const alpha_num_num = Sequence(.{ letter, Count(2, digit){} }){};

test "alphabet number number" {
    try parseEqualBuffer(alpha_num_num, "a12", "a12");
    try parseEqualBuffer(alpha_num_num, "a23", "a234");
    testing.err(error.NotSatisfy, parseEqualBuffer(alpha_num_num, "", "abc"));
    testing.err(error.NotSatisfy, parseEqualBuffer(alpha_num_num, "", "123"));
}

実装は、こんな感じです。 戻り値型で処理を切り替えたり、そこそこトリッキーです。 疲れたので、解説はまた後日。

/// Takes multiple parsers and applies them one after another.
/// `parsers`: a tuple consists of one or more Parser.
pub fn Sequence(parsers: var) type {
    if (@typeInfo(@TypeOf(parsers)) != .Struct) {
        @compileError("Expected struct argument, found " ++ @typeName(@TypeOf(parsers)));
    }
    // TODO: check each parser implements `Parser`.
    const _Sequence = struct {
        fn parse(self: @This(), str: *String) ParserError!Buffer {
            var buf = try Buffer.initSize(&heap.page_allocator, 0);
            inline for (parsers) |parser| {
                const return_type = switch (@typeInfo(@TypeOf(parser.parse))) {
                    .BoundFn => |info| info,
                    else => unreachable,
                }.return_type orelse @compileError("parse() should have return type.");

                switch (return_type) {
                    ParserError!u8 => try buf.appendByte(try parser.parse(str)),
                    ParserError!Buffer => {
                        var sub = try parser.parse(str);
                        defer sub.deinit();
                        try buf.append(sub.toSlice());
                    },
                    else => @compileError("No such parse() return type."),
                }
            }
            return buf;
        }
    };

    _ = @is(Parser(Buffer), _Sequence{});
    return _Sequence;
}