javascript - 为什么/^(.+)+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 所指出的，这听起来像是灾难性的回溯。有一篇关于此的优秀文章，Regular Expression Matching Can Be Simple And Fast .

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

"Even so, it would be reasonable to use Thompson's NFA simulation for most regular expressions, and only bring out backtracking when it is needed. A particularly clever implementation could combine the two, resorting to backtracking only to accommodate the backreferences."

我怀疑 Firefox 可能会这样做。