Lrama LRパーサジェネレータが切り開く、Rubyの構文解析の未来

シンプルで強力な文法はRubyの特徴のひとつだと言われています。その文法を技術的に支えているのがパーサです。Ruby 3系のひとつの目標として、LSPやRBS、TypeProfをはじめとした各種ツールの拡充があります。それらのツールは多くの場合AST（抽象構文木）というプログラムをパースした結果を対象に解析を行います。そこでこれらのツールに対してより良いAPIを提供するべく、Rubyのパーサを刷新する動きが活発になっています。

最新のRuby 3.3ではパーサの内部に大規模な改善が入っています。この記事ではRuby 3.3で導入されたLrama LALR (1) パーサジェネレータについて紹介します。

パーサジェネレータ —⁠—パーサをどのようにして実装するか

パーサを実装する方法は大きく2つあります。フルスクラッチで実装する方法と、パーサを生成するツールを使って実装する方法です。前者は手書きパーサと呼ばれ、C言語やRubyなどのプログラム言語で実装する方法です。後者はパーサジェネレータというツールを使い、BNF（Backus–Naur form / バッカス・ナウア記法）などのDSLで定義した文法ファイルからパーサの実装を自動生成します。パーサジェネレータというとYacc、Bison、ANTLRなどが有名です。

Rubyは後者の方法を選択しています。以下はRubyのparse.yというファイルの抜粋ですが、このように文法を定義することでパーサジェネレータが自動でパーサを生成してくれます。

primary : literal // numeric (数値) や symbol (シンボル)
        | k_if expr_value then compstmt if_tail k_end // if ... end
        | k_class cpath superclass bodystmt k_end // class C ... end

このパーサの生成のために、これまでRubyはGNU BisonというLRパーサジェネレータを使用していました。

なぜLRパーサジェネレータを使うのか

LRパーサジェネレータを利用することには、手書きパーサに比べて多くの利点があります。ここでは主な利点について紹介します。

文法が理解しやすい

パーサジェネレータの入力はBNFをもとにした文法定義です。BNFを用いることで文法定義を簡潔に記述できます。

たとえばRubyのclass定義の文法は以下のようになっており、classとendの間にクラス名（cpath⁠）⁠、省略可能なスーパークラス定義（superclass⁠）⁠、クラスの内容（bodystmt）が含まれるものだということがわかります。またclass定義はprimaryであることから、たとえば1や"str"といった他のprimaryと同じ位置に書けることが一目でわかります。

primary : k_class cpath superclass bodystmt k_end
        ;

superclass	: '<' expr_value term
            | /* none */
            ;

文法定義とパーサの実装に乖離がない

文法ファイルからパーサを自動で生成するため、文法定義とパーサの実装に乖離が発生しません。またパーサの実装が自動的に手に入るということは、言語開発者は文法のデザインに集中できます。

たとえば1 + 2 * 3が1 + (2 * 3)であるという演算子の優先順位や、1 + 2 + 3が(1 + 2)+ 3であるという結合規則について、パーサジェネレータであれば以下のように指定するだけでよく、その実装について開発者が気にする必要はありません。

// 上の演算子の方が優先度が低い。またleftなので左側に結合する
%left　'+'
%left　'*'

文法の変更に対してフィードバックを得ることができる

Rubyには時々新しい文法が追加されます。またイシュートラッカーには既存の文法の変更に関する提案もきます。LRパーサジェネレータは文法の追加および変更に対して、ある種のフィードバックを与えてくれます。

たとえばBug #18080はinや=>を用いた1行パターンマッチに関するチケットです。(1)のコードのように引数をカッコで囲んだときは=>を続けて書くことでパターンマッチをすることができますが、(2)のコードのように引数をカッコで囲まないときはシンタックスエラーになってしまいます。

# (1)
p(1) do
end => a

# (2)
p 1 do
end => a

一見すると(2)のケースでもパターンマッチできることが望ましいように思えますが、これには一つ落とし穴があります。次のようにブロックを書かなかった場合はどうなるでしょうか。(4)のコードは{1 => a}というハッシュを引数にしてpというメソッドを呼び出したという既存の構文と衝突してしまいます。

# (3)
p(1) => a
# (4)
p 1 => a

このケースでは3つの選択肢があると思います。

引数をカッコで囲んだメソッドの呼び出しと、カッコなしの呼び出しは異なるものなので、前者はパターンマッチできるが後者はできないとする
基本的にはパターンマッチできるが、ブロックなし、カッコなし、=>が続くケースのみパターンマッチではないという例外を入れる
非互換をいれて、すべてのケースをパターンマッチにする（この判断はかなり難しいと思いますが）

最終的にはデザインと意思決定の問題だと思いますが、ここで重要なのはLRパーサジェネレータがこのような論点を自動的に与えてくれるという点です。今後も新しい文法を追加していくために、このようなフィードバックが自動で得られる仕組みは必須だと思います。

コンピュータサイエンスの理論に基づいている

LRパーサは、形式言語理論やオートマトンといったコンピュータサイエンスの理論に基づいています。計算量や取り扱うことが可能な文法について多くの研究がありますし、その基本的な理論について優れた教科書もあります。それらの理論を学べばRubyのパーサを完全に理解できる、とはいきませんが、その多くの部分を理解できることでしょう。また研究結果を取り込むことで、より便利なパーサを手にすることができます。

エラートレラントなパーサを文法定義から自動生成できる

後述するようにLSPなどのツールでは不完全なソースコードをパースする必要があります。このような特性を持ったパーサをError Tolerance parserと呼んだりします。

LRパーサジェネレータの場合、一度アルゴリズムを実装してしまえばどのような文法定義に対してもエラートレラントなパーサを生成できます。LRパーサの実装というのはオートマトンです[1]。つまり行き止まり状態にならないように入力を修正することで、不完全なソースコードをパースできます。

# 不完全なコード
if end

# たとえばtrue thenの2つの入力を補うことでRubyのコードとしてパースできる
if true then end

またこの方法は文法定義に依存しない方法なので、今後Rubyに新しい文法を追加したときにも自動的にエラートレラントなパーサを生成できます。

BisonからLramaへ

そんな便利なLRパーサジェネレータですが、RubyがBisonを使い続けることにはいくつかの問題がありました。

Bisonの複数のバージョンをサポートしないといけなかった

Rubyをソースコードからビルドするときにはその環境にインストールされているBisonが使われます[2]。Rubyはさまざまな環境でビルドされるので、それにあわせて様々なバージョンのBisonでビルド可能でなければなりませんでした。そのためBisonに新しい機能が入ったとしてもすぐに使えなかったり、複数のバージョンで動くように生成したCのコードをsedでさらに書き換えていたりしました。

Bisonの機能の拡張が難しい

Rubyのパーサにとって必要な機能があったときに、それをBisonに入れることはかんたんとは限りません。たとえばLSP向けのパーサにはエラートレラントなパーサが必要になります。LSPはユーザがコードを変更するたびに、そのコードを解析します。コードを変更している最中、それが文法的に正しくないことはよくあります。たとえばメソッドを追加している最中には)が一時的に不足していることもあれば、デフォルトの引数が不足していることもあるでしょう。

# )が不足しているケース
def m1(
end

# デフォルトの引数が不足しているケース
def m2(a =)
end

そのような入力をうまく扱うために、きめ細やかなエラー復旧のアルゴリズムをパーサジェネレータが提供することが期待されます。

他に改善したいポイントとして、Bisonがサポートしている文法がプリミティブであるという点が挙げられます。メソッド呼び出しの引数（obj.m(1, 2, 3)）や配列リテラル（[1, 2, 3]）のように、複数回の繰り返しというのは文法定義によくでてきます。このような文法にはパターンがあり、以下のように書くことで実現できます。

list : item
     | list ',' item

しかしパターンなのであれば、これをもっと簡潔に書きたいと思うのは自然な考えでしょう。たとえばOCamlのMenhirというパーサジェネレータではseparated_list(',' item)という書き方ができます。セパレーターが入らない場合、item*と書くこともできます。こういった文法ファイルを書きやすくする仕組みもRubyで使いたいと思っていました。

これらをBisonに実装しようとしても、BisonはRuby以外にも様々な言語で使われているため、様々な調整や議論が必要になるでしょう。

Lramaによる改善

これらの問題を解決するために、Ruby 3.3では新しくRubyで実装されたLramaというパーサジェネレータを利用するようになりました。LramaはRubyのレポジトリに直接インストールしているので、ビルドする環境に依存せず常に同じバージョンを使えます。またLramaは私をはじめとしたRubyの開発者で開発・管理しているので、Rubyにとって必要な機能を実装して取り込んでいくことが可能です。リリースのタイミングについてもコントロールできます。

新しいBisonでは実装されていたのにもかかわらず使えていなかった機能として、Named Referencesという機能があります。Lramaにこれを実装し、すでにRubyでは使われています。他にもitem*やitem?といった記法もサポートをしています。こちらはRuby 3.4系から使っていきたいと思っています。

特筆すべき機能についてはNEWS.mdにまとめています。興味のある方はそちらもご覧ください。

パーサに関するその他の改善

パーサが生成するAST（抽象構文木）のノードのデータ構造が大きく変わりました。ノードは種類によって必要なメモリのサイズが異なります。a = 1という代入を表すためのノードでは左辺のaと右辺の1を保持する必要があります。一方でtrueを表すノードは付加的な情報を必要としません。いままではすべての種類のノードが同じデータ構造を使っていたため、ノードによっては無駄にメモリを使っていました。Ruby 3.3ではこのデータ構造を変更し、すべてのノードが必要十分なメモリを使うように改善しました。

Ruby 3.4に向けて

Ruby 3.3ではLramaの導入やノードのデータ構造の改善など、今後のために必要な改善を行いました。Ruby 3.4ではこれらを踏まえた更なる改善を予定しています。

使いやすいパーサを目指して

パーサを利用する人に関係する目標は以下の3つです。

ツールから使いやすいAPIを整備する

歴史的な理由からRubyのASTはコードを効率的に実行することに特化してきました。そのためパーサの内部で最適化のために一部のノードを書き換えたり、場合によってはノードを削除したりします。たとえばRubyのノードにはリテラルを表すNODE_LITと文字列リテラルを表すNODE_STRがありますが、最適化のために一部の文字列リテラルはNODE_LITになったりします。これらの最適化をより後段に移動するとともに、使い勝手のよいインターフェイスを整理していきます。

具体的な目標を挙げると、Ruby 3.4からはparser gemのバックエンドとしてRubyのパーサを使えるようにします。

エラートレラントパーサを提供する

細かい粒度でのエラーリカバリーをすでにLramaに実装していますが、まだ改善の余地があります。Ruby 3.4では高速化とアルゴリズムの改善に取り組みたいと思います。

CRuby以外からも使えるようにする

自分でRuby処理系を作るときや、Ruby以外の言語（たとえばCやC++）などで解析ツールを作る時に、Rubyのパーサがほしくなることがあります。現在のRubyのパーサはGCをはじめとしたRubyの他の機能に強く依存しているため、パーサだけを切り出して使うことはできません。Ruby 3.4ではRuby本体とは独立したパーサの提供を目指します。

理解しやすいパーサを目指して

次にパーサそのものの改善として、以下の2点を考えています。

文法定義を整理する

Lramaのサポートしているitem*やitem?といった記法を利用して、Rubyの文法定義をより読みやすいものにします。またこれら組み込みの記法だけでなく、Ruby開発者が必要に応じて新しいパターンを登録し、それを使えるようにします。

パーサとレキサの状態を統合する

以下のように一見同じに見える%s{a}であっても、場合によって異なるものになるというのがRubyの面白さのひとつだと思います。

# :a　というシンボル
%s{a}

# 1#% メソッドをsという引数とブロックで呼び出している
1 %s{a}

# :a　というシンボルを引数に p メソッドを呼び出している
p %s{a}

これらを実現するためにパーサとレキサは状態を共有し管理しています。このような状態の管理はRubyの構文解析を支える強力な技法なのですが、同時にRubyのパーサの実装を難しくしている原因にもなっています。

現在のRubyではこの状態をC言語のコードで管理しているため、理解するためには丁寧にコードを追わないといけません。Ruby 3.4ではLramaをさらに進化させ文法定義に状態管理を組み込むことで、文法定義を見ただけで状態管理のロジックが把握できるようにしたいと考えています。

Lramaパーサジェネレータの未来

Ruby 3.4のさらに先の未来について最後に少し触れておきます。

パーサとレキサをさらに統合したスキャナレスパーサ

Ruby 3.4ではパーサとレキサの状態を統合することを目標にしていますが、これをさらに進めてパーサとレキサを統合するとどうなるでしょう。たとえば|という文字はRubyの中で複数の意味で使われます。

# || はOR演算子
false || true

# doのあとの||はブロックの引数を囲むための文字
10.times do ||
end

前者では||という記号が1つであり、後者では|という記号が2つだと判定されます。パーサとレキサは状況に応じてこれらを切り替えられるように状態を管理しています。Ruby 3.4ではこれを文法定義の一部としてRuby開発者が指定できるようにする予定ですが、本来この2つは人間が指定しなくても自動で判別可能なはずです。そして、さらにパーサとレキサをさらに統合することで、自動で判別できるところではパーサが自動で判別し、判別がつかないケースでは開発者が指定をすることが可能になるでしょう。

このような試みはPSLR(1)（Pseudo-Scannerless Minimal LR(1)）として研究されています。自動化によって開発者が楽になるというメリット以上に、文法定義をみたときにどの箇所で特殊なことをしているかが明確になるというメリットがあります。

様々な言語で動くRubyのパーサ

真にポータブルなパーサ実装とはどういったものでしょうか。生成されるバイナリを他のツールから使えることではないと私は考えています。ひとつの文法定義からC言語の実装、Rubyの実装、JavaScriptの実装などさまざまな実装が生成できるものこそ、真にポータブルなパーサ実装なのではないでしょうか。

現在のRubyのパーサ実装にはC言語で書かれたロジックがたくさんあります。これらを適切に抽象化し、パーサジェネレータに必要な機能を実装したとき、さまざまな言語で使えるパーサ実装が手に入ります。これには構文解析だけでなく意味解析なども含めたパーサの役割の整理や、その整理に基づいたパーサジェネレータのデザインが必要になります。かんたんなことではないかもしれませんが、とてもチャレンジングなテーマだと思います。

まとめ

Ruby 3.3ではBisonをLramaで置き換えたり、ノードのデータ構造を改良したりと内部的な改善をたくさん行いました。Ruby 3.4ではこれらの改善を踏まえて、みなさんが使いやすいパーサを提供するとともに、パーサ本体をより理解しやすいものにしていきたいと思います。

LRパーサはまだまだこれから発展する可能性を秘めています。ruby-jpのslackに#lr-parserというチャンネルがありますので、RubyのパーサやLRパーサに興味を持った方は是非ともご参加ください。