イントロダクション
世はまさに大パーサー時代。人々はパーサーの海へと繰り出す。 ――― kaneko.y
RubyKaigi 2023 における "the bison killer" による大パーサー時代の幕開け宣言からはや4ヶ月が経ちました。みなさまいかがお過ごしでしょうか。@junk0612 です。
タイトルにも記載したとおり、今回は parse.y をちょっとわかったつもりになれるかもしれない記事です。 あらためて軽く説明すると、parse.y とは、Ruby の文法とその処理内容について定義されたファイルです。難解なことで有名になってしまっていますが、実際に軽い気持ちで手を出して、意味も分からず圧倒された経験がこれを読んでいる方にもあるのではないでしょうか。かくいう僕もそうでした。
ですが、パーサージェネレーターである Bison (== Lrama) の文法ファイルの書き方がわかっていれば、言い換えれば、どこに何が書かれているのかがわかっていれば、理解したい内容の部分に絞って読むことができるのでかなり理解しやすくなります。今回は Ruby の文法構造を例にとってみます。どれくらいわかりやすくなるか、注目しながら読んでみてください。
入門・Bison 文法ファイルの大まかな理解
なにはともあれ、Bison の文法ファイルがどうなっているか、ざっくりとした把握から始めていきましょう。まず、文法ファイルの構造の概要を Bison のドキュメント から引用すると、下記のとおりです。
%{ Prologue %} Bison declarations %% Grammar rules %% Epilogue
一番大きなくくりでは、Bison の文法ファイルを構成しているのはこの4つのセクションだけです。また、各セクションは記号で分けられており、実際に parse.y の内部を検索してみると、この記事を書いている時点の master では
にあります。
この中で文法はどこに書かれているかというと、Grammar rules セクションです。つまり %% の間だけ見ればいいので、それ以外の約 10,000 行を消すことができます。ということで、さくっと消してしまいましょう。消したものがこちらです。
本編・Grammar の理解
さて、続いては Grammar rules の内部の構造を軽く見ていきましょう。Grammar rules は、下記のような「文法」を任意の数だけ連ねたものとしてできています。
nterm: symbol1 symbol2 symbol3 ...
| symbolA symbolB symbolC ... { action }
| symbolX { action1 } symbolY { action2 } ...
これは、以下の内容を意味しています。
- この文法で生成される記号は
ntermという名前である ntermは、以下のいずれかの記号がこの順で並んでいるものであるsymbol1symbol2symbol3...symbolAsymbolBsymbolC...symbolXsymbolY...
{ }でくくられたactionを使って、ntermが出来上がった時点でどのような処理を行うかを記述している- Action がない場合、Bison は入力された文字列が
ntermとして正しいかどうか判定することだけ行う。AST を作ったりはしない
- Action がない場合、Bison は入力された文字列が
- 文法の記述途中にも Action を記載することができる。
action1はsymbolXを読み込んだ直後、action2はsymbolYを読み込んだ直後に実行される
いろいろ書き連ねましたが、大事なのは Action は、文法そのものとは関係がない ということです。言い換えれば、Action を消してしまっても、Ruby の文法構造は影響を受けないということになります。
今回は文法の理解に焦点を当てるので、不要な Action は消してしまいましょう。数が多いので、もりもり消すことができて、消したものがこちらになります。
どうでしょう？ ここまで消すと、ちょっと読めるかもという気がしてきませんか？
Bison の文法の読み方は上でお話ししたとおりなので、ちょっと読んでみましょう。
stmt : keyword_alias fitem fitem
| keyword_alias tGVAR tGVAR
| keyword_alias tGVAR tBACK_REF
| keyword_alias tGVAR tNTH_REF
| keyword_undef undef_list
| stmt modifier_if expr_value
| stmt modifier_unless expr_value
| stmt modifier_while expr_value
| stmt modifier_until expr_value
| stmt modifier_rescue stmt
| keyword_END '{' compstmt '}'
| command_asgn
| mlhs '=' lex_ctxt command_call
| lhs '=' lex_ctxt mrhs
| mlhs '=' lex_ctxt mrhs_arg modifier_rescue stmt
| mlhs '=' lex_ctxt mrhs_arg
| expr
| error
;
例えばこれは、stmt という記号に対する文法ですが、最初の4行は fiterm tGVAR tBACK_REF tNTH_REF などが何を指すのかよく分からなくても、keyword_alias から察するに alias のことを指していそうだ、というのはわかると思います。同様にその次の1行は undef、その次の5行は後置 if、後置 unless などの後置記法を指していそう、ということもなんとなく推測できると思います。
文法中に現れる各記号は、別の文法の左辺として現れる非終端記号か、実際の文字列に1対1で対応する終端記号のどちらかに必ず分類されます。stmt を例に取ると、keyword_alias は終端記号として parse.y の L1571 に定義されていますし、mrhs は非終端記号として別の場所に文法が定義されています。
このように文法の「展開」を繰り返して、最終的にソースコードの文字列に対応させるまでの文法をすべて記述することが、Bison の文法ファイルの中心的な機能であり、Ruby の文法を理解する上で一番重要なポイントになります。これさえ分かってしまえば、あとは読むか読まないかです。あなたもレッツ読解！
余談・Action のためにある文法の名寄せ
文法部分だけを抽出した parse.y を読んでいると、たまに別の記号と1対1で対応付けるだけの文法があることに気づきます。たとえばこのあたりなどです。
これらの存在している理由は、文脈によって異なる Action を書くためです。主に構文解析時の都合で、たとえば普通の if 式の if と後置 if の if では、読み込んでいる状態が異なるために別の処理をしなければならないということがよく起こります。このときに、別の文法として2つの非終端記号を定義し、片方は特例の処理を実装しておいてもう片方の記号を呼ぶようにしておくと便利に使えます。
ですが、あくまで文法理解の観点から見れば、これらは同じキーワードです。2つある文法を名寄せして1つにまとめてしまっても全体としては変わりません。今回は名寄せしたものは用意していませんが、上にも載せた文法のみのファイルからスタートして、試しにいじってみてはいかがでしょうか。Ruby の文法の理解に役立つと思います (一部の奇特な方には TRICK のネタになるかも？)。
終わりに
いかがでしたでしょうか。今回は、Ruby の文法理解に焦点を当てて parse.y を読んでいくにはどうするかをご紹介しました。
kaneko.y さんの書いたパーサーやりたいことリストにはいろんな内容があるので、一人でも多くの方に協力していただけると、世界がちょっとずつ良くなっていきます。この記事を読んで「意外といけるかも……」と思った方がいたら、ぜひ ruby-jp Slack の #lr-parser チャンネルへお越しください。加えて、弊社に入社いただければ構文解析器研究部員の肩書きもご用意しております。
永和システムマネジメントでは、パーサをいじってわいわい遊びたい方の応募をお待ちしております。
