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

• Z时代
• 2024-01-10
• 分类：问答

该文章显示，有一些正则表达式是O（2 ^

n）的时候回溯。例子是(x+x+)+y。当尝试匹配xxxx … p之类的字符串时，它会回溯一段时间，然后才发现它无法匹配。

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

谢谢

回答：

如果您的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

以上是 检测正则表达式是否为指数 的全部内容， 来源链接： utcz.com/qa/402469.html