如何避免正则表达式导致“灾难性回溯”？

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);

- Nic

---

它应该做什么？ - Akxe

在http://regexr.com/上测试过了，似乎正常工作...更新：与示例进行了检查，超时已报告。 - maborg

什么是正确的结果？ - Akxe

在Regexr中，您会看到右上角有一个小框，上面写着“timeout”。这基本上为该表达式设置了一个超时时间。那对我来说很有用。我该如何实现超时？ - Nic

你应该首先不使用 RegExp 构造函数，当你已经有一个正则表达式文本时。 - Bergi

Answer 1

你的正则表达式看起来是用来匹配平衡的大括号，其中有更多嵌套的平衡对，但只有一层深度。这个正则表达式可以在不挂掉错误输入的情况下实现。

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

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

这可能看起来更容易受到灾难性回溯的影响（嵌套量词，所有内容都是可选的），但它之所以有效，是因为即使没有匹配，它也不需要回溯。

顺便说一下，只要看起来你没有试图将大括号作为量词的一部分使用，你就不需要转义大括号。（在某些语言中，你需要转义左括号，但在JavaScript中不需要。）

此外，如果你想匹配未知深度的嵌套括号，那么你就没戏了。有些语言可以处理，但JavaScript太有限了。

- Alan Moore

---

即使这个结构更好，它可能会导致很多“正常”的（即：非灾难性的）回溯，特别是当您在示例字符串的末尾添加内容时（请参见https://regex101.com/r/zW9nG6/1）。您可以使用原子组模拟来防止它：https://regex101.com/r/zW9nG6/2。 - Casimir et Hippolyte

哇！！我认为你做得非常好 :) 它完美地工作，我仍在彻底测试之前标记它作为答案。 - Nic

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}"]

它运行速度快，如果该算法不正确，请提供更多的测试用例。

- Alex Vazhev

---

我已经嵌套了标记。在这种情况下，您的模式将无法工作。请查看此链接：http://regexr.com/3co1m - Nic

Nishit，我已经更新了我的解决方案，现在应该可以工作了。你的正则表达式没问题，你只需要稍微修改一下就行了，请看看我的解决方案，谢谢。 - Alex Vazhev

你的正则表达式现在与 OP 的相同，当输入格式不正确时会出现相同的问题。通过从测试字符串中删除第二个闭合括号（即 :AdministrativeWard 后面的一个），来测试它；我在 RegexBuddy 中得到了一个灾难性的回溯错误。 - Alan Moore

它在regexr上无法工作。是的，我的正则表达式也有同样的问题。 - Nic