2

从来没有想过有可能编写一个永远不会返回的正则表达式。

正则表达式

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

旨在匹配以数字或两个字母开头的数字，后跟破折号、空白或数字并以数字结尾。在开始模式之间可能会重复，或者可能会出现空格或破折号。

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

以下示例代码不会终止：

红宝石

#!/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"

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

尝试使用 Ruby 和 Scala。

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

4

1 回答 1

11

首先，\w不是字母，而是[a-zA-Z0-9_]。所以，如果你真的只是想要那里的字母，那就去做吧[a-zA-Z]。

其次，我想你可能会遇到灾难性回溯的情况。

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

所以假设它与OXwith匹配\w{1,2}并且失败了。然后它会丢弃整个第二个非捕获组的最后一个重复并返回一步，它与7with匹配[-\s\d]。现在它将尝试匹配or 7O，7但\w{1,2}随后又无法分别匹配or 。再退一步，它尝试重新匹配或再次失败。等等等等。往回走得越远，有可能再次匹配到一个字母，然后引擎将一路前进到[-\d\s]XO272\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为适当的字符组可能已经解决了问题，因为等效组合较少。试试看。

于 2012-11-07T11:08:20.597 回答