エンジン自作を通して理解する正規表現

• 正規表現の恩恵にあずかったことがある人は多い（はず）
• 一方実際に正規表現エンジンを実装したことのある人はそこまで多くない（はず）
• こういった技術を「使用する」ことと「原理を理解する」ことの間には大きな隔たりがある（正規表現に限らず!）

• 正規表現エンジンは正規表現を入力として受け取り，それが与えられた文字列にマッチするかどうかを判定することが主務

「やっていることは言ってしまえばそれだけなのに
なぜエンジンごとに機能の差が?」
→アプローチの仕方の差異

• github.com/lapla-cogito/rustegex
• Rust製
• 3つの実装アプローチ
  • オートマトンベース
  • VMベース
  • 微分ベース
• いずれのアプローチも連接・選択・反復を処理可能でUnicode文字に対応
• パーサーなどは共通のものを書いて使用（→ASTの仕様は同じ）

• 知りたい: 正規表現を等価なオートマトンに変換して，入力文字列を流したときにマッチするか

• （DFAに変換しているので）線形マッチングで速い

• （DFAに変換しているので）バックトラックができない

• （与えられた正規表現をパースしてASTに）
• ASTをThompsonの構成法でNFAに変換
• 得られたNFAを部分集合構成法を使ってDFAに変換$^1$
• 最後に入力文字列を流してDFAをエミュレートしてマッチするか判定

1: 本来はNFAのままでもマッチできますが，やりたかったので高速化を図るためにDFAに変換しています

• 各演算について下のような細かいパーツを考えて，それらをつなぎ合わせれば正規表現を表現する単一のNFAを構築可能（Thompsonの構成法）

a|bを表すNFAの例

• NFAをDFAに変換するためには等価性を保ったまま非決定性を解消する必要がある
• 「各ノードから$\varepsilon$のみで遷移できるノードの集合」を1つのノードとしてみてやればこれが可能（部分集合構成法）

• 知りたい: 正規表現を等価な仮想の命令列に変換して，入力文字列に対してエミュレートしたときにマッチするか

• 拡張するのが容易，バックトラックができる

• ReDoS等のリスク

• （与えられた正規表現をパースしてASTに）
• ASTを順に見ていってVM用の命令列にコンパイル
• 入力文字列を用いて命令列を実行していってマッチするか判定

• 前述の要件を満たすのであれば命令の種類は以下を表すものたちで十分
  • 任意の1文字
  • 分岐
  • プログラムカウンターの移動
  • マッチするか判定する

vec![
    crate::vm::instruction::Instruction::Split(1, 3),
    crate::vm::instruction::Instruction::Char('a'),
    crate::vm::instruction::Instruction::Jmp(4),
    crate::vm::instruction::Instruction::Char('b'),
    crate::vm::instruction::Instruction::Match,
]

• 知りたい: 入力文字列の各文字で正規表現を微分していって，最終的に空文字$\varepsilon$がマッチする表現にできるか

• 実装が（最低要件だけなら）簡単（Rustで100行未満$^1$で実装できた）

• 工夫しないと微分を繰り返した結果の式サイズが爆発しがち

• （与えられた正規表現をパースしてASTに）
• 入力文字列を先頭から見ていって，正規表現をその文字でBrzozowski微分するのを繰り返す
• 最後まで終わった表現に$\varepsilon$が含まれればマッチ，そうでなければマッチしないと判断

1: パーサーの部分などは除外しています

• 正規表現エンジンはいわゆる「コンピューターサイエンス的な概念」と相性が良いケースがある

  • どこにキャッシュを使うと効果的?
  • より効果的なデータ構造は?（ハッシュとかbitsetとか）

• 基本をシュッと実装でき，かつこういった工夫を実装して最適化の効果を割と簡単に見ることができる
  →これができる題材というのは案外少ない

DFAの遷移をキャッシュして超長い文字列をマッチさせたベンチ結果（工夫前との比較）

• 正規表現エンジンを自作することで，その裏にある原理やそれらの差異をある程度理解しながら正規表現を使うことができる
  • どのようなアプローチがあるか
  • それぞれのアプローチの長所・短所
  • どのような工夫ができるか
• それだけでなく，単に日曜大工的な作業の題材としても良いのでおすすめ