Raccで作る独自言語パーサー

こんにちは。VASILYでフロントエンドエンジニアをしている@AmatsukiKuです。この記事は[VASILY Advent Calendar 2017](https://qiita.com/advent-calendar/2017/vasily) 8日目の記事になります。

この記事では業務から離れ、Ruby上で動作する独自プログラミング言語を実装した際に用いたRaccの使い方について説明します。

## Raccとは
[Racc](http://i.loveruby.net/ja/projects/racc/)は、定義した文法からRuby上で動作するパーサーを生成するパーサージェネレーターであり、Rubyの標準添付ライブラリの1つです。
名前からもわかるようにYaccのRuby版といった感じで、細かな文法の違いはあれど同じ基本的には同じです。

# Raccの使い方
簡単なサンプルを交えながらRaccの使い方を解説していきます。
次のような一行から成るプログラムを解釈できるパーサーを実装することを考えます。

```ruby:sample1
x <- 1
```
```ruby:sample2
y <- 2
```

これらのプログラムは変数に整数を代入することを表していることとします。具体的には、sample1のプログラムをパーサーに通すとRuby上の`[:assignment, :x, 1]`という配列に相当することとします。

```ruby
parser = SampleParser1.new()
p parser.parse('x <- 1')
# => [:assignment, :x, 1]
```

このようなパーサーをRaccを用いて作成するには次のような元ファイルを作ります。

```ruby:syntax.txt
class SampleParser1 # 実際に生成されるパーサーのクラス名

token ASSIGNMENT VARIABLE INTEGER # プログラムを構成するトークンの一覧

rule # ここからendまで規則を表す
  statement : VARIABLE ASSIGNMENT INTEGER { result = [:assignment, val[0], val[2]] }

end

----inner
# ここに書かれたコードは生成されるクラスの先頭でmodule_evalされる
# ここで実際にパーサーの呼び出し部分を実装する必要がある

def parse(program)
  @tokens = []
  # トークンはそれぞれ[トークンを表すシンボル, 値]の配列の形にする必要がある
  until program.empty? # 字句解析
    case program
    when /\A\s+/
      # nop
    when /\A[A-z][\w]*\b/
      @tokens.push [:VARIABLE, $&.to_sym]
    when /\A\d+\b/
      @tokens.push [:INTEGER, $&.to_i]
    when /\A<-/
      @tokens.push [:ASSIGNMENT, $&]
    else
      raise RuntimeError, 'error: cannot tokenize.'
    end
    program = $' # 正規表現でマッチした部分より後ろを代入
  end
  @tokens.push [false, '$'] # トークン列の終わりを表す
  do_parse() # 自動生成されたパーサーのパース処理が走る。内部でnext_tokenが呼ばれる
end

def next_token()
  @tokens.shift()
end
```

このファイルにraccコマンドを適用することで目的のパーサーが実装されたRubyファイルを得ることが出来ます。

```bash
bundle exec racc -o sample_parser1.rb syntax.txt
```

上述のファイルの規則部分について簡単に説明します。

```rb
statement : VARIABLE ASSIGNMENT INTEGER { result = [:assignment, val[0], val[2]] }
```

今回は規則が1つしかないので、必然的にこの文法はstatementという記号1つだけで構成されることになります。
記号は`:`より右で定義された記号の列に分解されます。今回ですと、与えられた文書全体を1つの`statement`と捉え、`VARIABLE`, `ASSIGNMENT`, `INTEGER`という3つの記号に分割されます。この3つの記号は`token`という記述で予め与えた終端記号であり、それ以上分割されることはありません。
{ } の中では、分割された記号の値を使って、実際に`statement`がどのような値を返すかをresultに代入します。この中ではRubyコードを書けるため配列やハッシュなど自由な形で値を生成可能です。分割された各記号の値は配列`val`に順に格納されています。
sample1であれば、`val`の中身は`[:x, '<-', 1]`になり、`statement`は`[:assignment, :x, 1]`を返すことになります。
（各終端記号の値は`----inner`以下に書かれたスキャナ部分で定義されます）

次に、規則を追加して複数の文に対応することを考えます。

```ruby:syntax2.txt
class SampleParser2

token ASSIGNMENT VARIABLE INTEGER

start statements # パースの起点となる規則の指定

rule
  statements : statement { result = [val[0]] } # 一文の場合
             | statement statements { result = [val[0]] + val[1] } # 二文以上の場合

  statement  : VARIABLE ASSIGNMENT INTEGER { result = [:assignment, val[0], val[2]] }

end


# ... inner部分は同様
```

```ruby:
require './sample_parser2.rb'

parser = SampleParser2.new()
p parser.parse("x <- 1 y <- 2")
# => [[:assignment, :x, 1], [:assignment, :y, 2]]
```

今回は先の例と違い、規則が複数あるため、この文書を読み解くための最初の規則を`start`という記述で与える必要があります。`start`には`statements`という記号を与えてあるので、まず文書全体を`statements`として捉えて記号を分割していきます。また、規則部では`:`とは別に`|`を使っています。`|`はorを表し、分割先の記号列を複数指定するためのものです。
文書として`x <- 1 y <- 2`を与えたとすると、まず、次のような記号列として解釈されます。

`VARIABLE ASSIGNMENT INTEGER VARIABLE ASSIGNMENT INTEGER`

この記号列は次のような分解過程を経て、文法を満たしていると考えられます。

`statements` → `statement statements` → `statement statement`
 → `VARIABLE ASSIGNMENT INTEGER VARIABLE ASSIGNMENT INTEGER`

ここでの肝はstatementsが再帰的に定義されていることです。それにより、2文だけでなく任意の文数を表現できます。

簡単な例ではありましたが、最低限の使い方の説明ではできたと思いますので、トークンと規則を追加していくことで実用性のあるパーサーにしてください。

# デバッグ方法
実際にパーサーを利用していると、文法エラーに遭遇するがどこがエラーかわからないという自体に陥ると思います。
そういったときには、on_errorメソッドを工夫することで少しわかりやすくすることが可能です。

```ruby:
...

----inner

def parse(program)
  @tokens = []
  @before_tokens = []
  until program.empty?
    case program
    when /\A\s+/
    when /\A[A-z][\w]*\b/
      @tokens.push [:VARIABLE, $&.to_sym]
    when /\A\d+\b/
      @tokens.push [:NUMBER, $&.to_i]
    else
      raise RuntimeError, 'error: cannot tokenize.'
    end
    program = $'
  end
  @tokens.push [false, '$']
  do_parse()
end

def next_token()
  @before_tokens = (@before_tokens + [@tokens.first]).last(11)
  @tokens.shift()
end

def on_error(t, val, vstack)
  raise ParseError, sprintf(
    "Parse error on value %s (%s)\naround %s",
    val.inspect, token_to_str(t) || '?', (@before_tokens + @tokens[0...10]).map { |token| token[1]}.join('')
  )
end

```

上のコードではエラー時に、パースに失敗したトークンの前後10個を連結した文字列を表示することでエラー箇所をわかりやすくしています。
こうすることで、エラー時に括弧が一文字だけ表示されてどこの括弧がおかしいかわからないといった事態を防げます。

# 補足
字句解析の部分では、より説明を減らすために正規表現を用いていますが、実際にはstrscanライブラリを使うことが推奨されています。

# 関連文書
- [Racc ユーザマニュアル](http://i.loveruby.net/ja/projects/racc/doc/)
- [Ruby: Racc](https://qiita.com/lnznt/items/ecbc16cae8ab9c641391)
- [Ruby: Racc を利用した Prolog ミニパーサ](https://qiita.com/lnznt/items/3ab55937136b06cf44f8)