正则表达式只有“匹配”和“不匹配”两种状态吗？来看看第三种状态

@Ta 2019-04-14发布，2019-04-14修改 9060点击

第三种状态——无限循环。
考虑以下JS代码：

var url = 'http://www.example.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf'
var reg = /^(https?:\/\/)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\\/])+$/i
console.log(reg.test(url))

初看上去，结果应该是false，因为url中包含reg中不存在的字符? _ %等。
不过实际运行效果如何呢？

我们通过 https://regex101.com/ 网站来模拟一下这个正则表达式的匹配流程：

这个问题是怎么造成的呢？其实就是因为
var reg = /^(https?:\/\/)(([A-Za-z0-9-~]+).)+([A-Za-z0-9-~\\/])+$/i

没错就是因为这个点。这里本来是想匹配域名中的点本身，但是由于忘记加\，变成了匹配任意字符。于是([A-Za-z0-9-~]+).便可以匹配到download?，request=，6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw_等一系列片段，但由于后面的([A-Za-z0-9-~\\\/])+$始终与剩余部分不匹配，就发生了一系列“完全停不下来”的返回重新匹配，也称为“灾难性回溯”。

如果改成这样就完全没问题了：

var url = 'http://www.example.com/dddp-web/pdf/download?request=6e7JGxxxxx4ILd-kExxxxxxxqJ4-CHLmqVnenXC692m74H38sdfdsazxcUmfcOH2fAfY1Vw__%5EDadIfJgiEf'
var reg = /^(https?:\/\/)(([A-Za-z0-9-~]+)\.)+([A-Za-z0-9-~\\\/])+$/i
console.log(reg.test(url))

备注：PHP不会发生无限循环，可以返回false，是因为pcre.backtrack_limit参数限制了可回溯的次数。当回溯次数超过限制时就会放弃匹配并返回false。

创意来源：https://zhuanlan.zhihu.com/p/38278481

隐藏样式查看源码

回复列表(16|隐藏机器人聊天)

1

拒绝柳岩99次

@Ta / 2019-04-14 / 样 / 源

1
2

姜辰

@Ta / 2019-04-14 / 样 / 源

三个滑稽币暖贴
3

TabKey9

@Ta / 2019-04-14 / 样 / 源

很少用，通常我都是复制别人提供的常用规则
4

yun

@Ta / 2019-04-15 / 样 / 源

涨知识了
5

胡椒舰长

@Ta / 2019-04-15 / 样 / 源

还有这种操作，学习了
6

Curtion

@Ta / 2019-04-15 / 样 / 源

问问[A-Za-z0-9-~]中的波浪号有什么作用，或者说0-9-~有什么作用呢？
7

水木易安

@Ta / 2019-04-15 / 样 / 源

new reg = /(.*)/gm 不也是最简单的死循环吗
9

老虎会游泳

@Ta / 2019-04-15 / 样 / 源

@水木易安，.*会一次性匹配掉所有字符，然后直接就返回true了啊。

要构造一个灾难性回溯的话，应该是前半部分可以与字符串的任何前缀匹配，但是后半部分与字符串的任何后缀都不匹配。这样正则表达式引擎就会不断调整前半部分和后半部分的长度进行尝试。
10

老虎会游泳

@Ta / 2019-04-15 / 样 / 源

@Curtion，最后的-和~都表示这两个字符本身。
[A-Za-z0-9-~]表示允许出现字母、数字、减号与波浪线。
11

Curtion

@Ta / 2019-04-15 / 样 / 源

@老虎会游泳，行吧，我翻了一下MDN没找到我还以为是新东西呢..
12

老子会游泳

@Ta / 2019-04-16 / 样 / 源

看不懂
13

水木易安

@Ta / 2019-04-17 / 样 / 源

@老虎会游泳，有道理
14

大药瓶子

@Ta / 2019-04-29 / 样 / 源

我就喜欢老虎发的帖子
15

水木易安

@Ta / 2022-03-13 / 样 / 源
正则回溯引发的血案

学习到了这里，你是不是觉得自己对贪婪模式、非贪婪模式，以及独占模式比较了解了呢？其实在使用过程中稍不留神，就容易出问题，在网上可以看到不少因为回溯引起的线上问题。
这里我们挑选一个比较出名的，是阿里技术微信公众号上的发文。Lazada 卖家中心店铺名检验规则比较复杂，名称中可以出现下面这些组合：
- 英文字母大小写；
- 数字；
- 越南文；
一些特殊字符，如“&”，“-”，“_”等。
负责开发的小伙伴在开发过程中使用了正则来实现店铺名称校验，如下所示：
```
^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$
```
这个正则比较长，但很好理解，中括号里面代表多选一，我们简化一下，就成下面这样：
```
^([符合要求的组成1]|[符合要求的组成2])+$ 
```
脱字符（^）代表以这个正则开头，美元符号（$）代表以正则结尾，我们后面会专门进行讲解。这里可以先理解成整个店铺名称要能匹配上正则，即起到验证的作用。
你需要留意的是，正则中有个加号（+），表示前面的内容出现一到多次，进行贪婪匹配，这样会导致大量回溯，占用大量 CPU 资源，引发线上问题，我们只需要将贪婪模式改成独占模式就可以解决这个问题。
我之前说过，要根据具体情况来选择合适的模式，在这个例子中，匹配不上时证明店铺名不合法，不需要进行回溯，因此我们可以使用独占模式，但要注意并不是说所有的场合都可以用独占模式解决，我们要首先保证正则能满足功能需求。
仔细再看一下这个正则，你会发现 “组成 1” 和 “组成 2” 部分中，A-Za-z 英文字母在两个集合里面重复出现了，这会导致回溯后的重复判断。这里要强调一下，并不是说有回溯就会导致问题，你应该尽量减少回溯后的计算量，这些在后面的原理讲解中我们会进一步学习。
另外，腾讯云技术社区也有类似的技术文章，你如果感兴趣，可以点击这里进行查看。
小米MIX2s(白)

老虎会游泳

@Ta / 2022-03-16 / 样 / 源

@水木易安，写这篇文章的人似乎没有意识到，

^([A-Za-z0-9._()&'\- ]|[aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ])+$

等价于

^[A-Za-z0-9._()&'\- aAàÀảẢãÃáÁạẠăĂằẰẳẲẵẴắẮặẶâÂầẦẩẨẫẪấẤậẬbBcCdDđĐeEèÈẻẺẽẼéÉẹẸêÊềỀểỂễỄếẾệỆfFgGhHiIìÌỉỈĩĨíÍịỊjJkKlLmMnNoOòÒỏỎõÕóÓọỌôÔồỒổỔỗỖốỐộỘơƠờỜởỞỡỠớỚợỢpPqQrRsStTuUùÙủỦũŨúÚụỤưƯừỪửỬữỮứỨựỰvVwWxXyYỳỲỷỶỹỸýÝỵỴzZ]+$

但前者会造成回溯问题，后者却只需要简单的单次循环即可完成匹配。

前者的问题是因为两个字符类在英文字母部分重叠，所以正则表达式引擎在不匹配的时候就会让每个字母都在两个字符类之间横跳，导致需要2^n次尝试（n为不匹配点前的字母个数）。这一点他知道，但是他的反应却是“将贪婪模式改成独占模式”，而不是“删除没有意义的多个字符类”，我十分不理解。

到底是什么脑回路，让他把一个简单的字符类匹配写成([a]|[b])+，而不是[ab]+。难道程序员对“允许新字符”的第一反应不是把字符添加到现有字符类吗？

图片.png

17

老虎会游泳

@Ta / 2022-03-16 / 样 / 源

@水木易安，可以这么说，“对分支条件使用重复量词”就是构造灾难性回溯的标准模板：
(a|b)*
(a|b)+
只有一种情况可以避免回溯，就是条件a和b互斥。
如果有字符串能同时匹配条件a和b，那么重复该字符串N次，再加上一个同时不匹配a和b的字符串，必然导致灾难性回溯，回溯次数为2^N。

添加新回复

回复需要登录。

正则表达式只有“匹配”和“不匹配”两种状态吗？来看看第三种状态

正则回溯引发的血案