检测正则表达式是否为指数

检测正则表达式是否为指数

如果您的regexp引擎公开了（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/

要回答有关可确定性的问题：您不能。因为regexpr 没有 一个
回溯。在某些情况下，每种实现都有其自己的策略来处理其算法的指数增长，并且不涉及其他情况。一个规则可能适用于此处，而对于此处则是灾难性的。

更新：

例如，一个实现可能包含一个优化器，该优化器可以在执行之前使用代数转换来简化正则表达式：

(x+x+)+y

是相同的

xxx*y

，这对于任何回溯器来说都不是问题。但是同一个优化器无法识别下一个表达式，问题再次出现。这里有人描述了如何制作一个欺骗Perl优化器的正则表达式：

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