正则表达式的最坏情况分析

Question

有没有什么工具可以拿一个特定的正则表达式，告诉我在匹配一定数量的字符时，最糟糕的情况下需要多少操作步骤？

比如说，给定一个 (f|a)oo.*[ ]baz 的正则表达式，匹配100个字符时，匹配引擎可能需要经过多少步骤呢？

我也想知道有没有工具可以处理一堆文本样本，并显示每次运行的平均操作次数。

我知道这会很大程度上依赖于使用的引擎和具体的实现方式——但我对这方面的了解不多。所以如果很多编程语言都有类似的情况（可能让我这个问题显得太笼统），我特别想了解一下Perl和Python。

Answer 1

你可能会找到你想要的东西，比如使用 re.compile 和 re.DEBUG。可以看看这个来自 优秀回答，它来自 Python隐藏特性 社区维基，里面有详细的解释。

Answer 2

请注意，这个问题的答案取决于所使用的引擎。虽然正则表达式的理论是基于自动机理论的，但大多数引擎并不是这些理论的严格翻译。因此，有些引擎在处理时可能会花费指数级的时间，而严格的非确定性有限自动机（NFA）处理则不会出现这种情况。

Answer 3

Regexbuddy 的调试工具可以显示在给定示例中，程序需要多少步骤来判断是否匹配。关于灾难性回溯和正则表达式调试的更多信息。

附注：这个工具不是免费的，但他们提供三个月的退款保证。