C# でオレオレパーサコンビネータをつくってみる

2017.12.10

この記事について

この記事は C# Advent Calendar 2017 の 10 日目の記事です。アホなので 9 日の夜に書きはじめています。ちゃんと間に合ったらいいねください・・・！！！！

コードは github にあります wipiano/csharp-parser-combinators

Haskell や Scala で便利便利と言われているパーサコンビネータを自分でつくって遊んでみようという記事です。実用的なパーサコンビネータの完成までは至らなくても、雰囲気だけつかめればと。

関数をどんどん組み合わせていくので delegate と拡張メソッドを使って遊ぶ感じになります。この記事を読むにあたって、パーサコンビネータや Haskell や Scala や関数型プログラミングの知識は必要ありませんが、高階関数が出てくるので馴染みのない方は wikipedia でもさらっと読んでおくとわかりやすいかと思います。

Java 版のこの記事を参考に、 C# だったらどう書くかなあ、自分だったらどう書くかなあというところを考えて書きました。なので Haskell とも Scala とも下記の先行記事とも同じ実装にはなっていません。

Java パーサコンビネータ超入門

.NET のパーサコンビネータの実装はすでにあるようですが、これを再現しようという話ではありません

Sprache

私自身関数型にはあまり強くないので詳しい方にコメントいただけると、読んでくれる方も助かるのではないかと思います！

続編は json のパースあたりをいつか書くかもって感じです。

完成イメージ

例えば xxx-xxxx の形式の郵便番号を受け付けるパーサはこんなふうに書けます。この記事の最後にもうすこしだけ難しい例がのっていますが、 json のパーサなんかもかけるとおもいます。

// xxx-yyyy の xxx 部分
Parser<int> leftPart = Digit.Repeat(3).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の yyyy 部分
Parser<int> rightPart = Digit.Repeat(4).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の形式の郵便番号のパーサ
Parser<PostalCode> postalCodeParser = leftPart
    .Left(Literal('-'))
    .Sequence(rightPart, (left, right) => new PostalCode(left, right));

ParseResult<PostalCode> result = postalCodeParser(Source.Create("123-4567"));
PostalCode postalCode = result.Result;

public class PostalCode
{
    public int LeftPart { get; }

    public int RightPart { get; }

    public PostalCode(int left, int right)
    {
        this.LeftPart = left;
        this.RightPart = right;
    }

    public override string ToString() => $"{LeftPart}-{RightPart}";
}

パーサを定義する

パーサコンビネータは小さいパーサを組み合わせて大きいパーサをつくるための関数です。まずはパーサ周りの用意をしていきます

Parser への入力を表す Source
Parser の実行結果を表す ParseResult
Source を受け取って ParseResult を返す Parser

Source

パーサは文字列を受け取って結果を返せばいいのですが、パーサを組み合わせていくときに生の string を直接渡すと、読んでいる位置の管理などをパーサが行う必要があるので、あとから不便になります。そこで、うすくラップした Source 構造体を作ります。

元記事では Parser 自体が Source に対して位置を読み進めるという副作用をもっていましたが、 C# では構造体を書けるのでイミュータブルにします。

Read() メソッドを使って先頭の一文字と、位置が進められたあたらしい Source を取得できます。文字列の長さをこえて読もうとした場合は EndOfSourceException が発生します。

ちょっとだけ長いですが、、

/// <summary>
/// Parser への入力
/// </summary>
public struct Source
{
    // 最初に与えられた文字列をもっておく
    private readonly string _source;

    // 現在位置
    private readonly int _pos;

    private Source(string source, int pos)
    {
        _source = source;
        _pos = pos;
    }

    /// <summary>文字列の先頭をさす Source を作成します</summary>
    public static Source Create(string source)
        => new Source(source, 0);

    /// <summary>一文字読み出します</summary>
    public (char c, Source source) Read()
    {
        if (_source.Length <= _pos)
        {
            // source の終わりを超えて読もうとした場合は Exception
            throw new EndOfSourceException(this);
        }

        return (_source[_pos], new Source(_source, _pos + 1));
    }

    /// <summary>指定した文字数ぶん char を読み出します</summary>
    public (IEnumerable<char> chars, Source source) ReadChars(int count)
    {
        if (_source.Length < _pos + count)
        {
            // 読み出そうとしている長さが source をこえていたら Exception
            throw new EndOfSourceException(this);
        }

        return (_source.Skip(_pos).Take(count), new Source(_source, _pos + count));
    }

    /// <summary>指定した長さの文字列を読み出します</summary>
    public (string s, Source source) ReadString(int length)
    {
        if (_source.Length < _pos + length)
        {
            // 読み出そうとしている長さが source をこえていたら Exception
            throw new EndOfSourceException(this);
        }

        return (_source.Substring(_pos, length), new Source(_source, _pos + length));
    }

    /// <summary>Source の終わりに達したときの Exception</summary>
    public class EndOfSourceException : Exception
    {
        private static readonly string EndOfSource = "EndOfSource";

        /// <summary>例外発生時の Source</summary>
        public Source Source { get; }

        internal EndOfSourceException(Source source)
            : base(EndOfSource)
        {
            this.Source = source;
        }
    }
}

ParseResult

ParseResult<T> はパーサの実行結果です。パーサはすべてこれを返します。結果は任意の型で持っておくことができます。構造体が親をもてないのでこんな形にしてしまいましたが、 class にして型スイッチでも良かったかもしれないですね。。

public struct ParseResult<T>
{
    /// <summary>実行後の Source</summary>
    public Source Source { get; }

    /// <summary>成功したかどうか</summary>
    public bool IsSuccess { get; }

    /// <summary>パース結果</summary>
    public T Result =>
        this.IsSuccess ? _result : throw new Exception($"Parse error: {Reason}");

    private readonly T _result;

    // 失敗した理由
    public string Reason { get; }

    internal ParseResult(Source source, bool isSuccess, T result, string reason)
    {
        this.Source = source;
        this.IsSuccess = isSuccess;
        _result = result;
        this.Reason = reason;
    }
}

あとで using static で使いやすいように別クラスにヘルパー関数を定義しておきます

public static class ParseResultHelper
{
    public static ParseResult<T> Success<T>(Source source, T result)
        => new ParseResult<T>(source, true, result, default);

    public static ParseResult<T> Failed<T>(Source source, string reason)
        => new ParseResult<T>(source, false, default, reason);
}

Parser

パーサ本体の定義はとてもかんたんです。 Source を受け取って ParseResult を返します。 前に実行されたパーサの結果を気にするのはパーサコンビネータの役割なので、パーサ自体は Source だけに集中します。

public delegate ParseResult<T> Parser<T>(Source source);

一文字だけ読むパーサを実装する

まず簡単な一文字だけ読むパーサをいくつか実装してみます。

どんな文字でも受理するパーサ Any
数値 (0 〜 9) だけ受理するパーサ Digit
指定された文字だけ受理するパーサ (を返す高階関数) Literal(char c)
指定された関数が true を返す文字を受理するパーサ (を返す高階関数) Is(Func<char, bool>)

ここで、パーサが Success や Failed の ParseResult<T> を作りやすくする関数を import しておきます

using static ParseResultHelper;

public static class CharParsers
{
   // TODO
}

Any - どんな文字でも受け付ける

どんな文字がきてもいいからとりあえず読み進めたい、というときのためのパーサです。常に Success を返せば良いです。

public static Parser<char> Any { get; } = (Source s) =>
{
    var (c, next) = s.Read();
    return Success(next, c);
};

例:

var result = Any(Source.Create("a"));    // { IsSuccess: true, Result: 'a' }

Digit - 数字を読む

数値であれば Success を返します。

public static Parser<char> Digit { get; } = (Source s) =>
{
    var (c, next) = s.Read();
    return char.IsDigit(c) ? Success(next, c) : Failed<char>(next, "Is not a digit.");
};

例:

// xxx-yyyy の xxx 部分
Parser<int> leftPart = Digit.Repeat(3).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の yyyy 部分
Parser<int> rightPart = Digit.Repeat(4).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の形式の郵便番号のパーサ
Parser<PostalCode> postalCodeParser = leftPart
    .Left(Literal('-'))
    .Sequence(rightPart, (left, right) => new PostalCode(left, right));

ParseResult<PostalCode> result = postalCodeParser(Source.Create("123-4567"));
PostalCode postalCode = result.Result;
var success = Digit(Source.Create("12a"));    // { IsSuccess: true, Result: '1' }
var failed = Digit(Source.Create("a12"));     // { IsSuccess: false, Result: Exception }

Literal - ある文字に一致していたら OK

これは文字を指定してその都度パーサを作る必要があるので、 Parser<char> を返す高階関数を書きます。与えられた文字と、 Source から取得した文字が一致していれば成功です。

public static Parser<char> Literal(char literal) => (Source s) =>
{
    var (c, next) = s.Read();
    return c == literal ? Success(next, c) : Failed<char>(next, $"{c} is not equals {literal}");
};

例:

var parser = Literal('a'); // 'a' を受け付けるパーサ
var success = parser(Source.Create("abc"));    // { IsSuccess: true, Result: 'a' }
var failed = parser(Source.Create("ccc"));     // { IsSuccess: false, Result: Exception }

Is - 判定関数を指定する

これも Literal と同じように高階関数を書きます。与えられた関数が true を返すかどうかで成功か失敗かがきまります。

public static Parser<char> Is(Func<char, bool> predicate) => (Source s) =>
{
    var (c, next) = s.Read();
    return predicate(c) ? Success(next, c) : Failed<char>(next, $"predicate({c}) returns false.");
};

例:

var lowerParser = Is(char.IsLower);    // 小文字だけ受け付けるパーサ
var success = lowerParser(Source.Create("abc"));    // { IsSuccess: true, Result: 'a' }
var failed = lowerParser(Source.Create("ABC"));     // { IsSuccess: false, Result: Exception }

これまでにつくったパーサはすべて Is() で置き換えられます。

とりあえず、パーサコンビネータをかんたんに使ってみるにはこのぐらいでよさそうなので先に進みましょう。

パーサコンビネータ

いよいよパーサコンビネータをつくっていきます。パーサを組み合わせるための道具がパーサコンビネータですが、実装寄りの言い方をすると、パーサコンビネータは パーサを引数にとって新しいパーサを返す関数 です。

今回は 5 種類の基本的なパーサコンビネータをつくってみます。

Many: 0 回以上の繰り返し
Repeat: 指定回数の繰り返し
Sequence: 2 つのパーサを順番に結合する
Or: 2 つのパーサのどちらか成功した方の結果をとる
Left, Right: 成功する条件は Sequence と同じだが、結果は左辺または右辺のものだけをとりだす

ふつうに書くと () がたくさんになって Lisp((((())))) みたいになる上にちょっと書きごこちよくないので Parser<T> の拡張メソッドとしてつくります。（Lisp は好きですよ）

`ImmutableList<T>`

今回、コンビネータの戻り値として Parser<ImmutableList<T>> を使います。 List<T> と違ってイミュータブルなリストであり、 Add メソッドなどのメソッドはすべて副作用のない関数になっていて、そのコレクション自体を変更するのではなく、変更された新しいコレクションを返します。このために、データの構造も配列ではなく連結リストのような構造になっています。

この性質から、コンビネータが返すパーサを副作用のないパーサにすることができ、見通しがよくなっています。

標準では使えないので、 System.Collections.Immutable パッケージを nuget でインストールしてください。

Many - 0 回以上の繰り返し

まずは引数を 1 個しかとらないコンビネータが簡単なので Many からやっていきましょう。失敗するまで読み続けて、最後に成功した結果のリストを返します。「0回以上」なので 1 度も成功しなくても OK です。

public static Parser<ImmutableList<T>> Many<T>(this Parser<T> parser)
{
    ParseResult<ImmutableList<T>> Impl(Source s, ImmutableList<T> results)
    {
        var result = parser(s);

        return result.IsSuccess
            ? Impl(result.Source, results.Add(result.Result))
            : Success(s, results);
    }

    return (Source s) => Impl(s, ImmutableList<T>.Empty);
}

実際に parser を実行しているのは Impl 内です。 Impl は失敗するまで再帰的に呼ばれ続けます。

数字の 0 回以上の繰り返しはこのように書けます:

Parser<ImmutableList<char>> manyDigits = Digit.Many();

Repeat - 指定回数の繰り返し

Many の回数指定版です。今度は指定された回数分きっちり成功しつづけなければなりません。

public static Parser<ImmutableList<T>> Repeat<T>(this Parser<T> parser, int count)
{
    ParseResult<ImmutableList<T>> Impl(Source s, int c, ImmutableList<T> results)
    {
        if (c == 0)
        {
            // 0 回を指定されたら終わり
            return Success(s, results);
        }

        var result = parser(s);

        return result.IsSuccess
            ? Impl(result.Source, c - 1, results.Add(result.Result))
            : Failed<ImmutableList<T>>(result.Source, result.Reason);
    }

    return (Source s) => Impl(s, count, ImmutableList<T>.Empty);
}

3 桁の数字はこのように書けます:

Parser<ImmutableList<char>> parser = Digit.Repeat(3);

Sequence - 連結

ここから 2 つのパーサを引数にとるコンビネータの実装に入ります。

ParseResult を string に限定せずジェネリック型にしてしまったことでここから一気に実装がめんどくさくなってしまいました・・・。

渡されるパーサの型がちがう場合を考慮して、3 つのオーバーロードを用意する必要があります。

Parser<ImmutableList<T>> Sequence<T>(Parser<T> first, Parser<T> second): 型がおなじパーサを連結する
Parser<ImmutableList<T>> Sequence<T>(Parser<ImmutableList<T>> first, Parser<T> second): 型が同じパーサを 2 回以上つづけて連結したい場合のサポート
Parser<TResult> Sequence<TFirst, TSecond, TResult>(Parser<TFirst> first, Parser<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector): 型が一致しないパーサを連結する

public static Parser<ImmutableList<T>> Sequence<T>(this Parser<T> first, Parser<T> second) =>
    first.Sequence(second, (f, s) => ImmutableList<T>.Empty.Add(f).Add(s));

public static Parser<ImmutableList<T>> Sequence<T>(this Parser<ImmutableList<T>> first, Parser<T> second) =>
    first.Sequence(second, (f, s) => f.Add(s));

public static Parser<TResult> Sequence<TFirst, TSecond, TResult>(this Parser<TFirst> first, Parser<TSecond> second, Func<TFirst, TSecond, TResult> resultSelector) =>
    (Source s) =>
    {
        var firstResult = first(s);
        if (firstResult.IsSuccess)
        {
            var secondResult = second(firstResult.Source);

            return secondResult.IsSuccess
                ? Success(secondResult.Source, resultSelector(firstResult.Result, secondResult.Result))
                : Failed<TResult>(secondResult.Source, secondResult.Reason);
        }
        else
        {
            return Failed<TResult>(firstResult.Source, firstResult.Reason);
        }
    };

Qiita という文字列を受け付けるパーサはこんな感じになります:

var qiitaParser = Literal('Q')
    .Sequence(Literal('i').Repeat(2))
    .Sequence(Literal('t'))
    .Sequence(Literal('a'));

string qiita = string.Join("", qiitaParser(Source.Create("Qiita")).Result);

Or - 選択

Or も Sequence と同じように実装できます。ただし Or はふたつのパーサが同じ型である必要があります。ここで、 first が成功した場合は second は評価せずに first の結果を返すことにします。

public static Parser<T> Or<T>(this Parser<T> left, Parser<T> right) => (Source s) =>
{
    var leftResult = left(s);

    return leftResult.IsSuccess
        ? leftResult
        : right(s);
};

Left, Right

Left, Right の実装は Sequence に渡す ResultSelector が違うだけです。

Left は与えられたパーサ両方が成功したとき、右側の結果を捨てて左側の結果だけを返します。 Right はその逆で、左側の結果を捨てて右側の結果だけを返します。

public static Parser<TLeft> Left<TLeft, TRight>(this Parser<TLeft> left, Parser<TRight> right) =>
    left.Sequence(right, (l, r) => l);

public static Parser<TRight> Right<TLeft, TRight>(this Parser<TLeft> left, Parser<TRight> right) =>
    left.Sequence(right, (l, r) => r);

Map - 型変換

これはパーサどうしを組み合わせるものではないですが、便利な関数として Parser の型を変換するための関数をつくっておきます。

public static Parser<TResult> Map<TParser, TResult>(this Parser<TParser> parser, Func<TParser, TResult> mapper) =>
    (Source s) =>
    {
        var result = parser(s);
        return result.IsSuccess
            ? Success(result.Source, mapper(result.Result))
            : Failed<TResult>(result.Source, result.Reason);
    };

最後にしょぼい郵便番号のパーサをつくってみる

なんとか完成しました・・・！！！

最後に郵便番号のパーサをつくってみます。そのままだと Sequence だけで終わってしまうので、すこしゆるいパーサをつくります。

下記のような入力はすべて受け付けることができます

123-4567
1234567
〒1234567
〒123-4567

// xxx-yyyy の xxx 部分
Parser<int> leftPart = Digit.Repeat(3).Map(chars => int.Parse(new string(chars.ToArray())));

// xxx-yyyy の yyyy 部分
Parser<int> rightPart = Digit.Repeat(4).Map(chars => int.Parse(new string(chars.ToArray())));

// 普通の xxx-yyyy
Parser<PostalCode> normal = leftPart.Left(Literal('-')).Sequence(rightPart, (l, r) => new PostalCode(l, r));

// xxxyyyy
Parser<PostalCode> withoutSeparator = leftPart.Sequence(rightPart, (l, r) => new PostalCode(l, r));

Parser<PostalCode> postalCode = normal.Or(withoutSeparator);

// 〒 が付加されてもよい
Parser<PostalCode> postalCodeParser = Literal('〒').Right(postalCode).Or(postalCode);