BT

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

| 作者: Werner Schuster フォローする 9 人のフォロワー , 翻訳者 編集部 フォローする 0 人のフォロワー 投稿日 2008年1月27日. 推定読書時間: 3 分 |
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

このスレッドのメッセージについてEmailでリプライする

regular expressionsの訳などについて by 宏太 水島

原文: 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

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

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

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

このスレッドのメッセージについてEmailでリプライする

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

このスレッドのメッセージについてEmailでリプライする

2 ディスカッション

InfoQにログインし新機能を利用する


パスワードを忘れた方はこちらへ

Follow

お気に入りのトピックや著者をフォローする

業界やサイト内で一番重要な見出しを閲覧する

Like

より多いシグナル、より少ないノイズ

お気に入りのトピックと著者を選択して自分のフィードを作る

Notifications

最新情報をすぐ手に入れるようにしよう

通知設定をして、お気に入りコンテンツを見逃さないようにしよう!

BT