BT

InfoQ ホームページ ニュース Treetop-Ruby用のPEGパーサージェネレータ

Treetop-Ruby用のPEGパーサージェネレータ

ブックマーク
RubyはYACCのバージョン(Rubyパーサを作るときに使用されるRubyで書かれた最初のRubyパーサ)(source)であるRACCと呼ばれるパーサージェネレータと既に一緒に販売されている。

パーサジェネレータとなるとParsing Expression Grammars(PEG)(source)は、Bryan Ford氏の論文によって"Packrat Parsing"という最適化が紹介されて(source)以来最近かなり人気となっている。Packratパースはこの種の例えば指数のパースタイム問題を解消する。こ れはパーサーがコードをパースするためにバックトラッキングを使用することによって生じる。例えば、それらは正しい結果を見つけるまで可能性のあるコンビネーション全てを片っ端から試していく。Packratパースのソリューションはメモイゼーションを使用することである。例えばこれらの結果を何回も計算 するかわりに中間のパース結果を保管する。これはランタイムビヘイビアをリニアにさせるが、可能性としてインプットソースの数倍という比較的大きなメモリを必要とするという弱点もある。ANTLR(source)のようなほかのパーサジェネレータも同じようなアプローチを使用していることも覚えておいて欲しい。

これを念頭においてTreetop(サイト・英語)のWebサイトはPEGsの利点を解説している。
Parsing Expression Grammars(PEGs)は書きやすくまた保持しやすい。それらはシンプルだけれどLALRかもしくはLR-1グラマーの従来のパーサジェネレータよりも作業しやすい正規表現の強力な汎化である。字句解析のフェーズが必要無く、先読みによって文脈依存性の一部を扱うことができる
Treetopはパースツリーを自動的に生成するがユーザーがメソッドを付加することによって生成されたノードをカスタマイズするのを許容する。
grammar Arithmetic
 rule additive
 multitive '+' additive {
 def value
 multitive.value + additive.value
 end
  }
 /
 multitive
end
# other rules below ...
end
付加ノードのために生成されたノードはメソッドの名が付けられた数値を持つ。違う方法としてはそれぞれのルール用に生成されるノードクラスを特定することが可能である。(注:スラッシュはチョイスオペレータである。例:付加物はプラスキャラクタによって分離された二つのオペランドであるかもしくは単に multitive ruleの結果である)。

Treetopを始めるにはまずそれをインストール必要がある。RubyforgeプロジェクトからTreetopソースを得るか(source)、もしくはそれをジェムとしてインストールする。
gem install treetop
それを使い始めるにはTreetopのドキュメンテーションをチェックする(source)かもしくは提供されたサンプルを見てみる。Treetopには算術的表現用のシンプルなパーサととても基礎的な言語パーサとランタイムが含まれている。

Treetopはグラマー定義ファイルをttユーティリティを用いてRubyコードに変換することが可能である。
tt foo.treetop  
もう一つのオプションはRubyコードからパーサ生成を行うことである(source)
Treetop.load "arithmetic"
parser = ArithmeticParser.new
parser.parse('1+1')
Treetopのクリエータによるライブデモは、Nathan SoboのRuby Con 2007のTreetopのプレゼン(source)を参照して欲しい。

原文はこちらです:http://www.infoq.com/news/2008/01/treetop-ruby-parser-generator

# 2008/1/29 訳を一部修正しました。

この記事に星をつける

おすすめ度
スタイル

こんにちは

コメントするには InfoQアカウントの登録 または が必要です。InfoQ に登録するとさまざまなことができます。

アカウント登録をしてInfoQをお楽しみください。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

コミュニティコメント

  • regular expressionsの訳などについて

    by 宏太 水島 /

    スパムの可能性があると認識されました。モデレーターが確認し問題がなければ24時間以内に公開します。その際あなたへの通知は行われませんのでご了承ください。

    原文: powerful generalization of regular expressions
    訳: 通常表現の強力な総括物

    コメント:
    regular expressionsは「正規表現」とするのが一般的
    だと思います。また、generalizationはこの文脈では
    「汎化」あるいは「一般化」などとするのが適切だと
    思います。

    原文:There's no need for a tokenization phase, and lookahead assertions can be used for a limited degree of context-sensitivity.

    訳:トークン化段階の必要がなく、先読み想定が制限されたコンテキスト感度のために使用することができる。

    コメント:
    limited degree of context-sensitivityの訳が難しいところ
    ですが、

    字句解析のフェーズが必要無く、先読みによって文脈依存性
    の一部を扱うことができる。

    などとするのが良いのではないかと思いました。

  • Re: regular expressionsの訳などについて

    by Japan編集部 InfoQ /

    スパムの可能性があると認識されました。モデレーターが確認し問題がなければ24時間以内に公開します。その際あなたへの通知は行われませんのでご了承ください。

    水島様、
    コメントありがとうございます。訳が稚拙で申し訳ございません。

    早速ご意見を取り入れ修正させていただきました。
    今後ともInfoQを宜しくお願いします。

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

HTML: a,b,br,blockquote,i,li,pre,u,ul,p

BT

あなたのプロファイルは最新ですか?プロフィールを確認してアップデートしてください。

Eメールを変更すると確認のメールが配信されます。

会社名:
役職:
組織規模:
国:
都道府県:
新しいメールアドレスに確認用のメールを送信します。このポップアップ画面は自動的に閉じられます。