javascript - 学习 Google Chrome 中的正则表达式回溯

Question

我正在尝试学习和理解javascript中的正则表达式，并且想了解javascript中正则表达式回溯的概念。任何人都可以向我指出源代码或向我介绍 Google Chrome(V8 引擎)中的 javascript 用于解析正则表达式并检查它如何回溯的算法。由于 Google 的 V8 引擎是开源的，这一定不难。

Answer 1

V8 引擎的源代码并不是一个开始学习回溯的好地方。

乍一看，根据我阅读 Java 实现 Pattern 的经验来看类，文件 trunk/src/x87/regexp-macro-assembler-x87.cc 包含JS RegExp的源代码。您基本上是在源代码中的级别阅读汇编。

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

<小时/>

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

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

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

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

对于(惰性)量词 0 或更多 A*? ，与上面基本相同，只不过会先尝试到下一个原子的分支。

当你给量词添加上限和下限时，你可以想象添加一个计数器来记录多少次 A已匹配。根据计数器的不同，任一分支将无法在特定计数器处进行分支。

因此，您将使用上面的搜索树执行搜索，每次遇到困难(无法达到树的目标状态)时，您都会回溯并尝试另一个分支。

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