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

作者 Werner Schuster, 翻訳者 編集部 投稿日 2008年1月27日 午後5時47分

コミュニティ

Ruby

トピック

プログラミング,

Domain Specific Languages

タグ

言語特性,

言語,

Code Generation

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

1. トップへ戻る

   regular expressionsの訳などについて

   2008年1月28日 午前2時23分 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の訳が難しいところ
   ですが、
   
   字句解析のフェーズが必要無く、先読みによって文脈依存性
   の一部を扱うことができる。
   
   などとするのが良いのではないかと思いました。

   返信

2. トップへ戻る

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

   2008年1月28日 午後7時41分 by InfoQ Japan編集部

   水島様、
   コメントありがとうございます。訳が稚拙で申し訳ございません。
   
   早速ご意見を取り入れ修正させていただきました。
   今後ともInfoQを宜しくお願いします。

   返信

• 次へ >