可以编写一个在某些情况下需要指数运行时间的正则表达式.这样的例子是(aa|aa)*.如果输入奇数个as,则需要指数运行时间.
这很容易测试.如果输入仅包含as并且长度为51,则正则表达式需要几秒钟才能计算(在我的机器上).相反,如果输入长度为52,则其计算时间不明显(我使用JavaRE的内置Regex-parser对其进行了测试).
我写了一个正则表达式解析器来找到这种行为的原因,但我没有找到它.我的解析器可以基于正则表达式构建AST或NFA.之后,它可以将NFA翻译为DFA.为此,它使用了powerset构造算法.
当我解析上面提到的Rgex时,解析器会创建一个具有7种状态的NFA - 转换后,DFA中只剩下3个状态.DFA代表更明智的正则表达式(aa)*,可以非常快速地解析.
因此,我不明白为什么有解析器可以这么慢.这是什么原因？他们不会将NFA翻译成DFA吗？如果是的话,为什么不呢？他们计算得如此之慢的技术原因是什么？
小智 19
Russ Cox有一篇非常详细的文章,说明为什么会这样,以及正则表达式的历史(第2 部分,第3部分).
正则表达式匹配可以简单快速,使用已知数十年的基于有限自动机的技术.相比之下,Perl,PCRE,Python,Ruby,Java和许多其他语言都有基于递归回溯的正则表达式实现,这些实现简单但速度极慢.除了反向引用之外,慢速回溯实现提供的功能可以通过基于自动机的实现以更快,更一致的速度提供.
很大程度上,它归结为"常规"表达式中的非常规功能的扩散,例如反向引用,以及大多数程序员的(持续)无知,对于不包含此类功能的正则表达式(其中许多功能)有更好的替代方案.
在20世纪80年代早期编写文本编辑器时,Rob Pike编写了一个新的正则表达式实现,Dave Presotto将其提取到第八版中出现的库中.Pike的实现将子匹配跟踪整合到一个有效的NFA模拟中,但是,与第八版源的其余部分一样,并没有广泛分布.派克自己没有意识到他的技术有什么新意.Henry Spencer从零开始重新实现了第八版库接口,但使用了回溯,并将其实现发布到了公共领域.它被广泛使用,最终成为前面提到的慢速正则表达式实现的基础:Perl,PCRE,Python等.(在他的辩护中,Spencer知道例程可能很慢,他不知道存在更有效的算法.他甚至在文档中警告说,"许多用户发现速度完全足够,尽管用egrep取代了内部这段代码将是一个错误.")Pike的正则表达式实现,扩展为支持Unicode,在1992年末与sam一起免费提供,但特别有效的正则表达式搜索算法没有被注意到.