シンプルで強力な文法はRubyの特徴のひとつだと言われています。その文法を技術的に支えているのがパーサです。Ruby 3系のひとつの目標として、LSPやRBS、TypeProfをはじめとした各種ツールの拡充があります。それらのツールは多くの場合AST
最新のRuby 3.
パーサジェネレータ ——パーサをどのようにして実装するか
パーサを実装する方法は大きく2つあります。フルスクラッチで実装する方法と、パーサを生成するツールを使って実装する方法です。前者は手書きパーサと呼ばれ、C言語やRubyなどのプログラム言語で実装する方法です。後者はパーサジェネレータというツールを使い、BNF
Rubyは後者の方法を選択しています。以下はRubyのparse.
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
)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.
)[1, 2, 3]
)
list : item
| list ',' item
しかしパターンなのであれば、これをもっと簡潔に書きたいと思うのは自然な考えでしょう。たとえばOCamlのMenhirというパーサジェネレータではseparated_
という書き方ができます。セパレーターが入らない場合、item*
と書くこともできます。こういった文法ファイルを書きやすくする仕組みもRubyで使いたいと思っていました。
これらをBisonに実装しようとしても、BisonはRuby以外にも様々な言語で使われているため、様々な調整や議論が必要になるでしょう。
Lramaによる改善
これらの問題を解決するために、Ruby 3.
新しいBisonでは実装されていたのにもかかわらず使えていなかった機能として、Named Referencesという機能があります。Lramaにこれを実装し、すでにRubyでは使われています。他にもitem*
やitem?
といった記法もサポートをしています。こちらはRuby 3.
特筆すべき機能についてはNEWS.
パーサに関するその他の改善
パーサが生成するASTa = 1
という代入を表すためのノードでは左辺のa
と右辺の1
を保持する必要があります。一方でtrue
を表すノードは付加的な情報を必要としません。いままではすべての種類のノードが同じデータ構造を使っていたため、ノードによっては無駄にメモリを使っていました。Ruby 3.
Ruby 3.4に向けて
Ruby 3.
使いやすいパーサを目指して
パーサを利用する人に関係する目標は以下の3つです。
ツールから使いやすいAPIを整備する
歴史的な理由からRubyのASTはコードを効率的に実行することに特化してきました。そのためパーサの内部で最適化のために一部のノードを書き換えたり、場合によってはノードを削除したりします。たとえばRubyのノードにはリテラルを表すNODE_
と文字列リテラルを表すNODE_
がありますが、最適化のために一部の文字列リテラルはNODE_
になったりします。これらの最適化をより後段に移動するとともに、使い勝手のよいインターフェイスを整理していきます。
具体的な目標を挙げると、Ruby 3.
エラートレラントパーサを提供する
細かい粒度でのエラーリカバリーをすでにLramaに実装していますが、まだ改善の余地があります。Ruby 3.
CRuby以外からも使えるようにする
自分でRuby処理系を作るときや、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.
Lramaパーサジェネレータの未来
Ruby 3.
パーサとレキサをさらに統合したスキャナレスパーサ
Ruby 3.|
という文字はRubyの中で複数の意味で使われます。
# || はOR演算子
false || true
# doのあとの||はブロックの引数を囲むための文字
10.times do ||
end
前者では||
という記号が1つであり、後者では|
という記号が2つだと判定されます。パーサとレキサは状況に応じてこれらを切り替えられるように状態を管理しています。Ruby 3.
このような試みはPSLR(1)
様々な言語で動くRubyのパーサ
真にポータブルなパーサ実装とはどういったものでしょうか。生成されるバイナリを他のツールから使えることではないと私は考えています。ひとつの文法定義からC言語の実装、Rubyの実装、JavaScriptの実装などさまざまな実装が生成できるものこそ、真にポータブルなパーサ実装なのではないでしょうか。
現在のRubyのパーサ実装にはC言語で書かれたロジックがたくさんあります。これらを適切に抽象化し、パーサジェネレータに必要な機能を実装したとき、さまざまな言語で使えるパーサ実装が手に入ります。これには構文解析だけでなく意味解析なども含めたパーサの役割の整理や、その整理に基づいたパーサジェネレータのデザインが必要になります。かんたんなことではないかもしれませんが、とてもチャレンジングなテーマだと思います。
まとめ
Ruby 3.
LRパーサはまだまだこれから発展する可能性を秘めています。ruby-jpのslackに#lr-parser
というチャンネルがありますので、RubyのパーサやLRパーサに興味を持った方は是非ともご参加ください。