トップ «前の日記(2009-03-16) 最新 次の日記(2009-03-19)» 編集

Route 477



2009-03-18

[ruby] Ruby用PEGパーザ、Treetopを使ってみる

TreetopはRuby用のPEG(解析表現文法)のpackrat parserである。 よく分かってないけど、そういうものらしい。

PEGの特徴については適宜google検索してもらうとして(ひどい)、ここではTreetopを使って簡単な文法をパーズしてみた。

1. インストール

gem install treetop

Vim使いはvim用の色付けもインストールしておくと良いかも。

2. 文法を書く

パーザといったら(異論もあろうが)四則演算である。リファレンスを参考に、とりあえず足し算だけの文法を定義してみよう。

dentaku.treetop:

grammar Dentaku
  rule additive
    (number "+" number)
    /
    number
  end

  rule number
    [0-9]+
  end
end

使う側はこんな感じ。

den.rb:

require 'treetop'
require 'dentaku'
    
p DentakuParser.new.parse("1+2+3")

(環境によってはrequire 'rubygems'が必要だろう。)

dentaku.rbというファイルは存在しないが、treetopには*.treetopを直接ロードし、コンパイルして使うという機能がある(気持ち悪いw) のでこれで良い。

ちなみに

 $ tt dentaku.treetop

とすることで、文法のプリコンパイルを行うこともできる(dentaku.rbというファイルが生成される。ファイル名は-oで変更可)。

3. 動かしてみる。

$ ruby den.rb
SyntaxNode+Additive0 offset=0, "1+2+3" (number,additive):
  SyntaxNode offset=0, "1":
    SyntaxNode offset=0, "1"
  SyntaxNode offset=1, "+"
  SyntaxNode+Additive0 offset=2, "2+3" (number,additive):
    SyntaxNode offset=2, "2":
      SyntaxNode offset=2, "2"
    SyntaxNode offset=3, "+"
    SyntaxNode offset=4, "3":
      SyntaxNode offset=4, "3"

よく分からないが、とりあえずパーズできているみたいだ。

4. アクションを定義する

パーズができたので、yaccでいうところのアクションを定義しよう。

Treetopでは、非終端記号(上で言うSyntaxNode)にメソッドを定義することでアクションの実装を行う。

(いろいろ試した結果)以下のようなdentaku.treetopになった。

grammar Dentaku
  rule additive
    number "+" additive {
      def value
        number.value + additive.value
      end
    }
    /
    number
  end

  rule number
    [0-9]+ {
      def value
        text_value.to_i
      end
    }
  end
end

使う側は以下。

require 'treetop'
require 'dentaku'

result = DentakuParser.new.parse("1+2+3")
p result
p result.value

実行結果。

$ ruby den.rb
SyntaxNode+Additive1+Additive0 offset=0, "1+2+3" (number,value,additive):
  SyntaxNode+Number0 offset=0, "1" (value):
    SyntaxNode offset=0, "1"
  SyntaxNode offset=1, "+"
  SyntaxNode+Additive1+Additive0 offset=2, "2+3" (number,value,additive):
    SyntaxNode+Number0 offset=2, "2" (value):
      SyntaxNode offset=2, "2"
    SyntaxNode offset=3, "+"
    SyntaxNode+Number0 offset=4, "3" (value):
      SyntaxNode offset=4, "3"
6

動いているようだ。

あとは公式サイトなど見て頑張ってください。