JParsecで遊んでみる。 - 設計と実装の狭間で。

まぁ、何と言うか、コンパイラ的なアレに興味があったりなかったりするので、
思いつきでコンパイラ作れそうな何かで遊んでみたくなってみたり。

JavaCCとかANTLRとか、SableCCとか、色々あるけど、
一際マニアックなのいってみようかって気分で、JParsecで遊んでみる事にする。
後さ、構文ファイルの記法覚えるのがタルいんだよねぇ…正直。
デバッガビリティが低すぎてさ…。
あんのかなぁ…ANTLRの構文ファイルをステップ実行できるツールとか。
本家はHaskelで.NET版やRuby版の実装もあるので、知る人ぞ知るって感じなんだろうけども。

ちなみに、予防線を張っておくと、コンパイラに関しては、ワタクシほぼド素人デス。
書籍を斜め読みしたり、JavaCCのコード読んだり位はしてるけども、
何か数学的な話に対する理解はほぼ無いですなぁ。
っつうか、数学って高校二年の時以来それらしい事はナニ一つしてないので、
間違ってる事や分って無い事は山の様にある感じ。

うぇるかむつーざ…

とりあえず、コードとバイナリをダウンロードしない事には始まらないので、本家に。

http://jparsec.codehaus.org/

おいおい、ドキュメントらしいドキュメントは、
四則演算するチュートリアルが一つで終わりかいな…。
すげぇ話だ。これはこれで漢らしくてイイ。
どう考えても辛い未来が待っているのを分っていつつ突撃。

とりあえず、Parsecについては、ぐぐる先生が何やら色々知っている様なので、ほったらかし。
HaskelスゴイよねHaskel。爆速らしいよParsec。良く分らんけど。
Parsecが速いからって、JParsecが速いとは限らない罠。
いや、知らないとは言わないけども、知っているとも言えない関数型言語。
その凄さにJava使いがあやかれるんなら、それって結構おいしい話じゃね？*1

Tipsって言っても、細かい単位でテストするとイイよ。ってそれだけかいな…。

ちうとりある。って書くとチトエロくね？

最新版のJParsecはGenericsに全面対応しているけど、Tutorialには微塵も無いヨ。
これを、Generics対応にしていく過程の中で、きっと理解が進むに違いない。とか思ったりする。
まぁ、最初にそう思った時には、後で見る事になる地獄の様なメソッド宣言の事なんか想像もしてなかった訳だが。

まずは、ゴール決めるヨネ、ゴール。
どうなったら、終わりなのか最初に決めて貰えると、イイヨネ。

  public static void main(String[] args) {
    Parser<Double> parser = buildParser();
    // パーサを実行する。
    final String src = "(43 *2 + 21)* -2";
    final Double result = parser.parse(src);
    System.out.println(src + " = " + result);
  }

buildParserを上手く実装し終えた暁には、

(43 *2 + 21)* -2 = -214.0

とか、コンソールに出力される訳。ファンタステック。

じゃあ、そろそろパーサを作り始めますか。
四則演算したいんで、数字ってどんなよ？って定義する所から。

  final Pattern digits = Patterns.range('0', '9').many(1);
  final Pattern fractional = Patterns.isChar('.').seq(digits);
  final Pattern number = digits.seq(fractional.optional());
  final Parser<_> s_number = Scanners.isPattern("number", number, "number expected");

この辺はまだ、全然余裕。
digitsは、0〜9の範囲(range)で、1文字以上(many)。
fractionalは、小数点。後ろ(seq)にdigitsがつくでよ。
numberは、数字、digitsの後ろにfractionalが付いても付かなくてもいい(optional)。
んで、numberをマッチングするスキャナが、s_number。
三番目の引数は、上手くマッチング出来なかった時のエラーメッセージ。
コンテキスト情報を、エラーメッセージに足したい所だけども、ここでは我慢するなり。

さぁ、こっからがコンパイラっぽい雰囲気になってくるよ。
字句解析器を定義するます。「れきしかるあならいざー」って奴ですな。

  final Parser<Tok> l_number = Lexers.lexer(s_number, Tokenizers.forDecimal());
  final Terms ops = Terms.getOperatorsInstance("+", "-", "*", "/", "(", ")");
  final Parser<Tok> l_ops = ops.getLexer();
  final Parser<Tok> l_token = Parsers.plus(l_ops, l_number);

  final Parser<_> s_line_comment = Scanners.javaLineComment();
  final Parser<_> s_block_comment = Scanners.isBlockComment("/*", "*/");
  final Parser<_> s_whitespace = Scanners.isWhitespaces();
  final Parser<_> s_delim = Parsers.plus(s_line_comment, s_block_comment,s_whitespace);

  final Parser<Tok[]> lexer = Lexers.lexeme(s_delim.many(), l_token).followedBy(Parsers.eof());

小数点ありの文字列用トークナイザが既に定義されているので、そいつを拾う。
スキャナとガッコーンと合わせると、一つ目のレキサー、l_numberが出来る。
次に、オペレータを定義する。四則演算子と括弧をば。
オペレータのレキサーと数字のレキサーを足す(plus)すると、
今回のパーサが扱えるトークンが全て定義されるっつう感じかな。

Parsersには、色んなメソッドがあるのだけど、コードを見ると、どう見ても同じ処理をしてるのがあったりする。
多分、下位互換性を保つ為何だろうケド、初学者には、微妙にトラップっぽい。
例えば、plusとsumは、一緒だし、altとorは一緒。
それぞれ後者は、ハマるので使わない様にするがヨロシ。イキナリ型が消えて泣きそうになります。

次は、読み飛ばす文字を定義しるます。
空白とか、コメント行とか、コメントブロックとか、まぁ、そんなの。
Scannersには、JavaとSQLとHaskelのコメントスタイルが元々定義されているます。
ブロックコメントは、まぁ、自分で一つ位定義してもイイんじゃねぇかなぁ…とか思っただけ。
空白は、java.lang.Character#isWhitespaceがtrueになる文字全部とか、そんな感じ。
で、コメントと空白のレキサーを足しちゃったり(plus)する訳。

で、lexemeパーサを作れば、トークンを生成してくれるパーサとなる訳ですなぁ。
followedByは、パーサがどこで止まるかっつう話だと思うので、EOFを指定しているのだけど、
場合によっては、何かもっとイカす指定の方法がある希ガス。
パーサコンビネータは、無限に先読み出来る的な話があるので、
ほっとくときっと止まる事を知らないのだろう…とか、思ってる。
誰か良く知ってる人、分り易く解説して下さい。

ついに、構文解析器へ！と逝きたい所だけども、
その前に、気が早いのだけど、構文決まったら、そこでの動作も決まるぜ的な話なので、
オペレータの処理を作っておきます。

  interface Operator {
    double cal(double a, double b);
  }

スゲェ簡単。そこ！三項演算デキネェジャンとか言うな！
実装クラスは、こんな感じ。

  final Operator plus = new Operator() {
   public double cal(double n1, double n2) {
    return n1 + n2;
   }

   @Override
   public String toString() {
    return "+";
   }
  };

ご想像の通り、minusと、mulと、divも作ります。

後、マイナス(-)とプラス(+)は、演算子が重複してても、それなりに意味を持つケースがあるますので、
その為の動作も実装しるます。

  final Map<Double, Double> neg = new Map<Double, Double>() {
   public Double map(Double o) {
    return new Double(-o.doubleValue());
   }
   @Override
   public String toString() {
    return "-";
   }
  };

Mapとか言う謎のインターフェースを骨格実装しているます。
jfun.parsec.Mapと言うインターフェースで、オペレータの挙動を実装する時には、
本当はこっちを実装するのが正しい姿であるます。
つまり、さっき作ったplusは、どっかで、Mapにアダプトされる事になるます。

面倒なので、書いちゃうと、こういうコード。

 protected static Map2<Number, Number, Double> toMap2(final Operator op) {
  return new Map2<Number, Number, Double>() {
   public Double map(Number a, Number b) {
    return new Double(op.cal(a.doubleValue(), b.doubleValue()));
   }

   @Override
   public String toString() {
    return op.toString();
   }
  };
 }

Mapは引数一つで、Map2は引数2つ。Map3は引数3つ。Map5まであるます。
まぁ、僕には五項演算子なんつーモノには、当分縁遠い生活をすると思われますので、
とりあえず頭の片隅にでも置いておきまする。
こんなのを見ると、そういえばGenericsのTypeは可変長引数使えないね…と思ったり。

ここでやっとこそさ、構文解析器の定義に入るます。
大体気持ち悪い感じになるのはココから。
何回も使うので、こんなヘルパメソッドを定義しる。

 protected static Parser<Map2<Number, Number, Double>> getOperator2(Terms ops, String op, Operator v) {
  return ops.getParser(op).seq(Parsers.retn(toMap2(v)));
 }

ちなみに、Termsってのは、どんなんだっけか？っつうと、

final Terms ops = Terms.getOperatorsInstance("+", "-", "*", "/", "(", ")");

オペレータの定義でしたね。

オペレータの名前を指定しつつレキサーをゲトして、それに対して、
Map2の処理結果を返す(retn)様にしる(seq)ます。
ここでのseqは、javadocを見るとこんなん書いてます。

if this parser succeeds,
the returned value is discarded and the next parser is excuted.
The monadic seq (>>) operation. 
@param p the next parser.
@return the new Parser.

モナドるらしいです。まぁ、何か誤植ねぇか？とか、そんな気しないでも無いですけども。

ちなみに、さっきのヘルパは、こんな風に呼出されてるます。

final Parser<Map2<Number, Number, Double>> p_plus = getOperator2(ops, "+", plus);

例によって、四則演算全部呼出すます。そこはまぁ、見なくても分ってくだちぃ。

演算子だけは、単項演算子のケースがあるますので、さっきのヘルパが使えず、こんなん。

final Parser<Map<Double, Double>> p_neg = ops.getParser("-").seq(Parsers.retn(neg));

括弧的なアレは、特にする事も無いので、パーサだけ引っ張ってオシマイ。

final Parser<Tok> p_lparen = ops.getParser("(");

括弧は、その間にある式が再帰的に評価されるます。
これには、ちょっとしたトリックが必要で、ダメな感じに書いてしまうと無限ループしかねませぬ。
と言う訳でJParsecには、専用のAPIがあるます。

  final List<Parser<Double>> expr_holder = new ArrayList<Parser<Double>>(1);
  final Parser<Double> p_lazy_expr = Parsers.lazy(new ParserEval<Double>() {
     public Parser<Double> eval() {
      return expr_holder.get(0);
     }
    });

遅延評価されるパーサを定義し、その挙動としてParserEvalを実装しる。
骨格実装の外側にテンポラリ的なホルダ(expr_holder)を用意しておいて、
後で全部パーサが出来たらホルダに差し込むます。
ここは、JParsec固有なコーディングパターンだと思われるマス。

で、最後に演算子に引き渡されるオブジェクトを、文字列からどういう風に作るの？的なのを定義しる。

  final Parser<Double> p_number = Terms.decimalParser(
    new FromString<Double>() {
     public Double fromString(int from, int len, String s) {
      return Double.valueOf(s);
     }
    });

これは、後で使うので忘れるとヒドイ事になるます。
ここでの引数となる文字列には、レキサーがトークンとして解釈した範囲の文字列が入ってくるますので、
特に考える事も無くDoubleに変換してしまうます。
もうちょっと機能の多いパーサを書く時には、きっと解析対象全体における位置情報(from,len)が重要になるでしょう。

で、パーサを力強く結合。

final Parser<Double> p_term = Parsers.plus(Parsers.between(p_lparen, p_rparen, p_lazy_expr), p_number);

左括弧と右括弧の間(between)に遅延評価しるぜ〜なのと、レキサーが分析した数字作っちゃうぜ〜がこれでくっつきました。
若干、あんま関係ないのがくっついた様な印象があるのだけど、まぁ、そうでもないか…。
もう少し理解が進めば、すんなりいくのかな…ホントか……？

次に、忘れてた訳では無いけども、演算子の評価順序を決定するテーブルを作成しるます。

  final OperatorTable<Double> optable = new OperatorTable<Double>();
  optable.infixl(p_plus, 10);
  optable.infixl(p_minus, 10);
  optable.infixl(p_mul, 20);
  optable.infixl(p_div, 20);
  optable.prefix(p_neg, 30);
  optable.prefix(p_pos, 30);

気持ち悪いのは、このOperatorTableで定義出来るのは、二項演算子まで…と言う事です。
三項演算子は、どうすんよ？どうすんよ？ｺﾏﾀ！
二項演算子は、中置記法なので、infixl。おおぅ、分り易っーイ。
二項演算子なので、結合性が選択可能で、

infixl
infixr
infixn

と三種類のメソッドがあるます。っつうか、結合性なんて言葉聞いた事もねぇ。
まぁ、普通に考えたら左側から評価すんだろ。常考。
単項演算子は、前置記法なので、prefix。

このOperatorTable。これだけ見ると非常に使い易いAPIに見えます。
しかしながら、いざ使って見ようと思うと、それはそれはゲロいモノを見せ付けられる事になるます。
例えば、infixlのメソッド宣言はこんなデス。

public OperatorTable<E> infixr(final Parser<? extends Map2<? super E, ? super E, ? extends E>> p, 
      final int precedence)

は？……………。
まさか、extendsとsuperが一つの宣言の中でこんだけ入り混じってるのは、見た事がナイヨ！
なんぞこれ〜。
まぁ、何か一度色々弄ってみると見慣れてくるもんだけども、初めて見た時は、意味を把握しきれんかったよ。

これのポイントは、jfun.parsec.Map2の宣言がこんなんなってる事。

public interface Map2<A,B,R> extends java.io.Serializable{
  R map(A o1, B o2);
}

つまり、OperatorTableに食わせる予定のMap2は、好き勝手な型を三つ選ぶだけじゃなくて、
単一の型階層の中に三つとも収めておいてネ！って事になる。兄弟姉妹はダメだとさ。
まぁ、良く考えてみれば何となく分らんでも無いけどさ、別にイイジャンそんなのーと、言いたい。
ガタガタ細かい事言うなよ…と。

ここまで来てついに構文解析器の定義が終わるます。

final Parser<Double> p_expr = Expressions.buildExpressionParser(p_term, optable);

expr_holder.add(p_expr);

さっき力強く結合した括弧的なアレとかが入ってるやつと、OperatorTableから正に！正に！
buildExpressionParser。
これは、本家のParsecにもある関数らしいですなぁ。

んで、出来たパーサを遅延評価用のホルダに突っ込んで、構文解析器ヲシマイ。

これで、ホントに最後の最後。
字句解析器と構文解析器を結合しるます。

Parser<Double> parser = Parsers.parseTokens(lexer, p_expr.followedBy(Parsers.eof()), "calculator");

よく分らんのは、構文解析器も.followedBy(Parsers.eof())してる事。
チュートリアルのコードだと、こうなってるんよねぇ…
構文解析なんだから、EOFは関係無くネ？そういう単純な話じゃねぇの？
イランのジャマイカ？と思って、

Parser<Double> parser = Parsers.parseTokens(lexer, p_expr, "calculator");

としてみたけど、快調に動きます。ううむ…どうなんだろ…。

詳しい人、解説お願いします。

まぁ、と言う訳で、JParsecと戯れたっつうか、このエントリ書くのに掛かった時間の方が、
コード書くのにかかった時間よりも長かったので、実はHatenaと戯れてたんじゃないか…と。
あー、連休が終わる……

参考:

*1:とか思ったら大間違いである事に気付くのに一日掛かった。