正規表現
エンジン設計
ドラゴンブックに忠実なPOSIX-NFA。
理論そのまんま。
プログラムを小さく作ろうとすれば500行程度で完成(6kB)
してしまう。
正規表現エンジンの構造
以下の4つの部分により構成される。
P、プリプロセッサ、正規表現式を有向グラフに変換する。
W、ラッパー、仮想機械に対する操作を関数の形に纏める。
V、仮想機械、入力に応じて複数の状態を変更し状況を示す。
S、状態、仮想機械から複数保持され、ε遷移によって増殖し、停止時に消去される。
実行のシナリオ
以下の4つのステップにより実行される
STEP1：正規表現式の処理
プリプロセッサが正規表現式をグラフ構造に変換し、仮想機械を生成する。
STEP2：仮想機械の初期化
仮想機械が状態を一つだけ生成し、初期状態を設定する。
STEP3：入力および照合の実行
until
仮想機械の保持する状態が0個になるかまたは入力の終了まで
仮想機械に一文字入力する
foreach
保持している状態
遷移可能であるならば遷移先の状態へ変更(S'←(文字)─S)
ε遷移が発生したならば新し
い状態を一つ追加し別の遷移先を設定する
遷移不可能であるならば状態を消去
end
文字数 := 文字数 + 1
受理可能な状態が1個以上ならば文字数を一致した長さとして保存する
end
STEP4:結果の判定
if 一致した長さ=0 then
照合しなかった
式全体が空列生成可能であるならば長さゼロで一致した
else
照合した
end