如何使正则表达式不导致“灾难性的回溯”？

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

您的regex看起来像是要匹配内嵌套了更多平衡对的平衡大括号，但是只有一个层次深。这个正则表达式可以不挂在格式错误的输入上：

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

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

这可能更容易发生灾难性的回溯(嵌套量化符，所有可选的)，但它可以工作，因为它永远不需要回溯，即使不可能匹配。

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

另外，如果您想要将嵌套在未知深度的大括号匹配，那么您就不走运了。有些口味可以做到这一点，但JavaScript太有限了。

Answer 2

如果要选择没有花括号的区域，请尝试使用以下方法：

var temp = "{=rankedArea?metricType=3902&area={parent-area-identifier}:AdministrativeWard} {=rankedArea?metricType=3902&area={parent-area-identifier}:{ward-type-identifier}} {district-short-label}  adfasdfasdfasdf asdf asdf asdf asdf {child-area-short-label}  asdf asdf asdf  {authority-area-short-label} asdfasdfasdfasdf asdf  asdfasdfasdfasdf asdf{=compare?metricType=3343&greater=greater than&equal=equal to&less=less than}  asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=countAreas?area={ancestor-2-identifier}:{ancestor-1-type-identifier}}  asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=equivalent?metricDimension=[218][218_Number][Specificethnicity][Ethnicity_AsianorAsianBritish]}  asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf {=metricTypeMetadata?metricType=3341&returnValue=source}  asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=value?metricType=3284}  asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=percent?metricType=518}  asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=rank?metricType=3287}  asdfasdfasdfasdf asdf asdfasdfasdfasdf asdf{=rankedArea?metricType=3286}  asdfasdfasdfasdf asdf";
var strRegExp = new RegExp(/{(?:[^{}]+|{[^{}]*})*}/g);
var arrMatch = temp.match(strRegExp);
console.log(arrMatch.length);
console.log(arrMatch);

结果：

13
["{=rankedArea?metricType=3902&area={parent-area-identifier}:AdministrativeWard}",
 "{=rankedArea?metricType=3902&area={parent-area-identifier}:{ward-type-identifier}}",
 "{district-short-label}",
 "{child-area-short-label}",
 "{authority-area-short-label}",
 "{=compare?metricType=3343&greater=greater than&equal=equal to&less=less than}",
 "{=countAreas?area={ancestor-2-identifier}:{ancestor-1-type-identifier}}",
 "{=equivalent?metricDimension=[218][218_Number][Specificethnicity][Ethnicity_AsianorAsianBritish]}",
 "{=metricTypeMetadata?metricType=3341&returnValue=source}", "{=value?metricType=3284}",
 "{=percent?metricType=518}",
 "{=rank?metricType=3287}",
 "{=rankedArea?metricType=3286}"]

如果这个算法不正确，请提供更多的测试用例。