jparsec入門の編集

[ トップ ] [ 編集 | 差分 | バックアップ | 添付 | リロード ] [ 新規 | 一覧 | 単語検索 | 最終更新 | ヘルプ ]

[[構文解析の記事一覧]]
*目次 [#yca86807]
#contents
*jparsec [#e9851712]
http://jparsec.codehaus.org/

パーサ生成フレームワーク

YACCとの違いは外部ファイルを必要としない点が違う。

Ruby版も存在しており、rparsecという。言語の先頭１文字をとって区別をつけている。
haskell版もあるがこちらが、元になっているので、こちらの名前はparsecという。

*チュートリアル [#sf63f7e4]
http://jparsec.codehaus.org/jparsec2+Tutorial

**日本語のjparsec使用ブログ [#x951ebb7]

だいたいチュートリアルの和訳相当だと思っていいです。

ちょっとTermクラスの名前が変わっているので、少々古いのかもしれません。

http://d.hatena.ne.jp/taichitaichi/20071008/1191808121

*例 [#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]
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(":")));
 }
**おわり [#q129725e]

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

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

つづいて、別の資料について解説を試みる

*尖がった括弧の解析 原文 That Pointy Brackets [#j2318e29]

**>>が書けない問題 [#k409af8b]

C++では, 入れ子状のテンプレートには(まだ、やってんのかわかんないけど) 特殊な文法 があって、そいつのせいで次の記述が書けなくなっている。
 "Foo<Bar<int>>"
何でかっていうと ">>" って右シフト演算子なのであって、">"が２つ並んだ演算子ではないってことなのさ。すでに複雑になっている文法がよりいっそう複雑になっちゃいますねぇ。

でも、Javaにはこんな制限事項ってないんです。 It is still the job of the parser to properly disambiguate ">>" in expression from ">>" in nested generic types.

One possible solution is to muck around with the grammar so that ">>" is used in both generics and expression. The cost is that multiple not-so-intuitive production rules need to be introduced to work around the ambiguity.
**jparsecでの解決方法 [#mfde038b]

Jparsec provides a simpler solution (check out the Java parser sample in the source code).

In lexical analysis phase, "<" and ">" characters are uniformly tokenized individually. There will be no token for "<<", "<<<", ">>", or ">>>". Thus in parsing generic types, the parser will not be confused by any ">>" tokens.

***For example: [#o076df9c]

private static final String[] OPERATORS = {
  "+", "-", "*", "/", ">", "<", ">=", "<=", // and all other operators.
 };
 private static final String[] KEYWORDS = {
  "interface", "class", "enum", "private", "public", "protected", // all other operators
 };
 private static final Terminals TERMINALS = Terminals.caseSensitive(OPERATORS, KEYWORDS);
 //...

Now that makes it real simple for parsing nested generic types with the pointy brackets. But what about the "<<" and ">>" operators used in expression?

What happens is that lexical analysis phase has no idea of what context the current token is in, but in syntactical analysis we know whether we are parsing a generic type or an expression. In the latter case, we will treat three adjacent ">" tokens as one single ">>>" operator, and two adjacent ">" tokens as one single ">>" operator.

By adjacent, I mean that they have to be next to each other in the original source, if the first ">" character appears at line 7 column 6, the next one has to be at line 7, column 7. In other words, their physical indexes in the original source are adjacent.

Luckily, the Token class carries the physical index in the original source. By using the next() combinator, we can specially handle the "adjacency":

public static Parser<Token> adjacent(Parser<List<Token>> parser, final String name) {
  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 a parser are adjacent.

And then we can use the list() combinator to turn a the special operator string to the parser that returns token list:

public static Parser<Token> adjacent(String operator) {
  List<Parser<Token>> parsers = new ArrayList<Parser<Token>>(operator.length());
  for (int i = 0; i < operator.length(); i++) {
    parsers.add(TERMINALS.token(Character.toString(operator.charAt(i))));
  }
  return adjacent(Parsers.list(parsers), operator);
 }

And by calling adjacent(">>>"), we get a parser that parses three adjacent ">" tokens. Everything else in the grammar can stay as simple as they should be.

One catch is that we need to make sure ">>" is not a prefix of ">>>" so to get the parser for ">>" operator, we will need to do a little bit of tweaking as:

static final Parser<?> UNSIGNED_RIGHT_SHIFT = adjacent(">>>");
static final Parser<?> RIGHT_SHIFT = UNSIGNED_RIGHT_SHIFT.not().next(adjacent(">>"));

And that's about it. The same code can be applied to "<<" and "<<<".
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]-[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

*俺的チュートリアルを書いてみる [#la10fd7b]
実は、jparsecのソースコードをダウンロードすると、計算機のサンプルコードが入っていて、

これがチュートリアルで解説してあるようなコードよりもすっきりさわやかなコードなのだ。

だから、このサンプルから逆に構築する手順を、観察力＋妄想力で、作り、俺的チュートリアルをつくるのだ！。それが、漢ってもんだろ。

**ゴール [#k0421c8f]
はっきりとしたゴールがあるってことは、それだけでも、しあわせなことなのさ。

まずは、四則演算の構文解析の作成方法を理解できるようにする。

四則演算って、いろいろな言語の基本的機能だから、構文解析のHelloWold的存在かとは思うけど、

言語を解析するには、数学でいうところの必要条件にすぎない。

ちなみに、下記のコードを作れるような手順をコードから逆に作ってみることを目標にします。

その後、BNFの解析なども行います。

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

*大まかな概念 [#qe9b8e5b]
解析するものは、括弧などで括られている箇所はparenと命名する。
中身をExpressionと命名する。

*Jparsecのサンプルから説明書を作ってみる。 [#z9c4734a]

**パッケージ構成 [#m99766da]

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

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

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

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

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

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

大雑把に言って入れ物を作って次の順番でクラスを構築していく感じです。
全体的な入れ物は
 Parser.Reference<Integer> ref = Parser.newReference();
で定義します。

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

**末端表現をパターンで記述 [#a19619d8]
対象を表す正規表現と入れ物として定義したクラスを頭の中でイメージします。（実装では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(いまからせつめいする引数)

**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というメソッドをオーバロードさせていきます。

必要なパラメータは、どんな記号なのか？
その次に、何項演算子なのかでクラスが異なります。
２項演算子の場合は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);

**括弧を定義する場合 [#sff090ac]
昔はこんな感じでTermsクラスがあったみたいですが、
 final Terms ops = Terms.getOperatorsInstance("+", "-", "*", "/", "(", ")");
いまは、
括弧の中身をすぐには評価しないので、lazyをつけ、対になっている「(」と「)」をbetweenで括ります。もし、その対でなければ、
下記のようにorで連結していきます。
 Parser<Integer> term = ref.lazy().between(isChar('('), isChar(')')).or(NUMBER);

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

**構文を定義する。 [#u8e80826]

***SELECT文の定義例 [#p48d3599]
たとえばSELECT文を定義してみます。

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

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

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

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

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

**インデントとスペース、コメントなどの除去 [#c5147af5]
最後は、インデントとスペースを除去して解析するように記述する。

たとえば、このような感じである。
  static <T> T parse(Parser<T> parser, String source) {
    return parser.from(INDENTATION.lexer(TOKENIZER, Indentation.WHITESPACES.or(COMMENT).many()))
        .parse(source);
  }
  
***素朴な疑問 [#h2637aaf]
作者はunionとか、なぜ注意深く定義できたのか？

bnf SQL selectで検索してみた。

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

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

自分で解析しているのかもしれない。
  
*delete文の解析機を作ってみる。 [#f89a5667]
未記入

spamではない場合はチェックをいれてください。タイムスタンプを変更しない