浅谈正则表达式原理

正则表达式可能大部分人都用过，但是大家在使用的时候，有没有想过正则表达式背后的原理，又或者当我告诉你正则表达式可能存在性能问题导致线上挂掉，你会不会觉得特别吃惊？

创新互联公司是一家集网站建设,静乐企业网站建设,静乐品牌网站建设,网站定制,静乐网站建设报价,网络营销,网络优化,静乐网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。

我们先来看看7月初，因为一个正则表达式，导致线上事故的例子。

https://blog.cloudflare.com/d...

简单来说就是一个有性能问题的正则表达式，引起了灾难性回溯，导致cpu满载。

性能问题的正则

先看看出问题的正则

引起性能问题的关键部分是 .*(?:.*=.*) ，这里我们先不管那个非捕获组，将性能问题的正则看做 .*.*=.* 。

其中 . 表示匹配除了换行以外的任意字符（很多人把这里搞错，容易出bug）， .* 表示贪婪匹配任意字符任意次。

什么是回溯

在使用贪婪匹配或者惰性匹配或者或匹配进入到匹配路径选择的时候，遇到失败的匹配路径，尝试走另外一个匹配路径的这种行为，称作回溯。

可以理解为走迷宫，一条路走到底，发现无路可走就回到上一个三岔口选择另外的路。

回溯现象 

 
 
 
 
    
  
  
  
  
  1. // 性能问题正则  
    2. 
  
  
  
  
  2. // 将下面代码粘贴到浏览器控制台运行试试  
    3. 
  
  
  
  
  3. const regexp = `[A-Z]+\\d+(.*):(.*)+[A-Z]+\\d+`;  
    4. 
  
  
  
  
  4. const str = `A1:B$1,C$1:D$1,E$1:F$1,G$1:H$1`  
    5. 
  
  
  
  
  5. const reg = new RegExp(regexp);  
    6. 
  
  
  
  
  6. start = Date.now();  
    7. 
  
  
  
  
  7. const res = reg.test(str);  
    8. 
  
  
  
  
  8. end = Date.now();  
    9. 
  
  
  
  
  9. console.log('常规正则执行耗时:' + (end - start)) 
    10.

现在来看看回溯究竟是怎么一回事

假设我们有一段正则 (.*)+\d ，这个时候输入字符串为 abcd ，注意这个时候仅仅输入了一个长度为4的字符串，我们来分析一下匹配回溯的过程：

上面展示了一个回溯的匹配过程，大概描述一下前三轮匹配。

注意 (.*)+ 这里可以先暂且看成多次执行 .* 。 (.*){1,}

***次匹配，因为 .* 可以匹配任意个字符任意次，那么这里可以选择匹配空、a、ab、abc、abcd，因为 * 的贪婪特性，所以 .* 直接匹配了 abcd 4个字符， + 因为后面没有其他字符了，所以只看着 .* 吃掉 abcd 后就不匹配了，这里记录 + 的值为1，然后 \d 没有东西能够匹配，所以匹配失败，进行***次回溯。

第二次匹配，因为进行了回溯，所以回到上一个匹配路径选择的时候，上次 .* 匹配的是 abcd ，并且路不通，那么这次只能尝试匹配 abc ，这个时候末尾还有一个 d ，那么可以理解为 .* ***次匹配了 abc ，然后因为 (.*)+ 的原因， .* 可以进行第二次匹配，这里 .* 可以匹配 d ，这里记录 + 的值为2，然后 \d 没有东西能够匹配，所以匹配失败，进行第二次回溯。

第三次匹配，因为进行了回溯，所以回到上一个匹配路径选择的时候，上次***个 .* 匹配的是 abc ，第二个 .* 匹配的是 d ，并且路不通，所以这里第二次的 .* 不进行匹配，这个时候末尾还有一个 d ， \d 和 d 匹配失败，进行第三次回溯。

如何减少或避免回溯

  •  优化正则表达式：时刻注意回溯造成的性能影响。
  •  使用DFA正则引擎的正则表达式

什么是DFA正则引擎

传统正则引擎分为NFA（非确定性有限状态自动机），和DFA（确定性有限状态自动机）。

DFA

对于给定的任意一个状态和输入字符，DFA只会转移到一个确定的状态。并且DFA不允许出现没有输入字符的状态转移。

比如状态0，在输入字符A的时候，终点只有1个，只能到状态1。

NFA

对于任意一个状态和输入字符，NFA所能转移的状态是一个非空集合。

比如状态0，在输入字符A的时候，终点可以是多个，即能到状态1，也能到状态0。

DFA和NFA的正则引擎的区别

那么讲了这么多之后，DFA和NFA正则引擎究竟有什么区别呢？或者说DFA和NFA是如何实现正则引擎的呢？

DFA

正则里面的DFA引擎实际上就是把正则表达式转换成一个图的邻接表，然后通过跳表的形式判断一个字符串是否匹配该正则。 

 
 
 
 
    
  
  
  
  
  1. // 大概模拟一下  
    2. 
  
  
  
  
  2. function machine(input) {  
    3. 
  
  
  
  
  3.     if (typeof input !== 'string') {  
    4. 
  
  
  
  
  4.         console.log('输入有误');  
    5. 
  
  
  
  
  5.         return;  
    6. 
  
  
  
  
  6.     }  
    7. 
  
  
  
  
  7.     // 比如正则：/abc/ 转换成DFA之后  
    8. 
  
  
  
  
  8.     // 这里我们定义了4种状态，分别是0,1,2,3，初始状态为0  
    9. 
  
  
  
  
  9.     const reg = {  
    10. 
  
  
  
  
  10.         0: {  
    11. 
  
  
  
  
  11.             a: 1,  
    12. 
  
  
  
  
  12.         },  
    13. 
  
  
  
  
  13.         1: {  
    14. 
  
  
  
  
  14.             b: 3,  
    15. 
  
  
  
  
  15.         },  
    16. 
  
  
  
  
  16.         2: {  
    17. 
  
  
  
  
  17.             isEnd: true,  
    18. 
  
  
  
  
  18.         },  
    19. 
  
  
  
  
  19.         3: {  
    20. 
  
  
  
  
  20.             c: 2,  
    21. 
  
  
  
  
  21.         },  
    22. 
  
  
  
  
  22.     };  
    23. 
  
  
  
  
  23.     let status = 0;  
    24. 
  
  
  
  
  24.     for (let i = 0; i < input.length; i++) {  
    25. 
  
  
  
  
  25.         const inputinputChar = input[i];  
    26. 
  
  
  
  
  26.         status = reg[status][inputChar];  
    27. 
  
  
  
  
  27.         if (typeof status === 'undefined') {  
    28. 
  
  
  
  
  28.             console.log('匹配失败');  
    29. 
  
  
  
  
  29.             return false;  
    30. 
  
  
  
  
  30.         }  
    31. 
  
  
  
  
  31.     }  
    32. 
  
  
  
  
  32.     const end = reg[status];  
    33. 
  
  
  
  
  33.     if (end && end.isEnd === true) {  
    34. 
  
  
  
  
  34.         console.log('匹配成功');  
    35. 
  
  
  
  
  35.         return true;  
    36. 
  
  
  
  
  36.     } else {  
    37. 
  
  
  
  
  37.         console.log('匹配失败');  
    38. 
  
  
  
  
  38.         return false;  
    39. 
  
  
  
  
  39.     }  
    40. 
  
  
  
  
  40. }  
    41. 
  
  
  
  
  41. const input = 'abc';  
    42. 
  
  
  
  
  42. machine(input); 
    43.

优点：不管正则表达式写的再烂，匹配速度都很快

缺点：高级功能比如捕获组和断言都不支持

NFA

正则里面NFA引擎实际上就是在语法解析的时候，构造出的一个有向图。然后通过深搜的方式，去一条路径一条路径的递归尝试。

优点：功能强大，可以拿到匹配的上下文信息，支持各种断言捕获组环视之类的功能

缺点：对开发正则功底要求较高，需要注意回溯造成的性能问题

总结

现在回到问题的开头，我们再来看看为什么他的正则会有性能问题

  1.  首先他的正则使用的NFA的正则引擎（大部分语言的正则引擎都是NFA的，js也是，所以要注意性能问题产生的影响）
  2.  他写出了有性能问题的正则表达式，容易造成灾难性回溯。

如果要避免此类的问题，要么提高开发对正则的性能问题的意识，要么改用DFA的正则引擎（速度快，功能弱，没有补货组断言等功能）。

注意事项

在平常写正则的时候，少写模糊匹配，越精确越好，模糊匹配、贪婪匹配、惰性匹配都会带来回溯问题，选一个影响尽可能小的方式就好。写正则的时候有一个性能问题的概念在脑子里就行。

当前文章：浅谈正则表达式原理
网页链接：http://www.shufengxianlan.com/qtweb/news23/151623.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

建站公司知识

同城分类信息

公司网站建设　　 　内江托管服务器　　 　优化排名　　 　眉山网站建设　　 　成都响应式网站建设公司　　 　seo优化排名　　 　雕琢时光茶叶　　 　成都广告招牌制作　　 　腾讯云免备案主机　　 　成都商城开发　　 　西信服务器托管　　 　广安网站建设　　 　云南护栏打桩机　　 　成都网站制作　　 　成都门窗定制　　 　网络营销　　 　节能环保网站建设方案　　 　成都app制作　　 　百度推广公司　　 　教育建设方案