iOSDC Japan 2023
採択
2023/09/02 16:15〜
Track D
レギュラートーク（20分）
正規表現を"微分"する!?爆速で自作できる正規表現エンジン
ta_ka_tsu
ta_ka_tsu
昨年の「正規表現って結局何なのさ？〜エンジニアのためのコンピューターサイエンス入門〜」では主に理論の面から正規表現が何なのか話をさせて頂きました。
対して今年は実際に正規表現エンジンの実装に関する話をします。
正規表現エンジンの実装ではオートマトン型と仮想マシン型が主流です。
前者は正規表現から決定性有限オートマトンを、後者は、正規表現をバイトコードにコンパイルし仮想マシンを作成する方法です。
いずれの方法でも正規表現からオートマトンや仮想マシンを生成しなければならず、その実装はそれなりに大変です。
しかし正規表現が文字列にマッチするかどうかの判定であれば正規表現を"微分"するという方法があるのです。
本セッションではその原理と簡易的な実装を紹介します。
またオートマトン型、VM型との比較も可能な限りお伝えします。