正規表現が熱い
前回は、SpiderMonkeyの正規表現実装が直観的でいいんじゃないか、という話だったんだけど、どうも、こいつがあんまり効率が良くなさそうに見える。まあ、別に効率なんてどうでもいいといえばいいんだけど、やっぱり、気持ち悪いので、他に方法が無いかとPythonの正規表現の実装を調べてみた。
と、これが、結構面白い。正規表現をバイトコードに変換して、ちょっとしたVMでパターンマッチを行うというふうになっているのだ。(ひょっとしたら常識かもしれんが)
(あとで見たらgnuのregexもそんな感じの実装になってたんだけど、Pythonのほうが読みやすかったので、先に理解できた。)
Pythonのソースでいうと、Modulesディレクトリ下のregexpr.cがそれ。バイトコードのオペコードは、regexp_compiled_opsにあるんだけど、(多分)重要そうなのが、
- Cexact
- Cjump
- Cstar_jump
- Cfailure_jump
といったところだろうか。
たとえば、"((aa)|(bb))c"をコンパイルすると、
0: failure_jump 4 1: exact 'a' 2: exact 'a' 3: jump 6 4: exact 'b' 5: exact 'b' 6: exact 'c' 7: exact 'c'
と、いったような感じ。
簡単に説明すると、
- exact
- 一文字とマッチ。マッチしなかったらfailureスタックからアドレスを拾ってきてそこへジャンプして文字列位置を戻す。
- jump
- アドレスへジャンプ
- star_jump
- 最適化しなかったらjumpと一緒(と、コメントに書いてあった)
- failure_jump
- failureスタックにアドレスと文字列位置をプッシュ
って感じ。
なるほどなぁ…うまくできてるなあ…って、思った。
(…んんん？これだとexact 'c'で失敗したときに3に戻ってしまうような。もうちょい調べないとな…)
で、'?'とか'*'が文字列の後ろにくるという正規表現の都合上、コンパイル時はひたすら後埋めになってるっていうのが、これまたちょっと面白かったんだけど、そこらへんのおもしろさはちょっと文章ではあらわせないのでパス。
