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

Question

该文章显示,有一些正则表达式是O(2 ^ n)的回溯时.这个例子是(x+x+)+y.当尝试匹配像xxxx ...这样的字符串时,它会回溯一段时间,然后才发现它无法匹配.

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

谢谢

Answer 1

如果你的正则表达式引擎暴露了(x + x +)+ y的运行时指数行为,那么它就会被 破坏,因为DFA或NFA可以在线性时间内识别出这种模式:

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

都立即回答.

事实上,也有只在真正需要回溯少数情况下(如反向引用)(主要是因为向引用一个正则表达式是不是在语言理论意义上的正则表达式了).只有在给出这些极端情况时,一个有能力的实现应该切换到回溯.

公平地说,DFA也有一个黑暗的一面,因为一些正则表达式具有指数大小要求,但是尺寸约束比时间约束更容易实施,并且巨大的DFA在输入上运行线性,因此它比小型回溯窒息更便宜几个X的.

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

要回答关于可判定性的问题:你做不到.因为regexpr 没有一个回溯.每个实现都有自己的策略来处理某些情况下算法的指数增长,而不涉及其他情况.一条规则可能适合这里,也可能是灾难性的.

更新:

例如,一个实现可以包含一个优化器,它可以在执行它们之前使用代数转换来简化正则表达式:(x+x+)+y是相同的a xxx*y,这对于任何回溯都不应该是一个问题.但是同样的优化器不会识别下一个表达式,问题又出现了.在这里有人描述了如何制作一个愚弄Perl优化器的regexpr: