本文属于 正则表达式系列文章之一,更多请前往 正则表达式系列
贪婪模式和非贪婪模式是正则匹配中的重要特性 在理解贪婪和非贪婪的区别时,可以根据实例,一步一步的循序渐进
匹配规则简介
贪婪模式与非贪婪模式快速理解
实例练习
回溯现象与匹配失败
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
,因此*
不会吃进它,直接就匹配失败了,减少了很多回溯(当然,上述只是最简单的例子,实际情况要更复杂)
正则匹配中,贪婪模式与非贪婪模式乍看之下一看便知,很容易理解,但是真正的深入理解需要掌握正则的原理才行,并且,真正理解它们后,就不仅仅只是写出普通的正则表达式,而是高性能的正则表达式了,比如理解非贪婪模式中的回溯特性后更容易写出高性能的表达式
本文也只是做一些浅显的分析与引导,更多是起到抛砖引玉的作用,要深入理解还请去了解正则的原理