【学懂正则2】量词匹配模式：的贪婪、非贪婪和独占

总览

量词的作用在上一篇已经讲过了，接下来就通过几个实例来了解贪婪模式、非贪婪模式、独占模式之间的差异

贪婪模式与非贪婪模式

贪婪模式

使用 a* 来匹配 aaabb会得到如下结果：

总共有四次匹配符合，分别是：'aaa', '', '', '' 后三次都是空字符串，这也是 * 这一量词的特点，它会匹配空字符串，而正则认为字符串以空字符结尾。

如果 a* 去匹配 ‘aaa’，得到结果也会是两个，分别是'aaa', ‘’

非贪婪模式

在量词后面加上?就是非贪婪匹配了，使用 a*? 来匹配 aaabb 会得到如下结果：

分别有9个匹配，分别是：'','a','','a','','a','','','' ,每个最小匹配的a前面还有一个空字符串，前面末尾还要再匹配一次空字符串已经让人觉得费解了，现在跑出来说，每个a前面还要匹配一个空字符串，翻译翻译，什么叫 * 量词加上非贪婪模式

对于使用 a*? 来匹配字符 'a'，会有三种结果，分别是： '','a',''，正则匹配进行的过程是这样的：

可以看到，在0-0和1-1这两个端点位置进行了匹配，而每一个端点，正则都认为它是空字符串，1个字符那么就有两个断点，a的左侧是0，a的右侧是1，[0,1]区间代表了字符a，0，1这两个端点是空字符，再来看一下对aaabb的匹配结果就能够理解了:

0-5的六个端点全部做了一次空字符的匹配，所以一定要注意单字符使用 *? 时候的坑点。

回溯

回溯是正则在匹配时的一个重要概念，这里的通过一个例子简单的理解一下

待匹配字符串：xyyyz

使用贪婪匹配：xy{1,3}yz

非贪婪匹配：xy{1,3}?yz

都可以匹配成功，但二者的匹配过程是不一样的：

对于贪婪模式，它会先匹配3个y，然后遇到字符串字符是z，但是希望匹配的是y，它就会吐出一个已经匹配的y来尝试进行匹配，如果成功则继续进行，如果失败则继续吐出，直到成功或者无法满足返回失败。

对于非贪婪模式，它会只匹配一个y，之后遇到的字符串字符是y，想要匹配的也是y，继续匹配，再往前，遇到的字符串字符是y，但是想要匹配的z，不满足，则回到非贪婪匹配那里，尝试多匹配一个y，多匹配是能够满足要求的，则多匹配一个，然后继续前进，遇到的字符串字符是y，想要匹配的也是y，之后是z…

在这里我们可以知道回溯贪婪和非贪婪模式下是必须的，正则在具体实施过程中会对这个过程有优化，具体这里就不阐释了。

但是这里也还是可以再讲一点的，考虑待匹配字符串 xyyz，正则为 xy{1,3}z, 那么当原字符串指针到z的时候我吃进去，发现不是y，我再吐出来，这个过程是回溯吗？

其实是这个过程并不正确，要明确的是，z并不会被吃进去，在编译原理中的语义分析阶段就是大量的正则的过程，在这个环节匹配是模拟两个栈，一个是原字符串，一个是待匹配的正则式子，二者的栈顶是：原字符串是z，正则是y{0,2}（大概意思就是可以不匹配，最多再匹配两个），此时将正则栈pop了，而不是将z吃进去了

独占模式

回溯是耗费性能的，如果以匹配了一个很长的字符串，最后发现失败，那么要回溯，如果还要多次回溯，那么可想而知是占用资源的。

独占模式就一种不回溯的贪婪匹配，在量词后面添加 + 就是独占模式，但是不同语言对独占模式的支持不同，有的语言并不支持独占模式。

考虑原字符串：xyyz
正则表达式：xy{1,2}+yz

结果就会是： No Match

为什么呢，独占模式的匹配过程是这样的：

按照最长匹配匹配两个y，原字符串到z，正则是y，不符合，直接fail，它不会进行任何的回溯。

其它

关于正则回溯造成的性能问题感兴趣的可以阅读：
一个正则表达式引发的血案，让线上CPU100%异常！