数週間かけてC#でパーサーコンビネーターつくってみた

先日ふとFastParseというScala言語で開発されているパーサーコンビネーター・ライブラリーについての記事を見つけ、それを読んでいるうちにC#言語で似たようなものを作ってみたくなりました。

そして、実際に作ってみたのがこちら。

README.mdからの転載となりますが、例えば次のコードは浮動小数点数のパーサーの実装例です：

sealed class NumberParser : Parser<double>
{
    readonly Parser sign;
    readonly Parser digits;
    readonly Parser integral;
    readonly Parser fractional;
    readonly Parser exponent;
    readonly Parser<double> number;

    public NumberParser()
    {
        sign = CharIn("+-").OrNot();
        digits = CharsWhileIn("0123456789", min: 0);
        integral = Char('0') | (CharBetween('1', '9') & digits);
        fractional = Char('.') & digits;
        exponent = CharIn("eE") & (sign) & (digits);
        number = ((sign.OrNot() & integral & fractional.OrNot() 
                  & exponent.OrNot()).Capture()).Map(double.Parse);
    }

    protected override ParseResult<double> DoParse(Reader input)
    {
        return number.Parse(input);
    }
}

こうして作成したパーサーは次のようにして使用します：

var p = new NumberParser();

var r1 = p.Parse("-123.456");
var s1 = r.Successful; // returns true.
var c1 = r.Capture; // returns Optional(-123.456), and c1.Value returns -123.456.

var r2 = p.Parse("hello");
var s2 = r.Successful; // returns false.
var c2 = r.Capture; // throws InvalidOperationException.

FastParseのドキュメンテーションにあるサンプルを真似たものです。

比較してみてもらうと一目瞭然ですが、演算子オーバーロードの許容範囲の違いによる影響は大きいです。内部DSLを作り上げる場合、演算子オーバーロードでどこまでの演算子を（あるいは標準にはない演算子を）サポートできるかは、結果に大きく出てきます。逆に言えばDSLづくりでもしない限りそんなキャパシティはあるだけ無駄ということかもしれませんけど。。細かいところではその他にもいろいろ制約となった事項はあるのですが、くたびれてしまってここに書き出す気力もありません。

つくりながら今更ですが「パーサーコンビネーターにおけるパーサーは値のキャプチャを行わないケースが多いこと」「（パース対象の構文にもよりそうだが）パースの途中経過もしくは最終成果物として抽象構文木のような構造は必要不可欠ではないこと」「パーサーを組み立てる過程で『左再帰』の除去の工夫が必要になること」などなどの事項を学ぶことができました。