正则表达式进入无限循环

胡向阳

2023-03-14

问题内容：

我正在解析（种类）表格的名称：

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”处失败。]

注意：在调试此程序时，我发现正则表达式经常完成但非常慢（例如，在较短的目标字符串上）。通过病理案例发现此错误很有价值。我学到了重要的一课！

问题答案：

要解决问题的第一部分，您应该阅读灾难性的回溯。本质上，正在发生的事情是有太多方法可以将您的正则表达式与您的字符串进行匹配，并且解析器会不断回溯以尝试使其正常工作。

在您的情况下，可能是嵌套的重新布局： (\s*[a-z]+)*可能导致了一些非常非常奇怪的循环。正如Qtax熟练地指出的那样，没有更多的信息就很难分辨。

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

至于使您的正则表达式运行更快的一些技巧？那是一大罐蠕虫。我花了很多时间独自研究正则表达式，并花了一些时间对其进行优化，以下是我发现通常能提供的帮助：

如果您的语言支持，则在循环之外编译正则表达式。
只要有可能，就添加锚点。特别是^对于字符串的开头。另请参阅：字边界
避免像瘟疫一样嵌套重复。如果需要（必须这样做），请尽力为引擎提供提示，以使任何意外的回溯短路。
利用风味构造来加快处理速度。我偏爱非捕获组和所有格限定词。它们不会出现在每种口味中，但是当它们出现时，应该使用它们。还要检查原子组
我总是发现这是对的： 正则表达式获取的时间越长，使它变得高效的麻烦就越大。 正则表达式是一个强大而强大的工具，就像一个超级聪明的锤子。不要陷入将一切视为钉子的陷阱。有时，您要查找的字符串函数就在您的鼻子下面。

希望对您有帮助。祝好运。