11

当我跑

/^(.+)+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")
4

1 回答 1

8

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

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

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

我怀疑 Firefox 可能正在这样做。

于 2012-04-18T21:29:58.690 回答