jparsec入門
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
単語検索
|
最終更新
|
ヘルプ
]
開始行:
[[構文解析の記事一覧]]
*目次 [#yca86807]
#contents
*jparsec [#e9851712]
http://jparsec.codehaus.org/
パーサ生成フレームワーク
YACCとの違いは外部ファイルを必要としない点が違う。
Ruby版も存在しており、rparsecという。言語の先頭1文字をと...
haskell版もあるがこちらが、元になっているので、こちらの名...
*チュートリアル [#sf63f7e4]
http://jparsec.codehaus.org/jparsec2+Tutorial
**日本語のjparsec使用ブログ [#x951ebb7]
だいたいチュートリアルの和訳相当だと思っていいです。
ちょっとTermクラスの名前が変わっているので、少々古いのか...
http://d.hatena.ne.jp/taichitaichi/20071008/1191808121
*例 [#qc0d3069]
今朝みれてたのに、例に出していた記事が404になって見れ...
I Hate Anonymous Classes
**URL [#c041eb23]
http://docs.codehaus.org/display/JPARSEC/I+Hate+Anonymous...
404になって見れなくなっているかもしれん
**本文 [#sa51b147]
*Jparsecの核心のアイデアについて(原文)I Hate Anonyous C...
お察しのとおり, jparsec全般的に関数脳的な考え方に基づい...
例えば, 次のクラスがあったとします。
-Parser<A>,
-Parser<B>
-Parser<C>
さらに、それらを順次、実行させ結果を使って、クラスDを作り...
Parser<D> d = Parsers.sequence(a, b, c, new Map3<A, B, C...
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<Unbelie...
public D map(UnbelievableGadget<Ipod> ipod, IncredibleC...
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プログラマーだっ...
あなたが自暴自棄になってやけを起こすまえにるまえに、まっ...
そんなあなたのためにこのMapperクラスをご用意致しました!...
Parser<D> d = new Mapper<D>() {
D map(UnbelievableGadget<Ipod> ipod, IncredibleCartoon<...
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のコンストラクターがわかっていた...
Parser<D> d = Mapper.curry(D.class, true).sequence(a, b,...
**カリー化 演算子の例 [#z5b6af9d]
A real example is to parse the Java ternary "?:" operator...
public class ConditionaExpression implements Expression {
// ...
public ConditionalExpression(Expression cond, Expressio...
// ...
}
}
注意深く見てくれよ。"? consequence表現 :" の箇所は右側に...
"?:"を右結合のバイナリー演算子として宣言するためには、僕...
それは、 ”?”と”:”の間のconsequence表現の構文解析器だよ...
んでもって、この構文解析器の戻り値は Map2 になるわけでさ...
static Parser<Binary<Expression>> conditionalOperator(Pa...
return Parsers.between(terminals.token("?"), consequenc...
public Binary<Expression> map(final Expression conseq...
return new Binary<Expression>() {
public Expression map(Expression condExpr, Expres...
return new ConditionalExpression(condExpr, cons...
}
};
}
};
}
長いですね。複雑ですね。じっくり見ていただくためここで5...
(5分経過)
よーし、見ていただけたでしょうか
戻り値の
Parser<Binary<Expression>>
ってOperatorTable内で以下のようにつかわれてます。
Parser.Reference<Expression> ref = Parser.newReference();
Parser<Expression> expression = new OperatorTable<Expres...
.prefix(...)
.postfix(...)
.infixr(conditionalOperator(ref.lazy()), 50)
....;
ref.set(expression);
私が本当に驚きをもって、いま、あなたにお見せしたいのは、...
次のようになるんですよ。
static Parser<Binary<Expression>> conditionalOperator(Pa...
return Mapper.<Expression>curry(ConditionalExpression....
}
このコードでさっきのめんどくさくてご立派なコードと同等の...
そしてさらに _メソッドを用意しておりまして、これを使うと...
import static org.codehaus.jparsec.misc.Mapper._;
static Parser<Binary<Expression>> conditionalOperator(Pa...
return Mapper.<Expression>curry(ConditionalExpression.c...
}
**おわり [#q129725e]
Mapperクラスの狡猾な使い方としては、あなたがまともであれ...
以上、日本語に適当に訳してみた。
つづいて、別の資料について解説を試みる
*尖がった括弧の解析 原文 That Pointy Brackets [#j2318e29]
**>>が書けない問題 [#k409af8b]
C++では, 入れ子状のテンプレートには(まだ、やってんのかわ...
"Foo<Bar<int>>"
何でかっていうと ">>" って右シフト演算子なのであって、">"...
でも、Javaにはこんな制限事項ってないんです。 It is still ...
One possible solution is to muck around with the grammar ...
**jparsecでの解決方法 [#mfde038b]
Jparsec provides a simpler solution (check out the Java p...
In lexical analysis phase, "<" and ">" characters are uni...
***For example: [#o076df9c]
private static final String[] OPERATORS = {
"+", "-", "*", "/", ">", "<", ">=", "<=", // and all ot...
};
private static final String[] KEYWORDS = {
"interface", "class", "enum", "private", "public", "pro...
};
private static final Terminals TERMINALS = Terminals.cas...
//...
Now that makes it real simple for parsing nested generic ...
What happens is that lexical analysis phase has no idea o...
By adjacent, I mean that they have to be next to each oth...
Luckily, the Token class carries the physical index in th...
public static Parser<Token> adjacent(Parser<List<Token>>...
return parser.next(new Map<List<Token>, Parser<Object>>...
public Parser<Object> map(List<Token> tokens) {
if (tokens.isEmpty()) return Parsers.always();
int offset = tokens.get(0).index();
for (Token token : tokens) {
if (token.index() != offset) {
return Parsers.expect(name);
}
offset += token.length();
}
return Parsers.always();
}
}).atomic().source().token();
}
The above code checks that the list of tokens returned by...
And then we can use the list() combinator to turn a the s...
public static Parser<Token> adjacent(String operator) {
List<Parser<Token>> parsers = new ArrayList<Parser<Toke...
for (int i = 0; i < operator.length(); i++) {
parsers.add(TERMINALS.token(Character.toString(operat...
}
return adjacent(Parsers.list(parsers), operator);
}
And by calling adjacent(">>>"), we get a parser that pars...
One catch is that we need to make sure ">>" is not a pref...
static final Parser<?> UNSIGNED_RIGHT_SHIFT = adjacent(">...
static final Parser<?> RIGHT_SHIFT = UNSIGNED_RIGHT_SHIFT...
And that's about it. The same code can be applied to "<<"...
Labels parameters
Labels
Enter labels to add to this page:
Please wait
Looking for a label? Just start typing.
つづいて、別の資料について解説を試みる
対象はソースをダウンロードしてくると付いてくるサンプルコ...
*SQLの解析サンプルについて [#of950202]
jparsecをダウンロードし、解凍すると
[jparsec-2.0_src]-[examples]-[src]-[org]-[codehaus]-[jpar...
がある。
**Eclipseに取り込む手順 [#o49a3671]
jparsecからダウンロードしてきたファイルを解凍しておきます。
junitのjarファイルも手元になければ、ダウンロードしてきま...
ダウンロードしてきたjunitはjunit-4.18.jarとかバージョン名...
junit.jarという名前にかえておきます。
junitはjparsecのlibフォルダに格納しておきます。
では、eclipseがわの準備を行ってみましょう。
Eclipseに新規にJavaプロジェクトを作成します。
ファイルメニューのインポートで先ほど解凍してできたフォル...
srcフォルダは、4つあります、本体用、本体test用、example...
インポート直後は
まだ、プロジェクトのビルドパスにjarが登録されていませんの...
そこで、ビルドパスの設定でparsecのlibフォルダ内のjarをす...
コンパイルエラー表示はほぼ消えます。
が、1カ所だけAllTestクラスでエラーになっています。
それは、作者がライブラリをあげたくないからだと
build.xmlの80行目に明記してありました。
こんな感じ、
AllTests uses jtc, which is an extra dependency that I d...
おそらく、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は、ソースが公開されていないみた...
**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(NUMBE...
assertParser(parser, "select distinct 1, 2 as id from...
new Select(true,
Arrays.asList(new Projection(number(1), null)...
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.h...
*俺的チュートリアルを書いてみる [#la10fd7b]
実は、jparsecのソースコードをダウンロードすると、計算機の...
これがチュートリアルで解説してあるようなコードよりもすっ...
だから、このサンプルから逆に構築する手順を、観察力+妄想...
**ゴール [#k0421c8f]
はっきりとしたゴールがあるってことは、それだけでも、しあ...
まずは、四則演算の構文解析の作成方法を理解できるようにす...
四則演算って、いろいろな言語の基本的機能だから、構文解析...
言語を解析するには、数学でいうところの必要条件にすぎない。
ちなみに、下記のコードを作れるような手順をコードから逆に...
その後、BNFの解析なども行います。
/**
* The main calculator parser.
*
* @author Ben Yu
*/
public final class Calculator {
/** Parsers {@code source} and evaluates to an {@link I...
public static int evaluate(String source) {
return parser().parse(source);
}
static final Parser<Integer> NUMBER = Scanners.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('(')...
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;
}
}
*大まかな概念 [#qe9b8e5b]
解析するものは、括弧などで括られている箇所はparenと命名す...
中身をExpressionと命名する。
*Jparsecのサンプルから説明書を作ってみる。 [#z9c4734a]
**パッケージ構成 [#m99766da]
まずパーサにフォルダとしてastフォルダとpaserフォルダを作...
astフォルダは構文を解析した結果を保存しておくクラスです。
***astのクラスについて [#g15aed37]
astに格納するクラスの大部分は
ValueObjectクラスを継承しており、それ以外の残りのクラスは...
***Interface [#d89592c1]
Interfaceには、これから解析しようとする対象を意味する名前...
インタフェースを用意します。
このInterfaceは、構文木の末端のクラス名を意味するようにし...
**paserパッケージのクラスの作成 [#y885539b]
入れ物であるクラスの定義が終われば、今度はpaserパッケージ...
大雑把に言って入れ物を作って次の順番でクラスを構築してい...
全体的な入れ物は
Parser.Reference<Integer> ref = Parser.newReference();
で定義します。
この文をサンプルで探すとメインの処理が見つかりますが、複...
いくつか要所要所ででてきます。
たとえば、一番簡単な計算機のサンプルは、SQLのサンプルでは...
(サンプルのarithmeticメソッド参照)
**末端表現をパターンで記述 [#a19619d8]
対象を表す正規表現と入れ物として定義したクラスを頭の中で...
よく使うものであれば、
Scannersにはよく使うであろう正規表現のPatternクラスのイン...
Terminalsにもよく使うであろう物が登録されています。
Terminalsはcurryのsequenceメソッドの引数に使うような設計...
Scannersクラスで定義されていないかどうか確認します。
Scannersクラスで定義されていない場合、演算子の場合はStrin...
private static final String[] OPERATORS = {"*", "+", "?...
と定義したとすると、
private static final Terminals TERMS = Terminals.operat...
に格納します。
これらは、ルール定義の際に、
Mapper._(TERMS.token(name))
入れ物のクラスが決まれば、次の定型文で単位を定義できます。
static final Parser<Rule> LITERAL =
Mapper.curry(LiteralRule.class).sequence(いまからせ...
**Patternの定義 正規表現に使う名前を決める [#xa25f797]
Scanners.isPatternで正規表現をメソッドで置き換えたPattern...
たとえば、正規表現の「+」はmany1となります。
-分割の場合は sepBy1
-複数条件のOR結合はor
-間に挟む場合はbetween
ただしどれも、引数には、Mapper._(TERMS.token(name))のname...
***頻繁に使うであろうPatternクラス [#c7c08a6f]
Scannersにはよく使うであろう正規表現のPatternクラスのイン...
**Pattern Patternsクラスで定義 [#h75daaee]
Parser<_> Scanners.isPatternで定義
例:Parser<Integer> NUMBER
Parser<Tok> Lexers.lexerで定義
**演算子の組み立て方 [#hb0a41b0]
基本的にmapというメソッドをオーバロードさせていきます。
必要なパラメータは、どんな記号なのか?
その次に、何項演算子なのかでクラスが異なります。
2項演算子の場合はBinary<Integer>で、演算子は数値の真ん中...
OperatorTableの.infixlで登録
1項演算子の場合はUnary<Integer>で、演算子は数値の先頭に...
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);
**括弧を定義する場合 [#sff090ac]
昔はこんな感じでTermsクラスがあったみたいですが、
final Terms ops = Terms.getOperatorsInstance("+", "-", "...
いまは、
括弧の中身をすぐには評価しないので、lazyをつけ、対になっ...
下記のようにorで連結していきます。
Parser<Integer> term = ref.lazy().between(isChar('('), i...
で、OperatorTableの最後にbuildの引数として格納します。
**構文を定義する。 [#u8e80826]
***SELECT文の定義例 [#p48d3599]
たとえばSELECT文を定義してみます。
構文には、単体で意味のある箇所と
条件文のように塊で意味のある箇所があります。
さらに括弧のようなもっと上の優先順位で評価される塊を表現...
構文解析ではこのような、構成要素の数でパーサを分類してい...
引数の数でこの分類を観察すると、1,2,3とひとつづつ増...
**インデントとスペース、コメントなどの除去 [#c5147af5]
最後は、インデントとスペースを除去して解析するように記述...
たとえば、このような感じである。
static <T> T parse(Parser<T> parser, String source) {
return parser.from(INDENTATION.lexer(TOKENIZER, Inden...
.parse(source);
}
***素朴な疑問 [#h2637aaf]
作者はunionとか、なぜ注意深く定義できたのか?
bnf SQL selectで検索してみた。
http://savage.net.au/SQL/sql-92.bnf.html
あまり関係がないようだ。
自分で解析しているのかもしれない。
*delete文の解析機を作ってみる。 [#f89a5667]
未記入
終了行:
[[構文解析の記事一覧]]
*目次 [#yca86807]
#contents
*jparsec [#e9851712]
http://jparsec.codehaus.org/
パーサ生成フレームワーク
YACCとの違いは外部ファイルを必要としない点が違う。
Ruby版も存在しており、rparsecという。言語の先頭1文字をと...
haskell版もあるがこちらが、元になっているので、こちらの名...
*チュートリアル [#sf63f7e4]
http://jparsec.codehaus.org/jparsec2+Tutorial
**日本語のjparsec使用ブログ [#x951ebb7]
だいたいチュートリアルの和訳相当だと思っていいです。
ちょっとTermクラスの名前が変わっているので、少々古いのか...
http://d.hatena.ne.jp/taichitaichi/20071008/1191808121
*例 [#qc0d3069]
今朝みれてたのに、例に出していた記事が404になって見れ...
I Hate Anonymous Classes
**URL [#c041eb23]
http://docs.codehaus.org/display/JPARSEC/I+Hate+Anonymous...
404になって見れなくなっているかもしれん
**本文 [#sa51b147]
*Jparsecの核心のアイデアについて(原文)I Hate Anonyous C...
お察しのとおり, jparsec全般的に関数脳的な考え方に基づい...
例えば, 次のクラスがあったとします。
-Parser<A>,
-Parser<B>
-Parser<C>
さらに、それらを順次、実行させ結果を使って、クラスDを作り...
Parser<D> d = Parsers.sequence(a, b, c, new Map3<A, B, C...
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<Unbelie...
public D map(UnbelievableGadget<Ipod> ipod, IncredibleC...
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プログラマーだっ...
あなたが自暴自棄になってやけを起こすまえにるまえに、まっ...
そんなあなたのためにこのMapperクラスをご用意致しました!...
Parser<D> d = new Mapper<D>() {
D map(UnbelievableGadget<Ipod> ipod, IncredibleCartoon<...
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のコンストラクターがわかっていた...
Parser<D> d = Mapper.curry(D.class, true).sequence(a, b,...
**カリー化 演算子の例 [#z5b6af9d]
A real example is to parse the Java ternary "?:" operator...
public class ConditionaExpression implements Expression {
// ...
public ConditionalExpression(Expression cond, Expressio...
// ...
}
}
注意深く見てくれよ。"? consequence表現 :" の箇所は右側に...
"?:"を右結合のバイナリー演算子として宣言するためには、僕...
それは、 ”?”と”:”の間のconsequence表現の構文解析器だよ...
んでもって、この構文解析器の戻り値は Map2 になるわけでさ...
static Parser<Binary<Expression>> conditionalOperator(Pa...
return Parsers.between(terminals.token("?"), consequenc...
public Binary<Expression> map(final Expression conseq...
return new Binary<Expression>() {
public Expression map(Expression condExpr, Expres...
return new ConditionalExpression(condExpr, cons...
}
};
}
};
}
長いですね。複雑ですね。じっくり見ていただくためここで5...
(5分経過)
よーし、見ていただけたでしょうか
戻り値の
Parser<Binary<Expression>>
ってOperatorTable内で以下のようにつかわれてます。
Parser.Reference<Expression> ref = Parser.newReference();
Parser<Expression> expression = new OperatorTable<Expres...
.prefix(...)
.postfix(...)
.infixr(conditionalOperator(ref.lazy()), 50)
....;
ref.set(expression);
私が本当に驚きをもって、いま、あなたにお見せしたいのは、...
次のようになるんですよ。
static Parser<Binary<Expression>> conditionalOperator(Pa...
return Mapper.<Expression>curry(ConditionalExpression....
}
このコードでさっきのめんどくさくてご立派なコードと同等の...
そしてさらに _メソッドを用意しておりまして、これを使うと...
import static org.codehaus.jparsec.misc.Mapper._;
static Parser<Binary<Expression>> conditionalOperator(Pa...
return Mapper.<Expression>curry(ConditionalExpression.c...
}
**おわり [#q129725e]
Mapperクラスの狡猾な使い方としては、あなたがまともであれ...
以上、日本語に適当に訳してみた。
つづいて、別の資料について解説を試みる
*尖がった括弧の解析 原文 That Pointy Brackets [#j2318e29]
**>>が書けない問題 [#k409af8b]
C++では, 入れ子状のテンプレートには(まだ、やってんのかわ...
"Foo<Bar<int>>"
何でかっていうと ">>" って右シフト演算子なのであって、">"...
でも、Javaにはこんな制限事項ってないんです。 It is still ...
One possible solution is to muck around with the grammar ...
**jparsecでの解決方法 [#mfde038b]
Jparsec provides a simpler solution (check out the Java p...
In lexical analysis phase, "<" and ">" characters are uni...
***For example: [#o076df9c]
private static final String[] OPERATORS = {
"+", "-", "*", "/", ">", "<", ">=", "<=", // and all ot...
};
private static final String[] KEYWORDS = {
"interface", "class", "enum", "private", "public", "pro...
};
private static final Terminals TERMINALS = Terminals.cas...
//...
Now that makes it real simple for parsing nested generic ...
What happens is that lexical analysis phase has no idea o...
By adjacent, I mean that they have to be next to each oth...
Luckily, the Token class carries the physical index in th...
public static Parser<Token> adjacent(Parser<List<Token>>...
return parser.next(new Map<List<Token>, Parser<Object>>...
public Parser<Object> map(List<Token> tokens) {
if (tokens.isEmpty()) return Parsers.always();
int offset = tokens.get(0).index();
for (Token token : tokens) {
if (token.index() != offset) {
return Parsers.expect(name);
}
offset += token.length();
}
return Parsers.always();
}
}).atomic().source().token();
}
The above code checks that the list of tokens returned by...
And then we can use the list() combinator to turn a the s...
public static Parser<Token> adjacent(String operator) {
List<Parser<Token>> parsers = new ArrayList<Parser<Toke...
for (int i = 0; i < operator.length(); i++) {
parsers.add(TERMINALS.token(Character.toString(operat...
}
return adjacent(Parsers.list(parsers), operator);
}
And by calling adjacent(">>>"), we get a parser that pars...
One catch is that we need to make sure ">>" is not a pref...
static final Parser<?> UNSIGNED_RIGHT_SHIFT = adjacent(">...
static final Parser<?> RIGHT_SHIFT = UNSIGNED_RIGHT_SHIFT...
And that's about it. The same code can be applied to "<<"...
Labels parameters
Labels
Enter labels to add to this page:
Please wait
Looking for a label? Just start typing.
つづいて、別の資料について解説を試みる
対象はソースをダウンロードしてくると付いてくるサンプルコ...
*SQLの解析サンプルについて [#of950202]
jparsecをダウンロードし、解凍すると
[jparsec-2.0_src]-[examples]-[src]-[org]-[codehaus]-[jpar...
がある。
**Eclipseに取り込む手順 [#o49a3671]
jparsecからダウンロードしてきたファイルを解凍しておきます。
junitのjarファイルも手元になければ、ダウンロードしてきま...
ダウンロードしてきたjunitはjunit-4.18.jarとかバージョン名...
junit.jarという名前にかえておきます。
junitはjparsecのlibフォルダに格納しておきます。
では、eclipseがわの準備を行ってみましょう。
Eclipseに新規にJavaプロジェクトを作成します。
ファイルメニューのインポートで先ほど解凍してできたフォル...
srcフォルダは、4つあります、本体用、本体test用、example...
インポート直後は
まだ、プロジェクトのビルドパスにjarが登録されていませんの...
そこで、ビルドパスの設定でparsecのlibフォルダ内のjarをす...
コンパイルエラー表示はほぼ消えます。
が、1カ所だけAllTestクラスでエラーになっています。
それは、作者がライブラリをあげたくないからだと
build.xmlの80行目に明記してありました。
こんな感じ、
AllTests uses jtc, which is an extra dependency that I d...
おそらく、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は、ソースが公開されていないみた...
**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(NUMBE...
assertParser(parser, "select distinct 1, 2 as id from...
new Select(true,
Arrays.asList(new Projection(number(1), null)...
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.h...
*俺的チュートリアルを書いてみる [#la10fd7b]
実は、jparsecのソースコードをダウンロードすると、計算機の...
これがチュートリアルで解説してあるようなコードよりもすっ...
だから、このサンプルから逆に構築する手順を、観察力+妄想...
**ゴール [#k0421c8f]
はっきりとしたゴールがあるってことは、それだけでも、しあ...
まずは、四則演算の構文解析の作成方法を理解できるようにす...
四則演算って、いろいろな言語の基本的機能だから、構文解析...
言語を解析するには、数学でいうところの必要条件にすぎない。
ちなみに、下記のコードを作れるような手順をコードから逆に...
その後、BNFの解析なども行います。
/**
* The main calculator parser.
*
* @author Ben Yu
*/
public final class Calculator {
/** Parsers {@code source} and evaluates to an {@link I...
public static int evaluate(String source) {
return parser().parse(source);
}
static final Parser<Integer> NUMBER = Scanners.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('(')...
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;
}
}
*大まかな概念 [#qe9b8e5b]
解析するものは、括弧などで括られている箇所はparenと命名す...
中身をExpressionと命名する。
*Jparsecのサンプルから説明書を作ってみる。 [#z9c4734a]
**パッケージ構成 [#m99766da]
まずパーサにフォルダとしてastフォルダとpaserフォルダを作...
astフォルダは構文を解析した結果を保存しておくクラスです。
***astのクラスについて [#g15aed37]
astに格納するクラスの大部分は
ValueObjectクラスを継承しており、それ以外の残りのクラスは...
***Interface [#d89592c1]
Interfaceには、これから解析しようとする対象を意味する名前...
インタフェースを用意します。
このInterfaceは、構文木の末端のクラス名を意味するようにし...
**paserパッケージのクラスの作成 [#y885539b]
入れ物であるクラスの定義が終われば、今度はpaserパッケージ...
大雑把に言って入れ物を作って次の順番でクラスを構築してい...
全体的な入れ物は
Parser.Reference<Integer> ref = Parser.newReference();
で定義します。
この文をサンプルで探すとメインの処理が見つかりますが、複...
いくつか要所要所ででてきます。
たとえば、一番簡単な計算機のサンプルは、SQLのサンプルでは...
(サンプルのarithmeticメソッド参照)
**末端表現をパターンで記述 [#a19619d8]
対象を表す正規表現と入れ物として定義したクラスを頭の中で...
よく使うものであれば、
Scannersにはよく使うであろう正規表現のPatternクラスのイン...
Terminalsにもよく使うであろう物が登録されています。
Terminalsはcurryのsequenceメソッドの引数に使うような設計...
Scannersクラスで定義されていないかどうか確認します。
Scannersクラスで定義されていない場合、演算子の場合はStrin...
private static final String[] OPERATORS = {"*", "+", "?...
と定義したとすると、
private static final Terminals TERMS = Terminals.operat...
に格納します。
これらは、ルール定義の際に、
Mapper._(TERMS.token(name))
入れ物のクラスが決まれば、次の定型文で単位を定義できます。
static final Parser<Rule> LITERAL =
Mapper.curry(LiteralRule.class).sequence(いまからせ...
**Patternの定義 正規表現に使う名前を決める [#xa25f797]
Scanners.isPatternで正規表現をメソッドで置き換えたPattern...
たとえば、正規表現の「+」はmany1となります。
-分割の場合は sepBy1
-複数条件のOR結合はor
-間に挟む場合はbetween
ただしどれも、引数には、Mapper._(TERMS.token(name))のname...
***頻繁に使うであろうPatternクラス [#c7c08a6f]
Scannersにはよく使うであろう正規表現のPatternクラスのイン...
**Pattern Patternsクラスで定義 [#h75daaee]
Parser<_> Scanners.isPatternで定義
例:Parser<Integer> NUMBER
Parser<Tok> Lexers.lexerで定義
**演算子の組み立て方 [#hb0a41b0]
基本的にmapというメソッドをオーバロードさせていきます。
必要なパラメータは、どんな記号なのか?
その次に、何項演算子なのかでクラスが異なります。
2項演算子の場合はBinary<Integer>で、演算子は数値の真ん中...
OperatorTableの.infixlで登録
1項演算子の場合はUnary<Integer>で、演算子は数値の先頭に...
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);
**括弧を定義する場合 [#sff090ac]
昔はこんな感じでTermsクラスがあったみたいですが、
final Terms ops = Terms.getOperatorsInstance("+", "-", "...
いまは、
括弧の中身をすぐには評価しないので、lazyをつけ、対になっ...
下記のようにorで連結していきます。
Parser<Integer> term = ref.lazy().between(isChar('('), i...
で、OperatorTableの最後にbuildの引数として格納します。
**構文を定義する。 [#u8e80826]
***SELECT文の定義例 [#p48d3599]
たとえばSELECT文を定義してみます。
構文には、単体で意味のある箇所と
条件文のように塊で意味のある箇所があります。
さらに括弧のようなもっと上の優先順位で評価される塊を表現...
構文解析ではこのような、構成要素の数でパーサを分類してい...
引数の数でこの分類を観察すると、1,2,3とひとつづつ増...
**インデントとスペース、コメントなどの除去 [#c5147af5]
最後は、インデントとスペースを除去して解析するように記述...
たとえば、このような感じである。
static <T> T parse(Parser<T> parser, String source) {
return parser.from(INDENTATION.lexer(TOKENIZER, Inden...
.parse(source);
}
***素朴な疑問 [#h2637aaf]
作者はunionとか、なぜ注意深く定義できたのか?
bnf SQL selectで検索してみた。
http://savage.net.au/SQL/sql-92.bnf.html
あまり関係がないようだ。
自分で解析しているのかもしれない。
*delete文の解析機を作ってみる。 [#f89a5667]
未記入
ページ名: