perlって正規表現は常にNFAで扱うんだっけ？

はてブをウォッチしていてこんな話をみつけた。

http://qootas.org/blog/archives/2006/06/perl_regex_perf.html

来日してる US の TypePad エンジニア Garth と話をしているときにでてきた正規表現の話。

$char =~ m/\p{Han}|\p{Hiragana}|\p{Katakana}/; #NG
$char =~ m/[\p{Han}\p{Hiragana}\p{Katakana}]/; #OK

return if $char =~ m/abc|def|ghi/; #NG
return if ($char =~ m/abc/ or $char =~ m/def/ or $char =~ m/ghi/); #OK

"|"(パイプ)を使った正規表現はめちゃくちゃ遅いから使わないように、ということです。確かにベンチマークを取ると32倍速いです。

あと、こっちで、なんか続きがあるっぽい
http://d.hatena.ne.jp/fbis/20060615/1150333992
うーん｜が遅くなるのってNFA特有の話ですよねぇ。
perlって常にNFAなんでしたっけ？

記憶では後方参照とかない単純なやつはDFAに落としてくれるとなっていたのだが、どこと混線したのだろう・・・
GNU grepあたり？






おまえは何をいっているんだ？ ランキング！