初めに
パーサを書いてSQLなりC言語なりから文脈を抽出したいことが良くあります。
伝統的な方法としてはflexなりyaccなりのツールを組み合わせてアレコレするんですが、yacc以外の方法として treetop というライブラリが提案されています。
BNFとはちょっと違うPEGという文法規則を入力することでパーサを生成してくれるツールです。
BNFが | 記号で「AもしくはB」を記述したのに対し、PEGは / 記号で「Aを試してダメだった場合に限りBを試す」を表現するので、文法解釈時に候補の絞り込みが高速なことが利点らしいですが詳しい証明は知りません。
インストール
$ sudo gem install treetop
これで tt コマンドが使えるようになります。
$ tt
Treetop Parsing Expression Grammar (PEG) Comand Line Compiler
Usage: tt [options] grammar_file[.treetop|.tt] ...
Examples:
tt foo.tt # 1 grammar -> 1 parser source
tt foo bar.treetop # 2 grammars -> 2 separate parsers
tt -o alt_name.rb foo # alternately named output file
NOTE: while treetop grammar files *must* have one of the following
filename extensions, the extension name is not required when calling
the compiler with grammar file names.
Valid extensions: .treetop, .tt
Options:
-o, --output FILENAME Write parser source to FILENAME
-f, --force Overwrite existing output file(s)
-v, --version Show Treetop version
-h, --help Show this help message
専用記法で記述した treetop ファイルを記述して tt コマンドにかける事でパーサとして機能するRubyプログラムを出力してくれます。
$ tt hoge.treetop # これで hoge.rb ファイルが生成される
生成されたパーサは単体ではパースしか出来ないので、データを渡すなり表示するなりのコードを使う必要があります。
require 'treetop'
require './hoge' # treetopで生成されたRubyコード
parser = HogeParser.new
result = parser.parse("ターゲットとなるテキスト")
p result.get
簡単なパーサ（文字列にマッチさせて要素を獲得する）
C言語のプロトタイプ宣言部分を読み出すパーサを作ってみます。
まずはパーサの簡単な所から試していきます。
grammar CSignature
rule hoge
'int main(void);' {
def get
{'status'=>'success'}
end
}
end
end
これは、文法ルールとして「渡された文字列が int main(void);と一致した場合にその部分のSyntaxNode型オブジェクトに以下の内容の get 特異メソッドを定義せよ、という意味です。
その特異メソッドは本来まともな戻り値を返すべきですが、今回は説明のため {'status'=>'success'} という決め打ちオブジェクトを変えさせています。
実行させるならこんな感じ
require 'treetop'
require './c_signature' # treetopで生成されたRubyコード
parser = CSignatureParser.new
result = parser.parse("int main(void);")
p result.get
こんな感じのコードを用意して実行するだけです。
$ tt c_signature.treetop
$ ruby parse.rb
{'status'=>'success'}
このままだと int main(void); しか解釈できないので改造していきます。試しに int 以外の任意の型をparseさせてみましょう。
grammar CSignature
rule signature
[a-zA-Z_]+ ' main(void);' {
def get
{
'status' => 'success',
'returns' => elements[0].text_value
}
end
}
end
end
rule 文の中ではスペース区切りで複数のルールが連続してマッチすることを指定できます。
今回はこのように、 [a-zA-Z_] という正規表現にマッチする部分を探させて、戻り値部分に相当する場所から文字列を取り出そうとしています。
取り出した要素はスペース区切りになった要素の羅列の先頭から順番に elements 配列の要素として参照できます。
実行するとこんな感じになります。
$ tt c_signature.tt -f && ruby parse.rb
{"status"=>"success", "returns"=>"int"}
無事に int 型が戻り値に指定されている事がわかります。
なお、マッチングに失敗した場合には、getメソッドを持ったオブジェクトが生成されないので
parse.rb:7:in `<main>': undefined method `get' for nil:NilClass (NoMethodError)
のようなメッセージが出ます。
さて、この戻り値の取り出し方ですが、問題があります。
C言語の規格上では関数の定義から関数名の間は「半角スペース1個」以外にも「改行・タブ・半角スペースの複数の組み合わせ」を許容します。
つまり parser.parse("int\nmain(void);") をparseできません。そこに対応するためにはruleを書き改める必要があります。
grammar CSignature
rule signature
[a-zA-Z_]+ [ \t\n\r]+ 'main(void);' {
def get
{
'status' => 'success',
'returns' => elements[0].text_value
}
end
}
end
end
新たに [ \t\n\r]+ を加える事により「空白文字1文字以上」という条件をつける事が出来ました。
ついでに関数名も切り出せるようにしてみます。
grammar CSignature
rule signature
[a-zA-Z_]+ [ \t\n\r]+ ([a-zA-Z_]+ [a-zA-Z0-9_]*) '(void);' {
def get
{
'status' => 'success',
'name' => elements[2].text_value,
'returns' => elements[0].text_value
}
end
}
end
end
関数名に相当する部分をアルファベットを受け取る正規表現に書き換えるだけです。
C言語の関数名は最初の一文字目が数字で始まる事を許可しないので、ちょっと複雑な正規表現([a-zA-Z_]+ [a-zA-Z0-9_]*) になっています。
複数の正規表現を1つのエレメントとして見なさせるためには () で囲ってやれば良いです。
先頭からエレメント単位を数えていった場合、関数名を表す ([a-zA-Z_]+ [a-zA-Z0-9_]*) は3番目です。elementsの添字にはゼロスタートの数値を入れる必要があるので、 elements[2] が関数名を表します。言うまでもないですが、elements[1] は戻り値と関数名の間のスペースを保持しています。
実行結果はこんな感じになります。
$ tt c_signature.tt -f && ruby parse.rb
{"status"=>"success", "name"=>"main", "returns"=>"int"}
少し複雑なパーサ（複数のruleへ切り出す）
C言語の関数は0個以上の引数を取ることができます。それらを正しく受け取るのはちょっとめんどくさいです。
まず引数1つを正しく受け取れる物を作ってみましょう。
grammar CSignature
rule signature
[a-zA-Z_]+ [ \t\n\r]+ ([a-zA-Z_]+ [a-zA-Z0-9_]*) '(' ([a-zA-Z_]+ [a-zA-Z0-9_]*) [ \t\n\r]+ ([a-zA-Z_]+ [a-zA-Z0-9_]*) ');' {
def get
{
'status' => 'success',
'name' => elements[2].text_value,
'returns' => elements[0].text_value,
'args' => [
{
'type' => elements[4].text_value,
'name' => elements[6].text_value
}
]
}
end
}
end
end
軽く面食らう感じになりますね。ここらでそろそろruleを見やすく切り分けましょう。
grammar CSignature
rule signature
name space name '(' name space name ');' {
def get
{
'status' => 'success',
'name' => elements[2].text_value,
'returns' => elements[0].text_value,
'args' => [
{
'type' => elements[4].text_value,
'name' => elements[6].text_value
}
]
}
end
}
end
rule space
[ \t\n\r]+
end
rule name
[a-zA-Z_]+ [a-zA-Z0-9_]*
end
end
だいぶ見やすくなりました。ruleの中で他のruleを参照できるので、よく使うマッチング要素は別名で再定義しておくことをおすすめします。
マッチングは基本的に上から順番に行われるので、一番上にはトップレベルのマッチング条件を書いておきましょう。
次にC言語の規格上、'('や')'の前後に任意個の空白を入れることも認められているので、そこにスペースを許容するようにしてみます。
grammar CSignature
rule signature
name space name space? '(' space? name space name space? ')' space? ';' {
def get
{
'status' => 'success',
'name' => elements[2].text_value,
'returns' => elements[0].text_value,
'args' => [
{
'type' => elements[6].text_value,
'name' => elements[8].text_value
}
]
}
end
}
end
rule space
[ \t\n\r]+
end
rule name
[a-zA-Z_]+ [a-zA-Z0-9_]*
end
end
space? というのは正規表現から推測できるように「spaceルールにマッチしてもしなくても良い」という意味になります。
elements[6]とかelements[8]とかの添字は、ルールを先頭からゼロスタートで数えていった場合の数値を指します。
space? が入った事によって添字の番号がズレたので書き換える必要があります。
ちょっと要素に足したり引いたりする度にelementsの数値を先頭から数えるのがダルいので、名前を与える事もできます。
grammar CSignature
rule signature
returns:name space name:name space? '(' space? argtype:name space argname:name? space? ')' space? ';' {
def get
{
'status' => 'success',
'name' => name.text_value,
'returns' => returns.text_value,
'args' => [
{
'type' => argtype.text_value,
'name' => argname.text_value
}
]
}
end
}
end
rule space
[ \t\n\r]+
end
rule name
[a-zA-Z_]+ [a-zA-Z0-9_]*
end
end
マッチング条件の直前に : をつける事で、メソッド内からその名前でその要素にアクセスすることができます。
引数に関してはややこしいので別のruleに切り出してしまいましょう。
grammar CSignature
rule signature
returns:name space name:name space? '(' arg:arguments ')' space? ';' {
def get
{
'status' => 'success',
'name' => name.text_value,
'returns' => returns.text_value,
'args' => arg.get
}
end
}
end
rule argument
space? argtype:name space argname:name space? {
def type; argtype.text_value; end
def name; argname.text_value; end
def get
{
'type' => type,
'name' => name
}
end
}
end
rule space
[ \t\n\r]+
end
rule name
[a-zA-Z_]+ [a-zA-Z0-9_]*
end
end
ここまでで簡単な引数を受け取って表示するまでを実行してみます。{}内には複数の関数の宣言を書くことができます。
引数付きの関数のシグネチャを受け取るように parse.rb を書き換えます。
# -*- coding: utf-8 -*-
require 'treetop'
require './c_signature' # treetopで生成されたRubyコード
parser = CSignatureParser.new
result = parser.parse("int main(int argc);")
p result.get
実行するならこんな感じです。
$ tt c_signature.tt -f && ruby parse.rb
{"status"=>"success", "name"=>"main", "returns"=>"int", "args"=>{"type"=>"int", "name"=>"argc"}}
複数の引数を取る関数
さて、C言語は複数の引数を取る事ができます。コンマで接続しながら複数の引数を取ってみます。
grammar CSignature
rule signature
returns:name space name:name space? '(' arg:arguments ')' space? ';' {
def get
{
'status' => 'success',
'name' => name.text_value,
'returns' => returns.text_value,
'args' => arg.get
}
end
}
end
rule argument
space? argtype:name space argname:name space? {
def type; argtype.text_value; end
def name; argname.text_value; end
def get
{
'type' => type,
'name' => name
}
end
}
end
rule arguments
first:argument rest:(',' args:argument)* {
def get
first_arg = first.get
rest_args = rest.elements.map{|m|
m.args.get
}
[first_arg] + rest_args
end
}
end
rule space
[ \t\n\r]+
end
rule name
[a-zA-Z_]+ [a-zA-Z0-9_]*
end
end
ちょっと追いにくいですが、argument を複数取るのが arguments という感じに定義し直す事ができました。
この状態でなら
"int main(int a, int b, char c);" =>
{"status"=>"success",
"name"=>"main",
"returns"=>"int",
"args"=>
[{"type"=>"int", "name"=>"a"},
{"type"=>"int", "name"=>"b"},
{"type"=>"char", "name"=>"c"}]}
こんな感じに構造体を取ることができます。
更にまともなマッチング
C言語の関数はそもそも引数を取らない事ができますし、それを (void) という形で表現することもできます。
もっと言うと、仮引数に名前は必須ではありません。
更にはポインタを受け取る事もあり得ます。
それらを表現してみます。
grammar CSignature
rule signature
returns:type space name:name space? '(' arg:arguments ')' space? ';' {
def get
{
'status' => 'success',
'name' => name.text_value,
'returns' => returns.text_value,
'args' => arg.get
}
end
}
end
rule argument
space? argtype:type fname:(space argname:name)? space? {
def type; argtype.text_value; end
def name
return nil if fname.text_value == ""
fname.argname.text_value;
end
def get
{
'type' => type,
'name' => name
}
end
}
end
rule arguments
first:argument rest:(',' args:argument)* {
def get
first_arg = first.get
rest_args = rest.elements.map{|m|
m.args.get
}
[first_arg] + rest_args
end
}
end
rule space
[ \t\n\r]+
end
rule type
[a-zA-Z_]+ [a-zA-Z0-9_]* [*]*
end
rule name
[a-zA-Z_]+ [a-zA-Z0-9_]*
end
end
これを以下のようなプログラムで実行してみます。
# -*- coding: utf-8 -*-
require 'treetop'
require 'pp'
require './c_signature' # treetopで生成されたRubyコード
targets = [
"int main(void);",
"void main(int a, int b);",
"void hoge(int a, uint32_t** b);",
"void hoge(int a, uint32_t** b, time_t hoge);",
"char** hoge(fuga);"
]
parser = CSignatureParser.new
targets.each{|t|
result = parser.parse(t)
puts "#{t} =>"
pp result.get
}
すると結果はこうなります。
$ tt c_signature.tt -f && ruby parse.rb
int main(void); =>
{"status"=>"success",
"name"=>"main",
"returns"=>"int",
"args"=>[{"type"=>"void", "name"=>nil}]}
void main(int a, int b); =>
{"status"=>"success",
"name"=>"main",
"returns"=>"void",
"args"=>[{"type"=>"int", "name"=>"a"}, {"type"=>"int", "name"=>"b"}]}
void hoge(int a, uint32_t** b); =>
{"status"=>"success",
"name"=>"hoge",
"returns"=>"void",
"args"=>[{"type"=>"int", "name"=>"a"}, {"type"=>"uint32_t**", "name"=>"b"}]}
void hoge(int a, uint32_t** b, time_t hoge); =>
{"status"=>"success",
"name"=>"hoge",
"returns"=>"void",
"args"=>
[{"type"=>"int", "name"=>"a"},
{"type"=>"uint32_t**", "name"=>"b"},
{"type"=>"time_t", "name"=>"hoge"}]}
char** hoge(fuga); =>
{"status"=>"success",
"name"=>"hoge",
"returns"=>"char**",
"args"=>[{"type"=>"fuga", "name"=>nil}]}
うまくいってるようです。
今回は簡単のためオブジェクトをそのまま返させるパーサを作りましたが、そのうち破綻することが目に見えているので、本気で大きなパーサを作る必要に駆られた場合には専用のクラスを複数用意するなりして備えましょう。
今回のパーサでは int *hoge(fuga hoge); のように関数名の先頭に*が付いている場合の取り扱い方については触れませんでしたが、ちょっと複雑になるぐらいでどうにかできます。
treetopで快適なPEGライフを送りましょう！