javascript - Javascript 正则表达式挂起（使用 v8）

Question

我使用这个正则表达式来获取文件中标签的内容。

var regex = new RegExp("<tag:main>((?:.|\\s)*)</tag:main>");

这会导致 v8 引擎无限期挂起。

现在，如果我使用new RegExp("<tag:main>([\s\S]*)</tag:main>")，一切都很好。

任何人都知道为什么第一个需要太长时间？

Answer 1

</tag:main>这灾难性地回溯到最后一个结束标记之后出现的长空格序列。考虑主题字符串以 100 个空格结尾的情况。首先，它将它们全部与.交替左侧的 匹配。失败是因为没有结束标签，所以它尝试将最后一个字符与 the 匹配\s。这也失败了，因此它尝试将倒数第二个空格匹配为 a\s并将最后一个空格匹配为 a .。这失败了（仍然没有结束标签），所以它尝试最后一个空格作为\s. 当失败时，它将倒数第三个空格匹配为 a\s并尝试所有 4 种方法来匹配最后两个空格。当失败时，它会尝试倒数第四个空间作为\s以及最后 3 个空格的所有 8 种方式。然后是 16、32 等。宇宙在到达倒数第 100 个空间之前就结束了。

由于灾难性的回溯，不同的虚拟机对正则表达式匹配有不同的反应。有些人会简单地报告“不匹配”。在 V8 中，这就像编写任何其他无限或接近无限的循环一样。

使用 non-greedy*会做你想做的事（你想停在第一个</tag:main>，而不是最后一个），但仍然会对缺少关闭序列的长空格字符串进行灾难性的回溯。

确保内括号中的相同字符不能匹配交替的两侧，这将把问题从指数的一减少到字符串长度的线性问题。使用字符类而不是交替或放在\n交替栏的右侧。 \n是不相交的，.因此如果您遇到一长串空格，则正则表达式引擎在终止之前不会尝试所有左右组合。

Answer 2

我认为这是灾难性的回溯。

我认为问题的一部分很可能是点和 \s 不是相互排斥的。

如果我把你的表情改成

<tag:main>((?:.|[\r\n])*)</tag:main>

并在 Regex Buddy 调试器中运行它，如果测试字符串不匹配，它会更快地失败。

Answer 3

代替(?:.|\s)*，您可以[^]*用来匹配任何字符，包括各种形式的换行符。

没有交替，因此没有灾难性回溯的风险。