関数型言語ってこわい？C#erがLINQでパーサーに挑戦(3)

註：この記事は、「~~ごはんはおかず~~LINQはモナド」と聞いたことがあるけど、モナドって何なのかは特に知りたくない、でもLINQがモナドだと何ができるのかはちょっとだけ知りたい、という奇特な人向けに、「簡単なパーサーを実装する」というお題でコードを見てみようという、まったくPVの伸びなさそうな記事です。

前々回……関数型言語ってこわい？C#erがLINQでパーサーに挑戦(1) - 猫とC#について書くmatarilloの雑記 F#のリスト FList<T> を用意した。
前回……関数型言語ってこわい？C#erがLINQでパーサーに挑戦(2) - 猫とC#について書くmatarilloの雑記パーサー Parser<T> を用意した。

では、前々回で説明したパーサーの仕様をおさらい。

実装したいのは、ゼロ以上の整数、加算記号(+)、乗算記号(*)、開かっこ、閉かっこから構成される数式を文字列で与えられたときに、パースして結果を計算し、intを返すメソッド。その上、乗算は加算より優先度が高いとする。

BNFはこう。

expr   (* 式 *)   ::= term '+' expr | term
term   (* 項 *)   ::= factor '*' term | factor
factor (* 因子 *) ::= '(' expr ')' | number
number (* 数 *)   ::= digit number | digit
digit  (* 数字 *) ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

最初に実装するのは、1文字消費して、その文字をそのままパース結果とするパーサー。消費する文字がなければもちろんパース失敗。

  public static class Parser
  {
    public static Parser<char> Item()
    {
      return new Parser<char>(x => (x.IsEmpty) ? null : Tuple.Create(x.Head, x.Tail));
    }
  }

戻り値に含める「消費しなかった残りの文字列」は、F#のリストではTailプロパティで表されることがポイント。

さて、Parser<T>のコンストラクタを使うのはここまで。あとはすべてLINQ（クエリ構文）でまかなう。
まず、digit(数字)のパーサーを組み立てる。BNFでは OR(|) が並んでいるが、ORを使わないほうがシンプル。

    public static Parser<char> Digit()
    {
      return from x in Item()
             where '0' <= x && x <= '9'
             select x;
    }

Item()で1文字消費した上で、その文字が数字であればパース成功。パース結果の型はcharのまま。

次はnumber(数)。再帰的な定義になっているので、パース結果の型にはFList<char>を使うと簡単。

    public static Parser<FList<char>> Number()
    {
      return (from x in Digit()
              from xs in Number()
              select new FList<char>(x, xs))
              |
             (from x in Digit()
              select new FList<char>(x));
    }

残りに行く前に、加算記号(+)、乗算記号(*)、開かっこ、閉かっこをパースするための準備をしておこう。指定した文字と一致するときだけパースに成功するパーサーを作る。

    public static Parser<char> Char(char c)
    {
      return from x in Item()
             where x == c
             select x;
    }

これを使って、expr(式)、term(項)、factor(因子)を定義する。パース結果の型は構文木にしてもいいのだが、今回は構文木を作らずに、さっさと計算してしまおう。

    public static Parser<int> Expr()
    {
      return (from t in Term()
              from _ in Char('+')
              from e in Expr()
              select t + e)
              | Term();
    }

    public static Parser<int> Term()
    {
      return (from f in Factor()
              from _ in Char('*')
              from t in Term()
              select f * t)
              | Factor();
    }

    public static Parser<int> Factor()
    {
      return (from _1 in Char('(')
              from e in Expr()
              from _2 in Char(')')
              select e)
              |
             (from ns in Number()
              select int.Parse(new string(ns.ToArray())));
    }

ここまでできれば、目的のメソッドは実装できる。

    public static bool TryEval(string input, out int result)
    {
      result = 0;
      var r = Expr().Parse(input.ToFList());
      if (r == null) return false;        // パースが失敗した
      if (!r.Item2.IsEmpty) return false; // パースは成功したが、入力が余ってしまった
      result = r.Item1;
      return true;
    }

LINQでパーサーが合成できてしまった。こんな風に、順番に適用する「何か」を簡単に合成できることが、モナドの力ということらしいよ。
とりあえず、ここまでのソースはgistに上げておいた。
さて、次回はこのシリーズの最終回。今回のコードを部分的に変更してみる予定。

平々毎々（アーカイブ）

はてなダイアリーのアーカイブです。

関数型言語ってこわい？C#erがLINQでパーサーに挑戦(3)