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 訳を一部修正しました。