检测正则表达式是否呈指数形式

Question

这个article表明回溯时存在一些正则表达式O（2^n）。 示例为(x+x+)+y。 当试图匹配像xxxx ... p这样的字符串时，它会先回溯一段时间，然后找出它无法匹配的地方。

有没有办法检测这样的正则表达式？

感谢

Answer 1

如果你的正则表达式引擎公开运行时的指数行为（X + X +）+ Y，那么它是破因为DFA或NFA能够识别在线性时间内这种格局：

echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx" | egrep "(x+x+)+y" 
echo "xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxy" | egrep "(x+x+)+y" 

都立即回答。

事实上，也有只在真正需要回溯少数情况下（如反向引用）（主要是因为向引用一个正则表达式是不在语言理论意义上的正则表达式了）。一个有能力的实现应该只在给出这些角落案例时切换回溯。在公平性方面，DFA也有一个阴暗面，因为一些正则表达式具有指数大小的要求，但是大小限制比时间限制更容易实施，而且巨大的DFA在输入上线性运行，所以它比一个更好的讨价还价一个小型backtracker窒息了几个X的。

你应该真的阅读拉斯考克斯出色的系列文章中有关正则表达式的实现（和回溯的病态行为）：http://swtch.com/~rsc/regexp/

要回答你的问题有关可判定：不能。因为没有一个 backgracking正则表达式。每种实现都有自己的策略来处理在某些情况下算法的指数级增长，并且不包含其他策略。一条规则可能适合这里，对于那里来说是灾难性的。

UPDATE：

例如，一个实施方式可以包含一个优化器，其可以用代数变换执行它们之前以简化的正则表达式：(x+x+)+y是相同的一个xxx*y，其不应该是任何backtracker的问题。但同样的优化器不会识别下一个表达式，并且问题再次出现。这里有人描述了如何制作这傻瓜Perl的优化器regexpr：

http://perlgeek.de/blog-en/perl-tips/in-search-of-an-exponetial-regexp.html

Answer 2

不，我不这么认为，但您可以使用这些准则：如果它包含两个量词是开放式的，在高端

• 和它们嵌套则可能是 O（2^n）。
• 如果它不包含两个这样的量词，那么我认为它不能是O（2^n）。

量词可能导致此有：*，+和{k,}。

另请注意，评估正则表达式的最坏情况复杂度可能与典型字符串的复杂度非常不同，并且复杂程度取决于特定的正则表达式引擎。

Answer 3

没有反向引用的任何正则表达式可以在线性时间相匹配，尽管许多正则表达式引擎赫然出现在现实世界中不那样做， （至少有很多插入编程语言运行时环境的正则表达式引擎支持反向引用，并且在没有反向引用时不会切换到更高效的执行模式）。

有没有简单的方法来找出多少时间与反向引用的正则表达式将消耗。

Answer 4

您可以使用正则表达式解析器来检测和拒绝嵌套重复，其对应的star height为1.我刚刚使用npm的正则表达式解析器编写了a module to compute and reject start heights of >1。

$ node safe.js '(x+x+)+y' 
false 
$ node safe.js '(beep|boop)*' 
true 
$ node safe.js '(a+){10}' 
false 
$ node safe.js '\blocation\s*:[^:\n]+\b(Oakland|San Francisco)\b' 
true