parserをtreetopで作る

# 初めに

パーサを書いてSQLなりC言語なりから文脈を抽出したいことが良くあります。
伝統的な方法としてはflexなりyaccなりのツールを組み合わせてアレコレするんですが、yacc以外の方法として `treetop` というライブラリが提案されています。
BNFとはちょっと違うPEGという文法規則を入力することでパーサを生成してくれるツールです。
BNFが `|` 記号で「AもしくはB」を記述したのに対し、PEGは `/` 記号で「Aを試してダメだった場合に限りBを試す」を表現するので、文法解釈時に候補の絞り込みが高速なことが利点らしいですが詳しい証明は知りません。

# インストール
```shell-session:
$ sudo gem install treetop
```

これで `tt` コマンドが使えるようになります。

```shell-session
$ 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 ファイルが生成される
```

生成されたパーサは単体ではパースしか出来ないので、データを渡すなり表示するなりのコードを使う必要があります。

```hogeparse.rb:
require 'treetop'
require './hoge' # treetopで生成されたRubyコード

parser = HogeParser.new
result = parser.parse("ターゲットとなるテキスト")
p result.get
```

# 簡単なパーサ（文字列にマッチさせて要素を獲得する）

C言語のプロトタイプ宣言部分を読み出すパーサを作ってみます。
まずはパーサの簡単な所から試していきます。

```rb:c_signature.treetop:
grammar CSignature
  rule hoge
    'int main(void);' {
      def get
        {'status'=>'success'}
      end
    }
  end
end
```

これは、文法ルールとして「渡された文字列が `int main(void);`と一致した場合にその部分のSyntaxNode型オブジェクトに以下の内容の `get` 特異メソッドを定義せよ、という意味です。
その特異メソッドは本来まともな戻り値を返すべきですが、今回は説明のため `{'status'=>'success'}` という決め打ちオブジェクトを変えさせています。
実行させるならこんな感じ

```parse.rb:
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させてみましょう。

```rb:
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`メソッドを持ったオブジェクトが生成されないので

```shell-session:
parse.rb:7:in `<main>': undefined method `get' for nil:NilClass (NoMethodError)
```

のようなメッセージが出ます。
さて、この戻り値の取り出し方ですが、問題があります。
C言語の規格上では関数の定義から関数名の間は「半角スペース1個」以外にも「改行・タブ・半角スペースの複数の組み合わせ」を許容します。
つまり `parser.parse("int\nmain(void);")` をparseできません。そこに対応するためにはruleを書き改める必要があります。


```rb:
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文字以上」という条件をつける事が出来ました。
ついでに関数名も切り出せるようにしてみます。


```rb:
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つを正しく受け取れる物を作ってみましょう。

```rb:
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を見やすく切り分けましょう。

```rb:
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言語の規格上、'('や')'の前後に任意個の空白を入れることも認められているので、そこにスペースを許容するようにしてみます。

```rb:
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`の数値を先頭から数えるのがダルいので、名前を与える事もできます。

```rb:
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に切り出してしまいましょう。

```rb:
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` を書き換えます。

```rb: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言語は複数の引数を取る事ができます。コンマで接続しながら複数の引数を取ってみます。

```rb:
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` という感じに定義し直す事ができました。
この状態でなら

```shell-session:
"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)` という形で表現することもできます。
もっと言うと、仮引数に名前は必須ではありません。
更にはポインタを受け取る事もあり得ます。
それらを表現してみます。

```rb:

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
```

これを以下のようなプログラムで実行してみます。

```rb:
# -*- 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
}
```

すると結果はこうなります。

```shell-session:
$ 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ライフを送りましょう！