asin:4873113598
詳説 正規表現 第3版
Jeffrey Friedl
株式会社ロングテール / 長尾高弘訳
[原著:Mastering Regular Expressions (3rd Ed.)]
夏の正規表現祭りで一つ大事なことを言い忘れていたのは猛暑のせいにしておこう。

それは、タイトルどおり、/dan|dankogai/と/dankogai|dan/が違うということ。

Perl 5.12

use 5.012;
say ( "dankogai" =~ /(dan|dankogai)/ );
say ( "dankogai" =~ /(dankogai|dan)/ );

JavaScript (SpiderMonkey 1.7 node.js)

"dankogai".match(/(dan|dankogai)/);
console.log(RegExp.$1);
"dankogai".match(/(dankogai|dan)/);
console.log(RegExp.$1);

Ruby 1.9

"dankogai".match(/(dan|dankogai)/){ |m| p m }
"dankogai".match(/(dankogai|dan)/){ |m| p m }

どちらも/dan(?:kogai)?/と等価と思いきや、大間違い。/dankogai|dan/はそうだけど、/dan|dankogai/はただの/dan/と等価。

そうなるのは、 alteration の実装に原因がある。単純なリニアサーチの上、一致したところで探索を打ち切ってしまうのだ。

TRIE Optmizationの入ったPerl 5.9以降であれば一致するかと思ったら、そんなことはありませんでしたorz。

というわけで、よい子はRegexp::Assembleを使いましょうということなのだけど、他の言語で正規表現しているひとたちはどうしているのだろう…

Dan the (Irr|R)egular Expressionist