sir*_*usa 8 regex optimization oniguruma vm-implementation
我正在尝试基于探索Ruby的正则表达式算法中概述的回溯方法来实现正则表达式匹配器。编译后的正则表达式将转换为虚拟机命令数组；为了回溯，当前命令和输入字符串索引以及捕获组信息保留在堆栈中。
在“ 正则表达式匹配：虚拟机方法 Cox”中提供了有关如何将某些正则表达式组件编译为VM命令的更多详细信息，尽管所讨论的实现有所不同。根据这些文章，我的实现对于标准分组，字符类和重复组件非常有效。
现在，我想看看这种实现有哪些扩展和优化选项。Cox在他的文章中提供了许多有关DFA / NFA方法的有用信息，但是有关回溯方法的扩展或优化技术的信息却很少。
例如，关于他提到的反向引用
回溯在回溯实现中很简单。
并给出了DFA方法的想法。但是对我来说，尚不清楚如何通过VM方法“轻松地”完成。到达backreference命令后，您必须将来自相应组的先前匹配的字符串编译到另一组VM命令中，并以某种方式将这些命令合并到当前VM中，或者维护第二个VM并暂时将执行切换到该VM。
他还提到了通过使用超前方式在重复中可能进行的优化，但是没有详细说明如何实现。在我看来，这可以用来减少回溯堆栈上的项目数量。
tl; dr针对基于VM的回溯正则表达式实现存在哪些常规优化技术，它们如何工作？请注意，我并不是在寻找特定于某种编程语言的优化，而是在寻找这种正则表达式实现的通用技术。
编辑：如第一个链接中所述，Oniguruma库正是使用基于堆栈的回溯方法来实现正则表达式匹配器。也许有人可以解释该库所做的优化，这些优化可以推广到其他实现中。不幸的是，该库似乎未提供有关源代码的任何文档，并且该代码也缺少注释。
编辑2：在阅读有关解析表达语法（PEG）的文章时，我偶然发现了一篇关于Lua PEG实现的论文，该论文利用了类似的基于VM的方法。本文提到了一些优化选项，以减少已执行的VM命令的数量以及回溯堆栈的不必要增长。
我建议你看完整的讲座，很有趣，但这里是大纲：
\n\n回溯的复杂性爆炸。发生这种情况时，模式中存在歧义（[a-x]*[a-x0-9]*z例如在视频中），因此引擎必须回溯并测试所有条件，直到确定模式确实（或不）匹配。
\n\n\n它最多可能需要 O(N\xe1\xb5\x96)，其中 p 是模式的“模糊性度量”。\n 为了获得 O(pN)，我们需要避免一次又一次地评估等效线程。
\n\n...
\n
解决方案：\n一步将所有线程调整一个字符，“广度优先”执行会导致线性复杂性。
希望这可以帮助！
\n\nPS Lector 的存储库
\n