为什么/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX)需要这么长时间？

Question

我跑的时候

/^(.+)+Q$/.test("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXX")

在Chrome或IE中,完成需要大约10秒钟.(Firefox几乎可以立即对其进行评估.)

为什么需要这么长时间？(为什么Firefox如何能够如此快速地完成它？)

(当然,我从来没有运行过这个特殊的正则表达式,但是我在http://daringfireball.net/2010/07/improved_regex_for_matching_urls上遇到了与URL正则表达式类似的问题,它似乎归结为这个,即那里是某些会导致浏览器锁定的URL

例如:

var re = /\b((?:https?:\/\/|www\d{0,3}[.]|[a-z0-9.\-]+[.][a-z]{2,4}\/)(?:[^\s()<>]+|\(([^\s()<>]+|(\([^\s()<>]+\)))*\))+(?:\(([^\s()<>]+|(\([^\s()<>]+\)))*\)|[^\s`!()\[\]{};:'".,<>?«»“”‘’]))/i;
re.test("http://google.com/?q=(AAAAAAAAAAAAAAAAAAAAAAAAAAAAA")

Answer 1

如thg435所示,这听起来像是灾难性的回溯.有一篇很好的文章,正则表达式匹配可以简单快速.

它描述了一种称为Thompson NFA的有效方法.但是,如上所述,这并不支持现代正则表达式的所有功能.例如,它无法进行反向引用.但是,正如文章中所建议的那样:

"即便如此,对于大多数正则表达式使用Thompson的NFA模拟是合理的,并且只在需要时才进行回溯.一个特别聪明的实现可以将两者结合起来,仅仅为了适应反向引用而进行回溯."

我怀疑Firefox可能会这样做.