Python重新无限执行

Question

我正在尝试执行此代码:

import re
pattern = r"(\w+)\*([\w\s]+)*/$"
re_compiled = re.compile(pattern)
results = re_compiled.search('COPRO*HORIZON 2000                 HOR')
print(results.groups())

但是 Python 没有响应。该进程占用 100% 的 CPU 并且不会停止。我在 Python 2.7.1 和 Python 3.2 上都试过了，结果相同。

Answer 1

您的正则表达式遇到 catastrophic backtracking因为您有嵌套的量词 (([...]+)*)。由于您的正则表达式要求字符串以 / 结尾(在您的示例中失败)，因此正则表达式引擎徒劳地尝试字符串的所有排列，希望找到匹配的组合。这就是卡住的地方。

为了说明，我们假设 "A*BCD" 作为正则表达式的输入，看看会发生什么:

1. (\w+) 匹配 A。很好。
2. \* 匹配 *。耶。
3. [\w\s]+ 匹配 BCD。好的。
4. / 匹配失败(没有字符可匹配)。好的，让我们备份一个字符。
5. / 无法匹配 D。哼。让我们再备份一些。
6. [\w\s]+ 匹配BC，重复的[\w\s]+ 匹配D。
7. / 匹配失败。备份。
8. / 无法匹配 D。再备份一些。
9. [\w\s]+匹配B，重复的[\w\s]+匹配CD。
10. / 匹配失败。再次备份。
11. / 无法匹配 D。再备份一些。
12. [\w\s]+如何匹配B，重复[\w\s]+匹配C，重复 [\w\s]+ 匹配 D？不？让我们试试别的吧。
13. [\w\s]+ 匹配 BC。让我们在这里停下来看看会发生什么。
14. 该死，/ 仍然不匹配 D。
15. [\w\s]+ 匹配 B。
16. 还是没有运气。 / 与 C 不匹配。
17. 嘿嘿，全组可选(...)*。
18. 不，/ 仍然不匹配 B。
19. 好吧，我放弃了。

现在这是一个只有三个字母的字符串。你的有大约 30 个，尝试所有的排列可以让你的计算机忙到天结束。

我想你想要做的是在 * 之前/之后获取字符串，在这种情况下，使用

pattern = r"(\w+)\*([\w\s]+)$"