こんにちは。VASILYでフロントエンドエンジニアをしている@AmatsukiKuです。この記事はVASILY Advent Calendar 2017 8日目の記事になります。
この記事では業務から離れ、Ruby上で動作する独自プログラミング言語を実装した際に用いたRaccの使い方について説明します。
Raccとは
Raccは、定義した文法からRuby上で動作するパーサーを生成するパーサージェネレーターであり、Rubyの標準添付ライブラリの1つです。
名前からもわかるようにYaccのRuby版といった感じで、細かな文法の違いはあれど同じ基本的には同じです。
Raccの使い方
簡単なサンプルを交えながらRaccの使い方を解説していきます。
次のような一行から成るプログラムを解釈できるパーサーを実装することを考えます。
x <- 1
y <- 2
これらのプログラムは変数に整数を代入することを表していることとします。具体的には、sample1のプログラムをパーサーに通すとRuby上の[:assignment, :x, 1]という配列に相当することとします。
parser = SampleParser1.new()
p parser.parse('x <- 1')
# => [:assignment, :x, 1]
このようなパーサーをRaccを用いて作成するには次のような元ファイルを作ります。
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ファイルを得ることが出来ます。
bundle exec racc -o sample_parser1.rb syntax.txt
上述のファイルの規則部分について簡単に説明します。
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以下に書かれたスキャナ部分で定義されます）
次に、規則を追加して複数の文に対応することを考えます。
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部分は同様
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メソッドを工夫することで少しわかりやすくすることが可能です。
...
----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ライブラリを使うことが推奨されています。