javascript - 正则表达式的灾难性回溯问题

Question

我刚开始使用正则表达式，目前正面临着与此相关的问题。

我正在尝试构建一个匹配以下格式字符串的正则表达式:

OptionalStaticText{OptionalStaticText %(Placholder) OptionalStaticText {OptionalSubSection} OptionalStaticText} OptionalStaticText

每个 Section 或 Subsection 由 {...} 表示。每个 Placeholder 由 %(...) 表示。每个 Section 或 Subsection 都可以有 OptionalStaticText、%(Placholder) 和 OptionalSubSection< 的任意排列.

为此，我创建了一个正则表达式，如下所示(也可以看到 here )。

/^(?:(?:(?:[\s\w])*(?:({(?:(?:[\s\w])*[%\(\w\)]+(?:[\s\w])*)+(?:{(?:(?:[\s\w])*[%\(\w\)]+(?:[\s\w])*)+})*})+)(?:[\s\w])*)+)$/g

此表达式完全匹配有效字符串(例如:abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332} } cd 可以在给定的链接中进行测试。

但是，每当输入字符串无效(例如:abc {st1 %(ph1) st11} int {st2 %(ph2) st22}{st3 %(ph3) st33 {st31 %(ph4) st332}} c-d，- 不是 [\s\w] 字符组中的有效字符)。

此类无效字符串通过灾难性回溯导致超时，也可以在上面的链接中进行测试。

我一定是犯了一些菜鸟错误，但不确定是什么。我应该做些什么来避免这种情况？

谢谢。

Answer 1

如果你有超时问题，可能是因为这个 [%\(\w\)]+
这是您要查找的表单中包含的一类字符。

改用表单本身。

^(?:(?:[\s\w]*(?:({(?:[\s\w]*%\(\w*\)[\s\w]* )+(?:{(?:[\s\w]*%\(\w*\)[\s\w]*)+})*})+)[\s\w]*)+) $

Formatted and tested:

 ^ 
 (?:
      (?:
           [\s\w]* 
           (?:
                (                             # (1 start)
                     {
                     (?:
                          [\s\w]* 
                          % \( \w* \) 
                          [\s\w]* 
                     )+
                     (?:
                          {
                          (?:
                               [\s\w]* 
                               % \( \w* \) 
                               [\s\w]* 
                          )+
                          }
                     )*
                     }
                )+                            # (1 end)
           )
           [\s\w]* 
      )+
 )
 $