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

当我在铬或IE运行

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

，它需要约10秒内完成。（Firefox几乎可以立即评估它。）

为什么需要这么长时间？（为什么/如何Firefox能够这么做呢？）

（当然，我从来没有运行这个特定的正则表达式，但我遇到了类似的问题，与URL正则表达式在http://daringfireball.net/2010/07/improved_regex_for_matching_urls，它似乎归结到这一点，也就是，这将导致浏览器锁定某些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")

来源

2012-04-18 David Ingersol

+11

http://www.regular-expressions.info/catastrophic.html – georg 2012-04-18 21:28:57

一个原因可能是它做了很多回溯。这并不能解释为什么Firefox更快。也许他们有一些额外的优化。如果你想了解更多关于正则表达式引擎的内部工作原理，我建议阅读http://shop.oreilly.com/product/9780596528126.do – 2012-04-18 21:29:05

@thg发布这个答案，请 – 2012-04-18 21:30:50

正如thg435指出，这听起来像灾难性的反跟踪。有一篇关于此的优秀文章，Regular Expression Matching Can Be Simple And Fast。

它描述了一种称为Thompson NFA的有效方法。但是，如前所述，这并不支持现代正则表达式的所有特征。例如，它不能做反向引用。然而，所建议的文章：

“即便如此，这将是合理使用Thompson的NFA模拟大多数正则表达式，只有带出回溯当它是需要一个特别聪明的实现可以结合两个，诉诸回溯只适应反向引用。“

我怀疑Firefox可能会这样做。

来源

2012-04-18 21:29:58

如果他在评论中说，不应该把它作为answeR发布吗？ – 2012-04-18 21:30:43

@Martin。，我正在提供一个完全不同的文章。我从来没有说过他不应该回答。 – 2012-04-18 21:31:06

好吧，您在发布链接之前发布了答案 – 2012-04-18 21:32:11

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

回答

相关问题