在谷歌浏览器中学习正则表达式回溯

Learning Regular Expressions Backtracking in Google Chrome

本文关键字：正则表达式回溯学习谷歌浏览器更新时间：2023-09-26

我正在尝试学习和理解javascript中的正则表达式，并希望了解javascript中正则表达式回溯的概念。任何人都可以指出我的源代码或向我推荐谷歌浏览器（V8引擎）中的javascript用于解析正则表达式并检查它如何回溯的算法。由于谷歌的V8引擎是开源的，这肯定不难。

V8 Engine 的源代码并不是一个开始学习回溯的友好场所。

乍一看，根据我阅读Java的Pattern类实现的经验，文件trunk/src/x87/regexp-macro-assembler-x87.cc包含JS正则表达式的源代码。您基本上是在源代码中存在的级别读取程序集。

您可能对 trunk/src/runtime/runtime-regexp.cc 感兴趣，其中包含 RegEx 方法的实现。但是，该代码不包含有关RegExp内部工作的任何内容。

回溯的概念类似于搜索算法。由于您不知道结果，因此您将执行暴力搜索，但根据您定义搜索顺序的方式，您可以更快或更慢地到达结果。

对于串联，每个节点以线性方式连接到下一个节点。没有分支，所以没有回溯。

对于分支P1|P2|...|Pn，您可以将其视为具有n节点的搜索树，您将首先尝试节点P1，然后尝试P2，...最后Pn.分支中的所有n节点都连接到续集原子，因此如果任何节点成功，它将移动到续集原子，并且只有在下一个原子上的所有可能性都用尽时回溯分支中的下一个节点。

对于（贪婪的）量词 0 或更多 A* ，你可以把它想象成一个有 2 个分支的节点，一个分支A然后回到自身，另一个分支去下一个原子。将首先尝试分支到 A。请注意，这是一个简化的描述，因为引擎还必须处理 0 长度匹配。

对于（惰性）量词 0 或更多 A*?，它基本上与上面相同，只是将首先尝试分支到下一个原子。

当您将上限和下限添加到量词时，您可以想象添加一个计数器来记录A匹配的次数。根据计数器的不同，任一分支都无法在某些柜台进行分支。

因此，您将使用上面的搜索树执行搜索，每次遇到卡住（无法达到树的目标状态）时，您都会回溯并尝试其他分支。

希望这有助于您开始回溯的概念。