関数型言語ってこわい?C#erがLINQでパーサーに挑戦(最終回)
註:この記事は、(中略)「簡単なパーサーを実装する」というお題でコードを見てみようという、まったくPVの伸びなさそうな記事です。
- 初回……関数型言語ってこわい?C#erがLINQでパーサーに挑戦(1) - 猫とC#について書くmatarilloの雑記 F#のリスト FList<T> を用意した。
- 第2回……関数型言語ってこわい?C#erがLINQでパーサーに挑戦(2) - 猫とC#について書くmatarilloの雑記 パーサー Parser<T> を用意した。
- 第3回(前回)……関数型言語ってこわい?C#erがLINQでパーサーに挑戦(3) - 猫とC#について書くmatarilloの雑記 各種パーサーを組み立て、TryEvalを実装した。
今回は前回のコードを一部修正してみます。
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; }