正则表达式进入无限循环
我正在解析表单的（种类）名称：
Parus Ater H. sapiens T. rex Tyr. rex 通常有两个术语（二项式）但有时有3个或更多。
Troglodytes troglodytes troglodytes E. rubecula sensu stricto
我写
[AZ][az]*\.?\s+[az][az]+(\s*[az]+)*
它大部分时间都有效，但偶尔会进入无限循环。 需要一些时间来追踪它是在正则表达式匹配中，然后我意识到这是一个错字，我应该写
[AZ][az]*\.?\s+[az][az]+(\s+[az]+)*
表现得当。
我的问题是：
- 为什么这个循环发生？
- 有没有办法在运行程序之前检查类似的正则表达式错误？ 否则，在分发prgram之前可能难以捕获它们并导致问题。
[注意：对于物种，我不需要更一般的表达式 – 对于物种名称，有一个正式的100+行正则表达式规范 – 这只是一个初始filter]。
注意：问题出现了，因为虽然大多数名称被精确地提取为2或偶尔3/4术语（因为它们用斜体字表示），但是有一些误报（例如"Homo sapiens lives in big cities like London" ）并且匹配失败在“L”。]
注意：在调试中我发现正则表达式经常完成但速度很慢（例如在较短的目标字符串上）。 通过病理案例我发现了这个错误是很有价值的。 我学到了一个重要的教训！
要解决问题的第一部分，您应该阅读灾难性的回溯 。 从本质上讲，正在发生的事情是有太多的方法来匹配您的正则表达式与您的字符串，并且解析器不断回溯以尝试使其工作。
在你的情况下，它可能是嵌套的重复： (\s*[az]+)*这可能导致一些非常奇怪的循环。 正如Qtax娴熟地指出的那样，没有更多信息就很难说出来。
不幸的是，你的问题的第二部分是不可能回答的。 这基本上就是停机问题 。 由于正则表达式本质上是一个有限状态机，其输入是一个字符串，因此您无法创建一个通用解决方案来预测哪些正则表达式会灾难性地回溯，哪些不会。
一些使正则表达式运行得更快的技巧？ 这是一大堆蠕虫。 我花了很多时间自己研究正则表达式，有时候优化它们，这里我发现通常有帮助：
- 如果您的语言支持，请在循环外编译正则表达式。
- 只要有可能，在知道它们有用时添加锚点 。 特别是
^为字符串的开头。 另见： Word Boundaries - 避免像瘟疫一样的嵌套重复。 如果您必须拥有它（您会这样做），请尽力为发动机提供提示，以便短路任何意外的回溯。
- 利用风味构造来加快速度。 我偏爱非捕获组和占有量词 。 它们不会出现在每种口味中，但是当它们出现时，你应该使用它们。 还可以查看primefaces组
- 我总觉得这是真的： 你的正则表达式越长，你就越难以提高它的效率。 正则表达式是一个伟大而强大的工具，它们就像一个超级聪明的锤子。 不要陷入将一切视为钉子的陷阱 。 有时你正在寻找的弦乐function就在你的鼻子底下。
希望这对你有所帮助。 祝你好运。
对于第一个正则表达式：
[AZ][az]*\.?\s+[az][az]+(\s*[az]+)*
由于评论中指出的(\s*[az]+)* ，发生了灾难性的回溯。 但是，只有在使用String.matches()validation字符串时才会成立，因为这是遇到无效字符导致引擎尝试并回溯的唯一情况，而不是返回匹配（ Matcher循环）。
让我们匹配一个无效的字符串(\s*[az]+)* ：
inputstringinputstring; (Repetition 1) \s*=(empty) [az]+=inputstringinputstring FAILED Backtrack [az]+=inputstringinputstrin (Repetition 2) \s*=(empty) [az]+=g FAILED (End repetition 2 since all choices are exhausted) Backtrack [az]+=inputstringinputstri (Repetition 2) \s*=(empty) [az]+=ng FAILED Backtrack [az]+=n (Repetition 3) \s*(empty) [az]+=g FAILED (End repetition 3 since all choices are exhausted) (End repetition 2 since all choices are exhausted) Backtrack [az]+=inputstringinputstr
到现在为止，你应该注意到这个问题。 让我们将T(n)定义为检查长度为n的字符串与模式不匹配的工作量。 从回溯方法来看，我们知道T(n) = Sum [i = 0..(n-1)] T(i) 。 由此，我们可以推导出T(n + 1) = 2T(n) ，这意味着回溯过程在时间复杂度上是指数的！
将*更改为+ 可完全避免此问题 ，因为重复实例只能从空格字符和英文字母字符之间的边界开始。 相反，第一个正则表达式允许重复的实例在任何2个字母字符之间开始。
为了certificate这一点，当无效输入字符串包含许多用多个连续空格分隔的单词时， (\s+[az]+\s*)*会给你回溯地狱，因为它允许重复实例的多个位置开始。 这遵循公式b^d ，其中b是连续空格的最大数量（减1）， d是空格序列的数量。 它没有你所拥有的第一个正则表达式那么严重（每次重复需要至少一个Englsh字母和一个空格字符，而在你的第一个正则表达式中每次重复需要一个英文字母），但它仍然是一个问题。