RubyKaigi 2024 に参加してきた。RegexやParserの話とか。

2024-05-22 01:01

5/15 - 5/17 で沖縄（那覇）で行われた RubyKaigi 2024 に参加してきました。所属している会社（Leaner Technologies）もドリンクアップスポンサーとして協賛しました。

今年は RubyのParser、Profiler、Namespace あたりのトピックが盛り上がってるように思えましたが、個人的には DFA型の正規表現のエンジンを書いてみたいなーと思ったKaigiでした。

Make Your Own Regex Engine!

makenowjust氏によるバックトラック型VMの正規表現エンジンを自作するというセッションです。作って学ぶ正規表現エンジンにも公開されています。

正規表現周りはあまり詳しくなく、あんまり予習もせず🙈 聞いていたのですが、最初の疑問は「バックトラック型とは？正規表現であるなら、決定性有限オートマトンで表現するのが基本ではないのだろうか？」でした。

帰ってからこのへんを調べていたら同氏の去年の発表が見つかりました。セキュリティ関連っぽいと思ってスルーしてしまっていたやつ。（こんなにおもしろい話だったとは）

こちらで、Future Workとして決定性有限オートマトン（DFA）ベースの正規表現エンジンについて語られていました。

DFAベースであれば単純なオートマトンに対する事前最適化が効くので、コンパイルとめっちゃ相性がいいはず？今はYJITがあるぞ！ワンチャン！と思っていたら、2021年にTruffleRuby + JIT の発表がされていました。みんな考えることは同じだ。

このあたりまで調べて、DFA-based Regex engine + JIT (YJIT) でなんかすげぇいいかんじになるんじゃねえの〜？ヒュ〜！な妄想をして勝手にわくわくしています（現在）

ちなみにこの、VM型 => DFA型みたいな流れ機械学習の世界に似ているなぁと思っていて、いま巷で流行ってる LLM、ニューラルネットワークも基礎となる技術はシンプルなオートマトンなんですよね。

一周回って古典的な技術に戻ってくるのにエモさを感じます。

DFA型だと一定の制約が入るので、プッシュダウンオートマトン（PDA）にクラスをあげることで、やれることも増えそうだなあという感想もあります（あんまり理解していないので、適当に言っています）。ただしPDAはアルゴリズムが複雑になるので、シンプルなDFAに保っておいたほうが扱いやすいかも。

そして、PDA というと LR Parser なんですよね。繋がってきましたね。

そういえば昔、PDA ベースのパーサーを手書きして脳が爆発した経験がありました。そのときは、（自然言語処理をトライしていたので）自然言語解析の基礎という本とにらめっこしていました。もっと良い本があったら教えてください。

感想

来年に向けて

それではまた来年、松山でお会いしましょう 👋