Racc は文法規則から Ruby で書かれたパーサを生成するパーサジェネレータです。 パーサ生成アルゴリズムには yacc などと同じ LALR(1) を使用しています。
yacc を知っている人は記述法の違いだけわかれば使えると思います。 yacc を知らない人は 拙著『Ruby を 256 倍使うための本 無道編』(青木峰郎著、ASCII) などを一読していただくのがよいかと思います。 他の UNIX コマンドなどとは異なり、 いきなり使うだけで Racc を理解するのはかなり困難です。
Racc は文法を処理するツールです。 文字列はただの文字の列で、コンピュータにとっては意味を持ちません。 しかし人間はその文字の列の中になにか意味を見出すことができます。 コンピュータにもそのようなことを、部分的にでも、させられたら便利でしょう。 Racc はその手伝いをしてくれます。完全な自動化ではありませんが、 人間が全部やるよりも遥かに簡単になります。
Racc が自動化してくれる部分とは、文字列の含む「構造」の処理です。 たとえば Ruby の if 文を考えてみると、次のように定式化できます。
if 条件式 [then] 文 ： [elsif 条件式 [then] 文 ：] [else 文 ：] end
if 文では if という単語が最初になくてはならず、 elsif 節は else 節より前になくてはいけません。 このような配置の関係 (構造) が、Racc が処理する対象です。
一方、Racc で処理できないのはどういうことでしょうか。それは、たとえば if の条件式にあたる部分が「なんであるか」ということです。つまり、条件 式が if の条件だということです。これは、こっちで条件として扱うコードを 書いてやらないといけません。
と言っても、わかりにくいでしょう。こういう抽象的なものは実際にいじって みるのが一番です。
実際に Racc をどのように使うかという話をします。Racc には独自のソース コードみたいなものがあって、この中に処理したい「構造」を記述しておきま す。このソースファイルを「文法ファイル」と呼ぶことにしましょう。この文 法ファイルの名前が parse.y と仮定すると、コマンドラインから以下のよう に打ちこめば、その構造を処理するためのクラスを含んだファイルが得られま す。
$ racc parse.y
生成されるファイルはデフォルトでは "ファイル名.tab.rb" です。他の名前 にしたいなら、-o オプションで変更できます。
$ racc parse.y -o myparser.rb
このようにして作ったクラス、またはそのような処理を担当するパート、 のことはパーサ (parser) と呼ぶことになっています。解析するヤツ、 というくらいに適当にとらえてください。
Racc は文法ファイルから Ruby のクラスを生成するツールだと言いました。 そのクラスは全て Racc::Parser の下位クラスで、名前は文法ファイル中で 指定します。以下、ここに書くべきことが「なんなのか」を説明します。 ここでは内容に重点を置くので、文法ファイル自体の文法の詳細は 文法リファレンスを見てください。
まずは、全体の概形です。
class MyParser
rule
if_stmt: IF expr then stmt_list elsif else END
then : THEN
|
elsif :
| ELSIF stmt_list
else :
| ELSE stmt_list
expr : NUMBER
| IDENT
| STRING
stmt_list : ふにゃふにゃ
end
Ruby スクリプトのように class でパーサクラス名を指定し、rule ... end の間にパーサに解析させたい文法を記述します。
文法は、記号の並びでもって表します。rule ... end の間にあるコロンとバー 以外のもの、if_stmt IF expr then などが全て「記号」です。そしてコロン が日本語で言う「〜は××だ」の「は」みたいなもんで、その左の記号が右の 記号の列と同じものを指す、というふうに定義します。また、バーは「または」 を意味します。それと、単純にコロンの左の記号のことを左辺、右を右辺とも 言います。以下はこちらのほうを使って説明しましょう。
少し注意が必要な点を述べます。まず、then の、バーのあとの定義 (規則) を 見てください。ここには何も書いていないので、これはその通り「無」であっ てもいい、ということを表しています。つまり、then は記号 THEN 一個か、 またはなにもなし(省略する)でよい、ということです。記号 then は実際の Ruby のソースコードにある then とは切り離して考えましょう (それは実は大文字の記号 THEN が表しています)。
さて、そろそろ「記号」というものがなんなのか書きましょう。 ただし順番に話をしないといけないので、まずは聞いていてください。 この文章の最初に、パーサとは文字の列から構造を見出す部分だと言いました。 しかし文字の列からいきなり構造を探すのは面倒なので、実際にはまず 文字の列を単語の列に分割します。その時点でスペースやコメントは捨てて しまい、以降は純粋にプログラムの一部をなす部分だけを相手にします。 たとえば文字列の入力が次のようだったとすると、
if flag then # item found. puts 'ok' end
単語の列は次のようになります。
if flag then puts 'ok' end
ここで、工夫が必要です。どうやら flag はローカル変数名だと思われますが、 変数名というのは他にもいろいろあります。しかし名前が i だろうが a だろ うが vvvvvvvvvvvv だろうが、「構造」は同じです。つまり同じ扱いをされる べきです。変数 a を書ける場所なら b も書けなくてはいけません。だったら 一時的に同じ名前で読んでもいいじゃん。ということで、この単語の列を以下 のように読みかえましょう。
IF IDENT THEN IDENT STRING END
これが「記号」の列です。パーサではこの記号列のほうを扱い、構造を見付け ていきます。
さらに記号について見ていきましょう。 記号は二種類に分けられます。「左辺にある記号」と「ない記号」です。 左辺にある記号は「非終端」記号と言います。ないほうは「終端」記号と 言います。最初の例では終端記号はすべて大文字、非終端記号は小文字で 書いてあるので、もう一度戻って例の文法を見てください。
なぜこの区分が重要かと言うと、入力の記号列はすべて終端記号だからです。 一方、非終端記号はパーサの中でだけ、終端記号の列から「作りだす」ことに よって始めて存在します。例えば次の規則をもう一度見てください。
expr : NUMBER
| IDENT
| STRING
expr は NUMBER か IDENT か STRING だと言っています。逆に言うと、 IDENT は expr に「なることができます」。文法上 expr が存在できる 場所に IDENT が来ると、それは expr になります。例えば if の条件式の 部分は expr ですから、ここに IDENT があると expr になります。その ように文法的に「大きい」記号を作っていって、最終的に一個になると、 その入力は文法を満たしていることになります。実際にさっきの入力で 試してみましょう。入力はこうでした。
IF IDENT THEN IDENT STRING END
まず、IDENT が expr になります。
IF expr THEN IDENT STRING END
次に THEN が then になります。
IF expr then IDENT STRING END
IDENT STRING がメソッドコールになります。この定義はさきほどの例には ないですが、実は省略されているんだと考えてください。そしていろいろな 過程を経て、最終的には stmt_list (文のリスト)になります。
IF expr then stmt_list END
elsif と else は省略できる、つまり無から生成できます。
IF expr then stmt_list elsif else END
最後に if_stmt を作ります。
if_stmt
ということでひとつになりました。 つまりこの入力は文法的に正しいということがわかりました。
ここまでで入力の文法が正しいかどうかを確認する方法はわかりましたが、 これだけではなんにもなりません。最初に説明したように、ここまででは 構造が見えただけで、プログラムは「意味」を理解できません。そしてその 部分は Racc では自動処理できないので、人間が書く、とも言いました。 それを書くのが以下に説明する「アクション」という部分です。
前項で、記号の列がだんだんと大きな単位にまとめられていく過程を見ました。 そのまとめる時に、同時になにかをやらせることができます。それが アクションです。アクションは、文法ファイルで以下のように書きます。
class MyParser
rule
if_stmt: IF expr then stmt_list elsif else END
{ puts 'if_stmt found' }
then : THEN
{ puts 'then found' }
|
{ puts 'then is omitted' }
elsif :
{ puts 'elsif is omitted' }
| ELSIF stmt_list
{ puts 'elsif found' }
else :
{ puts 'else omitted' }
| ELSE stmt_list
{ puts 'else found' }
expr : NUMBER
{ puts 'expr found (NUMBER)' }
| IDENT
{ puts 'expr found (IDENT)' }
| STRING
{ puts 'expr found (STRING)' }
stmt_list : ふにゃふにゃ
end
見てのとおり、規則のあとに { と } で囲んで書きます。 アクションにはだいたい好きなように Ruby スクリプトが書けます。
(この節、未完)
yacc での $$ は Racc ではローカル変数 result
で、$1,$2... は配列 valです。
result は val[0] ($1) の値に初期化され、
アクションを抜けたときの result の値が左辺値になります。
Racc ではアクション中の return はアクションから抜けるだけで、
パース自体は終わりません。アクション中からパースを終了するには、
メソッド yyaccept を使ってください。
演算子の優先順位、スタートルールなどの yacc の一般的な機能も用意されて います。ただしこちらも少し文法が違います。
yacc では生成されたコードに直接転写されるコードがありました。 Racc でも同じように、ユーザ指定のコードが書けます。 Racc ではクラスを生成するので、クラス定義の前/中/後の三個所があります。 Racc ではそれを上から順番に header inner footer と呼んでいます。
パースのエントリポイントとなるメソッドは二つあります。ひとつは
do_parseで、こちらはトークンを
Parser#next_token から得ます。もうひとつは
yyparse で、こちらはスキャナから yield され
ることによってトークンを得ます。ユーザ側ではこのどちらか(両方でもいい
けど)を起動する簡単なメソッドを inner に書いてください。これらメソッド
の引数など、詳しいことはリファレンスを見てください。
どちらのメソッドにも共通なのはトークンの形式です。必ずトークンシンボル
とその値の二要素を持つ配列を返すようにします。またスキャンが終了して、
もう送るものがない場合は [false,なにか] を返し
てください。これは一回返せば十分です (逆に、yyparse を使
う場合は二回以上 yield してはいけない)。
パーサは別に文字列処理にだけ使われるものではありませんが、実際問題とし て、パーサを作る場面ではたいてい文字列のスキャナとセットで使うことが多 いでしょう。Ruby ならスキャナくらい楽勝で作れますが、高速なスキャナと なると実は難しかったりします。そこで高速なスキャナを作成するためのライ ブラリも作っています。詳しくは 「スキャナを作る」の項を見てください。
Racc には error トークンを使ったエラー回復機能もあります。yacc の
yyerror() は Racc では
Racc::Parser#on_error
で、エラーが起きたトークンとその値、値スタック、の三つの引数をとります。
on_error のデフォルトの実装は例外
Racc::ParseError を発生します。
ユーザがアクション中でパースエラーを発見した場合は、メソッド
yyerror
を呼べばパーサがエラー回復モードに入ります。
ただしこのとき on_errorは呼ばれません。
これだけあればだいたい書けると思います。あとは、最初に示した方法で文法 ファイルを処理し、Ruby スクリプトを得ます。
うまくいけばいいのですが、大きいものだと最初からはうまくいかないでしょ う。racc に -g オプションをつけてコンパイルし、@yydebug を true にする とデバッグ用の出力が得られます。デバッグ出力はパーサの @racc_debug_out に出力されます(デフォルトは stderr)。また、racc に -v オプションをつけ ると、状態遷移表を読みやすい形で出力したファイル(*.output)が得られます。 どちらもデバッグの参考になるでしょう。
Racc の生成したパーサは動作時にランタイムルーチンが必要です。 具体的には parser.rb と cparse.so です。 ただし cparse.so は単にパースを高速化するためのライブラリなので 必須ではありません。なくても動きます。
まず Ruby 1.8.0 以降にはこのランタイムが標準添付されているので、 Ruby 1.8 がある環境ならばランタイムについて考慮する必要はありません。 Racc 1.4.x のランタイムと Ruby 1.8 に添付されているランタイムは 完全互換です。
問題は Ruby 1.8 を仮定できない場合です。 Racc をユーザみんなにインストールしてもらうのも一つの手ですが、 これでは不親切です。そこでRacc では回避策を用意しました。
racc に -E オプションをつけてコンパイルすると、 パーサと racc/parser.rb を合体したファイルを出力できます。 これならばファイルは一つだけなので簡単に扱えます。 racc/parser.rb は擬似的に require したような扱いになるので、 この形式のパーサが複数あったとしてもクラスやメソッドが衝突することもありません。 ただし -E を使った場合は cparse.so が使えませんので、 必然的にパーサの速度は落ちます。
パーサを使うときは、たいてい文字列をトークンに切りわけてくれるスキャナ が必要になります。しかし実は Ruby は文字列の最初からトークンに切りわけ ていくという作業があまり得意ではありません。 正確に言うと、簡単にできるのですが、それなりのオーバーヘッドがかかります。
そのオーバーヘッドを回避しつつ、 手軽にスキャナを作れるように strscan というパッケージを作りました。 Ruby 1.8 以降には標準添付されていますし、 筆者のホームページには 単体パッケージがあります。