正则表达式进入无限循环。

Question

我正在解析形式为（物种）名称的内容：

Parus Ater
H. sapiens
T. rex
Tyr. rex

通常有两个术语（二项式），但有时会有3个或更多。

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto

我写了

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)*

这段代码大部分时候能够正常工作，但偶尔会进入无限循环。花费了一些时间才发现问题出在正则表达式匹配上，最终我意识到是因为拼写错误导致的。

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)*

表现良好的循环。

我的问题是：

• 这个循环为什么会发生？
• 有没有办法在运行程序之前检查类似的正则表达式错误？否则，可能很难在程序分发之前捕获它们并造成问题。

[注意：我不需要一个更通用的物种表达式 - 有一个正式的100+行物种名称的正则表达式规范 - 这只是一个初始过滤器]。

注意：问题出现的原因是，尽管大多数名称都被精确提取为2个或偶尔3/4个术语（因为它们是斜体），但也有一些误报（例如“Homo sapiens lives in big cities like London”），并且匹配在“L”处失败。]

注意：在调试此问题时，我发现正则表达式经常完成但速度非常慢（例如，在较短的目标字符串上）。通过一个病态案例发现了这个 bug 是非常有价值的。我学到了一个重要的教训！

- peter.murray.rust

---

我认为你应该写 (\s+[a-z]+)+ 而不是 \s+[a-z][a-z]+(\s+[a-z]+)*。 - shift66

你应该了解一下“灾难性回溯”（这是你实际遇到的问题，而不是无限循环：http://www.regular-expressions.info/catastrophic.html）和停机问题 （http://en.wikipedia.org/wiki/Halting_problem）。由于正则表达式本质上是描述用于解析字符串的有限状态机，因此你不能创建一个通用解决方案来预测哪些正则表达式会发生灾难性回溯，哪些不会。 - FrankieTheKneeMan

@FrankieTheKneeMan，我同意这应该是灾难性回溯。但我不明白为什么这个表达式会在这个输入上发生灾难性回溯。也不会在任何输入上。如果第三部分的任何部分失败，第二项就不应该回溯。对于第三项及其后续项的正则表达式应该像(\s*[a-z]+)?一样回溯。当然，除非OP在这个表达式之后还有其他内容。 - Qtax

我认为这是因为 (\s*[a-z]+)* 可能会导致多种解释：即使对于一个简单的字符串，引擎也可以在此处跟随许多路径。 - Denys Séguret

@FrankieTheKneeMan，为什么会这样？表达式没有被锚定。或者OP使用了一些锚定表达式的Java函数？这可能是情况，但OP应该提到这一点。 - Qtax

Answer 1

为了回答您问题的第一部分，您应该阅读有关灾难性回溯的内容。基本上，发生的情况是您的正则表达式与字符串匹配的方式太多了，解析器不断地回溯以尝试使其正常工作。

在您的情况下，可能是嵌套的重复造成了一些非常奇怪的循环：(\s*[a-z]+)*。正如Qtax所指出的那样，如果没有更多信息，很难确定。

不幸的是，您问题的第二部分无法回答。这基本上是停机问题。由于正则表达式本质上是一个有限状态机，其输入是一个字符串，因此您不能创建一个通用解决方案来预测哪些正则表达式会发生灾难性回溯，哪些不会。

至于一些使您的正则表达式运行更快的提示？那是一个大问题。我花了很多时间自学正则表达式，并优化它们的时间，以下是我找到的一些通用方法：

1. 如果你的编程语言支持，尽可能在循环外编译你的正则表达式。
2. 只要可能，当你知道它们有用时，添加 锚点。特别是字符串开头的 ^。另请参见：单词边界
3. 避免像瘟疫一样嵌套重复。如果你必须这样做（你肯定会），尽力为引擎提供提示，以便防止任何意外回溯。
4. 利用构造来加速匹配。我偏爱 非捕获组 和 占有量词。它们不会出现在每种语言中，但当它们出现时，你应该使用它们。还可以查看 原子组
5. 我总是发现这是真的：你的正则表达式越长，你就越难使它高效。 正则表达式是一个强大的工具，就像一个超级智能的锤子。不要陷入把所有东西都看作钉子的误区。有时你要找的字符串函数就在你眼前。

希望这可以帮到你。祝你好运。

- FrankieTheKneeMan

---

这里只需要用到第4点。第1点与回溯问题无关。锚点也与此无关，在必要时才应该添加。第3点在某些情况下非常有用，但仍然容易遇到回溯问题。 - nhahtdh

@nhahtdh，你的观点是错误的，因为在这个特定问题中，三才是解决方案。虽然四非常有帮助，但它并不是解决哪些正则表达式会和不会发生灾难性回溯的通用方法 - 特别是因为并非所有的RegEx都支持它们。锚点在避免灾难性回溯时非常有用。比较一下\bx+y和x+y在匹配任意长的X字符串时的性能差异。我并不是试图提供一个调试所有灾难性回溯的地图 - 只是提供一些避免低效RegEx的思路。 - FrankieTheKneeMan

占有量词是一种语法糖，用于原子组，在Java中有支持。对于我自己的表达式，我总是尽可能使用这些。 - Qtax

它们只是语法糖，但它们更容易阅读。实际上，你应该知道你在使用什么，并尽可能发挥更大的力量。 - FrankieTheKneeMan

@FrankieTheKneeMan：我对第三点的看法已经改正了。在回答时分析正则表达式后，稍微改变一下正则表达式的逻辑确实有所帮助。然而，就目前而言，你对第三点的建议并不切实际。更实际的建议是为要验证的文本编写语法，然后编写相应的正则表达式，或者找到适用于正则表达式的输入字符串的好假设。至于锚点，我不确定你的建议适用于何时何地。 - nhahtdh

Answer 2

对于第一个正则表达式：

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)*

由于评论中指出的(\s*[a-z]+)*，导致了灾难性回溯。但是，只有在使用String.matches()对字符串进行验证时才成立，因为只有在遇到无效字符时，引擎才会尝试回溯而不是返回匹配结果（Matcher循环）。

让我们将一个无效字符串与(\s*[a-z]+)*进行匹配：

inputstringinputstring;

(Repetition 1)
\s*=(empty)
[a-z]+=inputstringinputstring
FAILED

Backtrack [a-z]+=inputstringinputstrin
(Repetition 2)
\s*=(empty)
[a-z]+=g
FAILED

(End repetition 2 since all choices are exhausted)
Backtrack [a-z]+=inputstringinputstri
(Repetition 2)
\s*=(empty)
[a-z]+=ng
FAILED

Backtrack [a-z]+=n
(Repetition 3)
\s*(empty)
[a-z]+=g
FAILED

(End repetition 3 since all choices are exhausted)
(End repetition 2 since all choices are exhausted)
Backtrack [a-z]+=inputstringinputstr

到目前为止，你应该已经注意到了问题。让我们将 T(n) 定义为检查长度为 n 的字符串是否与模式不匹配所需的工作量。从回溯的方法中，我们知道 T(n) = Sum [i = 0..(n-1)] T(i)。由此，我们可以推导出 T(n + 1) = 2T(n)，这意味着回溯过程的时间复杂度是指数级的！

将 * 更改为 + 完全避免了这个问题，因为重复的实例只能从空格字符和英文字母字符之间的边界开始。相比之下，第一个正则表达式允许重复实例在任何两个字母字符之间开始。

为了证明这一点，当无效输入字符串包含许多用多个连续空格分隔的单词时，(\s+[a-z]+\s*)* 将使你陷入回溯地狱，因为它允许多个重复实例的开始位置。这遵循公式 b^d，其中 b 是最大连续空格数（减 1），d 是空格序列的数量。它比你的第一个正则表达式更不严重（它要求每个重复至少有一个英文字母和一个空格字符，而不是你的第一个正则表达式中每个重复只需要一个英文字母），但它仍然是一个问题。

- nhahtdh

---

+1 非常有用。我可能在不应该使用这个结构时使用它。如果有一个“lint”建议您何时做出不良操作，那将非常有用。 - peter.murray.rust