はじめに
Ruby には 標準添付ライブラリに Racc があります。
Racc はパーサジェネレータ(構文解析器生成系)です。
パーサジェネレータは、文法をあたえるとパーサを生成するツールです。
参考
簡単なサンプル
『数字の後に「.」がひとつ』という構文を決めます。
文法： 数字 '.' (例：「1.」「12.」などは妥当。「.1」などは不正)
この構文を解析するパーサを Racc で作ってみます。
以下が Racc のソースになります。
とりあえず字句解析はしていません。parse メソッド内で擬似的にトークンを作っています(「1.」を想定)。
class MyParser # パーサクラス定義 (クラス名は任意)
rule # rule 〜 end の間にパーサ文法を書く
statement : NUMBER '.' # 『数字 '.'』を表す文法
end
# 「---- inner」にはパーサクラス内部のコードを書く
---- inner
def parse # MyParser#parse メソッド。(メソッド名は任意)
@q = []
@q << [:NUMBER,'1'] # トークンを作る(ここでは擬似的に作る。「1.」が入力された想定)
@q << ['.', '.'] # 〃
do_parse # do_parse でパーサを起動する
end
def next_token # next_token はパーサ本体から呼び出される
@q.shift # トークンを返す
end
# 「---- footer」にはパーサクラスの外(後ろ)のコードを書く
---- footer
if __FILE__ == $0
parser = MyParser.new # MyParser インスタンス作成
begin
p parser.parse # MyParser#parse を呼び出す
rescue Racc::ParseError => e # パーサエラーになると Racc::ParseError 例外があがる
$stderr.puts e
end
end
Ruby 添付の racc コマンドでコンパイルします。
# -o は出力ファイル名の指定、-g はデバッグコードを付加するオプション(-g の指定は任意)
$ racc -g -o sample1.rb sample.ry # sample1.rb が出力される
実行してみます。OK のようです。(パーサエラーの場合は例外があがる)
$ ruby sample1.rb
"1"
動作概要は以下です。
- MyParser インスタンス の
parseメソッドが呼び出される -
parseメソッド内部で入力文字列を字句解析してトークン化する(上の例では擬似動作のみ) -
do_parseメソッドを呼び出しパーサ本体を起動 - パーサ本体はルール(文法)を解釈しつつ構文解析する
- パーサは構文解析で必要なトークンを
next_tokenメソッドで取得する -
next_tokenがnilを返すと入力終了とみなし構文解析を終了する
ルールは以下のようになっています。
statement : NUMBER '.'
「:」の右辺がトークンの並びです。「NUMBER」「'.'」のように並んでいます。
パーサは取得したトークンを順次マッチさせていき(シフト:shift)、右辺の並びに全てマッチすると左辺であると解釈します(還元：reduce)。
トークンがキューイングされた@qは do_parse を呼ぶ直前、以下のようになっています。
文法通りの並びのため、この構文解析は成功します。
[[:NUMBER, '1'], ['.', '.']] # トークンは 2個
トークンは [記号、その値] のようになっています。
記号はトークンの意味を表します。(上の例で「NUMBER」)。
値とは実際の文字列です。(上の例で、NUMBER の値は '1')
特に記号がないものは値そのものを記号として渡します。(上の例で['.', '.'])
ルールをもう一度見てみます。
statement : NUMBER '.'
statement のように小文字で表されるのは終端記号です。(ルールの中でさらに展開される記号)
NUMBER のように大文字で表されるのは非終端記号です。(ルールの中でもう展開しない記号)
非終端記号は、取得するトークンの記号と直結します。
'.'のようにクオートされているのは直の値(文字列そのもの)です。
パーサエラーを起こしてみる
parse を以下のように変更して、再コンパイルして実行してみます。(不正なのでエラーになる)
def parse
:
@q << ['.', '.'] # この２行を逆にする。
@q << [:NUMBER,'1'] # 「.1」が入力された想定。
:
$ racc -g -o sample1.rb sample.ry
$ ruby sample1.rb
parse error on value "." (".")
パーサエラーになりました。(Racc::ParseError 例外があがっています)
もう少し拡張する
class MyParser
rule
statement : number '.' # 数字の部分を number (非終端記号) にする
number : DEC # number は DEC か HEX
| HEX # 2つ目以降の右辺の区切りは「|」
end
# 「---- header」にはパーサクラスの外(その前)の>コードが書ける
---- header
require 'pp'
require 'strscan' # strscan を使う
---- inner
attr_accessor :yydebug # @yydebug のアクセサ定義
attr_accessor :verbose # @verbose のアクセサ定義
def parse(str)
s = StringScanner.new(str) # StringScanner インスタンス作成
@q = []
# 文字列をスキャンしてトークン化する
until s.eos? # EOS(End of String:文字列の終わり)までループ
s.scan(/0x\d+/) ? @q << [:HEX, s.matched] : # scan はパターンがマッチするか判定するメソッド
s.scan(/\d+/) ? @q << [:DEC, s.matched] : # matched はマッチした箇所を返すメソッド
s.scan(/./) ? @q << [s.matched, s.matched] : # /./ はどんな文字にもマッチする
(raise "scanner error") # この raise は起こらないはず
end
pp @q if verbose # @verbose が真値の場合 @q をダンプ (デバッグ用)
do_parse
end
def next_token
@q.shift
end
---- footer
if __FILE__ == $0
require 'optparse'
require 'ostruct'
opt = OpenStruct.new ARGV.getopts 'vd'
str = ARGV.shift or (raise "no arguments")
parser = MyParser.new
parser.yydebug = opt.d # 「-d」が指定された場合 @yydebug を true
parser.verbose = opt.v # 「-v」が指定された場合 @verbose を true
begin
p parser.parse(str) # コマンド引数で渡された文字列を parse に渡す
rescue Racc::ParseError => e
$stderr.puts e
end
end
$ racc -g -o sample2.rb sample2.ry
$ ruby myparser.rb 10.
"10"
$ ruby sample2.rb 0xff.
"0xff"
$ ruby sample2.rb x.
parse error on value "x" (error)
主な変更点は以下の３つです。
- ルールを拡張。数字列は 10進数表記(DEC)と16進数表記(HEX)が使えるよう修正。
- コマンドライン引数で渡された文字列を
parseメソッドで字句解析するように修正 - コマンドラインオプションで
@yydebugと@verboseを指定できるように修正
ルールの拡張では、NUMBER の代わりに DEC と HEX を使うようにしてみました。
こんな感じで拡張していくともっと複雑な文法も定義できるようになると思います。
字句解析には標準添付ライブラリの strscan を使っています。
インスタンス変数 @yydebug を true にすると、racc コンパイル時に「-g」で付けたデバッグコードが有効になります。
インスタンス変数 @verbose を true にした場合、トークン切り出し後の @q をダンプするようにしています。これは、Racc の機能でありませんが、@qの中身を見たほうがデバッグが早い場合があるので付けました。
$ ruby sample2.rb -v 10.
[[:DEC, "10"], [".", "."]]
"10"
ちょっとした使い方程度であれば、sample2.ry をひな形にしてルールを肉付けしていけば実現できると思います。
Racc、strscan とも他にも機能があるので、それらを活用してもいいと思います。
ルールについて補足
アクション
上の例では省略していますが、ルールにはアクション(構文解釈時に行う処理)を記述できます。
ルールの左辺は result、右辺は val(Array) という変数が割り当てられています。
文法 statement : number '.'
変数 result val[0] val[1]
省略時のアクションは result = val[0] です。
なので今までは number(val[0]) の値がそのまま statement(result) に還元されて、それが parse の戻り値になっていました。(例えば "10")
値を文字列でなく数値(to_i する)として扱うようにアクションを記述してみます。
class MyParser
rule
statement : number '.' { result = val[0].to_i }
number : DEC
| HEX
end
:
(以下、略)
$ racc -g -o sample2.rb sample.ry
$ ruby sample2.rb 10.
10 # 文字列でなく数値になっている
上記と同じことは、以下のようにルールを記述しても同じです。
class MyParser
rule
statement : number '.' { result = val[0] } # このアクションは省略しても同じ
number : DEC { result = val[0].to_i } # このタイミングで変換
| HEX { result = val[0].to_i } # 〃
end
:
(以下、略)
リストの表現(繰り返し)
例えば、「数字列,数字列,数字列,...」のように 1 個以上の数字列を「,」で区切って並べてよい文法は以下のように定義とします。(ついでに、結果が数値の配列になるようにアクションを変更します)
class MyParser
rule
statement : number_list '.'
number_list : number { result = [val[0]] }
| number_list ',' number { result << val[2] }
number : DEC { result = val[0].to_i }
| HEX { result = val[0].to_i }
end
:
(以下、略)
$ racc -g -o sample2.rb sample2.ry
$ ruby sample2.rb 10,11,12.
[10, 11, 12]
曖昧な文法
文法が二通り以上に解釈できるとき、それを「曖昧」といいます。
C言語の「ぶらさがり(懸垂) else」が有名と思います。
パーサはこの時以下のような状態です。
- シフトしていいか、還元していいか分からない (シフト/還元衝突: shift/reduce conflict)
- どちら(どこに)に還元していいかか分からない (還元/還元衝突: reduce/reduce conflict)
シフト/還元衝突は「警告」です。パーサが適当に処理します。
還元/還元衝突は「エラー」です。ルール(文法)の修正を要します。
これらの「警告」「エラー」は racc コンパイル時に報告されます。
(ちょっとしたパーサを作る程度の作業であれば) いきなり大きな文法をコーディングしないで、トップレベルだけの小さなものから徐々に拡張していって、都度コンパイルしてチェックしながら作るのが無難と思います。
confict は racc のコンパイル時に出やすいと思うエラーメッセージなので説明しました。
簡単な例でも示せればいいのですが、私もそれほど詳しくないので、この程度の説明でご勘弁ください。
おわりに
本稿内容の動作確認は以下の環境で行っています。
- Ruby 2.1.5 p273
関連記事を投稿しました。(※2015.01.13追記)