こんにちは、2024年に新卒入社し、株式会社Techouseクラウドハウス労務でバックエンドエンジニアをしているsatohです。
本記事では、Rubykaigi 2024 1日目のYuichiro Kaneko(@spikeolaf) さんによるセッション、「The Grand Strategy of Ruby Parser」について紹介させていただきます。
The Grand Strategy of Ruby Parser
はじめに
パーサとは
Rubyのパーサは、Rubyのスクリプトを受け取りAST (抽象構文木) に変換するプログラムです。CRubyでは、LALRパーサという種類のパーサが使われています。
パーサの作り方
パーサを作成する方法は大きく2つに分けられます。
- 文法定義ファイルと、パーサジェネレータと呼ばれる文法定義からパーサを生成するプログラムを用いる
- パーサプログラムを手書きする
CRubyでは、Bisonというパーサジェネレータが使われていましたが、Ruby3.3からは後述するLramaに置き換えられています。
パーサに求めるもの
Rubyのパーサで達成したい長期的な目標が３つ挙げられています。
- LSPなどで使いやすいプラットフォームになる
- Universal parser を提供する
- 文法定義の保守性を高める
そしてこれらを実現する手法として、LRパーサとパーサジェネレータを用いる手法を採用し開発が進められています。
なぜLRパーサなのか
LRパーサの強みとして、多くの言語を扱えることや、人間にとって比較的理解しやすいことが挙げられます。
他の構文分析法に基づくパーサとしてLLパーサやPEGパーサなどがありますが、LLパーサはそもそもの表現力が低く、PEGパーサはどこでSyntax errorが起きているのかわかりにくいという問題点があります。
なぜパーサジェネレータなのか
手書きパーサではなくパーサジェネレータを採用するメリットは主に4つあります。
適切な文法定義のためのフィードバックを得られる
文法定義に新しい文法を追加する場合、既存の文法定義とのコンフリクトが生じる場合があります。さらに実際のRubyの構文は複数の文法を組み合わせて作られ、そのあり得る組み合わせは膨大になるため人間がコンフリクトを洗い出すのは困難です。
LRパーサはこうしたコンフリクトの検証を自動で行うことができ、文法のデザインに対してフィードバックを与えることができます。
文法定義が宣言的である
パーサジェネレータでは、パースのためのロジックと分離されているため、宣言的な文法定義ができます。
文法がパーサの実装に先立つ
パーサジェネレータを用いる場合、文法は文法定義で完結し、パーサの実装に影響を受けることはありません。
これに対し、手書きパーサにおける文法の実態はパーサがパースするものであり、文法がパーサの実装に大きく依存することとなります。その結果、不具合が生じた際に文法そのものとパーサの実装のどちらに問題があるのかがわかりにくくなります。
コンピュータサイエンスの理論に基づいている
LRパーサの開発においては、コンピュータサイエンスの理論的な研究成果を大いに活用できます。LRパーサは1965年に考案されてから研究はそこまで活発ではなくなっていましたが、2020年代にいくつかの論文が発表されてきています。
次世代のLRパーサジェネレータ
2023年に、CRubyのパーサジェネレータはBisonからLramaに置き換わりました。
LramaとはRubyで書かれたLRパーサジェネレータであり、Bisonでは実現しにくい機能をサポートするため開発が始められました。
現状のBisonはわかりやすいparse.yを作るための機能が足りていない上、環境に依存する部分が大きく扱いにくいという問題があります。
戦略と開発状況
こうした背景のもと、3つの長期的目標を実現する戦略と現在の開発状況が紹介されました。こちらはspikeolafさんの発表資料スライドにロードマップとしてわかりやすくまとめられています。
LSPが使いやすいパーサ
LSPなどのツールに活用しやすいパーサがサポートしてほしい機能として、
- わかりやすい AST Node 構造
- パーサ層での最適化の削除
- Error tolerance
が挙げられていました。
さらに、AST Node はどの種類でも1つの構造体を共有するようになっており、上2つの機能の実現には先にこの構造を変更する必要があります。
発表時点では、Nodeの種類ごとに構造体を定義する機能が追加されています。
Error toleranceなパーサは、CPCT+というアルゴリズムにより実現が可能です。CPCT+では、LRパーサが動かすオートマトンを有効活用し、エラーを検知した際の位置や状態の情報を付加できます。
理解しやすいparse.y
Rubyの文法定義ファイルであるparse.yはかなり複雑で理解しにくいものになっていて、しばしば「parse.yは魔境」などと言われてきたそうです。
これはparse.yを読み込むパーサジェネレータを裏付けている理論が、実際にparse.yに書かれているRuby文法の表現に対して十分でないことが要因となっています。従来のparse.yはLR構文解析の理論に従ったものになっていますが、実際にはさらに4つの理論的背景があるとのことです。
これら5つの理論に基づいたparse.yを読み込めるようなパーサジェネレータを作ることで、構文解析理論の教科書レベルの知識がある人なら理解できるparse.yを目指しています。
各理論的背景の詳細は難しかったためここでは省きますが、開発がそれぞれ進められており、2日目以降のセッションやLTで紹介されます。
Universal Parser
現在Lramaで生成されるパーサはCRubyの機能に依存しているので、CRuby以外のRuby実装では使うことができません。
どのRuby実装でも使えるUniversalなパーサの生成のため、CRubyのobjectとASTとの依存関係を解消する開発が進められています。
本当のUniversal Parser
現在のUniversal ParserはC言語での実装で与えられており、Javaなどの他の言語で使うためにはそれぞれの言語からCでの実装を実行するための処理が必要になります。
そこから進み、真のUniversalなパーサとして文法定義ファイルからその言語自身で書かれたパーサを生成するパーサジェネレータが考えられるのではないかという話がありました。
おわりに
こうした戦略によりパーサジェネレータが整備されることで、文法定義をより読みやすく書きやすく、文法のデザインとパーサジェネレータの開発を分離して進めることができます。
また、Ruby 3.4に向けてLramaでサポートしたい機能として、Universal parser，Error tolerance parser，Prism APIとの互換性 が挙げられていました。
感想
Rubyのパーサについて今まであまり触れたことがなかったのですが、その奥深い世界を少し知ることができ大変興味深い内容でした。
宣言的でクリーンな文法定義と言語や実装に依存しないUniversalなパーサという構想は理論的にきれいでとても魅力的です。
また、Lramaを取り巻く開発がハイスピードで進められており、Lrama開発コミュニティの力強さを感じました。
Techouseでは、社会課題の解決に一緒に取り組むエンジニアを募集しております。 ご応募お待ちしております。 jp.techouse.com
