Question

正则表达式之原理篇

Answer 1

背景

       最近公司规范出来后，关于字符串不提倡用 “ + ”  进行拼接，于是自己写了个function，利用正则表达式来进行匹配。对于正则表达式，之前不了解原理，每胡和迹次要用的时候查一下，很浪费时间。

内容

基础知识；

正则表达式引擎；

贪婪与非贪婪模式；

DFA与NFA引擎；

回溯机制及常见的回溯形式

基础知识

1. 占有字符：正则表达式匹配过程中，如果子表达式匹配到东西，而并非是一个位置，并最终保存到匹配的结果当中

2. 零宽度：只匹配一个位置，或者是匹配的内容并不保存到匹配结果中

一个字符，同一时间只能由一个子表达式匹配，而一个位置，却可以同时由多个零宽度的子表达式匹配

3.控制权：正则表达式由左到右依次进行匹配，通常情况下是由一个表达式取得控制权，从字符串的的某个位置进行匹配，一个子表达式开始尝试匹配的位置，是从前一子表达匹配成功的结束位置开始的（例如：（表达式一）（表达式二）意思就是表达式一匹配完成后才能匹配表达式二，而匹配表达式二的位置是从表达式一的位置匹配结束后的位置开始）。如果表达式一是零宽度，那表达式一匹配完成后，表达式二匹配的位置还是原来表达式以匹配的位置。也就是说它匹配开始和结束的位置是同一个

4. 元字符 

5. 反义元字符

6. 转义字符：\  使元字符失去它的意义，仅代表其输入中字符的意义

需要转义的字符列表 \ * + ? | { [ ( ) ^ $ . # 和 空白

7. 重复限定符：匹配优先裤并量词，忽略优先量词，即：贪婪与非贪婪

{n,}、 {n, m}、 {, m}、 ’+’ 、‘?’、 '*'

8. 字符类：[ ]，区分大小写

9. 分支条件： |

10. 分组 ：（）指定子表达式，可限制多选项的范围、将若干字符组合为一个单元、受问号或星号之类的量词作用，例：(\d{1,3}){3}\d{3}

断言；(?

11. 括号及反向引用：（子表达式一）（子表达式二）\1      此时括号作用为分组，它具有记忆的功能，即棚山在正则表达式内部仍然能回忆上次匹配到的是什么；\1、\2、\n 是用在正则表达式的匹配环节。在正则表达式的替换环节，则要使用像 $1、$2、$n 这样的语法

12. 平衡组 参考

正则表达式引擎

有两个主要特点：

1. 默认贪婪匹配；（ 贪婪匹配与非贪婪匹配 ）

2. 返回最先匹配到的结果

针对简单的正则匹配进行分析，例：

        当把cat应用到“He captured a catfish for his cat”，引擎先比较c和“H”，结果失败了。于是引擎再比较c和“e”，也失败了。直到第四个字符，c匹配了“c”。a匹配了第五个字符。到第六个字符t没能匹配“p”，也失败了。引擎再继续从第五个字符重新检查匹配性。直到第十五个字符开始，cat匹配上了“catfish”中的“cat”，正则表达式引擎急切的返回第一个匹配的结果，而不会再继续查找是否有其他更好的匹配

Rubular: 基于 Web 的 Ruby 正则表达式编辑器

贪婪与非贪婪（又称惰性、懒惰等）模式

两者影响的是被量词修饰的子表达式的行为。

贪婪模式在整个表达式匹配成功的前提下，尽可能多的匹配；而非贪婪模式（只被部分NFA引擎支持）在整个表达式匹配成功的前提下，尽可能少的匹配。

匹配优先量词（属于贪婪模式的量词）：

“{m,n}”、“{m,}”、“?”、“*”和“+”。

忽略优先量词（匹配优先量词后加上“?”：非贪婪模式的量词）：

“{m,n}?”、“{m,}?”、“??”、“*?”和“+?”

例：

源字符串：aa

正则表达式一：

正则表达式二：

DFA与NFA引擎（JS的正则引擎是NFA：非确定型有限自动机）

参考： 正则表达式引擎及其分类

DFA引擎：在线性时状态下执行，不要求回溯（因此永远不测试相同的字符两次）；确保匹配最长的可能的字符串；因为只包含有限的状态（？），所以它不能匹配具有反向引用的模式；并且因为它不构造显示扩展，所以它不可以捕获子表达式

传统的NFA引擎：运行匹配回溯算法——以指定顺序测试正则表达式的所有可能的扩展并接受第一个匹配项。因为传统的 NFA 构造正则表达式的特定扩展以获得成功的匹配，所以它可以捕获子表达式匹配和匹配的反向引用。但传统 NFA的 回溯使它可以访问完全相同的状态多次（如果通过不同的路径到达该状态）。因此，在最坏情况下，它的执行速度可能非常慢。因为传统的 NFA 接受它找到的第一个匹配，所以它还可能会导致其他（可能更长）匹配未被发现

POSIX NFA 引擎：与传统 NFA 引擎类似，不同点：在可以确保已找到了可能的最长的匹配之前，它们将继续回溯（更慢）；并且在使用 POSIX NFA 时，您恐怕不会愿意在更改回溯搜索的顺序的情况下来支持较短的匹配搜索，而非较长的匹配搜索

例：

字符串： this is yansen’s dog

正则表达式： /ya(msen|nsen|nsem)/

NFA工作方式：先在字符串中查找 y， 然后匹配其后是否为 a；  如果是 a 则继续查找其后是否为 m； 如果不是则匹配其后是否为 n (此时淘汰 msen 支分支)； 然后继续看其后是否依次为 s,e； 接着测试是否为 n ，是 n 则匹配成功，不是则测试是否为 m 。为什么是 m ？因为 NFA 工作方式是以正则表达式为标准，反复测试字符串，这样同样一个字符串有可能被反复测试了很多次！

DFA：从 this 中 t 开始依次查找 y ，定位到 y ，已知其后为 a ，则查看表达式是否有 a ，此处正好有 a； 然后字符串 a 后为 n ，DFA依次测试表达式，此时 msen 不符合要求淘汰。 nsen 和 nsem 符合要求，然后DFA依次检查字符串，检测到 sen 中的 n 时只有 nsen 分支符合，则匹配成功！

由此两种引擎是完全不同的工作方式：NFA以表达式为主导，更容易操纵；DFA以文本为主导（搜索更快）

回溯机制

引擎是如何来处理那些模糊的条件匹配？

从问题的某一种状态（初始状态）出发，搜索从这种状态出发所能达到的所有“状态”，当一条路走到“尽头”的时候（不能再前进），再后退一步或若干步，从另一种可能“状态”出发，继续搜索，直到所有的“路径”（状态）都试探过。这种不断“前进”、不断“回溯”寻找解的方法，就称作“回溯法”

--来自百度百科

本质上就是深度优先搜索算法：尝试匹配失败时的下一步通常就是回溯

JS中正则表达式会产生回溯的地方都有哪些呢？

常见的回溯形式

1.贪婪量词

例：正则：/ab{1,3}c/

可视化形式

1. 没有回溯的匹配：当目标字符串是"abbbc"时

匹配过程

2. 有回溯的匹配：当目标字符串是“abbc”时

匹配过程

上图第5步有红颜色（仅表示匹配不成功）：此时b{1,3}已经匹配到了2个字符“b”，准备尝试第三个时，结果发现接下来的字符是“c”。那么就认为b{1,3}就已经匹配完毕。然后状态又回到之前的状态（即第6步，与第4步一样），最后再用子表达式c，去匹配字符“c”。当然，此时整个表达式匹配成功了；上图的第6步，就是“回溯”

即：尝试可能的顺序是“从多往少”的方向去尝试：首先会尝试"bbb"，然后再看整个正则是否能匹配。不能匹配时，吐出一个"b"，即在"bb"的基础上，再继续尝试。如果还不行，再吐出一个，再试。如果还不行呢？只能说明匹配失败了

另一个清晰的回溯：

正则：/".*"/

目标字符串："acd"ef

省略了尝试匹配双引号失败的匹配过程

其实“.*”最简单但也是非常影响效率的

2.惰性量词

虽然惰性量词不贪，但也会有回溯的现象（为了整体匹配成）

正则表达式

目标字符串："12345"

匹配过程

3.分支结构

分支也是惰性的，比如/Java|JavaScript/，去匹配字符串"JavaScript"，得到的结果是"Java"，因为分支会一个一个尝试，如果前面的满足了，后面就不会再试验了。

分支结构中可能前面的子模式会形成了局部匹配，如果接下来表达式整体不匹配时，仍会继续尝试剩下的分支。这种尝试也可以看成一种回溯：

正则表达式

匹配过程

虽然第五步没有回到之前的状态，但仍然回到了分支结构，尝试下一种可能

总结：有回溯的过程，那么匹配效率肯定比DFA相对低一些；别看匹配慢，但是编译快而且还挺有趣

参考： 正则表达式的回溯机制