【正则表达式系列】贪婪与非贪婪模式

| 分类 blog  | 标签 正则表达式  贪婪模式  非贪婪模式  | 浏览  
正则表达式

前言

本文属于 正则表达式系列文章之一,更多请前往 正则表达式系列

贪婪模式和非贪婪模式是正则匹配中的重要特性 在理解贪婪和非贪婪的区别时,可以根据实例,一步一步的循序渐进

大纲

  • 匹配规则简介

  • 贪婪模式与非贪婪模式快速理解

  • 实例练习

  • 回溯现象与匹配失败

匹配规则简介

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/匹配,因此此次匹配成功,返回了abindex=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开始匹配,依次成功匹配了Regex,接着继续匹配最后一个字符",匹配成功,这时候已经匹配到了字符串的结尾,所以.*匹配结束,将控制符交给正则式中最后的"

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

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

非贪婪匹配表达式

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

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

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

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

  • "取得控制权后,开始匹配6处的",匹配成功

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

优化去除回溯

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

"[^"]*"

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

总结

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

匹配失败的情况

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

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

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

  • "匹配",接着[]^"*匹配Regex

  • 接着到了最后,"获取控制权,由于到了最后,开始回溯

  • 依次回溯的结果是*让出xegeR,直到*已经无法再让出字符,第一轮匹配失败

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

那非贪婪模式呢?

/"[^"]*?"/g
  • "匹配",接着*尝试不匹配,"匹配R,失败,然后回溯,*吃进R

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

  • 接着index开始往下挪,依次用"匹配Regex都失败了,返回null

总结

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

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

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

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

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

写在最后的话

正则匹配中,贪婪模式与非贪婪模式乍看之下一看便知,很容易理解,但是真正的深入理解需要掌握正则的原理才行,并且,真正理解它们后,就不仅仅只是写出普通的正则表达式,而是高性能的正则表达式了,比如理解非贪婪模式中的回溯特性后更容易写出高性能的表达式

本文也只是做一些浅显的分析与引导,更多是起到抛砖引玉的作用,要深入理解还请去了解正则的原理

附录

参考资料

上一篇     下一篇
Lichun Dai

Lichun Dai

程序员,偏前端。会点口琴和吉他。

博客 62 项目 2 随笔 108

GitHub 5sing 知乎 segmentfault 掘金