[[構文解析の記事一覧]]
*目次 [#yca86807]
#contents
*jparsec [#e9851712]
http://jparsec.codehaus.org/
パーサ生成フレームワーク
YACCとの違いは外部ファイルを必要としない点が違う。
Ruby版も存在しており、rparsecという。言語の先頭１文字をとって区別をつけている。
haskell版もあるがこちらが、元になっているので、こちらの名前はparsecという。
*チュートリアル [#sf63f7e4]
http://jparsec.codehaus.org/jparsec2+Tutorial
**日本語のjparsec使用ブログ [#x951ebb7]
だいたいチュートリアルの和訳相当だと思っていいです。
http://d.hatena.ne.jp/taichitaichi/20071008/1191808121
*俺的チュートリアル [#la10fd7b]
実は、jparsecのソースコードをダウンロードすると、計算機のサンプルコードが入っていて、
これがチュートリアルで解説してあるようなコードよりもすっきりさわやかなコードなのだ。
だから、このサンプルから逆に構築する手順を、観察力＋妄想力で、作り、俺的チュートリアルをつくるのだ！。それが、漢ってもんだろ。
**ゴール [#k0421c8f]
はっきりとしたゴールがあるってことは、それだけでも、しあわせなことなのさ。
とか、書いておきながら、まだ書きかけだったりします。
/**
* 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;
}
}
*例 [#qc0d3069]
今朝みれてたのに、例に出していた記事が４０４になって見れなくなっていた、あわててgoogleのキャッシュから保存する。
I Hate Anonymous Classes
**URL [#c041eb23]
http://docs.codehaus.org/display/JPARSEC/I+Hate+Anonymous+Classes
404になって見れなくなっているかもしれん
**本文 [#sa51b147]
*Jparsecの核心のアイデアについて（原文）I Hate Anonyous Classes! [#v1db40ab]
お察しのとおり, 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クラス [#r2d724a4]
というわけで、こんな時には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);
**カリー化 演算子の例 [#z5b6af9d]
After careful observation of the precedence and associativity, the "? consequenceExpression :" part is indeed a right-associative binary operator. Any expression can be the consequenceExpression, but the "?:" binds more tightly to the alternativeExpression than the condExpression.
In order to declare the "?:" operator as a binary right associative operator, we'll need to create a parser that parses the consequence expression between a "?" and a ":". This parser should return a Map2 that transforms the left operand (condition) and the right operand (alternative) to the conditional expression. Like this:
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);
}
};
}
};
}
I'll pause for 5 minutes for you to read through the above code snippet and understand the wits buried in the annonymous class nested in the outer anonymous class, and of course, to understand this sentence.
Okay, time's up.
The returned Parser<Binary<Expression>> can then be used in an OperatorTable, as:
Parser.Reference<Expression> ref = Parser.newReference();
Parser<Expression> expression = new OperatorTable<Expression>()
.prefix(...)
.postfix(...)
.infixr(conditionalOperator(ref.lazy()), 50)
....;
ref.set(expression);
And if you now see what I'm really up to, and unsurprisingly not impressed by the extra noises in the anonymous classes, here's how we can do it differently with Mapper:
static Parser<Binary<Expression>> conditionalOperator(Parser<Expression> consequence) {
return Mapper.<Expression>curry(ConditionalExpression.class).infix(consequence.between(terminals.token("?"), terminals.token(":")));
}
This code does exactly the same thing as our super duper anonymous classes above.
And using the _ method to explicitly ignore the return values of the "?" and ":" operators, we can make it look even more intuitive:
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(":")));
}
**The End [#q129725e]
For something as cunning as Mapper, I hope you aren't surprised by its extra requirement of cglib to stay sane performance wise.
Labels parameters
*SQLの解析サンプルについて [#of950202]
jparsecをダウンロードし、解凍すると
[jparsec-2.0_src]-[examples]-[src]-[org]-[codehaus]-[jparsec]-[examples]-[sql]
がある。
**Eclipseに取り込む手順 [#o49a3671]
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;
}
}
**コンパイル方法 [#v14b1801]
build.xmlがあるので、toolは、ソースが公開されていないみたいなので、開発元の方用のantタスクかもしれません。それ以外はコンパイルできました。
**exampleにあるSQLパーサの使い方 [#ded7b6e6]
exampleのテストケースをみると使い方が書いてありました。
***どこに書いてあるかというと [#fae6fde4]
***パッケージ名： [#n1f6c4af]
package org.codehaus.jparsec.examples.sql.parser;
***クラス名： [#i643a3ac]
RelationParserTest
***メソッド名： [#s819af7a]
public void testSelect() {
***内容の抜粋： [#p5e84e0f]
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のよみもの [#g2d334d4]
**Parsec, 高速なコンビネータパーサ [#rf72fbda]
文字コードをEUCにしないと文字化けします。
http://www.lab2.kuis.kyoto-u.ac.jp/~hanatani/tmp/Parsec.html
