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

Question

是否有任何工具可以采用特定的正则表达式,并根据正则表达式匹配的特定数量的字符所需的操作数返回最坏的情况？

例如,给定a (f|a)oo.*[ ]baz,引擎可能会通过多少步骤来匹配100个字符？

如果有一个工具可以获取大量文本样本并显示每次运行的平均操作,我也会感兴趣.

我意识到这将在很大程度上取决于所使用的引擎和实现 - 但我不知道这是多么常见.因此,如果它对于许多语言来说很常见(使我的问题太模糊),我会对Perl和Python特别感兴趣.

Answer 1

Regexbuddy的调试器显示引擎在给定样本上完成匹配的步数.有关灾难性回溯和调试正则表达式的更多信息.

PS:它不是免费的,但它们提供3个月的退款保证.

Answer 2

请注意,这取决于引擎.虽然正则表达式理论基于直线自动机理论,但大多数引擎并不是那些理论的严格翻译.因此,例如,某些引擎会在指数时间内发生,而严格的NFA处理则不会.

Answer 3

你可能会得到你在找什么东西喜欢使用re.compile有re.DEBUG.看到这个优秀的答案来自Python的隐藏功能社区维基广泛的解释.