Rubyで「expected tokens」をどうやって知るか？ Part.2

パーザの話の前に、文法の話

Yuichiro Kaneko氏：「パーザとはなにか？」とちゃんと考えると難しいです。パーザにはいろんな書き方があるんですけど、僕が理解している範囲では、なにか文字がガーッと入力されてくるので、あるルールから入力された文字を、「ルールを展開していった結果それができるんでしたっけ？」ということを計算するロジックのことがパーズであると僕は理解しています。

Rubyの場合、パーザはいろいろな種類や書き方があって、自分でパーザをダイレクトに書くのは、例えば僕の知っているものだとGoとかPythonとかは再帰下降パーザというかたちで自分の言語を（つまりGoのパーザはGoで）書いたりしているんですけど、Rubyは.yファイルなので、GNU Bisonという、Cで書かれたパーザを作り出すためのDSLのかたまりみたいな伝統的なツールを使ってパーザを作ります。

さっき言ったとおりですけど、parse.yというのを入力として食べさせてあげるとCのコードがベロっと吐かれるので、それをコンパイルしてリンクして使うというのがRubyのパーザの仕組みです。

この「LALR(1)」パーザの話は教科書1章分とかになってしまうのであまり細かいことは言えないんですけど、基本的には構造解析表という表の中から作ってあげて、プッシュダウンオートマトンというオートマトンを作って、その構文を解析していくフェーズが中で行われています。

本当はパーザの話をしたいんです。でもパーザの話をするためには、まず文法の話をしないといけません。文法はいくつかの要素から成立しているんですけど、さっき言った、まず1つめのルール。これは「simple_numericはtINTEGER」みたいな対応関係を表したものがルールになっています。

つまり、このルールをどう書くかによってRubyとかPythonという言語はいったいどういうファイルだったら入力してOKか、あるいはダメなのか、ということが定義されます。

その他にもこのあと出てくる単語なので説明すると、非終端記号と終端記号という考え方があって、非終端記号とは左側に現れる記号のことを指します。例えば「program」とか「numeric」とか「simple_numeric」と言われているものは全部左側に表れるので、これは非終端記号です。非終端記号が右辺に表れることもあるけど、それはあとで説明します。

終端記号というのはルールの右辺にしか現れない記号で、例えばtINTEGERであるとかtUMINUS_NUMというのはルールを見ても左側に絶対に現れないので、これを終端記号と言います。つまり終端記号とはみなさんが入力したものが直接終端記号になって、非終端記号はみなさんが直接入力することができない。そんな感じです。

パーザでどう処理されていくか

例えばこういう右側に書いたルールを持つような構文があったときに、左側の「a;()」というのがvalidなシンタックスなんですけど、これがどうやってパーザで処理されていくか見ていきたいと思います。

パーザというのは各タイミングにおいて、ShiftとReduceのどちらかを選択することができます。Shiftとは、次のトークンを1個食べるという処理です。Reduceは、今自分がスタックに積んでいるんですけど、スタックの上から何個かをあるルールの右辺をベースに左辺に置き換えるという処理のことです。

もしこの両方ができない状態なら、それはシンタックス上おかしいので「syntax error」が出ます。さっきの「a;()」というのはこの図に書いてあるとおり、「ShiftとReduceを繰り返して処理を進んでいき、一番最後にacceptという状態になるので、これはシンタックスとしては正しいみたいな感じになります。

大丈夫ですか？　大丈夫ですね？

（会場笑）

今ShiftとかReduceとか言っているんですけど、ShiftしたりReduceしたりというのは天から降ってくるものでもなければ地から湧いてくるわけでもなくて、なにかしらの基準に基づいて「Shiftしてよい」「Reduceしてよい」と考えないといけない。たぶんここが一番難しいところだと思います。ここでは、構文解析表という表を内部で作っていて、それに応じて「何をしていいのか」を決定していきます。

二次元の表で表すと

これはあるホームページから引っ張ってきた資料ですけど、縦にはステートと言われる何らかの「状態」（詳しくは後述）があり、横には、次に入ってくる「非終端記号」もしくは「終端記号」によってどういう振る舞いをするかという二次元の表を作ることができます。

「s」と書いてあるところがShift可能で、「r」と書いてあるところがReduce可能です。「acc」と書いてあるところはacceptなので、それは構文としてはOKです。空欄ならばそれはダメです。例えばstate0の状態で「)」が来た場合は、それは認められません。右側のGOTO表というのは非終端記号用のもので、すべてスタックに番号をプッシュしていきます。

このテーブルをどうやって作るかという話は非常に長いです。スルッといってしまうと、ルールというものの右辺に「.」を加えたものというのを考えます。これは上の0というのがベースのルールで、下の要素は、右側には「L」と「;」と「E」の3つあるから、「.」を打てる場所が4か所あるわけですね。つまり4ヶ所打ったものをまずは考えてあげて、これがそれぞれ何を意味しているかと言うと、1番の場合というのは、今自分があるところにいて、「次はLが来てほしいな」という願いが込められていると。

2であれば、「Lが1個来たので次は『;』が来てほしいな」という気持ちがあると。「;」が来たらShiftするし、「;」でなければそこで死亡という感じになります。一番最後の4番は、全部3つとも、Eというかたちで全部読み込みが終わったので、「よし！　これだったら3つ行けてるからReduceできるぞ！」みたいな気持ちが込められているというものがあって、これらをLR(0)項といったかたちで教科書では言ったりします。

「LALR(1)」というのは「LR」よりもちょっと強いので実際には「LR(1)項」というのを作らなくちゃいけなくて、本当はさらにもう1個先に何が来るべきかみたいな情報まで付加した状態を考えるんですけど、ちょっと説明が難しいので一旦ここで省きます。これが何を意味しているかと言うと、さっき言った1番の場合は次に「E」が来てほしい。

さっき言ったステートというのがいっぱいできるんです。さっきだったら、ルール1個に対してステートが4つできたように、ルールが10個あったら40個とか50個ができるんです。それぞれのルールはある一点に注目するとグループ分けをすることができます。

例えば一番上の1番の例だと、「次に『E』が来てほしい」と願っているとき、「E」そのものは他のルールによって生成される可能性があるんです。例えば3番とか4番がそうです。「E」というのはさらにそのあとになにかいくつか続くとReduceして「E」が出てくることがあります。4番に注目すると、「P」の直前に自分がいる認識なので、「P」はまたさらに別のルールからつくることができるんですよ。

最後の下2つは「P」だけど、「P」は基本的には「a」か「(」しか来ないはずです。これはさっき言ったとおり終端記号であって、終端記号は他のルールからは作られないので、ここまで来ると、「自分の次に来るものは、あるルールによって生み出されるかもしれない」というのは認識をストップすることができます。

作ったルールをグループ分けした図

このようにして、さっき作ったたくさんのルールをいくつかにグループ分けできて、このような図になります。

8個ルールがあります。これを初見で読める人は僕の話を聞かなくてよいのですが。ここを説明していくと、このstate0というのが最初の状態。ステートマシンなのでどこが最初の状態にならなくてはいけません。state8というのが受理状態なので、いろいろやった結果「ここにいったらOK」みたいな話になります。

例えばこのstate2からstate5にかけてPと書いてあって、これは「P」をShiftすればstate5にいけますよということです。

例えばこのstate5はここから行き先がないじゃないですか。なにかというと、このstate5というのは「P」を読み終わったあとで「E」にReduce可能なので、ここに来た場合はReduceをする。

その「Reduceをする」というのは、「E」は「P」から生成可能ということでReduceしてあげることができます。例えばちょっと特殊ですけど、state12というのは上のルールで見ると、今は「E」まで読み終わっていてReduceをしたいと言っていています。下のルールで見ると「次に『P』が来てほしい」と言っているから、状態によっては次に来るトークンが何かによってReduceすることもShiftすることもできるというような状態も存在しています。

Bisonがテーブルを圧縮する

ここまでやって、今のグラフを表に展開したものが、先程から説明しているこの構文解析表になります。

ここまで準備ができれば、実は「expected tokens」というのはわかっています。例えば今この赤く塗ってあるstate3の状態にいるのであれば、そのときに次にReduceもしくはShiftしてよいトークンというのは4つしかないんですよ。

だから今自分がstate3にいるとわかれば、そのときに次に来てほしいトークンはここに書いてある「;」と「,」と「)」と、あとは「$」というのはエンドオブインプットなんですけど、この4つだったら良い。つまりsyntax errorがこの場所で起きた場合、「例えば『a』と『(』はダメなんだけど他の4つだったら良い」というのがわかるので「これが僕たちが探し求めていたexpected tokensだ！」みたいな感じになる。これをRubyの中でもとることができれば実装完了みたいになるんです、……けどぜんぜんだめで。

（会場笑）

Bisonもテーブルをけっこう圧縮するんです。なぜかと言うと、40パーセントとか19パーセントしかテーブルを使っていないのですごいスパースなテーブルなんですけど、Rubyの場合は1,000ステートとか400シンボルとかが普通にあるので、これをもろにメモリ2×2でもつとすごい重いです。

なので、1つの注目ポイントとしては、Bisonは「横に関しては同じルールが並ぶことが多くて、縦に関してはGOTOの場合に関しても同じ数字が並ぶことが多い」というところに着目して、デフォルト値として圧縮を掛けます。

「これでもまだぜんぜん圧縮ができてない」と昔の人は思ったんでしょうね。なのでもう1個別のアプローチがあります。これをよく見ると「1」と「2」というのが横に同じ場所に並んでることがあるので、うまいこと場所を調整してあげると、圧縮したテーブルが手に入るという図になっています。

こんな感じでチェックテーブルを用意して「その値は『1』だよね」という感じで取ることができる。

この2つのBisonがテーブルをギュッと圧縮を掛けるんですが、これが問題になりがちです。

default reduceによって起こる問題

今2番目に説明した例では、気合で元のテーブルを復元できるんですけど、default reduceは「本当は勝手にReduceしてはいけないところをReduceしてくる」ので、いろいろ問題が起きます。

例えば最近のRubyだと、こういう文章を食わせると「whenで書いてほしかったんだよ」とか言うんですけど、ぜんぜん嘘で。

（会場笑）

Rubyは最近パターンマッチが入ったので、ここにinと書くことができるんです。

だけどエラーメッセージ上ではwhenになっている。なぜかと言うと、あるステートで本当は「syntax errorです」と言ってほしいんだけど、たまたまdefault reduceが入っていると、Reduceを何回かやったあとで初めて「あれ？　行き止まりになっちゃった……」と認識をするんです。

つまり本当はエラーを認識してほしいタイミングよりもあとでエラーを認識することになって、そのときには本来ほしかったトークンのリストと異なるものが出ることになる。例えばこんな感じ。

さっきの左側が正しいはずなんだけど、右側では「r7」というのがいっぱい埋まっていて、本当はこの「2」の中のある状態でエラーを認識してほしいんだけど、とりあえずReduceしちゃうために、エラー判定を難しくしているという話があります。

あとはdefault reduceということは、自分が今積んできたスタックに対して実際にReduceをガンガンかけて、どこの時点で行き詰るかチェックをすればエラーかどうか判断できるんです。でもこの計算はスタックの状態に依存した計算なので、もしこの方法で計算すると、今後テストを書くのがすごく難しくなるという問題があって、「困ったなあ」と言うのがあります。

default-reductionをなくしたとしても問題が

どうすればいいかと言うと、素晴らしいことにBisonにはdefault-reductionをなくすことができるオプションがあります。これを使えば、さっきの左側みたいなテーブルが手に入って「やったあ！　expected tokensのテーブルが手に入った！」と……。

……思うんですけど、これをRubyでオンにすると主にビルドが失敗するというのがあってぜんぜんダメでした。

（会場笑）

何が失敗するかと言うと「./miniruby -v」とやっただけで突然「syntax error」を言い出して、「何を言っているんだ？」と思ってしまうんですが……。何かというと、今この赤くしているところで問題が起きています。

本当はtLABELというトークンがほしいんですが、tLABELというトークンを吐くためにはRubyのトークナイザのステートをいじらなければいけなくて、LABELかENDFNという状態にしておかないといけないんです。

これをどこで設定しているかと言うと、おもむろに関数名を読んだあとに謎のアクションで設定しているんです。

「default reduce」がオンのときはとりあえずReduceするので、このルールを先に評価してから次のトークンを探しにいくから問題ないんです。でも、「default reduce」をオフにしてしまうと、（上の図の）この真ん中で囲っている大きい部分を実行する前に「次のトークンはtLABELだよね？」と要求してきます。

なので、本来はステートを書き換えてから次のトークンがほしかったのに、ステートを書き換える暇もなく次のトークンを要求されたために、手に入らないトークンを要求されてsyntax errorが起きるという問題があります。

実際に問題をどう処理しているか

なので、僕が今どうやってこの問題を処理しているかという話が最後に来るんですけど、おもむろにスタックとステートのポインタをRubyの中にバーッと出せるようにして、おもむろにスタックをバーッとコピーするようにして、それを使ってトークンの計算を都度やるようにすると解決します。

処理自体は難しくなくて、トークンの数は有限なので、今のその状態に対してすべてのトークンをバーッとforで回してあげてexpected tokensをその都度計算してあげて、その計算結果をここでは第1引数にプッシュしてあげると解決します。

さっき言ったpush_expected_tokenという関数の中では、今取ってきたものがもしdefault reductionの場合は実際に今自分が持っているスタックのルールによってReduceして状態を書き換えた上で次の計算を走らせてあげる、となっています。

defaultじゃないReduceの場合や、defaultじゃなくてもShiftの場合というのは、それは絶対に読んでいいトークンなので、そのときは自分の持っているexpected tokensの一覧に追加してあげて処理を終わらせるとしてあげると、こんな感じです。

さっきのwhenとしか言ってなかったやつがあったじゃないですか。それがちゃんと「when」と「in」と「;」かな？　「in」と「;」の次の行として認識されるやつの3つが「expected tokensだよとできて、「よかった、これで僕たちのほしかったexpected tokensがちゃんと手に入った」というのが、今の実装になっています。

大丈夫ですか？

（会場笑）

果たしてこんな実装を入れていいのか？

何が言いたいかと言うと、今のRubyでもがんばれば本当にほしかったトークンを認識することは可能。

……なんですが、どう考えてもyypactとかyytableみたいなものは自然界に落ちてるわけがないんです。

（会場笑）

これらはBisonというツールが吐き出すCの中におもむろに現れる、要するに「本当はRubyから見えない世界」にいるんですよ。だけどもちろん触ることができる。

果たしてこんな実装を入れていいのか？　という話があり、ダメそうですよね？

（会場笑）

当然Bisonドキュメントにも「yyから始まるものは僕たちが管理しているもので、君たちが勝手に使っていいものじゃないんだから、そんなのに依存するコードを書くんじゃないぞ」みたいなことが書いてあるんですよ。

でも考えてください。Rubyの中にはこういう邪悪なコードが普通に入っていて……。

（会場笑）

sedなんですけど、おもむろにBisonで拡張ができない関数とかマクロの引数の数を増やすために、1回Bisonを使って生成したCのコードを手動で書き換えるみたいなコードがけっこう入っていて、「治安なんかないんだなあ」みたいな気持ちになるわけです。

（会場笑）

こうしても実際「yy〇〇」に依存しているので、僕の書いたコードを入れても怒る人はいないんじゃないかな？　というのが今の心境です。

大丈夫ですか？　ちょっと早かったかな？

（会場笑）

次に期待されるトークンはパーザから決定できる

というわけで、今の僕の手元にはexpected tokensを取ることが可能なコードがあるんですが、Rubyのmasterに入れるためにはちょっと考えなきゃいけないことがあって。1つは、これはどうやってテストをするんでしょうね？（笑）

さっき言ったとおりただ表を作って投げているわけではなくて、syntax errorとかになったときにその状態に依存してexpected tokensを計算するようにしてしているので、テストをするためにはまず正しいスタックを作ってあげないといけないんですよ。

スタックというのは理屈的にはRubyのスクリプトが無限に長くできるのでスタックは無限に長くなるんですけど、果たしてどうやったら網羅性のあるテストが書けるのかなぁという問題があって、もしこの辺詳しい方がいたら論文を紹介していただくとか「こうやってやるといいよ」とご教示いただけると開発が進みます。

あともう1個些末な話ではあるんですけど、SEGVすることがあるので、あまりパフォーマンスを落とさないでポインタを管理できる方法を考えないといけないなと思っていて、これは案があるので実装されたらまた説明すると思います。

駆け足になってしまいましたが、以上で今日のまとめをすると、Rubyにおいて「次に期待されるトークン」というのは一応パーザから決定することができます。

例えば「syntax errorになったから何かをする」みたいなことを、「みなさんは正規表現にマッチさせて……」みたいにやっていると思うんですけど、こんなことをしなくても本当はすべての情報はRubyが持っているはずという話です。

あとはBison固有の話ですけど、さっきの圧縮をするために使っている技法というのは便利でRubyはそれに依存しているんだけどうまく扱うのは難しいよねという話と、Rubyがそれに依存しているから付き合わなきゃいけないよねという話が、今回の発見です。

今回の資料を作るにあたって、今日いないと思うんですけど、篠田さん（@takeshinoda）という方と僕の目の前にいる、はくどー氏（@hkdnet）にレビューをしてもらったのでありがとうございます。

あとは今日いろいろと駆け足で話してしまったので、もしこの辺の話に興味のある方がいらっしゃったら参考文献として青木峰郎さんという方が書かれた『Ruby Hacking Guide』が、日本語のテキストはWebで読めるので、ここには今言われたトークナイザやパーザの話が載っていますし、Rubyそのものの仕組みに興味がある場合は『Ruby Under a Microscope』という「顕微鏡本」と言われている本がおすすめです。

パーザに関してもっと踏み込んで知りたかったら「ドラゴンブック」と言われている『コンパイラ—原理・技法・ツール』という本があるので、この辺を読んでいただくと良いと思います。Bison系の話だったら一番最後に書いてあるBisonがどういうふうに中のデータ構造を持っているかという、これはuic……どこかのアメリカの大学ですかね。そこが出している資料があるので、もっと詳しく中の構造について書かれていると思います。

というわけで駆け足でしたが、Keynoteとさせていただきます。ありがとうございました。

（会場拍手）

default reduceをオフにはできないのか

司会者：ご質問とかがある方いらっしゃいましたら2、3分以内で。質問ある方いらっしゃいますか？　

（会場挙手）

質問者：先ほどdefault reduceをオフにしてみると失敗するというのがわかったので別の方法でアプローチをしていただいたと思うんですけど、その場合Bisonの何かに依存するような方法をするときはdefault reduceを入れたままあれをやって動くようになっているような……。

Kaneko：はい。僕は自分のリポジトリにプッシュしているブランチにおいてはdefault reduceはいつもと同じ、今のRubyの本番と同じ状態にしつつ動くようなコードが作れているので、質問に関して言うとdefault-reductionをフルで使いながらexpected tokensをちゃんと取るというのはできます。……で、答えになりますか？

質問者：ありがとうございます。もう1個いいですか？　default reduceをオフにするという方式は取れないんでしょうか？　聞いている感じだと評価し終わったステートのドウタラコウタラじゃないとtLABELが作れないので、ステートの変更みたいなものにReduce後のステートのほうに依存しているから、書き換えられるかというと微妙に怪しいんじゃないかなと思っているんですけど、書き換えられますか？

Kaneko：僕はそもそも書き換えることを諦めています。なぜかと言うとRubyのパーザの中でもわりと面倒くさいジャンルに入っているLEX_STATEと言われるものを完全に理解しないといけないというのが1個。あと、こういうコードは1ヶ所じゃないんです。普通Bisonで書くときはトークンを全部並べて「最後にこういうアクションをしてください」と書くのが普通なんですね。

ここは普通じゃないですよ。実はこれ1ヶ所じゃなくて、このルールだけでもここでも実はもう1個SET_LEX_STATEというやつが隠れているんですね。これに真っ向から勝負する元気はちょっと僕にはないです。ただ、理屈的には何かがんばればできるかもしれないです。

質問者：ありがとうございます。

司会者：では時間になりましたのでKeynoteは以上とさせていただきます。ありがとうございました。

（会場拍手）