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

/**
* 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

↑

大まかな概念 †

解析するものは、括弧などで括られている箇所はparenと命名する。中身をExpressionと命名する。

↑

Patternの定義 †

↑

Jparsecのサンプルから説明書を作ってみる。 †

↑

パッケージ構成 †

まずパーサにフォルダとしてastフォルダとpaserフォルダを作ります。

astフォルダは構文を解析した結果を保存しておくクラスです。

↑

astのクラスについて †

astに格納するクラスの大部分は ValueObject?クラスを継承しており、それ以外の残りのクラスはenum型やInterfaceです。

↑

Interface †

Interfaceには、これから解析しようとする対象を意味する名前だけでもいいので、シンプルなインタフェースを用意します。

このInterfaceは、構文木の末端のクラス名を意味するようにします。

入れ物であるクラスの定義が終われば、今度はpaserパッケージのクラスの作成をします。

大雑把に言って入れ物を作って次の順番でクラスを構築していく感じです。全体的な入れ物は

Parser.Reference<Integer> ref = Parser.newReference();

で定義します。

この文をサンプルで探すとメインの処理が見つかりますが、複雑な構文になってくると、ルールごとに部分部分で解析するため、いくつか要所要所ででてきます。たとえば、一番簡単な計算機のサンプルは、SQLのサンプルではExpressionの構文解析の一機能にすぎません。（サンプルのarithmeticメソッド参照)

対象を表す正規表現と入れ物として定義したクラスを頭の中でイメージします。（実装ではPatternクラスのメソッドで正規表現を表現します。）よく使うものであれば、 Scannersにはよく使うであろう正規表現のPatternクラスのインスタンスが登録されていますし、 Terminalsにもよく使うであろう物が登録されています。 Terminalsはcurryのsequenceメソッドの引数に使うような設計です。

Scannersクラスで定義されていないかどうか確認します。

Scannersクラスで定義されていない場合、演算子の場合はString[]型で

 private static final String[] OPERATORS = {"*", "+", "?", "|", "::=", "(", ")"};

と定義したとすると、

 private static final Terminals TERMS = Terminals.operators(OPERATORS);
 に格納します。
 
 これらは、ルール定義の際に、Mapper._(TERMS.token(name))

入れ物のクラスが決まれば、次の定型文で単位を定義できます。 static final Parser<Rule> LITERAL =

     Mapper.curry(LiteralRule.class).sequence(いまからせつめいする引数)

↑

正規表現に使う名前を決める †

Scanners.isPatternで正規表現をメソッドで置き換えたPatternクラスのインスタンスを登録します。たとえば、正規表現の「+」はmany1となります。

分割の場合は sepBy1
複数条件のOR結合はor
間に挟む場合はbetween

ただしどれも、引数には、Mapper._(TERMS.token(name))のnameに登録済みの文字列を入れたものを使います。

Scannersにはよく使うであろう正規表現のPatternクラスのインスタンスが登録されています。

Pattern Patternsクラスで定義 Parser<_> Scanners.isPatternで定義

例：Parser<Integer> NUMBER

Parser<Tok> Lexers.lexerで定義

↑

演算子の組み立て方 †

基本的にmapというメソッドをオーバロードさせていきます。

必要なパラメータは、どんな記号なのか？その次に、何項演算子なのかでクラスが異なります。２項演算子の場合はBinary<Integer>で、演算子は数値の真ん中に来るので、

OperatorTable?の.infixlで登録１項演算子の場合はUnary<Integer>で、演算子は数値の先頭にくるので、.prefixで登録します。

 static final Unary<Integer> NEG = new Unary<Integer>() {
   public Integer map(Integer i) {
     return -i;
   }
 };

 static final Binary<Integer> PLUS = new Binary<Integer>() {
   public Integer map(Integer a, Integer b) {
     return a + b;
   }
 };

   Parser<Integer> parser = new OperatorTable<Integer>()
       .prefix(op('-', NEG), 100)
       .infixl(op('+', PLUS), 10)
       .build(term);

↑

括弧を定義する場合 †

昔はこんな感じでTermsクラスがあったみたいですが、

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

いまは、括弧の中身をすぐには評価しないので、lazyをつけ、対になっている「(」と「)」をbetweenで括ります。もし、その対でなければ、下記のようにorで連結していきます。

Parser<Integer> term = ref.lazy().between(isChar('('), isChar(')')).or(NUMBER);

で、OperatorTable?の最後にbuildの引数として格納します。

↑

構文を定義する。 †

たとえばSELECT文を定義してみます。

構文には、単体で意味のある箇所と

条件文のように塊で意味のある箇所があります。

さらに括弧のようなもっと上の優先順位で評価される塊を表現する箇所があり、

構文解析ではこのような、構成要素の数でパーサを分類していきます。

引数の数でこの分類を観察すると、１，２，３とひとつづつ増えていっています。

最後は、インデントとスペースを除去して解析するように記述する。

たとえば、このような感じである。

 static <T> T parse(Parser<T> parser, String source) {
   return parser.from(INDENTATION.lexer(TOKENIZER, Indentation.WHITESPACES.or(COMMENT).many()))
       .parse(source);
 }

↑

素朴な疑問 †

作者はunionとか、なぜ注意深く定義できたのか？

bnf SQL selectで検索してみた。

http://savage.net.au/SQL/sql-92.bnf.html

あまり関係がないようだ。

自分で解析しているのかもしれない。

↑

delete文の解析機を作ってみる。 †

未記入

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

目次 †

jparsec †

チュートリアル †

日本語のjparsec使用ブログ †

俺的チュートリアル †

ゴール †

例 †