正規表現エンジン設計(遅延評価DFA)
正規表現エンジン(遅延評価DFA)の構造
ベースであるPOSIX-NFAの設計サンプルにおける、仮想機械の実行シナリオSTEP3の各サイクルと
レッドドラゴンブックの3.9章の図3.39の(b)を比較して見れば分かるように、
NFAを縦型ではなく横型探索すると、その過程の副産物としてDFAの遷移表の断片が生成される。
これをキャッシュし、再利用することにより、
エンジンはまずNFAとして動作し、繰り返しが起きた時にDFAに動作を切り替える。
利点：
手数が多いので条件の良い場合のピーク性能は望めないが悪化もしにくい。
表が断片として生成され、歯抜けのまま扱われるため、
テーブルサイズの圧縮が効く...したがって文字コードの制約がない。
欠点：
キャッシュに当てるためには保持する状態の重複を許せないので
個々の遷移の追跡が不可能になる。
つまりバックリファレンスの機能を捨てざるを得ない。(すれ住民の指摘により誤字修正( ´ー｀)ノ )
以下の5つの部分により構成される。
(赤くしてある部分が追加される部分の肝)
P、プリプロセッサ、正規表現式を有向グラフに変換する。
W、ラッパー、仮想機械に対する操作を関数の形に纏める。
V、仮想機械、入力に応じて複数の状態を変更し状況を示す。
C、キャッシュコントローラー、Vが構成した状態遷移表の断片をキャッシュし再利用する
S、状態、仮想機械から複数保持され、ε遷移によって増殖し、停止時に消去される。
実行のシナリオ
シナリオではNFAエンジンのSTEP3に処理が追加される。
以下の4つのステップにより実行される
STEP1：正規表現式の処理
プリプロセッサが正規表現式をグラフ構造に変換し、仮想機械を生成する。
STEP2：仮想機械の初期化
仮想機械が状態を一つだけ生成し、初期状態を設定する。
中身が空の状態遷移表Dtransを生成する。
(表は疎となるのでハッシュなどが望ましい)
STEP3：入力および照合の実行
until
仮想機械の保持する状態が0個になるかまたは入力の終了まで
仮想機械に一文字入力する
保持している状態Sの集合をDとする。
if Dtrans[D, 文字]が空欄であれば then
foreach Dの各要素S
遷移可能であるならば遷移先の状態へ変更(S'←(文字)─S)
ε遷移が発生したならば新し
い状態を一つ追加し別の遷移先を設定する
遷移不可能であるならば状態を消去
end
Dtrans[D, 文字]←D'
else
D'←Dtrans[D, 文字]
end
文字数 := 文字数 + 1
受理可能な状態が1個以上ならば文字数を一致した長さとして保存する
end
STEP4:結果の判定
if 一致した長さ=0 then
照合しなかった
式全体が空列生成可能であるならば長さゼロで一致した
else
照合した
end