专辑：正则表达式专题(JS版)_正则表达式回溯法原理-Java充电社【公众号：Java充电社】

学习正则表达式，是需要懂点儿匹配原理的。

而研究匹配原理时，有两个字出现的频率比较高：“回溯”。

听起来挺高大上，确实还有很多人对此不明不白的。

因此，本章就简单扼要地说清楚回溯到底是什么东西。

## 内容包括

1. 没有回溯的匹配
2. 有回溯的匹配
3. 常见的回溯形式

## 1. 没有回溯的匹配

假设我们的正则是`/ab{1,3}c/`，其可视化形式是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/b30e57a9-787b-4e21-88b1-bb647c1c17a3.png)

而当目标字符串是"abbbc"时，就没有所谓的“回溯”。其匹配过程是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/88b7039e-ad22-41ca-962f-f3d903a9da1e.png)

其中子表达式`b{1,3}`表示“b”字符连续出现1到3次。

## 2. 有回溯的匹配

如果目标字符串是"abbc"，中间就有回溯。

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/54c95d1b-dbcf-4e4c-a7d0-79988380c648.png)

图中第5步有红颜色，表示匹配不成功。此时`b{1,3}`已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为`b{1,3}`就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式`c`，去匹配字符“c”。当然，此时整个表达式匹配成功了。

图中的第6步，就是“回溯”。

你可能对此没有感觉，这里我们再举一个例子。正则是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/da354b9d-5fba-4197-9760-c8359289b3d5.png)

目标字符串是"abbbc"，匹配过程是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/76daf8cd-2458-4991-8c02-da08806f8a90.png)

其中第7步和第10步是回溯。第7步与第4步一样，此时`b{1,3}`匹配了两个"b"，而第10步与第3步一样，此时`b{1,3}`只匹配了一个"b"，这也是`b{1,3}`的最终匹配结果。

这里再看一个清晰的回溯，正则是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/9cf8da67-b361-4328-b6c4-42f0a26730c8.png)

目标字符串是："acd"ef，匹配过程是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/187138eb-9488-4b82-9092-53201863ca52.png)

图中省略了尝试匹配双引号失败的过程。可以看出`.*`是非常影响效率的。

为了减少一些不必要的回溯，可以把正则修改为`/"[^"]*"/`。

## 3. 常见的回溯形式

正则表达式匹配字符串的这种方式，有个学名，叫回溯法。

回溯法也称试探法，它的基本思想是：从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”。（copy于百度百科）。

本质上就是深度优先搜索算法。**其中退到之前的某一步这一过程，我们称为“回溯”。**从上面的描述过程中，可以看出，路走不通时，就会发生“回溯”。即，**尝试匹配失败时，接下来的一步通常就是回溯。**

道理，我们是懂了。那么JS中正则表达式会产生回溯的地方都有哪些呢？

### 3.1 贪婪量词

之前的例子都是贪婪量词相关的。比如`b{1,3}`，因为其是贪婪的，尝试可能的顺序是从多往少的方向去尝试。首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了。

虽然局部匹配是贪婪的，但也要满足整体能正确匹配。否则，皮之不存，毛将焉附？

此时我们不禁会问，如果当多个贪婪量词挨着存在，并相互有冲突时，此时会是怎样？

答案是，先下手为强！因为深度优先搜索。测试如下：

```javascript
var string = "12345";
var regex = /(\d{1,3})(\d{1,3})/;
console.log( string.match(regex) );
// => ["12345", "123", "45", index: 0, input: "12345"]

```

其中，前面的`\d{1,3}`匹配的是"123"，后面的`\d{1,3}`匹配的是"45"。

### 3.2 惰性量词

惰性量词就是在贪婪量词后面加个问号。表示尽可能少的匹配，比如：

```javascript
var string = "12345";
var regex = /(\d{1,3}?)(\d{1,3})/;
console.log( string.match(regex) );
// => ["1234", "1", "234", index: 0, input: "12345"]

```

其中`\d{1,3}?`只匹配到一个字符"1"，而后面的`\d{1,3}`匹配了"234"。

虽然惰性量词不贪，但也会有回溯的现象。比如正则是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/87a7d597-a9f8-422e-8a42-f411a7041922.png)

目标字符串是"12345"，匹配过程是：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/b228262d-de1d-4624-8b4f-4121958ca1b1.png)

知道你不贪、很知足，但是为了整体匹配成，没办法，也只能给你多塞点了。因此最后`\d{1,3}?`匹配的字符是"12"，是两个数字，而不是一个。

### 3.3 分支结构

我们知道分支也是惰性的，比如`/can|candy/`，去匹配字符串"candy"，得到的结果是"can"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。

分支结构，可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯。

比如正则：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/849764ab-6ff2-4044-a71e-d748ff972148.png)

目标字符串是"candy"，匹配过程：

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/174/cd920822-2634-40ad-9016-893af813c838.png)

上面第5步，虽然没有回到之前的状态，但仍然回到了分支结构，尝试下一种可能。所以，可以认为它是一种回溯的。

## 小结

其实回溯法，很容易掌握的。

简单总结就是，正因为有多种可能，所以要一个一个试。直到，要么到某一步时，整体匹配成功了；要么最后都试完后，发现整体匹配不成功。

1. 贪婪量词“试”的策略是：买衣服砍价。价钱太高了，便宜点，不行，再便宜点。
2. 惰性量词“试”的策略是：卖东西加价。给少了，再多给点行不，还有点少啊，再给点。
3. 分支结构“试”的策略是：货比三家。这家不行，换一家吧，还不行，再换。

既然有回溯的过程，那么匹配效率肯定低一些。相对谁呢？相对那些DFA引擎。

而JS的正则引擎是NFA，NFA是“非确定型有限自动机”的简写。

大部分语言中的正则都是NFA，为啥它这么流行呢？

答：你别看我匹配慢，但是我编译快啊，而且我还有趣哦。

```html
作者：老姚
链接：https://juejin.im/post/5965943ff265da6c30653879
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
```

<a style="display:none" target="_blank" href="https://mp.weixin.qq.com/s/_S1DD2JADnXvpexxaBwLLg" style="color:red; font-size:20px; font-weight:bold">继续收门徒，亲手带，月薪 4W 以下的可以来找我</a>

## 最新资料

1. <a href="https://mp.weixin.qq.com/s?__biz=MzkzOTI3Nzc0Mg==&mid=2247484964&idx=2&sn=c81bce2f26015ee0f9632ddc6c67df03&scene=21#wechat_redirect" target="_blank">尚硅谷 Java 学科全套教程（总 207.77GB）</a>
2. <a href="https://mp.weixin.qq.com/s?__biz=MzkwOTAyMTY2NA==&mid=2247484192&idx=1&sn=505f2faaa4cc911f553850667749bcbb&scene=21#wechat_redirect" target="_blank">2021 最新版 Java 微服务学习线路图 + 视频</a>
3. <a href="https://mp.weixin.qq.com/s?__biz=MzkwOTAyMTY2NA==&mid=2247484573&idx=1&sn=7f3d83892186c16c57bc0b99f03f1ffd&scene=21#wechat_redirect" target="_blank">阿里技术大佬整理的《Spring 学习笔记.pdf》</a>
4. <a href="https://mp.weixin.qq.com/s?__biz=MzkwOTAyMTY2NA==&mid=2247484544&idx=2&sn=c1dfe907cfaa5b9ae8e66fc247ccbe84&scene=21#wechat_redirect" target="_blank">阿里大佬的《MySQL 学习笔记高清.pdf》</a>
5. <a href="https://mp.weixin.qq.com/s?__biz=MzkwOTAyMTY2NA==&mid=2247485167&idx=1&sn=48d75c8e93e748235a3547f34921dfb7&scene=21#wechat_redirect" target="_blank">2021 版 java 高并发常见面试题汇总.pdf</a>
6. <a href="https://mp.weixin.qq.com/s?__biz=MzkwOTAyMTY2NA==&mid=2247485664&idx=1&sn=435f9f515a8f881642820d7790ad20ce&scene=21#wechat_redirect" target="_blank">Idea 快捷键大全.pdf</a>

![](https://itsoku.oss-cn-hangzhou.aliyuncs.com/itsoku/blog/article/1/2883e86e-3eff-404a-8943-0066e5e2b454.png)