Ruby構文解析器 開発日録#1
こんにちはydahです。最近はPure Ruby LALR parser generatorであるLramaにパッチを送っています。
気がつけば12月もあとわずかとなり、Ruby3.3.0のリリース日も近づいてきましたね。5月半ばに開催されたRubyKaigi 2023で金子さん(@spikeolaf)の「The future vision of Ruby Parser」を聞いてから、約半年が経ちました。あの時の自分はまさか半年後には自分がパーサージェネレーターの開発に関わっている人生を送っているとは思いもしなかったと思います。
今回のRuby3.3.0のリリースノートには、私が実装した機能が載っていてとても感慨深いです。
Use Lrama instead of Bison
…
- Parameterizing Rules (?, *, +) are supported, it will be used in Ruby parse.y
継続して関わっていこうと思っているので、実装した機能や、学んだこと、今考えていることを記録として残していこうと思います。
今回は、Kyoto.rbやFukuoka.rbで発表した内容をまとめたものを書いていこうと思います。以下に発表資料を貼っておきます。
Lramaとは何なのか
Lramaとは何かを簡単に説明すると、Rubyで書かれたLALR (1)パーサージェネレーターです。パーサージェネレーターなのでパーサーそのものではなく、文法ファイルをインプットとしてパーサーを生成するためのツールです。
Ruby 3.2まではGNU Bisonという、パーサージェネレーターを使用していましたが、このBisonを置き換えるために金子さんによって作られました。
なお、LramaはRubyKaigi 2023の2日目にBisonからLramaへの移行は完了しています。
なぜ、BisonからLramaに置き換えたかったのか、その理由はいくつかあります。その内の1つは、Bisonのバージョンに引きづられずにすむという点です。
たとえばユーザー^1ごとに使用しているBisonのバージョンは異なります。つまり、複数のバージョンを対象にメンテナンスをしなければなりませんでした。
要するに、異なるバージョンのBisonで動作するようにするための労力を払っていく必要があり、それをメンテナンスしていくのは簡単ではないです。
また、例え最新のバージョンのBisonで新しい機能が導入されたとしても、その新機能を使えないという制約がありました。
Lramaへと置き換えることで、これらの制約から解放されます。
つまり、Lramaへ置き換えることで、どうなるかというと以下の大きなメリットがあるということです。
- 複数バージョンのBisonをサポートする必要がなくなる
- 最新のBisonの機能を使えるようになる（実装すれば）
- Bisonに縛られないので、もしBison以外のパーサージェネレーターの便利な機能も使えるようになる（実装すれば）
Lramaが目指すもの
Lramaが目指すものは、Bisonの機能をそのままRubyに移植することではありません。
詳しくは金子さんのRuby Parser Roadmapを参照していただければと思いますが、いくつかあるGoalのうちの1つに、parse.y for Under graduateというGoalがあります。
これは、parse.yををより読みやすく理解しやすいものにしていくというものです。歴史的な経緯によって、parse.yは複雑になってしまっているので、これを解消していくことが目標です。
具体的にいうと教科書などで構文解析について学習していれば、parse.yを読んで理解できる状態に持っていくことが目標です。
このゴールを達成するために、現在は前述の通りBisonに縛られることがなくなったので、パーサーを生成するための文法ファイルのBNF[^2]の記法をよりリッチにしていくアプローチをとっています。
Bisonにはプリミティブな記法しか提供されていないので、他のパーサージェネレーターにはあるような便利な記法をLramaに実装していくことで、より読みやすく理解しやすい文法ファイルを作ることができるはずです。
我々はBisonからLramaに置き換えることで、どんなパーサージェネレーターの機能も実装すれば使えるようになったのです。
取り込むために文法を調整しながら実装していけばいいだけですし、実装すればするほど便利な文法が増えていくので、とても良いですね。
Menhirがやってきた
現在、LramaにMenhir[^3]で提供されている記法を実装していっています。
MenhirはOCaml向けのLR(1)パーサージェネレーターです。OCamlにはocamlyaccというパーサージェネレーターがありますが、Menhirは互換性を保ちつつocamlyaccの機能を拡張したものです。
つまりはLramaと同じでより力を引き出したパーサージェネレーターを作るという目的を持って作られている訳ですね。
Menhirには便利な記法がいくつかありますが、その中の1つであるParameterizing rulesという記法を実装していっています。
Prameterizing rulesとは非終端記号の定義を、他の（終端または非終端）記号でパラメーター化できるというものです。つまり、文法ファイルにおける共通的なパターンのためのシンタックスシュガーを提供できる機能です。
ルールは基本的にはユーザーが定義するものです。要はマクロを定義しているようなものと考えてもらえれば良いと思います。
ただ、いくつかの汎用的なパターンについてはstandard libraryとして提供することを想定していて、これらはユーザーが定義する必要はありません。
言葉で説明してもよくわからないと思うので、実際にどのような記法なのかを見ていきましょう。
たとえば、以下のような文法ファイルがあったとします。
args : arg
| args ',' arg
;
これは、引数のリストを表現する文法です。[^4]この文法をParameterizing rulesを使って書き換えると以下のようになります。
separated_list(',', arg)
こう見てみると、引数のリストを表現する文法ということがより明確になりますね。また、記述量も減っているので、より読みやすくなっています。
このルールについてはstandard library[^5]として提供しているので、ユーザーはルールを定義する必要はありません。
Ruby 3.3では以下の表に示す、ルールをstandard libraryとして提供しています。
| Name | Recognizes | Alias |
|---|---|---|
| option(X) | є ｜ X | X? |
| list(X) | a possibly empty sequence of X’s | X* |
| nonempty_list(X) | a nonempty sequence of X’s | X+ |
| separated_list(sep, X) | a possibly empty sequence of X’s separated with sep’s | |
| separated_nonempty_list(sep, X) | a nonempty sequence of X’s separated with sep’s |
また、Aliasに示すように正規表現でよく見るような[^6]シンタックスシュガーも実装しています。
これらのstandard libraryはそれぞれのルールごとに展開する処理として実装していますが、最終的にはそれぞれのルールを定義した文法ファイルのみを提供するようにする必要があります。
Menhirでも同様に文法ファイルを提供して、ユーザーがパーサージェネレーターに渡す文法ファイルの前にloadすることで、standard libraryとして提供している[^7]ので、Lramaでも同様に実装していく予定です。
このためには、ユーザー定義のルールのサポートを実装・改善していく必要があるので、これからの課題となります。
まとめ
Lramaとは何か、Lramaが目指すものは何か、BNFの記法の拡張のためにMenhirの機能を移植しているという内容を書いてきました。
Ruby Parser Roadmapを見た方はわかると思いますが、まだまだLramaが達成すべきGoalはたくさんあります。
パーサー/パーサジェネレーターの開発は難しいこともあるかもしれませんが、とても楽しいので是非興味がある方は参加してみてください。きっと楽しいと思います。
[^2]: Backus–Naur formのこと。
[^3]: 余談ですが、Menhirはいわゆるモノリスやメガリスと呼ばれる石の記念物のことです。日本にもいくつか有名なMenhirがあるらしくって、岐阜にはたくさんのMenhirがあるそうです。そうだ、岐阜に行こう。
[^4]: BNFは皆さん気がつくと読めるようになっているはずなのできっと説明は不要なはず。(BNFはBokutachi No Friendの略でもあります(?))
[^5]: 要は組み込みライブラリのようなものと考えてもらえれば良いと思います。
[^6]: https://docs.ruby-lang.org/ja/latest/doc/spec=2fregexp.html#quantifier
[^7]: https://gitlab.inria.fr/fpottier/menhir/-/blob/20230608/src/standard.mly?ref_type=tags