你好，我是涂伟忠。在上一讲中，我们已经学习了正则中和一些元字符相关的内容。这一节我们讲一下正则中的三种模式，贪婪匹配、非贪婪匹配和独占模式。
这些模式会改变正则中量词的匹配行为，比如匹配一到多次；在匹配的时候，匹配长度是尽可能长还是要尽可能短呢？如果不知道贪婪和非贪婪匹配模式，我们写的正则很可能是错误的，这样匹配就达不到期望的效果了。
为什么会有贪婪与非贪婪模式？
由于本节内容和量词相关的元字符密切相关，所以我们先来回顾一下正则中表示量词的元字符。
在这6种元字符中，我们可以用 {m,n} 来表示 （*）（+）（?） 这3种元字符：
表示量词的星号（*）和 加号（+）可能没你想象的那么简单，我用一个例子给你讲解一下。我们先看一下加号（+），使用 a+ 在 aaabb 中查找，可以看到只有一个输出结果：
对应的Python代码如下：
>>> import re
>>> re.findall(r'a+', 'aaabb')
['aaa']
加号应该很容易理解，我们再使用 a* 在 aaabb 这个字符串中进行查找，这次我们看到可以找到4个匹配结果。
使用Python示例如下，我们可以看到输出结果，也是得到了4个匹配结果：
>>> import re
>>> re.findall(r'a*', 'aaabb')
['aaa', '', '', '']
但这一次的结果匹配到了三次空字符串。为什么会匹配到空字符串呢？因为星号（*）代表0到多次，匹配0次就是空字符串。到这里，你可能会有疑问，如果这样，aaa 部分应该也有空字符串，为什么没匹配上呢？
这就引入了我们今天要讲的话题，贪婪与非贪婪模式。这两种模式都必须满足匹配次数的要求才能匹配上。贪婪模式，简单说就是尽可能进行最长匹配。非贪婪模式呢，则会尽可能进行最短匹配。正是这两种模式产生了不同的匹配结果。
贪婪、非贪婪与独占模式
贪婪匹配（Greedy）
首先，我们来看一下贪婪匹配。在正则中，表示次数的量词默认是贪婪的，在贪婪模式下，会尝试尽可能最大长度去匹配。
首先，我们来看一下在字符串 aaabb 中使用正则 a* 的匹配过程。
a* 在匹配开头的 a 时，会尝试尽量匹配更多的 a，直到第一个字母 b 不满足要求为止，匹配上三个a，后面每次匹配时都得到了空字符串。
相信看到这里你也发现了，贪婪模式的特点就是尽可能进行最大长度匹配。所以要不要使用贪婪模式是根据需求场景来定的。如果我们想尽可能最短匹配呢？那就要用到非贪婪匹配模式了。
非贪婪匹配（Lazy）
那么如何将贪婪模式变成非贪婪模式呢？我们可以在量词后面加上英文的问号(?)，正则就变成了 a*?。此时的匹配结果如下：
>>> import re
>>> re.findall(r'a*', 'aaabb') # 贪婪模式
['aaa', '', '', '']
>>> re.findall(r'a*?', 'aaabb') # 非贪婪模式
['', 'a', '', 'a', '', 'a', '', '', '']
这一次我们可以看到，这次匹配到的结果都是单个的a，就连每个a左边的空字符串也匹配上了。
到这里你可能就明白了，非贪婪模式会尽可能短地去匹配，我把这两者之间的区别写到了下面这张图中。
为了让你加深理解，我们再来看一个示例，这一次让我们查找一下引号中的单词。
从下面这个示例中，我们可以很容易看出两者对比上的差异。左右的文本是一样的，其中有两对双引号。不同之处在于，左边的示例中，不加问号时正则是贪婪匹配，匹配上了从第一个引号到最后一个引号之间的所有内容；而右边的图是非贪婪匹配，找到了符合要求的结果。
独占模式（Possessive）
不管是贪婪模式，还是非贪婪模式，都需要发生回溯才能完成相应的功能。但是在一些场景下，我们不需要回溯，匹配不上返回失败就好了，因此正则中还有另外一种模式，独占模式，它类似贪婪匹配，但匹配过程不会发生回溯，因此在一些场合下性能会更好。
你可能会问，那什么是回溯呢？我们来看一些例子，例如下面的正则：
regex = “xy{1,3}z”
text = “xyyz”
在匹配时，y{1,3}会尽可能长地去匹配，当匹配完 xyy 后，由于 y 要尽可能匹配最长，即三个，但字符串中后面是个 z 就会导致匹配不上，这时候正则就会向前回溯，吐出当前字符 z，接着用正则中的 z 去匹配。
如果我们把这个正则改成非贪婪模式，如下：
regex = “xy{1,3}?z”
text = “xyyz”
由于 y{1,3}? 代表匹配1到3个 y，尽可能少地匹配。匹配上一个 y 之后，也就是在匹配上 text 中的 xy 后，正则会使用 z 和 text 中的 xy 后面的 y 比较，发现正则 z 和 y 不匹配，这时正则就会向前回溯，重新查看 y 匹配两个的情况，匹配上正则中的 xyy，然后再用 z 去匹配 text 中的 z，匹配成功。
了解了回溯，我们再看下独占模式。
独占模式和贪婪模式很像，独占模式会尽可能多地去匹配，如果匹配失败就结束，不会进行回溯，这样的话就比较节省时间。具体的方法就是在量词后面加上加号（+）。
regex = “xy{1,3}+yz”
text = “xyyz”
需要注意的是 Python 和 Go 的标准库目前都不支持独占模式，会报错，如下所示：
>>> import re
>>> re.findall(r'xy{1,3}+yz', 'xyyz')
error: multiple repeat at position 7
报错显示，加号（+）被认为是重复次数的元字符了。如果要测试这个功能，我们可以安装 PyPI 上的 regex 模块。
注意：需要先安装 regex 模块，pip install regex
>>> import regex
>>> regex.findall(r'xy{1,3}z', 'xyyz') # 贪婪模式
['xyyz']
>>> regex.findall(r'xy{1,3}+z', 'xyyz') # 独占模式
['xyyz']
>>> regex.findall(r'xy{1,2}+yz', 'xyyz') # 独占模式
[]
你也可以使用 Java 或 Perl 等其它语言来测试独占模式，查阅相关文档，看一下你所用的语言对独占模式的支持程度。
如果你用 a{1,3}+ab 去匹配 aaab 字符串，a{1,3}+ 会把前面三个 a 都用掉，并且不会回溯，这样字符串中内容只剩下 b 了，导致正则中加号后面的 a 匹配不到符合要求的内容，匹配失败。如果是贪婪模式 a{1,3} 或非贪婪模式 a{1,3}? 都可以匹配上。
这里我简单总结一下，独占模式性能比较好，可以节约匹配的时间和CPU资源，但有些情况下并不能满足需求，要想使用这个模式还要看具体需求（比如我们接下来要讲的案例），另外还得看你当前使用的语言或库的支持程度。
正则回溯引发的血案
学习到了这里，你是不是觉得自己对贪婪模式、非贪婪模式，以及独占模式比较了解了呢？其实在使用过程中稍不留神，就容易出问题，在网上可以看到不少因为回溯引起的线上问题。
这里我们挑选一个比较出名的，是阿里技术微信公众号上的发文。Lazada卖家中心店铺名检验规则比较复杂，名称中可以出现下面这些组合：
-
英文字母大小写；
-
数字；
-
越南文；
-
一些特殊字符，如“&”，“-”，“_”等。
负责开发的小伙伴在开发过程中使用了正则来实现店铺名称校验，如下所示：
^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
这个正则比较长，但很好理解，中括号里面代表多选一，我们简化一下，就成下面这样：
^([符合要求的组成1]|[符合要求的组成2])+$
脱字符（^）代表以这个正则开头，美元符号（$）代表以正则结尾，我们后面会专门进行讲解。这里可以先理解成整个店铺名称要能匹配上正则，即起到验证的作用。
你需要留意的是，正则中有个加号（+），表示前面的内容出现一到多次，进行贪婪匹配，这样会导致大量回溯，占用大量CPU资源，引发线上问题，我们只需要将贪婪模式改成独占模式就可以解决这个问题。
我之前说过，要根据具体情况来选择合适的模式，在这个例子中，匹配不上时证明店铺名不合法，不需要进行回溯，因此我们可以使用独占模式，但要注意并不是说所有的场合都可以用独占模式解决，我们要首先保证正则能满足功能需求。
仔细再看一下 这个正则，你会发现 “组成1” 和 “组成2” 部分中，A-Za-z 英文字母在两个集合里面重复出现了，这会导致回溯后的重复判断。这里要强调一下，并不是说有回溯就会导致问题，你应该尽量减少回溯后的计算量，这些在后面的原理讲解中我们会进一步学习。
另外，腾讯云技术社区也有类似的技术文章，你如果感兴趣，可以点击这里进行查看。
说到这里，你是不是想起了课程开篇里面提到的一句话：
如果你有一个问题，你想到可以用正则来解决，那么你有两个问题了。
Some people, when confronted with a problem, think “I know, I’ll use regular expressions.” Now they have two problems.
所以一个小小的正则，有些时候也可能会把CPU拖垮，这也提醒我们在写正则的时候，一定要思考下回溯问题，避免使用低效的正则，引发线上问题。
最后总结
最后我来给你总结一下：正则中量词默认是贪婪匹配，如果想要进行非贪婪匹配需要在量词后面加上问号。贪婪和非贪婪匹配都可能会进行回溯，独占模式也是进行贪婪匹配，但不进行回溯，因此在一些场景下，可以提高匹配的效率，具体能不能用独占模式需要看使用的编程语言的类库的支持情况，以及独占模式能不能满足需求。
课后思考
最后，我们来做一个小练习吧。
有一篇英文文章，里面有很多单词，单词和单词之间是用空格隔开的，在引号里面的一到多个单词表示特殊含义，即引号里面的多个单词要看成一个单词。现在你需要提取出文章中所有的单词。我们可以假设文章中除了引号没有其它的标点符号，有什么方法可以解决这个问题呢？如果用正则来解决，你能不能写出一个正则，提取出文章中所有的单词呢（不要求结果去重）？
we found “the little cat” is in the hat, we like “the little cat”
其中 the little cat 需要看成一个单词
好了，今天的课程就结束了，希望可以帮助到你，也希望你在下方的留言区和我参与讨论，并把文章分享给你的朋友或者同事，一起交流一下。
精选留言
2020-06-15 02:06:41
如果只是判断文本是否符合规则，则可以使用独占模式; 如果需要获取匹配的结果，则根据需要使用贪婪或非贪婪。
作业题: (这里需要获取单词，不能使用独占模式)
\w+|“[^”]+” (注意: 例句中的双引号是中文状态下的)
结果(10 次匹配, 48 步): ['we', 'found', '"the little cat"', 'is', 'in', 'the', 'hat', 'we', 'like', '"the little cat"']
相应的 Python 代码:
>>> import re
>>> text = '''we found “the little cat” is in the hat, we like “the little cat”''' # 注意: 例句中的双引号是中文状态下的
>>> pattern = re.compile(r'''\w+|“[^”]+”''')
>>> pattern.findall(text)
['we', 'found', '"the little cat"', 'is', 'in', 'the', 'hat', 'we', 'like', '"the little cat"']
示例: https://regex101.com/r/l8hkqi/1
2020-06-15 21:50:23
regex.findall(r'xy{1,3}+z', 'xyyz')
这里是独占模式，不进行回溯。这里在尽可能多的匹配第三个 y的时候匹配失败，不应该是直接匹配失败 返回空数组吗？ 怎么是返回 xyyz 呢？ 如果返回 xyyz 不就进行回溯了吗？
2020-06-16 17:51:25
>>> import re
>>> re.findall(r'a*?','aaabb')
['', '', '', '', '', '']
2020-06-15 19:16:52
\w+|“[\w\s]+?
\w+|“.+?”
还有第四种方法吗?
2020-08-13 10:51:10
2020-06-23 18:39:43
```javascript
let str = `we found "the little cat" is in the hat, we like "the little cat"`
let re = new RegExp(/"[^"]+"|\w+/, 'g')
let res = str.match(re)
console.log(res)
```
2020-06-15 07:57:00
".+?"|[^\s|,]+
关于回溯，是不是就是递归调用函数栈的原理？拿 xy{1,3}z 匹配 xyyz 举例，步骤如下：
1. 正则中的 x 入栈，匹配上 text 的第一个字符 x
2. 正则中的 y 入栈，匹配上 text 中的第二个字符 y
3. 因为这里没有加问号，属于贪婪匹配，正则中的 y 继续入栈，匹配上 text 中的第三个字符 y
4. 正则中的 y 继续入栈，但是这个时候 y 和 z 不匹配，执行回溯，就是当前正则的第三个 y 出栈
5. 用范围量词后的字符 z 继续入栈匹配，匹配上 text 的最后一个字符，完成匹配
2020-06-16 18:16:54
2020-06-15 19:54:33
2020-06-15 14:49:37
还请解惑。
2021-02-02 21:46:10
比如对于regex.findall(r'a{1,3}ab', 'aaab') 这个例子，因为表示量词是默认开启贪婪模式的，所以a{1,3}会尽可能地匹配三个aaa,剩下的表达式ab会去匹配字符串'aaab'中b，发现ab和b对不上，这个时候由于贪婪模式会发生回溯，它就会去上次匹配的结果"aaa"中借一个a过来，被借了一个a之后上次的匹配结果变为aa,发现也是符合a{1,3}这个规则的(可匹配1-3个a),借到a之后,刚好可以匹配到ab字符串，匹配结束。
再来理解regex.findall(r'a{1,3}?ab', 'aaab') 这个例子,加?号之后，表示非贪婪模式,a{1,3}会尽可能少匹配a,第一次会匹配到一个a,接下来正则剩ab,用a去匹配'aaab'中的第二个a，最后正则剩一个b，它会去先匹配'aaab'中第三个a，发现对不上，因为非贪婪模式也会发生回溯，所以会尝试把匹配不上的a送到上次的匹配结果中，由于上次匹配结果经历了第一次和第二次的匹配，为aa，再加上第三次倒贴过来的a，就变成了aaa，还是符合a{1,3}这个规则的，最后面剩下的规则b刚好匹配上最后一个字符b，匹配结束。
对于regex.findall(r'a{1,3}+ab', 'aaab')这个例子，由于是独占模式，有贪婪的特性，最开始就会去尝试匹配一个最大的结果，a{1,3}会去匹配‘aaab’中的三个a，字符串'aaab'在经历最大匹配之后就只剩下一个b了，跟剩下的规则ab匹配不上,最终匹配结果为空。由于独占模式不发生回溯，也就不会像贪婪模式一样会去上次的匹配结果中借一个a来和ab匹配，而是发现对不上之后就马上放弃结束掉。
上面就是我的理解，再结合老师文章中总结的要点，我觉得会更明白。
贪婪匹配中的回溯：后面匹配不上，会吐出已匹配的再尝试
非贪婪匹配中的回溯：后面匹配不上，会匹配更长再接着尝试
独占模式：不会发生回溯，匹配不上即失败。
2020-07-21 21:16:14
正则: \w+|“.+?”
字符串 : we found “the little cat” is in the hat, we like “the little cat”
结果的确是把每个单词单独匹配到了, 并且 引号的也当成一个单词了,
那么请问 为什么 \w+ 不会把 引号内的单词匹配到呢, 为什么不会出现 the 与 “the little cat” 共存呢
正则匹配的过程是怎么样的 ?
2020-06-27 23:30:32
2020-06-18 17:09:54
1、掌握基本规则
2、多用，多试验
我的运行环境：MacOS，python 3.6.2
我匹配的英文引号 " 例子
text = 'we found "the little cat" is in the hat, we like "the little cat"'
re.findall(r'"(.*?)"', text)
输出：['the little cat', 'the little cat']
中文引号版本 “ ”
text = 'we found “the little cat” is in the hat, we like “the little cat”'
re.findall(r'“(.*?)”', text)
输出：['the little cat', 'the little cat']
so easy
2020-06-15 14:43:17
2021-07-27 16:40:50
[a-zA-Z]+|“.+? 匹配出来10个
”但是为什么我用.+|“.+?”把整个句子都匹配上了呢？
2020-07-03 20:09:37
2020-06-19 23:57:05
确实将 aaabb 拆成了 空白符+a+空白符+...
可以理解 但是这样做的意义是什么？？？
此外 我想问一下对于同一个正则表达式 不同的语言引擎的解释是可以不一样的吗？
一样用这个进行举例。
const regex1 = new RegExp('a*?','g')
const str1 = 'aaabb'
console.log(str1.match(regex1)) // ['','','','','','','']
预期的结果不是 a a a b b 吗？
而对于这个结果我做了一个尝试性的解读。
macth返回的不是字符串的子串，而是正则的结果
因此 返回的结果应该为 '' a aa a*
因此即使是a匹配到了 返回的也是对应的正则的匹配形式 空字符 因为非贪婪模式下并不需要到a就可以返回了
可是这样得话 为什么会多出来一个 空白符 呢？
对于这个空白符 个人的理解是 当输出一个空字符的时候 a* 也是可以匹配成功的，因此需要对这种情况进行处理，那么是在什么时候进行处理的呢？在一开始的时候进行处理的，还是在结尾的时候进行处理的？
老师在讲原理的时候会聊这块吗？
我的问题主要有三点
1、不同的语言对正则的理解是不是可能不一样
2、为什么python要对字符串进行加上空字符的处理
3、为什么JavaScript的match会返回这样的结果
希望老师能给一个解答
还有一个请求
老师在在讲原理的时候，能不能提一下这块
2020-06-16 17:41:48
/"[^"]+"|[a-z]+/g
2020-06-16 08:19:13