正则表达式中的回溯过程

请注意：本文编写于 2019-07-16，其中某些信息可能已经失去时效性。

本文所有正则表达式皆为 JavaScript 正则形式 本文所有图片和实例都来自：知乎-老姚：正则表达式回溯法原理

回溯算法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就「回溯」返回，尝试别的路径。回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为「回溯点」。许多复杂的，规模较大的问题都可以使用回溯法，有「通用解题方法」的美称。 来自「百度百科」

正则中的回溯

没有回溯过程的正则匹配

正则表达式：/ab{1,3}c/ 目标字符串：abbbc

正则表达式可视化

正则表达式可视化

正则匹配过程可视化

正则匹配过程可视化

有回溯过程的正则匹配

正则表达式：/ab{1,3}c/ 目标字符串：abbc

正则表达式可视化

正则表达式可视化

正则匹配过程可视化

正则匹配过程可视化

分析

从有回溯过程的正则匹配过程可视化图能够看到，进行到第四步时 /ab{1,3}c/ 已经匹配到了字符串 abbc 中的 abb 到第五步时正则表达式会继续尝试匹配第三个 b 然而字符串中已经没有更多的 b 可供匹配，因此我们能够看到第五步中 c 标有红色，代表的是正则匹配第三个 b 失败。

至此整个正则匹配的过程并没有完成，正则没有直接返回匹配失败而是：

1. 将匹配节点回退到字符串 abbc 中的 abb 后；
2. 结束 b{1,3} 的匹配开始 c 的匹配；

如上两步也是图中第六步所做的事情，整个过程就是「回溯」的过程。

这里我仅引用了 知乎-老姚：正则表达式回溯法原理 中的第一个也是最简单的一个例子作为讲解「正则中的回溯过程」的实例，而该文中还有两个更能体现回溯过程的实例如果感兴趣的话可以自行查看。

参考

知乎-老姚：正则表达式回溯法原理 百度百科：回溯算法