はじめに
松山にて4/16(水)から4/18(金)にかけて行われたRubyKaigi 2025に行ってきました。RubyKaigiへの参加は昨年に続き2回目です。
今回のRubyKaigiでは、パーサーや文法構造についてのセッションを中心に聞いていました。最初からそうしようと決めていたわけではないのですが、1日目の基調講演の次にパーサーとオートマトンの話を聞いて少し興味を持ったので、その後はそれに近いテーマのセッションを選ぶようにしたという感じでした。
そのきっかけとなったセッションについて、理解したことをまとめてみようと思います。
（もともとこの記事は社内向けに書いたものなのですが、せっかくなので公開してみます。）
Make Parsers Compatible Using Automata Learning（オートマトン理論を用いてパーサーの互換性を実現する）
このセッションの主な内容は、オートマトン理論を活用して、parse.yとPrismの互換性の問題を発見した、というものです。
parse.yは以前Rubyのデフォルトとして使用されていたパーサーで、PrismはRuby3.4から新しくデフォルトになったパーサーです。
スライドはこちら↓
オートマトンとは
オートマトンは、入力に従って状態が遷移するという抽象的な計算モデルです。
この例だと${q_0}$が初期状態（スタート）で、二重丸で囲まれた${q_1}$が受理状態（定められた条件を満たしているということで終わり）です。
矢印の上に数字が書いてありますが、これが入力です。その数字を読み込んだら矢印の方向に遷移するという意味になります。これは例なので使用している入力文字の集合が{0, 1}という簡易的なものになっていますが、実際のパーサーでは数字・文字・記号などもっといろいろな入力を受けつけるはずです。
このオートマトンは/0*1(0*10*1)*/という入力が来たときに受理されます。これは正規表現で、マッチする文字列としては
- 1
- 01
- 1011
- 100101
- 0010011
などがあります。
オートマトンの演算
AND（論理積）のオートマトンは、2つのオートマトンそれぞれで入力が受理される場合にのみ受理状態となるように構成したオートマトンのことを言うようです。上のスライドのオートマトンも、一つひとつ状態遷移を辿っていくと実際に等価であることがわかると思います。
| A | B | AND |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
次にXOR（排他的論理和）ですが、これは以下の通り、どちらか一方のみが真の時に真を返す演算です。
| A | B | XOR |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
このXORのオートマトンは、どちらか一方のオートマトンのみが受理する入力を受けた時に受理状態となるよう構成されたオートマトンのことを言うようです。今回のお話ではこのXORが重要とのことでした。
オートマトン学習
まず、parse.y、Prismのそれぞれのパーサーに対応するオートマトンを生成し、その2つのXORが空だった場合＝どちらか一方だけが受理するような文字列がない場合、両パーサーには互換性があると言える、という前提から出発します。
ではその「それぞれのパーサーに対応するオートマトン」をどうやって得るのか？というと、オートマトン学習という手法を用いるそうです。
これにはAngluinのL* 1というオートマトン学習用のアルゴリズムを使います。
ただ、AngluinのL*は正規言語用のアルゴリズムである一方、Rubyは正規言語の範疇にはおさまらず、文脈自由文法もしくはより広い文法クラスに入る可能性もあるとのことでした 2。そのためRubyはL*で学習することができません。
そこでどうするかというと、VPA（Visibly Pushdown Automata） 3というものを使います。
そもそもプッシュダウンオートマトンとはスタックを利用できるようなオートマトンのことを言い、このうちスタックのpushやpopのタイミングが入力によって決定されるプッシュダウンオートマトンを、VPA（Visibly Pushdown Automata）と呼ぶようです 4。そして、そのVPAによって認識される言語のことを、VPL（Visibly Pushdown Languages）と言います。
VPLは文脈自由言語に含まれ、Rubyの文法全部をカバーできるわけではないものの、正規言語よりはよいとのことでした。
互換性の問題を発見
VPAを学習するにあたり、Rubyの構文規則全体に対応するオートマトンを学習するのは難しいので、使えるトークンを"a", :, (, )の4種類に絞ったとのことでした。
そして実際にそのVPAを得ると、parse.yの状態は6つ、Prismは9つとなりました。
両者のXORが空であれば両パーサーには互換性があるということになりますが、実際にXORを取ってみたところ空ではなく、'("a":)'という反例があったそうです※。
この文字列は本来文法エラーとなるもので、実際にparse.yではエラーになりますが、Prismでは正常な文法として判断されてしまっていました。
つまり、parse.yとPrismの間に互換性の問題があったということになります。
※以下のようにバグが修正される前後のRubyバージョンを指定してruby --parser=prism -e 'x = ("a":); p x'を実行すると、修正前は文法エラーを検知できずに正常な文法として受理してしまっているのに対し、修正後はエラーを検知するようになっています。
# 修正前
$ rbenv local 3.3.8
$ rbenv exec ruby --version
ruby 3.3.8 (2025-04-09 revision b200bad6cd) [arm64-darwin23]
# パーサーとしてPrismを指定すると問題なく通ってしまう
$ rbenv exec ruby --parser=prism -e 'x = ("a":); p x'
ruby: warning: The compiler based on the Prism parser is currently experimental and compatibility with the compiler based on parse.y is not yet complete. Please report any issues you find on the `ruby/prism` issue tracker.
:a
# パーサーとしてparse.yを指定するとsyntax errorになる
$ rbenv exec ruby --parser=parse.y -e 'x = ("a":); p x'
-e:1: syntax error, unexpected tLABEL_END, expecting literal content or terminator or tSTRING_DBEG or tSTRING_DVAR
x = ("a":); p x
# 修正後
$ rbenv local 3.4.1
$ rbenv exec ruby --version
ruby 3.4.1 (2024-12-25 revision 48d4efcb85) +PRISM [arm64-darwin23]
# Prismでもsyntax errorが出る
$ rbenv exec ruby --parser=prism -e 'x = ("a":); p x'
-e: -e:1: syntax error found (SyntaxError)
> 1 | x = ("a":); p x
| ^~~~ unexpected label
https://github.com/makenowjust/lernen 5
今後
将来的にはパーサー全体を推測することを目指しているそうですが、L*の計算量が多すぎること、そしてRubyの文法が複雑すぎることから、かなり難しいそうです。
また、パーサー同士の完全な互換性の実現は現在の科学技術では難しいとのことでした。
（スライドではLargeとComplexの他にOutputの課題についても触れられていますが、どういうことだったかメモがなくわかりません…）
おわりに
大学時代にわけもわからず描かされていたオートマトンがこんなところで出てくるのかと思いました（去年のRubyKaigiでも出てきていたはずですが）。当時はオートマトンやパーサーについて習ったところでその先になにがあるのか見えていなかったので、大学時代にこういう話を聞いていればもう少しモチベが上がったのかもなぁとか思いました。
このセッションに関しては理解が及ばないところも多々あるのですが、自分なりに一通りの流れをまとめてみました。間違いやわかりにくいところなどありましたらご指摘お願いします！