无休止的正则表达式:正则表达式无法在匹配69个字符的字符串时终止(一周后被杀死)

Question

从来没有想过会写一个永不回归的正则表达式.

正则表达式

/^((?:\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.

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

Answer 1

首先,\w不是一封信,而是[a-zA-Z0-9_].所以,如果你真的只想要信件就可以了[a-zA-Z].

其次,我想你可能有一个灾难性的回溯案例.

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

因此,假设它匹配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到适当的字符组可能已经解决了问题,因为等效组合较少.试试看.