jparsec入門のバックアップ(No.5)

/**
* The main calculator parser.
* 
* @author Ben Yu
*/
public final class Calculator {
 
 /** Parsers {@code source} and evaluates to an {@link Integer}. */
 public static int evaluate(String source) {
   return parser().parse(source);
 }
 
 static final Parser<Integer> NUMBER = Scanners.INTEGER.map(new Map<String, Integer>() {
   public Integer map(String text) {
     return Integer.valueOf(text);
   }
 });
 
 static final Binary<Integer> PLUS = new Binary<Integer>() {
   public Integer map(Integer a, Integer b) {
     return a + b;
   }
 };
 
 static final Binary<Integer> MINUS = new Binary<Integer>() {
   public Integer map(Integer a, Integer b) {
     return a - b;
   }
 };
 
 static final Binary<Integer> MUL = new Binary<Integer>() {
   public Integer map(Integer a, Integer b) {
     return a * b;
   }
 };
 
 static final Binary<Integer> DIV = new Binary<Integer>() {
   public Integer map(Integer a, Integer b) {
     return a / b;
   }
 };
 
 static final Binary<Integer> MOD = new Binary<Integer>() {
   public Integer map(Integer a, Integer b) {
     return a % b;
   }
 };
 
 static final Unary<Integer> NEG = new Unary<Integer>() {
   public Integer map(Integer i) {
     return -i;
   }
 };
 
 private static <T> Parser<T> op(char ch, T value) {
   return isChar(ch).retn(value);
 }
 
 static Parser<Integer> parser() {
   Parser.Reference<Integer> ref = Parser.newReference();
   Parser<Integer> term = ref.lazy().between(isChar('('), isChar(')')).or(NUMBER);
   Parser<Integer> parser = new OperatorTable<Integer>()
       .prefix(op('-', NEG), 100)
       .infixl(op('+', PLUS), 10)
       .infixl(op('-', MINUS), 10)
       .infixl(op('*', MUL), 20)
       .infixl(op('/', DIV), 20)
       .infixl(op('%', MOD), 20)
       .build(term);
   ref.set(parser);
   return parser;
 }
}

↑

例 †

今朝みれてたのに、例に出していた記事が４０４になって見れなくなっていた、あわててgoogleのキャッシュから保存する。 I Hate Anonymous Classes

↑

URL †

http://docs.codehaus.org/display/JPARSEC/I+Hate+Anonymous+Classes

404になって見れなくなっているかもしれん

↑

本文 †

↑

Jparsecの核心のアイデアについて（原文）I Hate Anonyous Classes! †

お察しのとおり, jparsec全般的に関数脳的な考え方に基づいております。 jparsecを使い始めたら,MapやMap2,Map3などなどの実装にでくわします。で、型を入れていくとかったるくなるんです。

例えば, 次のクラスがあったとします。

Parser<A>,
Parser<B>
Parser<C> さらに、それらを順次、実行させ結果を使って、クラスDを作りたいとします。つまりこんな感じの時です、

Parser<D> d = Parsers.sequence(a, b, c, new Map3<A, B, C, D>() {
 public D map(A a, B b, C c) {
   return new D(a, b, c);
 }
});

まあ、そんなに悪くはないコードですよね？で、このAに具体的なクラス名を当てはめてかんがえてみますよ。

A	UnbelievableGadget?<Ipod>
B	IncredibleCartoon?<Panda<KungFu?>>
C	ViciouslyBeautiful?<KingKong?>

代入すると次のコードになるよね。

Parser<D> d = Parsers.sequence(a, b, c, new Map3<UnbelievableGadget<Ipod>,  IncredibleCartoon<Panda<KungFu>>, ViciouslyBeautiful<KingKong>, D>() {
 public D map(UnbelievableGadget<Ipod> ipod, IncredibleCartoon<Panda<KungFu>> panda,  ViciouslyBeautiful<KingKong> kingkong) {
   return new D(ipod, panda, kingkong);
 }
});

使いやすくなったと思うかな？

↑

JavaでHaskell的なコードが書けるMapperクラス †

というわけで、こんな時にはRubyのような動的言語を使っている場合だと、そんなに非常識な記述じゃないんだよね。こんな感じ

d = sequence(a, b, c) do |ipod, panda, kingkong|
  new D(ipod, panda, kingkong);
end

さらに関数言語オタク御用達のHaskellだと次のようにかけちゃうんです。

d = sequence a b c D

ギャー、簡潔すぎる。えっ何？あなたはJavaプログラマーだって？

あなたが自暴自棄になってやけを起こすまえにるまえに、まってください。まだ望みはあります。コーディング野郎どもは、Javaでも等価なコードが書けるものを作っていたんですよ！

そんなあなたのためにこのMapperクラスをご用意致しました！！。ルビー風に記述するとこんな具合です。

Parser<D> d = new Mapper<D>() {
 D map(UnbelievableGadget<Ipod> ipod, IncredibleCartoon<Panda<KungFu>> panda, ViciouslyBeautiful<KingKong> kingkong) {
   return new D(ipod, panda, kingkong);
 }
}.sequence(a, b, c);

あれ？、「言っていること違うんじゃね？そこらじゅうにブラケットだらけじねぇかよ。！」だって？

JAVA プログラマーよ、そんなに嘆くな。もう一個おもしろいものがあるんだぜ。

そいつは、”curry"っていうんだ。

Parser<D> d = Mapper.curry(D.class).sequence(a, b, c);

このcurry()メソッドっていうのは、カリー化のための引数をとる。それはなにかっていうと、たとえば、

構文解析する前に、クラスDのコンストラクターがわかっていたとするよね？さらに、Dクラスかどうかで、判定したい場合は、次のように記述します。

Parser<D> d = Mapper.curry(D.class, true).sequence(a, b, c);

↑

カリー化演算子の例 †

A real example is to parse the Java ternary "?:" operator. let's first assume that the conditional expression is modeled as:

public class ConditionaExpression implements Expression {
 // ...
 public ConditionalExpression(Expression cond, Expression consequence, Expression alternative) {
   // ...
 }
}

注意深く見てくれよ。"? consequence表現 :" の箇所は右側に２つの演算の指示(右結合のバイナリー演算子ともいう)を持っている. どんな表現も consequence表現になるが, "?:"は、cond表現よりも緊密にalternative表現に絡んでいる。

"?:"を右結合のバイナリー演算子として宣言するためには、僕らは、次のようなパーサを作んなきゃならない。

それは、 ”？”と”：”の間のconsequence表現の構文解析器だよね。んでもって、この構文解析器の戻り値は Map2 になるわけでさらに左側の演算指示箇所と右側の演算指示箇所を conditional表現に変換しなくてはなりません。ちょっとみてもらうとこんな具合です。:

static Parser<Binary<Expression>> conditionalOperator(Parser<Expression> consequence) {
 return Parsers.between(terminals.token("?"), consequence, terminals.token(":")).map(new Map<Expression, Binary<Expression>>() {
   public Binary<Expression> map(final Expression consequenceExpr) {
     return new Binary<Expression>() {
       public Expression map(Expression condExpr, Expression alternativeExpr) {
         return new ConditionalExpression(condExpr, consequenceExpr, alternativeExpr);
       }
     };
   }
 };
}

長いですね。複雑ですね。じっくり見ていただくためここで５分待ちましょうか。

（５分経過）

よーし、見ていただけたでしょうか

戻り値の

Parser<Binary<Expression>>

ってOperatorTable?内で以下のようにつかわれてます。

Parser.Reference<Expression> ref = Parser.newReference();
Parser<Expression> expression = new OperatorTable<Expression>()
 .prefix(...)
 .postfix(...)
 .infixr(conditionalOperator(ref.lazy()), 50)
 ....;
ref.set(expression);

私が本当に驚きをもって、いま、あなたにお見せしたいのは、じゃまな、匿名クラスの記述なしに、同等のことをMapperクラスをつかうことでできるということなんです。

次のようになるんですよ。

static Parser<Binary<Expression>> conditionalOperator(Parser<Expression> consequence) {
 return  Mapper.<Expression>curry(ConditionalExpression.class).infix(consequence.between(terminals.token("?"), terminals.token(":")));
}

このコードでさっきのめんどくさくてご立派なコードと同等のコードとなります。

そしてさらに＿メソッドを用意しておりまして、これを使うと、 "?" や":" の演算子の戻り値を気にせずに、直感的な記述になります。

import static org.codehaus.jparsec.misc.Mapper._;

static Parser<Binary<Expression>> conditionalOperator(Parser<Expression> consequence) {
 return Mapper.<Expression>curry(ConditionalExpression.class).infix(_(terminals.token("?")), consequence, _(terminals.token(":")));
}

↑

おわり †

Mapperクラスの狡猾な使い方としては、あなたがまともであれば、cglibを使うともっと便利になるかもしれません。

以上、日本語に適当に訳してみた。

↑

SQLの解析サンプルについて †

jparsecをダウンロードし、解凍すると [jparsec-2.0_src]-[examples]-[src]-[org]-[codehaus]-[jparsec]-[examples]-[sql] がある。

↑

Eclipseに取り込む手順 †

jparsecからダウンロードしてきたファイルを解凍しておきます。

junitのjarファイルも手元になければ、ダウンロードしてきます。

ダウンロードしてきたjunitはjunit-4.18.jarとかバージョン名がついているので、

junit.jarという名前にかえておきます。

junitはjparsecのlibフォルダに格納しておきます。

では、eclipseがわの準備を行ってみましょう。

Eclipseに新規にJavaプロジェクトを作成します。

ファイルメニューのインポートで先ほど解凍してできたフォルダを選択し、それをプロジェクトのsrcディレクトリを指定してとりこみます。

srcフォルダは、４つあります、本体用、本体test用、example用、exampleテスト用

インポート直後は

まだ、プロジェクトのビルドパスにjarが登録されていませんので、コンパイルエラーになっています。

そこで、ビルドパスの設定でparsecのlibフォルダ内のjarをすべて登録します。

コンパイルエラー表示はほぼ消えます。

が、１カ所だけAllTest?クラスでエラーになっています。

それは、作者がライブラリをあげたくないからだと build.xmlの８０行目に明記してありました。

こんな感じ、

AllTests uses jtc, which is an extra dependency that I don't want to upload.

おそらく、Androidのソースを流用したコードだから、著作権の問題であげれないとでも思ったのでしょうか。

それはさておき、

build.xmlには、このクラスのみ除外してコンパイルする記述がありました。

要するにいらないんです。この

だからbuild.xmlをいじくりたくなかったので、つぎのようにクラスを書き換えておきました。

package org.codehaus.jparsec;

//import org.openqa.jtc.junit.TestSuiteBuilder;

import junit.framework.TestSuite;

/**
*
* @author benyu
*/
public class AllTests extends TestSuite {
 public static TestSuite suite() {
   //return TestSuiteBuilder.suite(AllTests.class);
   return null;
 }
}

↑

コンパイル方法 †

build.xmlがあるので、toolは、ソースが公開されていないみたいなので、開発元の方用のantタスクかもしれません。それ以外はコンパイルできました。

↑

exampleにあるSQLパーサの使い方 †

exampleのテストケースをみると使い方が書いてありました。

↑

どこに書いてあるかというと †

↑

パッケージ名： †

package org.codehaus.jparsec.examples.sql.parser;

↑

クラス名： †

RelationParserTest?

↑

メソッド名： †

 public void testSelect() {

↑

内容の抜粋： †

SQLの問い合わせ文

select distinct 1, 2 as id from t1, t2

が下記のようにクラスの構造に解析されているのを確認しているテストコードが書かれていました。

   Parser<Relation> parser = RelationParser.select(NUMBER, NUMBER, TABLE);
   assertParser(parser, "select distinct 1, 2 as id from t1, t2",
       new Select(true, 
           Arrays.asList(new Projection(number(1), null), new Projection(number(2), "id")),
           Arrays.asList(table("t1"), table("t2")),
           null, null, null));

↑

persecのよみもの †

↑

Parsec, 高速なコンビネータパーサ †

文字コードをEUCにしないと文字化けします。

http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.html

jparsec入門 のバックアップ(No.5)

目次 †

jparsec †

チュートリアル †

日本語のjparsec使用ブログ †

俺的チュートリアル †

ゴール †

例 †