正则表达式超时

Question

正则表达式超时

4

我正在尝试匹配类似以下内容的东西：

foo: anything after the colon can be matched with (.*)+
foo.bar1.BAZ: balh5317{}({}(

这是我使用的正则表达式：

/^((?:(?:(?:[A-Za-z_]+)(?:[0-9]+)?)+[\.]?)+)(?:\s)?(?:\:)(?:\s)?((?:.*)+)$/

抱歉非匹配组和多余的括号，这是从生成器类编译的。

这对于例子来说很有效。问题出现在我尝试输入像这样的字符串时：

foo.bar.baz.beef.stew.ect.and.forward

我需要能够检查这样的字符串，但是正则表达式引擎在每次遇到一定数量的foo.后就会超时或无限运行（据我所知）。

我相信这是一个逻辑问题，可惜我远未掌握正则表达式，希望有经验的用户能够为我指点如何更高效地匹配。

此外，以下是我需要匹配的更详细描述:

Property Name: can contain A-z, numbers, and underscores but can't start with a number

<Property Name>.<Property Name>.<Prop...:<Anything after the colon>

感谢您的时间！

- Sam DeSota

当我试图从头开始编写时，我想到了\b((?:[A-Za-z_][A-Za-z_0-9]*\.?)*[A-Za-z_][A-Za-z_0-9]*):(.+)这个正则表达式，它可以工作，但几乎与你的正则表达式相同...在http://regex101.com上，这个正则表达式没有发生无限循环。但是，我可以确认你的正则表达式会超时！ - Sebastian Simon

好的，显然如果去掉那些 ^ 和 $ 标记并设置 g 标志，它就可以工作。 - Sebastian Simon

1

我认为这很相关：灾难性回溯。 - Sebastian Simon

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Regular Jo · Accepted Answer

从你的正则表达式开始：

^((?:(?:(?:[A-Za-z_]+)(?:[0-9]+)?)+[\.]?)+)(?:\s)?(?:\:)(?:\s)?((?:.*)+)$


 ^                                  # Anchors to the beginning to the string.
 (                                  # Opens CG1
     (?:                            # Opens NCG
         (?:                        # Opens NCG
             (?:                    # Opens NCG
                 [A-Za-z_]+         # Character class (any of the characters within)
             )                      # Closes NCG
             (?:                    # Opens NCG
                 [0-9]+             # Character class (any of the characters within)
             )?                     # Closes NCG
         )+                         # Closes NCG
         [\.]?                      # Character class (any of the characters within)
     )+                             # Closes NCG
 )                                  # Closes CG1
 (?:                                # Opens NCG
     \s                             # Token: \s (white space)
 )?                                 # Closes NCG
 (?:                                # Opens NCG
     \:                             # Literal :
 )                                  # Closes NCG
 (?:                                # Opens NCG
     \s                             # Token: \s (white space)
 )?                                 # Closes NCG
 (                                  # Opens CG2
     (?:                            # Opens NCG
         .*                         # . denotes any single character, except for newline
     )+                             # Closes NCG
 )                                  # Closes CG2
 $                                  # Anchors to the end to the string.

我将 [0-9] 转换为 \d，只是为了更容易地阅读（两者匹配相同的内容）。同时，我还删除了很多未被使用的非捕获组。

^((?:(?:[A-Za-z_]+\d*)+\.?)+)\s?\:\s?((?:.*)+)$

我把\s和.*合并成了[\s\S]*，但是发现它后面跟着一个+符号，所以我去掉了这个组，并只使用了[\s\S]。

^((?:(?:[A-Za-z_]+\d*)+\.?)+)\s?\:([\s\S]+)$
                      ^

现在我不确定插入符号上方的+应该做什么。我们可以移除它，因此移除非捕获组。

^((?:[A-Za-z_]+\d*\.?)+)\s?\:([\s\S]+)$

解释：

 ^                          # Anchors to the beginning to the string.
 (                          # Opens CG1
     (?:                    # Opens NCG
         [A-Za-z_]+         # Character class (any of the characters within)
         \d*                # Token: \d (digit)
         \.?                # Literal .
     )+                     # Closes NCG
 )                          # Closes CG1
 \s?                        # Token: \s (white space)
 \:                         # Literal :
 (                          # Opens CG2
     [\s\S]+                # Character class (any of the characters within)
 )                          # Closes CG2
 $                          # Anchors to the end to the string.

现在，如果你正在处理多行内容，你可能想把[\s\S]+改回.*。对此有几种不同的选择，但这取决于你使用的语言。

老实说，我是分步骤完成的，但最大的问题是(?:.*)+。这告诉引擎去匹配0个或多个字符1次或多次，会导致灾难性回溯（如评论中所述）。

最终的正则表达式和你原来的一样，允许以.结尾的变量。我建议使用更像这样的东西，你的正则表达式离这也不远。

这将匹配像foo.ba5r这样的名称，如果可以接受的话，你之前的正则表达式则不行。

^([A-Za-z_]\w*(?:\.[A-Za-z_]+\w*)*)\s?\:([\s\S]+)$

解释：

 ^                          # Anchors to the beginning to the string.
 (                          # Opens CG1
     [A-Za-z_]              # Character class (any of the characters within)
     \w*                    # Token: \w (a-z, A-Z, 0-9, _)
     (?:                    # Opens NCG
         \.                 # Literal .
         [A-Za-z_]          # Character class (any of the characters within)
         \w*                # Token: \w (a-z, A-Z, 0-9, _)
     )*                     # Closes NCG
 )                          # Closes CG1
 \s?                        # Token: \s (white space)
 \:                         # Literal :
 (                          # Opens CG2
     [\s\S]+                # Character class (any of the characters within)
 )                          # Closes CG2
 $                          # Anchors to the end to the string.