平々毎々（アーカイブ）

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

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

C# Functional

註：この記事は、（中略）「簡単なパーサーを実装する」というお題でコードを見てみようという、まったくPVの伸びなさそうな記事です。

今回は前回のコードを一部修正してみます。

0回以上の繰り返し／1回以上の繰り返し

前回のNumber()を再掲。

  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));
  }

expr(式)やterm(項)やfactor(因子)はパース結果の型がintなのに、これはFList<char>。それは再帰的定義をそのまま実装したためなのだが、ちょっとすっきりしない。
そこで、パーサー部品を少し改造して、「0回以上の繰り返し(正規表現で言う "*")」「1回以上の繰り返し(正規表現で言う "+")」を用意する。とりあえず今回はParser<T>のメソッドとしておこう。

public class Parser<T>
{
  // 他のメンバー定義は省略

  public Parser<FList<T>> ZeroOrMore()
  {
    return OneOrMore() | new Parser<T>(input => FList<T>.Empty);
  }

  public Parser<FList<T>> OneOrMore()
  {
    return from x in this
           from xs in this.ZeroOrMore()
           select new FList<T>(x, xs);
  }
}

このように、再帰的定義の部分を汎用部品化しておけば、Number()はそれを使って実装すればいい。

number ::= digit+
  public static Parser<int> Number()
  {
    return from xs in Digit().OneOrMore()
           select int.Parse(new string(xs.ToArray()));
  }

バックトラック時の無駄を省けるか

expr(式)のBNFは

expr ::= term '+' expr | term

こうなので、これをそのままコードに落としていた。しかしそれだとちょっとだけ無駄がある。ORの左側でパースに失敗し、ORの右側に移行しようとする場合、termのパースをやり直すことになる。
BNFを書き換えて

expr ::= term ('+' expr | ε) (* εは何も生成しない *)

こんな感じにしたとしても意味は同じ。このBNFをコードで表現すれば、termを使い回せないだろうか。
これは、やればできるのだけど、ちょっとだけ注意点がある。

    public static Parser<int> Expr()
    {
      return from t in Term()
             from x in
               ((from _ in Char('+')
                 from e in Expr()
                 select t + e)
                 |
                // 2014/8/4バグ修正
                // new Parser<int>(input => t))
                new Parser<int>(input => Tuple.Create(t, input)))
             select x;
    }

from x in (...) select xの所が気持ち悪い。このクエリ式は(...)を何も変更していないのだから、単に(...)だけを書ければよかったのだけど、そうするとfrom t in Term()に対応するselect句がなくなってしまい、コンパイルできない。これはクエリ構文の制約として受け入れるしかない。*1

Parser<T>のコンストラクタ

あえてスルーしてたんだけど、モナド的には「xを受け取って、『入力を消費せずにパース結果としてxを返すパーサー』を生成するメソッド、もしくはコンストラクタ」を用意しておくべきなのです。でも、LINQのクエリ構文だとselectがそれと同じ役目を果たすんで、そういうコンストラクタがなくても割と何とかなってしまう。前回の記事がその例。
今回は、Parser<T>のコンストラクタを2ヶ所で使用しています。なので、

public class Parser<T>
{
  public Parser(T returnValue)
  {
    this.f = input => returnValue;
  }
}

を作っておけばOK。

蛇足：ε

あえて

public static class Parser
{
  public static Parser<object> Epsilon()
  {
    // 2014/8/4バグ修正
    // return new Parser<object>(input => null);
    return new Parser<object>(input => Tuple.Create((object)null, input));
  }
}

も作ってみる。*2

これを使うと、Expr()は

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

になる。

(2014/8/4 追記)

  public static Parser<T> Epsilon<T>()
  {
      return new Parser<T>(input => Tuple.Create(default(T), input));
  }

こんな感じで default(T) を返すようにしておけば、もっといい感じになった。

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

*1:Haskellのdo構文ではreturnは単なる関数であり、使わなくてもいい。

*2:C#はvoidがunitじゃないので、nullで代用するしかない。