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个空格结尾的情况。首先，将它们与.交替项左侧的匹配。失败是因为没有结束标记，因此它尝试将最后一个字符与\s代替匹配。这也失败了，因此它尝试将倒数第二个空格作为a匹配最后\s一个空格作为a
.。失败（仍然没有结束标记），因此它将最后一个空格作为尝试\s。如果失败，则将倒数第二个空格与a
\s匹配，并尝试所有4种方式来匹配最后两个空格。如果失败，它将尝试倒数第二个空格作为\s以及最后3个空格的所有8种方式。然后是16、32等。宇宙在到达倒数第100个空间之前就结束了。

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

使用非贪婪*可以完成您想要的操作（您要在第一个</tag:main>而不是最后一个位置停止），但是对于缺少终止序列的长字符串空间仍然会发生灾难性的回溯。

确保内括号中的相同字符不能与交替符的两边都匹配，可以将问题从指数形式的一个减少到一个在字符串长度上线性的问题。使用字符类代替替代字符，或将其\n放在替代条的右侧。
\n是不相交的，.因此如果您遇到了较长的空格序列，则regexp引擎在终止之前不会尝试所有左右，左，右等组合。