ruby - 无休止的正则表达式 : Regex couldn't terminate while matching a 69 character String (killed after a week)

Question

从没想过可以编写一个永不返回的正则表达式。

正则表达式

/^((?:\d|\w{1,2}[-\d\s])(?:[-\s\d]|\w{1,2}[-\d\s])*\d)$/

用于匹配以一个数字或两个字母开头，后跟破折号、空格或数字并以数字结尾的数字。中间可能会重复起始模式，也可能会出现空格或破折号。

示例:1234、de-12943、EN - 12de -50

以下示例代码不会终止:

ruby

#!/usr/bin/ruby
string = "101000000750000000000000000000000001000038127OXMOO0OOOOO00000000000N9"
re = /^((?:\d|\w{1,2}[-\d\s])(?:[-\s\d]|\w{1,2}[-\d\s])*\d)$/
p re.match("101000000750000000000000000000000001000038127OXMOO0OOOOO00000000000N9")

斯卡拉

"""^((?:\d|\w{1,2}[-\d\s])(?:[-\s\d]|\w{1,2}[-\d\s])*\d)$""".r findFirstIn "101000000750000000000000000000000001000038127OXMOO0OOOOO00000000000N9"

删除 anchor (^, $) 可让正则表达式快速终止。

尝试使用 Ruby 和 Scala。

那里发生了什么？ anchor 不应该导致更快的终止吗？

Answer 1

首先，\w 不是字母，而是[a-zA-Z0-9_]。因此，如果您真的只想要字母，请使用 [a-zA-Z]。

其次，我想你可能有一个案例 catastrophic backtracking .

您的正则表达式显然不会超过 OXM，因为无法匹配您的模式中的三个连续字母。如果您删除 $ anchor ，正则表达式会很乐意匹配那里，但是当您离开它时，正则表达式将失败并开始回溯。

所以假设它匹配 OX 和 \w{1,2} 但失败了。然后它将丢弃整个第二个非捕获组的最后一次重复并返回一个步骤，它匹配 7 和 [-\s\d]。现在它将尝试将 7O 或 7 与 \w{1,2} 匹配，但随后再次无法匹配 [ -\d\s] 分别针对 X 或 O。再退一步，它尝试将 27 或 2 与 \w{1,2} 重新匹配，但再次失败。等等等等。返回得越远，可能再次将 [-\d\s] 与一个字母匹配，然后引擎将一直前进到 OXM 再次开始乐趣。当回溯最终到达字符串的开头和您的第一个交替时，它也会尝试该交替的所有三个选项，并将一遍又一遍地执行整个操作。

让我试着通过写出重复中使用了哪些交替来形象化回溯的第一步。每两行中的第一行是测试字符串，第二行包含使用的相应正则表达式结构。每次尝试都在最后一个字符处失败。

... 1       2       7       O
... [-\s\d] [-\s\d] [-\s\d] [-\s\d] 

... 1       2       7       OX    M
... [-\s\d] [-\s\d] [-\s\d] \w{2} [-\d\s]

... 1       2       7       O     X
... [-\s\d] [-\s\d] [-\s\d] \w{1} [-\d\s]

... 1       2       7O    X
... [-\s\d] [-\s\d] \w{2} [-\d\s]

... 1       2       7     O
... [-\s\d] [-\s\d] \w{1} [-\d\s]

... 1       27    O      
... [-\s\d] \w{2} [-\d\s]

... 1       2     7       O
... [-\s\d] \w{1} [-\d\s] [-\s\d]

... 1       2     7       OX    M
... [-\s\d] \w{1} [-\s\d] \w{2} [-\d\s]

... 1       2     7O    X
... [-\s\d] \w{1} \w{2} [-\d\s]

等等。我希望你明白了。很难用几行 ASCII 将其形象化。

我想，只需将 \w 更改为适当的字符组就可以解决问题，因为等效组合较少。试试吧。