【正则表达式系列】贪婪与非贪婪模式
前言
本文属于 正则表达式系列文章之一，更多请前往 正则表达式系列
贪婪模式和非贪婪模式是正则匹配中的重要特性 在理解贪婪和非贪婪的区别时，可以根据实例，一步一步的循序渐进
大纲
-
匹配规则简介
-
贪婪模式与非贪婪模式快速理解
-
实例练习
-
回溯现象与匹配失败
匹配规则简介
var str='aabcab';
var reg=/ab/;
var res=str.match(reg);
// ab index 为 1
console.log(res);
要快速理解正则的匹配规则，可以先尝试理解上述的例子
匹配步骤是这样的:
-
初始
index=0，匹配到了字符a -
接下来匹配下一个字符
a，但是由于aa和/ab/不匹配，因此此次匹配失败 -
index挪到下一个，从1开始，又重新匹配了a -
接下来匹配下一个字符
b，刚好和/ab/匹配，因此此次匹配成功，返回了ab，index=1 -
如果正则的匹配后面有
g这种关键字，则会继续开始下一组的匹配(但是本例中没有g，因此只有一组结果)
要点
- 最先开始的匹配拥有最高的优先权
这一个要点的详细解释是: 例如第一个匹配的字符是a，假设之后的匹配没有出现匹配失败的情况。则它将一直匹配下去，直到匹配完成，也就是说index=0不会变，直到匹配完成(如果出现匹配失败并且无法回溯，index才会继续往下挪)
这一点适用于下面的贪婪模式与非贪婪模式中(并且优先级高于它们)，因此请谨记
贪婪模式与非贪婪模式快速理解
贪婪匹配模式
定义
正则表达式去匹配时，会尽量多的匹配符合条件的内容
标识符
+，?，*，{n}，{n,}，{n,m}
匹配时，如果遇到上述标识符，代表是贪婪匹配，会尽可能多的去匹配内容
示例
var str='aacbacbc';
var reg=/a.*b/;
var res=str.match(reg);
// aacbacb index为0
console.log(res);
上例中，匹配到第一个a后，开始匹配.*，由于是贪婪模式，它会一直往后匹配，直到最后一个满足条件的b为止，因此匹配结果是aacbacb
示例2
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}?
可以看到，非贪婪模式的标识符很有规律，就是贪婪模式的标识符后面加上一个?
示例
var str='aacbacbc';
var reg=/a.*?b/;
var res=str.match(reg);
// aacb index为0
console.log(res);
上例中，匹配到第一个a后，开始匹配.*?，由于是非贪婪模式，它在匹配到了第一个b后，就匹配成功了，因此匹配结果是aacb
为什么是aacb而不是acb呢？
因为前面有提到过一个正在匹配的优先规则: 最先开始的匹配拥有最高的优先权
第一个a匹配到了，只要之后没有发生匹配失败的情况，它就会一直匹配下去，直到匹配成功
示例2
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
示例3
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字符串，如下
其它元素
<div><span>用户:<span/><span>张三<span/></div>
<div><span>密码:<span/><span>123456<span/></div>
其它元素
需求: 提取出div包裹的内容(包括div标签本身)，并将各个结果存入数组
代码: 通过非贪婪模式的全局匹配来完成，如下
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，这样可以确保每一个div不会越界 -
最后的
g代表全局匹配，即第一次匹配成功后，会将匹配结果放入数组，然后从下一个index重新开始匹配新的结果
另外: 假设使用了/<div>.*<\/div>/g进行贪婪模式的匹配，结果则是
["<div><span>用户:<span/><span>张三<span/></div><div><span>密码:<span/><span>123456<span/></div>"]
因为贪婪模式匹配了第一个<div>后会无限贪婪的匹配接下来的字符，直到最后一个符合条件的</div>为止，导致了将中间所有的div标签都一起匹配上了
提取两个""中的子串，其中不能再包含""
示例引用自: 正则表达式之 贪婪与非贪婪模式详解
"The phrase \"regular expression\" is called \"Regex\" for short"
需求: 提取两个引号之间的子串，其中不能再包括引号，例如上述的提取结果应该是: "regular expression" 与 "Regex"(每一个结束的"后面都接空格)
错误解法: 通过如下的非贪婪匹配(请注意空格)
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);
可以看到，上述的匹配完全就是匹配错误了，这个正则匹配到第一个符合条件的"+空格后就自动停下来了
正确解法: 使用贪婪模式进行匹配
var reg=/"[^"]*" /g;
var res=str.match(reg);
// ['"regular expression" ', '"Regex" ']
console.log(res);
这个匹配中
-
从第一个
"开始匹配，接下来到12位时("r的")，不满足[^"]，也不满足之后的"+空格，因此匹配失败了，index挪到下一个，开始下一次匹配 -
第二个匹配从
"r的"开始，一直匹配到n"空格的空格，这一组刚刚好匹配成功(因为最后符合了正则的"空格)，匹配好了"regular expression"空格 -
第三个匹配匹配到了
"Regex"空格(过程不再复述) -
到最后时，仅剩一个
"直接匹配失败(因为首先得符合"才能开始挣扎匹配) -
至此，正则匹配结束，匹配成功，并且符合预期
最后: 这个例子相对来说复杂一点，如要更好的理解，可以参考引用来源中的文章，里面有就原理进行介绍 另外，参考文章中还有对非贪婪模式的匹配失败，回溯影响性能等特性进行原理分析与讲解
回溯现象与匹配失败
你真的已经理解了贪婪模式和非贪婪模式么？
回溯现象
不知道对上面最后例子中提到的回溯这词有没有概念？
这里仍然以上例引用来源中的示例来分析
原字符串
"Regex"
贪婪匹配过程分析
".*"
-
第一个
"取得控制权，匹配正则中的"，匹配成功，控制权交给.* -
.*取得控制权后，匹配接下来的字符，.代表匹配任何字符，*代表可匹配可不匹配，这属于贪婪模式的标识符，会优先尝试匹配，于是接下来从1位置处的R开始匹配，依次成功匹配了R，e，g，e，x，接着继续匹配最后一个字符"，匹配成功，这时候已经匹配到了字符串的结尾，所以.*匹配结束，将控制符交给正则式中最后的" -
"取得控制权后，由于已经是到了字符串的结尾，因此匹配失败，向前查找可供回溯的状态，控制权交给.*，.*让出一个字符"，再把控制权交给"，此时刚好匹配成功 -
至此，整个正则表达式匹配完毕，匹配结果为
"Regex"，匹配过程中回溯了1次
非贪婪匹配表达式
".*?"
-
第一个
"取得控制权，匹配正则中的"，匹配成功，控制权交给.*? -
.*?取得控制权后，由于这是非贪婪模式下的标识符，因此在可匹配可不匹配的情况下会优先不匹配，因此尝试不匹配任何内容，将控制权交给"，此时index在1处(R字符处) -
"取得控制权后，开始匹配1处的R，匹配失败，向前查找可供回溯的状态，控制权交给.*?，.*?吃进一个字符，index到了2处，再把控制权交给" -
"取得控制权后，开始匹配2处的e，匹配失败，重复上述的回溯过程，直到.*?吃进了x字符，再将控制权交给” -
"取得控制权后，开始匹配6处的"，匹配成功 -
至此，整个正则表达式匹配完毕，匹配结果为”Regex”，匹配过程中回溯了
5次
优化去除回溯
上述的贪婪匹配中，出现了一次回溯现象，其实也可以通过优化表达式来防止回溯的，比如
"[^"]*"
这个表达式中构建了一个子表达式-[]中的^"，它的作用是排除"匹配，这样*的贪婪匹配就不会主动吃进"，这样最后就直接是"匹配"，匹配成功，不会进行回溯
总结
上述的分析中可以看出，在匹配成功的情况下，贪婪模式进行了更少的回溯(可以自行通过更多的实验进行验证)，因此在应用中，在对正则掌握不是很精通的情况下，可以优先考虑贪婪模式的匹配，这样可以避免很多性能上的问题
匹配失败的情况
上述的回溯分析都是基于匹配成功的情况，那如果是匹配失败呢？
var str = '"Regex'
var reg = /"[^"]*"/g;
这个原字符中，没有最好的"，因此匹配是会失败的，它的过程大致如下
-
"匹配"，接着[]的^"与*匹配R，e，g，e，x -
接着到了最后，
"获取控制权，由于到了最后，开始回溯 -
依次回溯的结果是
*让出x，e，g，e，R，直到*已经无法再让出字符，第一轮匹配失败 -
接着
index开始往下挪，依次用"匹配R，e，g，e，x都失败了，一直到最后也没有再匹配到结果，因此此次正则表达式的匹配失败，没有匹配到结果(或者返回null)
那非贪婪模式呢？
/"[^"]*?"/g
-
"匹配"，接着*尝试不匹配，"匹配R，失败，然后回溯，*吃进R -
接下来类似于上一步，
*依次回溯吃进e，g，e，x，一直到最后，*再次回溯想吃进时，已经到了字符串结尾了，无法继续，因此第一轮匹配失败 -
接着
index开始往下挪，依次用"匹配R，e，g，e，x都失败了，返回null
总结
通过匹配失败的例子可以看出贪婪和非贪婪的模式区别。贪婪是先吃进，回溯再让出，非贪婪是先忽略，回溯再吃进
而且，在匹配失败的情况下，贪婪模式也会进行不少的回溯(非贪婪当然一直都很多回溯)
但是，实际情况中是可以通过子表达式优化的，比如构建^xxx，可以当匹配到不符合条件的时候提前匹配失败，这样就会少很多回溯
var str = '"cccccc'
var reg = /"[^"c]*"/g;
这个由于直接排除了c，因此*不会吃进它，直接就匹配失败了，减少了很多回溯(当然，上述只是最简单的例子，实际情况要更复杂)
写在最后的话
正则匹配中，贪婪模式与非贪婪模式乍看之下一看便知，很容易理解，但是真正的深入理解需要掌握正则的原理才行，并且，真正理解它们后，就不仅仅只是写出普通的正则表达式，而是高性能的正则表达式了，比如理解非贪婪模式中的回溯特性后更容易写出高性能的表达式
本文也只是做一些浅显的分析与引导，更多是起到抛砖引玉的作用，要深入理解还请去了解正则的原理
附录
参考资料
