正则表达式模式——灾难性回溯问题

12

我在旧的Java系统中使用了下面展示的正则表达式,最近它导致回溯问题。很多时候回溯线程会导致机器的CPU达到上限,直到应用程序重新启动才恢复正常。

有没有人能建议一种更好的重写这个模式的方法或一个可以帮助我做到这一点的工具?

模式:

^\[(([\p{N}]*\]\,\[[\p{N}]*)*|[\p{N}]*)\]$

价值观正在发挥作用:

[1234567],[89023432],[124534543],[4564362],[1234543],[12234567],[124567],[1234567],[1234567]

灾难性回溯值 - 如果值中有任何错误(例如在末尾添加了额外的括号):

[1234567],[89023432],[124534543],[4564362],[1234543],[12234567],[124567],[1234567],[1234567]]

你是指这个 https://regex101.com/r/oV8pN3/1 吗? - Avinash Raj
1个回答

22

当您的意图是使用+时,请勿使用*。我注意到您的正则表达式几乎所有内容都是可选的,只有开括号和闭括号是必需的,而且我非常确定您不希望将[]视为有效输入。

导致回溯失控的最大原因之一是存在两个或更多可以匹配相同内容的备选项。|[\p{N}]*就是这种情况。正则表达式引擎必须尝试字符串中的每个可能路径,然后才会放弃,因此所有那些\p{N}*构造都会在每组数字上陷入无休止的拉锯战。

但修复这些问题没有意义,因为总体结构是错误的。我认为您要找的是:

^\[\p{N}+\](?:,\[\p{N}+\])*$

在它消耗了第一个标记 ([1234567]) 后,如果字符串中的下一个字符不是逗号或字符串结尾,那么匹配将立即失败。如果它看到逗号,它必须继续匹配另一个完整的标记 ([89023432]),否则也会立即失败。

这可能是创建正则表达式时需要记住的最重要的事情:如果它将失败,您希望它尽快失败。您可以使用原子组和贪婪量词等功能来实现这一点,但如果您正确构造了正则表达式的结构,则很少需要它们。回溯并非不可避免。


网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接