Node.js dom-parser tagRegExp 正则表达式匹配挂起:灾难性回溯

Question

我正在使用node.js dom-parser，它(不理想地(使用正则表达式从DOM中提取标签。

您可以在以下位置找到 dom-parser：https://github.com/ershov-konst/dom-parser

有时，某些网页(例如 https://www.ecosia.org/(的HTML会导致节点.js应用程序挂起。我已经使用普通的原版匹配脚本进行了测试，发现 tagRegExp 会导致脚本挂起(也许是因为灾难性的回溯？

我实际上正在使用它来查找链接rel="canonical"和href="xyz"(如果有的话，ecosia没有规范(。

标签RegExp：

/(</?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?s*(?:s+[a-z0-9-_]+=(?:(?:'[sS]*?')|(?:"[sS]*?")))*s*/?>)|([^<]|<(?![a-z/]))*/gi

纯JS测试脚本：

<script type="text/javascript">
var text = '... html source ...';
var text_esc = text
text_esc = text_esc.replace(/</g, "&lt;");
text_esc = text_esc.replace(/>/g, "&gt;");
var regex = /(</?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?s*(?:s+[a-z0-9-_]+=(?:(?:'[sS]*?')|(?:"[sS]*?")))*s*/?>)|([^<]|<(?![a-z/]))*/gi;
var found = text.match(regex);
var found_len = found.length;
document.write("Text: " + text_esc + "<br /><br />" + "Regex pattern: " + regex + "<br /><br />");
document.write("Matches: " + found_len + "<br /><br />");
for (var i=0;i<found_len;i++)
{
    found[i] = found[i].replace(/</g, "&lt;");
    found[i] = found[i].replace(/>/g, "&gt;");
    document.write("[" + i + "]: " + found[i] + "<br /><br />");
}
</script>

任何想法都非常欢迎。提前谢谢。

Answer 1

该问题是由[sS]*?模式和低效的(x|[^x])*类模式引起的。

您可以使用

/(</?[a-z][a-z0-9]*(?::[a-z][a-z0-9]*)?s*(?:s+[a-z0-9-_]+=(?:'[^']*'|"[^"]*"))*s*/?>)|[^<]*(?:<(?![a-z/])[^<]*)*/gi

'[sS]*?'变成'[^']*'其中[^']*是一个贪婪量化的否定字符类，匹配除'以外的任何字符，并且"[sS]*?"以相同的方式处理。否定字符类比惰性字符类更好.*?因为它一次性匹配指定字符以外的所有字符，并且正则表达式引擎不必在此模式之后尝试所有后续子模式，然后在每次失败时扩展。

([^<]|<(?![a-z/]))*可以展开为[^<]*(?:<(?![a-z/])[^<]*)*，它将匹配相同的文本但更快(与以前相同，带有贪婪量词的否定字符类模式更快地浏览文本(。

注意 我还删除了几个多余的非捕获组。