RubyKaigi 2025 Day1 参加記 ──オートマトン学習によるRubyパーサーの検証

こんにちは！タレントマネジメントプロダクト開発本部の horiyu です。

SmartHRはRubyKaigi 2025に「Scheduler and Drinkup Sponsor」として協賛しています。「松山で会い鯛！」をテーマに、事前勉強会やDrinkup、スケジュールアプリの提供など様々な企画で参加しています。詳しくはSmartHR Tech Blogの記事をご覧ください！

本記事では、RubyKaigi 2025のHiroya Fujinamiさん（@makenowjust）の発表「Make Parsers Compatible Using Automata Learning」の感想を述べます。

Fujinamiさんの発表では、プログラムの振る舞いを数学的に学習・解析する「オートマトン学習」のアルゴリズムを用いてRubyパーサーの互換性問題を発見する方法について学べました。特に、Rubyのパーサーに興味がある方やオートマトン理論を知りたい方に役立つ内容でした。

発表スライドも共有されていますので、併せてご覧ください。
Make Parsers Compatible Using Automata Learning

Rubyに存在する2つのパーサーとその違い

Rubyには現在2つのパーサーが実装されています。

parse.y: 従来から利用されているRubyパーサーを生成するための文法ファイル。当初はRubyのパーサージェネレーターはyacc（bison）ベースで構築されていましたが、最近ではRuby製のパーサージェネレータであるLramaに置き換えられました。parse.yを用いてパーサーが生成されます。
Prism: C言語で書かれた新しい手書きパーサー。Ruby 3.4以降のデフォルトになりました。

これらのパーサーは --parser=prism などのオプションで切り替え可能です、

互換性問題の事例 - オートマトン学習による発見

Fujinamiさんは、オートマトン学習を用いて2つのRubyパーサー間の互換性問題を特定しました。具体的には、'("a":)' という文字列が両者で異なる挙動を示すことを発見しました。

この問題は以下のIssueで報告され、現在は解決しています。

Prism accepts ("a":) as a symbol literal with parenthese, but Ruby rejects it · Issue #3035 · ruby/prism

発見された非互換性は次の通りです：

$ ruby --parser=prism -e 'x = ("a":); p x'
:a

Prism: '("a":)' というコードを、括弧付きのシンボルリテラル :a として受け入れる
parse.y: 同じコードを構文エラーとして拒否する

なぜオートマトン理論を選ばれたのか？

発表では、この互換性問題を検証する上で、まず考えられる一般的なアプローチについて触れられていました。

例えば、多くのユニットテストを書くこと、実際の gem を使ってテストすること、あるいはファジングを行うことなどです。

しかし、Fujinamiさんは発表の中で、これらの手法には限界があると話されていました。それは、これらのテストが決して網羅的 (exhaustive) ではないためです。

この「網羅性」の課題に対応するため、発表ではオートマトン理論を用いたアプローチが提案されました。

オートマトン理論 - 文字列パターンを数学的に表現する手法

Fujinamiさんはどのようにオートマトン学習を利用してこの問題を発見したのでしょうか。まずはオートマトン理論の基本を見てみましょう。

オートマトンとは、コンピュータにおける状態や遷移を表現するための数学的なモデルです。特定の文字列の集合を数学的に表現することにも使えます。

Automaton = regular expression — a set of strings

オートマトン理論を用いることで、特定の文字列の集まりを扱い、それらに対して共通部分を求めたり、合併させたり、一方にしかない部分を取り出したりといった操作が計算によって行えます。

AngluinのL*アルゴリズム - 質問を通じて学習する手法

オートマトンを効率的に学習し、作成するための代表的な手法として、Dana Angluinさんが提案したL*アルゴリズムがあります。このアルゴリズムは、システムに質問（クエリ）を投げかけることで学習を進めます。

L*アルゴリズムでは、以下の2種類のクエリを使用するそうです。

Membership query(MQ): 「この文字列は受理される？」という質問
Equivalence query(EQ): 「学習したオートマトンは実際のものと同じか？」という検証

パーサー自体が「教師」となり、これらの質問に答えることでオートマトンが学習されます。Fujinamiさんはこれを「Akinator（アキネーター）」のように質問を重ねて学習する手法と例えています。

Rubyの複雑な文法へのアプローチ

Rubyの文法は非常に複雑であり、一般的なオートマトンでは完全にモデル化できません。そこで、Visibly Pushdown Automaton (VPA) というオートマトンの拡張が必要になります。VPAは括弧や構文のネストをうまく扱える特性を持っています。

Lernen - オートマトン学習を実現するRubyライブラリ

Fujinamiさんは、オートマトン学習を実装した「Lernen」というRubyライブラリを開発しました。このライブラリは、一般的なオートマトンだけでなく、VPAやSPA（System of Procedural Automata）といった非正規言語も扱えます。

Also, this library supports inferring an automaton accepting a non-regular language, namely VPA (visibly pushdown automaton) and SPA (system of procedural automata).

github.com

Lernenの使用例：

automaton = Lernen.learn(alphabet: [0, 1]) do |word|
  word.count(1) % 2 == 0
end

このライブラリを用いて、前述の非互換性を発見することができたそうです！

実際にLernenを使ってみる - シンプルな例から

Lernenをインストールして簡単な例で試してみましょう。

$ gem install lernen
Successfully installed lernen-0.3.0
1 gem installed

「a」を含む文字列を識別するオートマトンの学習

「a」が少なくとも1つ含まれる文字列を受理するオートマトンを学習させる例です。

#!/usr/bin/env ruby
require 'lernen'

alphabet = ['a', 'b']

automaton = Lernen.learn(alphabet: alphabet) do |word|
  word.include?('a')
end

puts "Number of states: #{automaton.states.size}"
puts "Accepting states: #{automaton.accept_state_set.inspect}"
puts "Initial state: #{automaton.initial_state}"

puts automaton.to_mermaid

['', 'a', 'ab', 'ba', 'b'].each do |s|
  input = s.chars
  final_state = automaton.run(input)
  is_accepted = automaton.accept_state_set.include?(final_state[1])
  result = is_accepted ? "accept" : "reject"
  puts "String '#{s}': #{result}"
end

実行結果：

Number of states: 2
Accepting states: #<Set: {1}>
Initial state: 0

flowchart TD
  0(("0"))
  1((("1")))

  0 -- "a" --> 1
  0 -- "b" --> 0
  1 -- "a" --> 1
  1 -- "b" --> 1

String '': reject
String 'a': accept
String 'ab': accept
String 'ba': accept
String 'b': reject
=> ["", "a", "ab", "ba", "b"]

学習されたオートマトンは2つの状態からなるシンプルな構造です：