回溯正则表达式实现的优化技术

Question

我正在尝试基于回溯法实现正则表达式匹配器，该方法在Exploring Ruby’s Regular Expression Algorithm中概述。编译后的正则表达式被翻译成虚拟机命令数组；对于回溯，当前命令和输入字符串索引以及捕获组信息在堆栈上维护。

在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命令数量和回溯堆栈的不必要增长。

- siracusa

---

我不确定Perl的正则表达式解释器是否基于虚拟机，但它肯定是一种混合的NFA/DFA方法，并且有无数的优化。有关详细信息，请参见perlreguts。我特别喜欢peep-hole optimization，它使用Boyer-Moore来快速搜索最长静态字符串，然后扫描周围的内容（我曾经自己想出这个想法，但后来一个同事给我发了那个链接！） - Adam Katz

@AdamKatz 感谢您提供的链接。它已经包含了一些有用的提示，可以进行可能的优化（例如对于我的用例非常相关的许多固定字符串替代的TRIE构造）。我还没有找到时间研究regcomp.c，但是乍一看，它包括了很多解释性注释。 - siracusa

有趣。你在开发新的正则表达式实现吗？我认为golang的re2模块是基于Cox的建议进行建模的。因此，值得看一下re2的实现。 - wp78de

@wp78de 是的，但这是一种可能对大众不太感兴趣的语言（TeX/LaTeX）。唯一可用的实现相当笨重，在处理较大的正则表达式或在循环中使用时非常慢，并且存在一些其他缺陷。因此，我正在尝试编写一个更轻量级的版本，但对输入类型有一定限制。由于（La）TeX是一种解释性语言，尽可能进行优化对于速度至关重要。 - siracusa

Answer 1

我建议你观看完整的讲座，非常有趣，但以下是大纲：

• 回溯中的复杂度爆炸Complexity explosion。 当模式（例如视频中的[a-x]*[a-x0-9]*z）具有歧义时，引擎必须回溯并测试所有条件，直到确定模式是否匹配。

  它可能需要O(Nᵖ)的时间，其中p是模式的“歧义度量”。为了获得O(pN)，我们需要避免一遍又一遍地评估等效线程。

  ...

  解决方案：在一步中通过一个字符调整所有线程，“广度优先”执行结果具有线性复杂度。

• 节省每一点性能的技巧

• std::regex内部

希望这可以帮助！

附言：Lector的代码库

- nonForgivingJesus

---

谢谢你的视频。我还没有时间研究视频中提到的所有方法，例如Shift-Or听起来也很有趣。你能详细说明一下你提到的优化是如何工作的吗？从视频中我了解到他们改变了线程的执行顺序，但这不应该会产生相同数量的回溯，只是顺序不同吗？ - siracusa

在这种方法中，我们消除了相同操作的重复。可以将其视为执行树。靠近顶部的是“已批准的”，您不需要重新评估这些操作。因此，您可以只获取先前状态中拥有的数据并使用它。您可以在此时间代码上看到差异。总之：他建议的方法，我们可以生成3个线程：第一个考虑[a-x]*成功，第二个考虑[a-x0-9]成功但第一个失败，第三个仅考虑z将成功。 - nonForgivingJesus