NFA→DFA変換
正規表現のマッチング処理を改善するため、ちょこちょこと手を入れていたらある日、急に動かなくなってしまい、
以前の一番正常な状態に戻そうとしたら前にコミットするのをすっかり忘れていて、
マッチング処理だけ一から書き直す羽目になってしまった。
これは書き換えている最中に一部の正規表現だけ動かなくなって、ちょっと書き換えた後、今度は
また別の正規表現がちゃんと動作しなくなり、その2つを直したら今度は普通の文字列にマッチしなくなったりと、
まあ、だんだんぐちゃぐちゃになっていったからなのだが、毎回1つずつ手で入力して
テストしてたせいで見逃していたのが悪かったのだと反省し、以下のような感じでちゃんとテストを書くことにした。
match_test("abc", "abc", args, 1); match_test("abc", "abd", args, 0); match_test("abc", "fabcf", args, 1); match_test("abc", "fababdcf", args, 0); match_test("a|b", "a", args, 1); match_test("a|b", "b", args, 1); match_test("a|b", "c", args, 0);
で、NFAでのマッチングの現状。
bokko@narazuya:regex_engine$ ./regex_engine pattern: abc, str: abc, expect:1, is_match:1, passed pattern: abc, str: abd, expect:0, is_match:0, passed pattern: abc, str: fabcf, expect:1, is_match:1, passed pattern: abc, str: fababdcf, expect:0, is_match:0, passed pattern: a|b, str: a, expect:1, is_match:1, passed pattern: a|b, str: b, expect:1, is_match:1, passed pattern: a|b, str: c, expect:0, is_match:0, passed pattern: ab|cd, str: abd, expect:1, is_match:1, passed pattern: ab|cd, str: acd, expect:1, is_match:1, passed pattern: ab|cd, str: ad, expect:0, is_match:0, passed pattern: ab|cd, str: aqqd, expect:0, is_match:0, passed pattern: ab|cd|ef, str: abdf, expect:1, is_match:1, passed pattern: ab|cod|ef, str: abodf, expect:1, is_match:1, passed pattern: ab|cod|ef, str: abdf, expect:0, is_match:0, passed pattern: abc|def, str: abcef, expect:1, is_match:1, passed pattern: abc|def, str: abdef, expect:1, is_match:1, passed pattern: abc|def, str: abqqqdef, expect:0, is_match:0, passed pattern: a*, str: a, expect:1, is_match:1, passed pattern: a*, str: b, expect:1, is_match:1, passed pattern: a*b, str: b, expect:1, is_match:1, passed pattern: a*b, str: aqqqb, expect:0, is_match:0, passed pattern: abc*def, str: abccdef, expect:1, is_match:1, passed pattern: abc*def, str: abqqqdef, expect:0, is_match:0, passed pattern: abc*def, str: abdef, expect:1, is_match:1, passed pattern: a*b*c, str: c, expect:1, is_match:1, passed pattern: aa*bb*c, str: abc, expect:1, is_match:1, passed pattern: aa*bb*c, str: aaaabbbc, expect:1, is_match:1, passed pattern: aa*bb*c, str: aaacabbb, expect:0, is_match:0, passed pattern: a*b*c*, str: d, expect:1, is_match:1, passed pattern: a*bb*c*, str: d, expect:0, is_match:0, passed pattern: a*b*c, str: d, expect:0, is_match:0, passed num:31, passed:31, failed:0 bokko@narazuya:regex_engine$
やっぱりテスト書くのは重要ですね。
で、本題。NFAからDFAへの変換処理でやってることは実はNFAのマッチング処理とあんまり変わらない。
NFAのマッチング処理では、現在の状態から入力された文字で遷移可能な状態とε遷移で遷移可能な状態を求め、
その求めた状態の集合に対して同じことを繰り返す。最後に状態集合の中に受理状態が含まれていれば、
マッチしたと見なす。NFAからDFAへの変換処理では同じように遷移可能な状態を求めた後、
それをDFAの構造体に突っ込み、あとはそれを繰り返せばいい、と、思って実装してみたのだが、
DFAでのマッチング結果
bokko@narazuya:regex_engine$ ./regex_engine pattern: abc, str: abc, expect:1, is_match:1, passed pattern: abc, str: abd, expect:0, is_match:0, passed pattern: abc, str: fabcf, expect:1, is_match:1, passed pattern: abc, str: fababdcf, expect:0, is_match:0, passed pattern: a|b, str: a, expect:1, is_match:1, passed pattern: a|b, str: b, expect:1, is_match:0, failed pattern: a|b, str: c, expect:0, is_match:0, passed pattern: ab|cd, str: abd, expect:1, is_match:0, failed pattern: ab|cd, str: acd, expect:1, is_match:0, failed pattern: ab|cd, str: ad, expect:0, is_match:0, passed pattern: ab|cd, str: aqqd, expect:0, is_match:0, passed pattern: ab|cd|ef, str: abdf, expect:1, is_match:0, failed pattern: ab|cod|ef, str: abodf, expect:1, is_match:0, failed pattern: ab|cod|ef, str: abdf, expect:0, is_match:0, passed pattern: abc|def, str: abcef, expect:1, is_match:1, passed pattern: abc|def, str: abdef, expect:1, is_match:1, passed pattern: abc|def, str: abqqqdef, expect:0, is_match:0, passed pattern: a*, str: a, expect:1, is_match:1, passed pattern: a*, str: b, expect:1, is_match:1, passed pattern: a*b, str: b, expect:1, is_match:1, passed pattern: a*b, str: aqqqb, expect:0, is_match:1, failed pattern: abc*def, str: abccdef, expect:1, is_match:1, passed pattern: abc*def, str: abqqqdef, expect:0, is_match:0, passed pattern: abc*def, str: abdef, expect:1, is_match:1, passed pattern: a*b*c, str: c, expect:1, is_match:1, passed pattern: aa*bb*c, str: abc, expect:1, is_match:1, passed pattern: aa*bb*c, str: aaaabbbc, expect:1, is_match:1, passed pattern: aa*bb*c, str: aaacabbb, expect:0, is_match:0, passed pattern: a*b*c*, str: d, expect:1, is_match:1, passed pattern: a*bb*c*, str: d, expect:0, is_match:0, passed pattern: a*b*c, str: d, expect:0, is_match:0, passed num:31, passed:25, failed:6 bokko@narazuya:regex_engine
なんか選択回りが特に動いていない。実際の処理では計算した各DFAをリストでつないで、
マッチングさせているのだが、よく考えたらDFAって経路が一つなんじゃなくて、
1つの状態に対して、各文字の経路が1つずつだから原因はその辺かな？
とすると、NFAの構造体にDFAの構造体へのポインタを持たせないといけなくなる。なんだかなあ。
ちなみに仕事では専らSubversionだが、最近、プライベートではMercurialを使っている。
MercurialはCVSやSubversionのようにリポジトリで集中管理するようなのとは違い、
分散型のVCSなのだが、実のところ、分散型の利点は全く活かしていない。
ただ、MercurialはCVSやSubversionのようにいちいちリポジトリを作る必要がなく、
ローカルで動作させることができるので非常に手軽に使うことができる。
svkを使うことも考えたが、ローカルで管理するならこっちの方が使い勝手がいい。
