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

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的展开循环技术的一个例子.当第一个[^{}]*用完非支撑字符时,下一部分会尝试匹配一个简单的非嵌套支撑对,然后返回寻找非支撑.该部分循环以允许多个嵌套的括号对(但都在同一级别).

这可能看起来更容易受到灾难性回溯(嵌套量词,一切可选)的影响,但它的工作原理是因为即使不可能匹配也无需回溯.

顺便说一句,只要看起来你不想将它们用作量词的一部分,你就不需要逃避括号.(在某些版本中你需要逃避左括号,但不是JavaScript.)

此外,如果你想匹配嵌套到未知深度的大括号,那你就不走运了.有些风格可以管理,但JavaScript太有限了.