检测regexp是否为指数型

如果您的regexp引擎公开(x+x+)+y的运行时指数行为,那么它就是 因为DFA或NFA可以在线性时间内识别这种模式:

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

两人立即回答。

事实上,只有少数情况(比如backreferences)真正需要回溯(主要是因为带有回溯引用的regexp是 语言理论意义上的正则表达式)。一个有能力的实现应该只在给定这些转角情况时才切换到回溯。

公平地说,DFA也有阴暗的一面,因为有些regexp有指数级的大小要求,但是大小限制比时间限制更容易实施,而且巨大的DFA在输入上是线性的,所以这比一个小的回溯器在几个X上阻塞要好。

你应该 真正地 http://swtch.com/~rsc/regexp/

回答你关于可判定性的问题:你不能。因为没有 那个 regexpr的回溯。每个实现都有自己的策略来处理算法在某些情况下的指数增长,而不包括其他情况。一条规则可能适用于这里,也可能适用于那里。

更新:

(x+x+)+y xxx*y ,这对任何回溯者来说都不是问题。但是同一个优化器不会识别下一个表达式,问题又出现了。这里有人描述了如何制作一个regexpr,它愚弄了Perl的优化器:

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

• 如果它包含两个在高端开放的量词,并且它们是嵌套的,那么 O(2^n)。
• 如果它不包含两个这样的量词,那么我认为它不可能是O(2^n)。

可能导致这种情况的量词有: * , + {k,} .

还要注意,计算正则表达式的最坏情况的复杂度可能与典型字符串的复杂度非常不同,而且复杂度取决于特定的正则表达式引擎。

任何没有反向引用的regex都可以在线性时间内进行匹配,尽管现实世界中的许多regex引擎不是这样做的(至少许多插入到编程语言运行时环境中的regex引擎支持反向引用,并且在没有反向引用时不会切换到更有效的执行模型)。

您可以使用regex解析器检测和拒绝嵌套重复,该解析器对应于 star height 第1页。我刚写完信 a module to compute and reject start heights of >1 使用npm的正则表达式解析器。

$ 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