Tclの正規表現は最速

>> id:syd_syd:20080209:p3

その話は、詳説 正規表現 第2版で読んだことがあります。

曰く、

• 正規表現エンジンにはDFA型とNFA型がある
• DFA型は高速だが能力が低い。NFA型は低速だが能力が高い。たしかDFAはキャプチャができなかった気がする
• でも、TclのエンジンはDFAなみの速度とNFAなみの能力を持った「究極の」正規表現エンジンだ

といった話だったはずです。

でもどう高速化しているかは知らないです。