我正在尝试基于回溯法实现正则表达式匹配器,该方法在Exploring Ruby’s Regular Expression Algorithm中概述。编译后的正则表达式被翻译成虚拟机命令数组;对于回溯,当前命令和输入字符串索引以及捕获组信息在堆栈上维护。
在Regular Expression Matching: the Virtual Machine Approach中,Cox提供了有关如何将某些正则表达式组件编译为VM命令的更详细信息,尽管所讨论的实现略有不同。基于这些文章,我的实现对于标准分组、字符类和重复组件效果很好。
现在,我想看看这种实现的扩展和优化选项。 Cox在他的文章中提供了关于DFA / NFA方法的大量有用信息,但是关于回溯方法的扩展或优化技术的信息有点稀少。
例如,关于反向引用,他说
他还提到了在重复中可能使用look-ahead进行优化的可能性,但没有详细说明如何工作。我认为这可以用于减少回溯堆栈中的项目数。 tl;dr:基于VM的回溯正则表达式实现存在哪些通用的优化技术,它们是如何工作的?请注意,我不是寻找特定编程语言的优化,而是针对此类正则表达式实现的通用技术。
编辑:如第一个链接中所述,Oniguruma库使用了基于堆栈的回溯方法实现了正则表达式匹配器。也许有人可以解释该库所做的优化,这些优化可以推广到其他实现。不幸的是,该库似乎没有提供有关源代码的任何文档,代码也缺乏注释。
编辑2:在阅读有关解析表达式语法(PEG)的文章时,我偶然发现了有关Lua PEG实现的论文,该论文使用了类似的基于VM的方法。该论文提到了几种优化选项,以减少执行的VM命令数量和回溯堆栈的不必要增长。
在Regular Expression Matching: the Virtual Machine Approach中,Cox提供了有关如何将某些正则表达式组件编译为VM命令的更详细信息,尽管所讨论的实现略有不同。基于这些文章,我的实现对于标准分组、字符类和重复组件效果很好。
现在,我想看看这种实现的扩展和优化选项。 Cox在他的文章中提供了关于DFA / NFA方法的大量有用信息,但是关于回溯方法的扩展或优化技术的信息有点稀少。
例如,关于反向引用,他说
并提供了一种DFA方法的思路。但是我不清楚如何使用VM方法“轻松”完成这项工作。当到达反向引用命令时,您必须将相应组中先前匹配的字符串编译成另一个VM命令列表,并将这些命令以某种方式合并到当前VM中,或者维护第二个VM并临时切换执行。在回溯实现中,反向引用很简单。
他还提到了在重复中可能使用look-ahead进行优化的可能性,但没有详细说明如何工作。我认为这可以用于减少回溯堆栈中的项目数。 tl;dr:基于VM的回溯正则表达式实现存在哪些通用的优化技术,它们是如何工作的?请注意,我不是寻找特定编程语言的优化,而是针对此类正则表达式实现的通用技术。
编辑:如第一个链接中所述,Oniguruma库使用了基于堆栈的回溯方法实现了正则表达式匹配器。也许有人可以解释该库所做的优化,这些优化可以推广到其他实现。不幸的是,该库似乎没有提供有关源代码的任何文档,代码也缺乏注释。
编辑2:在阅读有关解析表达式语法(PEG)的文章时,我偶然发现了有关Lua PEG实现的论文,该论文使用了类似的基于VM的方法。该论文提到了几种优化选项,以减少执行的VM命令数量和回溯堆栈的不必要增长。
regcomp.c
,但是乍一看,它包括了很多解释性注释。 - siracusa