为什么大多数语言都无法有效地实现通配符正则表达式？

Question

我获得了以下关于许多现代语言中正则表达式实现的文章的链接.

http://swtch.com/~rsc/regexp/regexp1.html

TL; DNR:某些正则表达式(例如(a?)^na^n固定$ n $)需要与指数时间匹配,例如,a^n因为它在匹配?节时通过回溯字符串实现.通过保留状态列表将这些实现为NFA,可以明显地提高效率

每种语言实际上是如何实现这些细节不是很详细(以及该物品是旧的),但我很好奇:什么,如果有的话,使用的是NFA而不是其他实现技术的缺点.我能想到的唯一的事情是,大多数库的所有花里胡哨或者a)为所有这些功能构建NFA是不切实际的,或者b)上面的表达式和其他表达式之间存在一些冲突的性能问题,可能更多共同的,操作.

Answer 1

虽然有可能构建能很好地处理这些复杂情况的DFA(由Henry Spencer编写的Tcl RE引擎,这是一个示例证明;文章链接表明它与其性能数据),但它也非常难.

但有一个关键的事情是,如果您可以检测到您从不需要匹配的组信息,那么(对于许多RE,尤其是那些没有内部反向引用的RE),可以将RE转换为仅使用括号进行分组的 RE,从而允许更高效的RE生成(所以(a?){n}a{n}- 我使用现代传统语法 - 变得有效等同a{n,2n}).反向引用打破了主要的优化; 亨利的RE代码(上面提到)中有一条代码注释将它们描述为"来自黑色泻湖的特征".这是我在代码中读过的最好的评论之一(除了描述编码算法的学术论文的参考).

另一方面,具有递归下降评估方案的Perl/PCRE样式引擎可以将更加精确的语义集合归因于混合贪婪RE以及许多其他内容.(在极端情况下,递归模式 - (?R) 等等 - 使用自动机理论方法是完全不可能的.它们需要堆栈匹配,使它们形式上不是正则表达式.)

在实际层面上,构建NFA的成本和然后编译的DFA可能会非常高.您需要聪明的缓存才能使它不会太昂贵.而且在实际层面上,PCRE和Perl实现已经有更多的开发人员工作应用于它们.