Let's start Scheme

2011-12-19

ハイブリッドVM(正規表現)

正規表現を書き書き直している最中、RE1とRE2を参考にしたPikeVMでは肯定先読み系はおろかpossessiveマッチさえも実装が困難だということに気づいた。
そこでとりあえず普通に再帰を使って書いてみたら恐ろしく遅かった。
どうしたらいいかなぁと電車の中で考えていたら、「ハイブリッドにしちまえよ」という悪魔のささやきが聞こえたのでやってみた。

どうしたか?
拡張正規表現(ここでは上記の2つ+バックリファレンスを指します)を除いた単純な正規表現のみで記述されたパターンはPikeVMで動かし、えらいごてごてした正規表現は再帰を使ったVMで動かしてみた。
これやるとおそらくpossessiveマッチで書いた方が遅いという不思議現象が起きるがそれは置いておいて、後読み(と後方参照もかな?)を除いた210個の単体テストが通った。遅いVMだと異常に実装が楽だったが、涙が出るほど遅く、PikeVMでは速いけどバックトラック系の処理が書けないというジレンマをまぁ使えそうかなぁと思える程度には解消した気がする。
(それでもJavaから移植したコードの方がまだ多少速い・・・まぁ最適化ほとんどしてないからある意味当たり前なんだけど)

後は後読みと細かいフラグの部分を実装して、APIを実装したら一応完成か。クリスマスまでに間に合うだろうか?

No comments:

Post a Comment