正则表达式 - 贪婪模式回溯

# 贪婪模式与非贪婪模式

# 贪婪匹配模式

# 定义

正则表达式去匹配时，会尽量多的匹配符合条件的内容

# 标识符

+，?，*，{n}，{n,}，{n,m}

匹配时，如果遇到上述标识符，代表是贪婪匹配，会尽可能多的去匹配内容

# 示例

1
2
3
4
5
6


var str='aacbacbc';
var reg=/a.*b/;
var res=str.match(reg);

// aacbacb index为0
console.log(res);

上例中，匹配到第一个a后，开始匹配.*，由于是贪婪模式，它会一直往后匹配，直到最后一个满足条件的b为止，因此匹配结果是aacbacb

1
2
3
4
5
6


var str='aacbacbc';
var reg=/ac.*b/;
var res=str.match(reg);

// acbacb index为1
console.log(res);

第一个匹配的是a，然后再匹配下一个字符a时，和正则不匹配，因此匹配失败，index挪到1，接下来匹配成功了ac，继续往下匹配，由于是贪婪模式，尽可能多的去匹配结果，直到最后一个符合要求的b为止，因此匹配结果是acbacb

# 非贪婪匹配模式

# 定义

正则表达式去匹配时，会尽量少的匹配符合条件的内容也就是说，一旦发现匹配符合要求，立马就匹配成功，而不会继续匹配下去(除非有g，开启下一组匹配)

# 标识符

+?，??，*?，{n}?，{n,}?，{n,m}?

可以看到，非贪婪模式的标识符很有规律，就是贪婪模式的标识符后面加上一个?

# 示例

1
2
3
4
5
6


var str='aacbacbc';
var reg=/a.*?b/;
var res=str.match(reg);

// aacb index为0
console.log(res);

上例中，匹配到第一个a后，开始匹配.*?，由于是非贪婪模式，它在匹配到了第一个b后，就匹配成功了，因此匹配结果是aacb

为什么是aacb而不是acb呢？因为前面有提到过一个正在匹配的优先规则: 最先开始的匹配拥有最高的优先权第一个a匹配到了，只要之后没有发生匹配失败的情况，它就会一直匹配下去，直到匹配成功

1
2
3
4
5
6


var str='aacbacbc';
var reg=/ac.*?b/;
var res=str.match(reg);

// acb index为1
console.log(res);

先匹配的a，接下来匹配第二个a时，匹配失败了index变为1，继续匹配ac成功，继续匹配b，由于是非贪婪模式，此时acb已经满足了正则的最低要求了，因此匹配成功，结果为acb

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


var str='aacbacbc';
var reg=/a.*?/;
var res=str.match(reg);

// a index为0
console.log(res);

var reg2=/a.*/;
var res2=str.match(reg2);

// aacbacbc index为0
console.log(res2);

这一个例子则是对示例1的补充，可以发现，当后面没有b时，由于是非贪婪模式，匹配到第一个a就直接匹配成功了而后面一个贪婪模式的匹配则是会匹配所有

# 实例练习

在初步理解了贪婪模式与非贪婪模式后，可以通过练习加深理解

提取HTML中的Div标签

给出一个HTML字符串，如下

1
2


<div><span>用户:<span/><span>张三<span/></div>
<div><span>密码:<span/><span>123456<span/></div>

需求: 提取出div包裹的内容(包括div标签本身)，并将各个结果存入数组

代码: 通过非贪婪模式的全局匹配来完成，如下

1
2
3
4
5


var reg=/<div>.*?<\/div>/g;
var res=str.match(reg);

// ["<div><span>用户:<span/><span>张三<span/></div>", "<div><span>密码:<span/><span>123456<span/></div>"]
console.log(res);

详解: 用到了两个知识点，.*?的非贪婪模式匹配以及g全局匹配

.*?<\/div>代表每次只会匹配一次div，这样可以确保每一个div不会越界

最后的g代表全局匹配，即第一次匹配成功后，会将匹配结果放入数组，然后从下一个index重新开始匹配新的结果

另外: 假设使用了/

.*</div>/g进行贪婪模式的匹配，结果则是

用户:张三

密码:123456

"] 因为贪婪模式匹配了第一个

后会无限贪婪的匹配接下来的字符，直到最后一个符合条件的

为止，导致了将中间所有的div标签都一起匹配上了

提取两个"“中的子串，其中不能再包含”"

示例引用自: 正则表达式之贪婪与非贪婪模式详解(http://www.jb51.net/article/31491.htm)

“The phrase "regular expression" is called "Regex" for short” 需求: 提取两个引号之间的子串，其中不能再包括引号，例如上述的提取结果应该是: “regular expression” 与 “Regex”(每一个结束的"后面都接空格)

1
2
3
4
5
6
7
8


错误解法: 通过如下的非贪婪匹配(请注意空格)

var str='"The phrase \"regular expression\" is called \"Regex\" for short"';
var reg=/".*?" /g;
var res=str.match(reg);

// ['"The phrase "regular expression"  ', '"Regex"  ']
console.log(res);

可以看到，上述的匹配完全就是匹配错误了，这个正则匹配到第一个符合条件的"+空格后就自动停下来了

1
2
3
4
5
6
7


正确解法: 使用贪婪模式进行匹配

var reg=/"[^"]*" /g;
var res=str.match(reg);

// ['"regular expression" ', '"Regex" ']
console.log(res);

这个匹配中

从第一个"开始匹配，接下来到12位时(“r的”)，不满足{FNXX==XXFN}，也不满足之后的"+空格，因此匹配失败了，index挪到下一个，开始下一次匹配

第二个匹配从"r的"开始，一直匹配到n"空格的空格，这一组刚刚好匹配成功(因为最后符合了正则的"空格)，匹配好了"regular expression"空格

第三个匹配匹配到了"Regex"空格(过程不再复述)

到最后时，仅剩一个"直接匹配失败(因为首先得符合"才能开始挣扎匹配)

至此，正则匹配结束，匹配成功，并且符合预期

最后: 这个例子相对来说复杂一点，如要更好的理解，可以参考引用来源中的文章，里面有就原理进行介绍另外，参考文章中还有对非贪婪模式的匹配失败，回溯影响性能等特性进行原理分析与讲解

# 回溯现象与匹配失败

你真的已经理解了贪婪模式和非贪婪模式么？

# 回溯现象

不知道对上面最后例子中提到的回溯这词有没有概念？这里仍然以上例引用来源中的示例来分析

原字符串

“Regex”

# 贪婪匹配过程分析

“.” 第一个"取得控制权，匹配正则中的"，匹配成功，控制权交给.

.*取得控制权后，匹配接下来的字符，.代表匹配任何字符，*代表可匹配可不匹配，这属于贪婪模式的标识符，会优先尝试匹配，于是接下来从1位置处的R开始匹配，依次成功匹配了R，e，g，e，x，接着继续匹配最后一个字符"，匹配成功，这时候已经匹配到了字符串的结尾，所以.*匹配结束，将控制符交给正则式中最后的"

“取得控制权后，由于已经是到了字符串的结尾，因此匹配失败，向前查找可供回溯的状态，控制权交给.*，.*让出一个字符”，再把控制权交给"，此时刚好匹配成功

至此，整个正则表达式匹配完毕，匹配结果为"Regex"，匹配过程中回溯了1次

# 非贪婪匹配表达式

1

".*?"

第一个"取得控制权，匹配正则中的"，匹配成功，控制权交给.*?

.*?取得控制权后，由于这是非贪婪模式下的标识符，因此在可匹配可不匹配的情况下会优先不匹配，因此尝试不匹配任何内容，将控制权交给"，此时index在1处(R字符处)

“取得控制权后，开始匹配1处的R，匹配失败，向前查找可供回溯的状态，控制权交给.?，.?吃进一个字符，index到了2处，再把控制权交给”

“取得控制权后，开始匹配2处的e，匹配失败，重复上述的回溯过程，直到.*?吃进了x字符，再将控制权交给”

“取得控制权后，开始匹配6处的”，匹配成功

至此，整个正则表达式匹配完毕，匹配结果为"Regex”，匹配过程中回溯了5次

优化去除回溯

上述的贪婪匹配中，出现了一次回溯现象，其实也可以通过优化表达式来防止回溯的，比如

1

"[^"]*"

这个表达式中构建了一个子表达式-[]中的^"，它的作用是排除"匹配，这样*的贪婪匹配就不会主动吃进"，这样最后就直接是"匹配"，匹配成功，不会进行回溯

# 总结

上述的分析中可以看出，在匹配成功的情况下，贪婪模式进行了更少的回溯(可以自行通过更多的实验进行验证)，因此在应用中，在对正则掌握不是很精通的情况下，可以优先考虑贪婪模式的匹配，这样可以避免很多性能上的问题

匹配失败的情况

上述的回溯分析都是基于匹配成功的情况，那如果是匹配失败呢？

1
2


var str = '"Regex'
var reg = /"[^"]*"/g;

这个原字符中，没有最后的"，因此匹配是会失败的，它的过程大致如下

“匹配”，接着[]的^“与*匹配R，e，g，e，x

接着到了最后，“获取控制权，由于到了最后，开始回溯

依次回溯的结果是让出x，e，g，e，R，直到已经无法再让出字符，第一轮匹配失败

接着index开始往下挪，依次用"匹配R，e，g，e，x都失败了，一直到最后也没有再匹配到结果，因此此次正则表达式的匹配失败，没有匹配到结果(或者返回null)

那非贪婪模式呢？

1

/"[^"]*?"/g

“匹配”，接着*尝试不匹配，“匹配R，失败，然后回溯，*吃进R

接下来类似于上一步，*依次回溯吃进e，g，e，x，一直到最后，*再次回溯想吃进时，已经到了字符串结尾了，无法继续，因此第一轮匹配失败

接着index开始往下挪，依次用"匹配R，e，g，e，x都失败了，返回null

# 总结

通过匹配失败的例子可以看出贪婪和非贪婪的模式区别。贪婪是先吃进，回溯再让出，非贪婪是先忽略，回溯再吃进

而且，在匹配失败的情况下，贪婪模式也会进行不少的回溯(非贪婪当然一直都很多回溯)

但是，实际情况中是可以通过子表达式优化的，比如构建^xxx，可以当匹配到不符合条件的时候提前匹配失败，这样就会少很多回溯

1
2


var str = '"cccccc'
var reg = /"[^"c]*"/g;

这个由于直接排除了c，因此*不会吃进它，直接就匹配失败了，减少了很多回溯(当然，上述只是最简单的例子，实际情况要更复杂)

# 非贪婪匹配的效率

可能有不少的人和我一样，有过这样的经历：当我们要匹配类似 “内容” 或者 “[b]加粗[/b]” 这样的文本时，我们根据正向预搜索功能写出这样的表达式："([^<]|<(?!/td>))” 或者 “((?!).)"。

当发现非贪婪匹配之时，恍然大悟，同样功能的表达式可以写得如此简单：".?"。顿时间如获至宝，凡是按边界匹配的地方，尽量使用简捷的非贪婪匹配 “.?"。特别是对于复杂的表达式来说，采用非贪婪匹配 “.*?” 写出来的表达式的确是简练了许多。

然而，当一个表达式中，有多个非贪婪匹配时，或者多个未知匹配次数的表达式时，这个表达式将可能存在效率上的陷阱。有时候，匹配速度慢得莫名奇妙，甚至开始怀疑正则表达式是否实用。

# 效率陷阱的产生：

在本站基础文章里，对非贪婪匹配的描述中说到：“如果少匹配就会导致整个表达式匹配失败的时候，与贪婪模式类似，非贪婪模式会最小限度的再匹配一些，以使整个表达式匹配成功。”

具体的匹配过程是这样的：

“非贪婪部分” 先匹配最少次数，然后尝试匹配 “右侧的表达式”。如果右侧的表达式匹配成功，则整个表达式匹配结束。如果右侧表达式匹配失败，则 “非贪婪部分” 将增加匹配一次，然后再尝试匹配 “右侧的表达式”。如果右侧的表达式又匹配失败，则 “非贪婪部分” 将再增加匹配一次。再尝试匹配 “右侧的表达式”。依此类推，最后得到的结果是 “非贪婪部分” 以尽可能少的匹配次数，使整个表达式匹配成功。或者最终仍然匹配失败。当一个表达式中有多个非贪婪匹配，以表达式 “d(\w+?)d(\w+?)z” 为例，对于第一个括号中的 “\w+?” 来说，右边的 “d(\w+?)z” 属于它的 “右侧的表达式”，对于第二个括号中的 “\w+?” 来说，右边的 “z” 属于它的 “右侧的表达式”。

当 “z” 匹配失败时，第二个 “\w+?” 会 “增加匹配一次”，再尝试匹配 “z”。如果第二个 “\w+?” 无论怎样 “增加匹配次数”，直至整篇文本结束，“z” 都不能匹配，那么表示 “d(\w+?)z” 匹配失败，也就是说第一个 “\w+?” 的 “右侧” 匹配失败。此时，第一个 “\w+?” 会增加匹配一次，然后再进行 “d(\w+?)z” 的匹配。循环前面所讲的过程，直至第一个 “\w+?” 无论怎么 “增加匹配次数”，后边的 “d(\w+?)z” 都不能匹配时，整个表达式才宣告匹配失败。

其实，为了使整个表达式匹配成功，贪婪匹配也会适当的“让出”已经匹配的字符。因此贪婪匹配也有类似的情况。当一个表达式中有较多的未知匹配次数的表达式时，为了让整个表达式匹配成功，各个贪婪或非贪婪的表达式都要进行尝试减少或增加匹配次数，由此容易形成一个大循环的尝试，造成了很长的匹配时间。本文之所以称之为“陷阱”，因为这种效率问题往往不易察觉。

举例：“d(\w+?)d(\w+?)d(\w+?)z” 匹配 “ddddddddddd…” 时，将花费较长一段时间才能判断出匹配失败。

# 效率陷阱的避免：

避免效率陷阱的原则是：避免“多重循环”的“尝试匹配”。并不是说非贪婪匹配就是不好的，只是在运用非贪婪匹配的时候，需要注意避免过多“循环尝试”的问题。

情况一：对于只有一个非贪婪或者贪婪匹配的表达式来说，不存在效率陷阱。也就是说，要匹配类似 “ 内容 ” 这样的文本，表达式 “([^<]|<(?!/td>))” 和 “((?!).)” 和 “.*?” 的效率是完全相同的。

情况二：如果一个表达式中有多个未知匹配次数的表达式，应防止进行不必要的尝试匹配。

比如，对表达式 “” 来说，如果前面部分表达式在遇到 “” 却匹配失败，将导致第一个 “.?” 增加匹配次数再尝试。而对于表达式真正目的，让第一个 “.?” 增加匹配成“vbscript’>”是不对的，因此这种尝试是不必要的尝试。

因此，对依靠边界来识别的表达式，不要让未知匹配次数的部分跨过它的边界。前面的表达式中，第一个 “.?” 应该改写成 “[^’]"。后边那个 “.?” 的右边再没有未知匹配次数的表达式，因此这个非贪婪匹配没有效率陷阱。于是，这个匹配脚本块的表达式，应该写成："<script language=’([^’])’>(.*?)” 更好。