javascript - 如何使正则表达式不导致 “catastrophic backtracking” ？

Question

当我尝试在 javascript 中运行以下代码时，浏览器由于灾难性的回溯而挂起，回溯无限循环可能是因为设计不当的正则表达式。我需要一个替代表达式或一种方法来防止这个问题:

string temp = "Testing robustness {parent-area-identifier Some text in between the tokens {parent-area-label}";
var strRegExp = new RegExp(/[{](?:[^{}]+|[{][^{}]*[}])*[}]/g);
var arrMatch = temp.match(strRegExp);

Answer 1

你的正则表达式看起来像是要匹配平衡括号，其中嵌套了更多平衡对，但只有一层深。这个正则表达式不会卡在格式错误的输入上:

{[^{}]*(?:{[^{}]*}[^{}]*)*}

这是 Jeffrey Friedl's 的示例展开循环技术。当第一个 [^{}]* 用完非大括号字符时，下一部分会尝试匹配一个简单的、非嵌套的大括号对，然后返回寻找非大括号。该部分被循环以允许多个嵌套大括号对(但都在同一级别)。

这似乎更容易受到灾难性回溯(嵌套量词，一切都是可选的)的影响，但它确实有效，因为它永远不必回溯，即使在不可能匹配的情况下也是如此。

顺便说一句，只要看起来不像是在尝试将大括号用作量词的一部分，就不需要转义大括号。 (在某些风格中，您需要转义左大括号，但 JavaScript 不需要。)

另外，如果你想匹配嵌套到未知深度的大括号，那你就不走运了。有些风格可以做到这一点，但 JavaScript 的局限性太大了。