在Google Chrome中学习正则表达式回溯

Question

我正在努力学习和理解javascript中的正则表达式，并想了解javascript中正则表达式的回溯概念。有没有人能告诉我源代码或者是Google Chrome (V8引擎)中的javascript用来解析正则表达式的算法，看看它是如何回溯的。由于谷歌的V8引擎是开源的，这肯定不难。

Answer 1

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

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

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

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

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

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

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

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

当您将上限和下限添加到量词时，您可以想象添加了一个计数器来记录匹配A的次数。根据计数器的不同，两个分支中的任何一个在某个计数器上都不能用于分支。

因此，您将使用上面的搜索树执行搜索，每次遇到问题(无法到达树的目标状态)时，您将回溯并尝试其他分支。

希望这能帮助你开始了解回溯的概念。