摘要：

1. 使用正则表达式时需要清楚使用到的引擎，根据不同的场景，可以选择不同的引擎(Thompson NFA、DFA等)
2. 常用的js、java、python等使用的是递归回溯NFA，容易出现极大的性能问题

推荐网站：https://regex101.com/

元字符

匹配模式

如何区分贪婪和非贪婪模式

默认情况下匹配都是贪婪模式，如果要改成非贪婪模式，只需要量词后面加上一个问号?。

常用的量词有：

这些默认都是贪婪模式，若改成非贪婪模式，只需这样：

• {m,n}?
• {m,}?
• ??
• *?
• +?

独占模式

独占模式会尽可能多地去匹配，如果匹配失败就结束，不会进行回溯

表达式后加上一个加号（+）

效率

非贪婪模式可以实现的，通过优化量词修饰的子表达式的贪婪模式都可以实现，而贪婪模式可以实现的一些优化效果，却未必是非贪婪模式可以实现的

贪婪模式还有一点优势，就是在匹配失败时，贪婪模式可以更快速的报告失败，从而提升匹配效率

但是在相同的子表达式，又都可以满足需求的情况下，比如“[^"]*”和“[^"]*?”，贪婪模式的匹配效率通常要高些

回溯

没有回溯的匹配

有回溯的匹配

Demo

demo1

逗号分隔，第12项为P开头

^(.*?,){11}P

当第12项不是P开头时，giving up the last match of the comma. The next token is again the dot. The dot matches a comma

the part of the regex (the dot) matching the contents of the field also matches the delimiter (the comma). Because of the double repetition (star inside {11}), this leads to a catastrophic amount of backtracking.

demo2

[a-z]+@[a-z]+([a-z.]+.)+[a-z]+

java Validate "[a-z]+@[a-z]+([a-z.]+.)+[a-z]+" spammer@x......................

测试

避免灾难性回溯的总结

• 正确使用贪婪模式和非贪婪模式
• 不过分依赖.*，通过使用有明显特征的具体字符、字符组代替通配符，来消除某些回溯
• 复杂情况可以考虑通过断言、固化分组(javascript中暂时不支持)等来解决回溯问题
• 减少嵌套的量词
• 减少多选分支数量
• 使用检测工具进行测试
• 必要时可以考虑更换正则引擎

效率优化

使用字符组代替分支条件

匹配abcd字符请使用[a-d]而不是使用a|b|c|d,前者匹配一次即可匹配需要的字符，而后者需要进行匹配四次(因为需要进行回溯)

尽量使用锚点优化(^或者$)

如果知道一个字符串开头是什么，尽量使用^,如果知道结尾是什么尽量使用$,它可以从字符串末尾倒数若干个字符开始进行匹配，比如regex$只可能从字符串默认倒数的第五个字符开始匹配，这样可以略过很多字符，达到优化的效果。

尽量使用长度优化

如果你知道一个字符串的长度不超过多少，或者这个字符串是定长的，那么请一定加上长度匹配，比如d{11}匹配11位的数字，d{4,8}匹配4到8位的数字，在匹配的时候就不会匹配小于4位的数字。

使用占有优先量词和固化分组

占有优先量词

?+ *+ ++ {m,n}+

占有优先量词与匹配优先量词很相似,只是它们从来不会交还已经匹配的字符。固化分组

(?>...) ...是指具体内容

固化分组的内容与正常的匹配并无区别，只是当匹配完括号中的内容后，括号中的备用状态会全部舍去。

是否使用非捕获型括号

在上一篇文章正则表达式的基本使用中指出了使用非捕获型括号有利于性能提升，因为你不在需要捕获文本的开销,但是这也不是必然的，比如(000|999)$使用了非捕获型括号之后反而比之前还变慢了，那是因为非捕获型括号不会使用$这个锚结尾优化，但是大多数时候非捕获型括号都是有益的，所以这个使用就需要自己权衡。

尽可能少的编译

正则表达式的编辑也是需要耗费时间的，不要每次在循环内重新编辑正则表达式

不要滥用括号

只有在需要的时候才使用括号，要不然括号会阻止某些优化措施，比如.*请不要用成(.)*

不要滥用字符组

字符组使用时有好处，但是不要滥用呀,并不需要用到字符组提供的多字符匹配功能的时候请不要使用字符组

像写代码一样优化

这个是什么意思？其实就是尽量将常量字符串提取出来,将共同的部分提取出来

别写太长的正则表达式

太长的正则表达式效率不一定高，而且后期不好维护，所以尽量不要写太长的表达式，就算有长的也尽量拆分成比较短的正则表达式，能用字符串处理解决的就尽量不用正则表达式。

使用环视模拟开头符识别

如果正则表达式为 Jan|Feb|Dec， 对应的就是(?=[JFMASOND])(?:Jan|Feb|Dec)。 开头的[JFMASOND]代表了英文中月份单词可能的开始字母。

将尽可能多的多选分支放在前面

多选分支下尽可能将出现概率比较大的表达式放在前面，比如匹配主机名的表达式中(?:aero|biz|com|cooph|...)的效率没有(?:com|net|edu|org|...)的效率高

Thompson构造法

汤普森构造法在计算机科学中是指一个能将正则表达式转化为一个与之等价的非确定有限状态自动机（NFA）的算法。算法得到的NFA可以在编程中用于匹配一个正则表达式，这也是正则表达式引擎实现的基本思路之一。

正则表达式和非确定有限状态自动机是形式语言的两种不同的抽象表达方式。在诸如文本编辑器的高级“查找和替换”以及许多编程语言中，人们都习惯使用正则表达式来表示字符串的匹配模式。然而，当计算机执行匹配程序时，NFA却是更加适合的一种格式。因此，汤普森构造法有着重要的应用价值，它实际上可以视作正则表达式到NFA的一个编译器。而从理论角度上来说，该算法实际上是正则表达式和NFA等价性证明的一部分——事实上，这两种表述形式本质上都对应着相同的语言，即正则语言。

在应用中，算法得到的NFA可以再次通过幂集构造和最小化的过程得到一个对应的最简的确定有限状态自动机（DFA），进而用于匹配正则表达式。但是有些情况下也会直接使用对应的NFA。

算法介绍编辑

构造规则编辑

算法通过递归地将一个正则表达式划分成构成它的子表达式，在得到每个子表达式对应的NFA之后，根据子表达式之间的运算关系和一系列规则构造表达式自身对应的NFA。(([1]))具体来说，这套构造规则如下所示(([2])) ：

递归终点编辑

对于正则表达式为ε或者只由一个符号构成的情况，则无需继续递归，对应的NFA可以直接由下列规则给出：

空表达式ε直接转化为：

字母表中的单个符号a直接转化为：

子表达式运算的构造规则编辑

下面针对正则表达式的三种运算——并、连接和Kleene*闭包给出NFA的构造规则。设子表达式为s和t，则它们对应的NFA分别记作N(s)和N(t)。

两个正则表达式的并s|t可以转化为：

通过ε转移， 状态q 可以直接到达N(s)或N(t)的初态。而N(s)或N(t)原来的终态也可以通过ε转移直接到达整个NFA的新终态。

连接表达式st可以转化为：

N(s)的初态成为新的NFA的初态。 原来N(s)的终态成为N(t)的初态。而原来N(t)的终态成为新的NFA的终态。

Kleene*闭包s((*))可以转化为：

将新表达式的初态和终态以及夹在中间的子表达式的NFA N(s)连接起来的ε转移使得可以选择经过或者不经过子表达式。而从N(s)的终态到初态的ε转移使得s可以重复任意多次。

• 加括号的表达式 (s) 直接转化为 N(s) 自身即可。

构建正则表达式抽象语法树

1. 算法描述：

整个语法树的构建过程中需要一个词法分析器Lex，词法分析器从左到右逐个字符地扫描正则表达式，根据遇到的字符返回正确的Token给语法树构建器，对于不合法的正则表达式给出报错信息（例如转义字符后面跟的不是特殊字符）。 语法树构建器拿到词法分析器返回的词法Token后，开始进行自下而上的建树过程，在不考虑括号的情况下，正确的正则表达式的第一个词法Token应该是一个非运算符，它被包装为语法树节点结构然后被压入语法树构建器的语法树节点栈中。

之后第二个词法Token可能是一个运算符也可能是一个非运算符，如果是非运算符，则需要添加一个表示连接的cat运算符到运算符栈中，并将得到的操作数Token包装为语法树节点压入语法树节点栈中。每次向运算符栈中压入新的运算符new之前，都需要查看当前运算符栈顶的运算符old，和new谁的优先级更高，如果old的优先级较高，则先处理old运算符（会用掉语法树节点栈中的节点，运算得到的节点再压回语法树节点栈），old被处理完后，old出栈，接下来的栈顶元素成为old，再次和new进行比较，重复这个过程，直到old的运算符优先级低于new，再将new运算符压栈。如果遇到了左括号，则先将左括号压入运算符栈中，在遇到右括号时需要将运算符栈中的节点从栈顶开始处理，直到处理到最靠近栈顶的左括号为止。当正则表达式处理完后，最后再处理运算符栈中剩余的运算符。正确的结果应该是运算符栈为空，语法树节点栈中有一个节点，这个节点就是整个语法树的根节点。

例子：对正则表达式（a|b)*a|bcd 构造语法树。过程如下：

1. 词法分析器从左向右扫描表达式，先得到左括号，将左括号包装成节点，压入运算符栈中； 
2. 词法分析器获得的下一个节点为字符a，压入语法树节点栈中； 
3. 词法分析器继续获取词法Token，得到运算符|，压入运算符栈中； 
4. 下一个字符是b，将b包装成节点压入语法树节点栈中； 
5. 继续获取字符，得到右括号，此时语法树构建器开始根据语法树节点栈和运算符栈进行运算合并已有节点，
直到在语法树节点栈中遇到左括号为止。开始处理时语法树节点栈和运算符栈中内容如下： 运算符栈：
（| 语法树节点栈：ab 运算符栈的栈顶运算符出栈，得到|运算符，这是一个双目运算符，所以从语法树节
点栈中出栈2个节点b和a，|运算符和节点a节点b，得到新的节点（记为M），M再压入语法树节点栈，
此时在运算符栈顶已经是左括号，将其出栈，节点合并结束。 两个栈的内容如下： 运算符栈：空 语法树节点栈：M 
6. 接下来是*号运算符，因为*号是优先级最高的运算符，所以可以直接处理，无需进行运算符优先级的比较，
  *号会消耗语法树节点栈中一个节点（也就是M），*号运算符和M节点运算得到新的节点N，重新压入节点栈中。
7. 接下来词法分析器得到字符a，但是在节点N和字符a之间需要插入一个连接cat运算符，
我们把cat运算符用‘+’来表示，‘+’压入运算符栈，a压入节点栈。 
8. 词法分析器得到的下一个Token是运算符|，在向运算符栈中压入‘|’运算符之前，我们需要检查运算符栈的栈顶运算符和当前想要压栈的运算符的优先级，
如果栈顶运算符的优先级大于等于将要压栈的运算符，则需要先处理栈顶的运算符（这里是一个循环的过程，也就是说处理完栈顶的运算符之后，
还要继续比较栈顶的运算符和将要压栈的运算符之间的优先级，以决定接下来该执行什么步骤）。在这里栈顶的运算符‘+’的优先级比运算符‘|’的优先级高，
所以先进行栈顶运算符的运算，‘+’连接运算符将节点N和a组成为新的节点（记为P）并重新压入节点栈中。然后运算符栈为空，此时把前面所说的“将要压入运算符栈的‘|’运算符”压入运算符栈。 
9. 下一个字符是b，此时不需要插入连接运算符，只需要将字符b包装为节点压入节点栈。 
10. 下一个字符是c，此时同样需要插入一个连接运算符，在向运算符栈中压入‘+’运算符之前，我们需要检查运算符栈的栈顶运算符和当前想要压栈的运算符的优先级。在这里‘+’的优先级高于栈顶的‘|’，
所以直接将运算符‘+’压入运算符栈中，并将字符c包装为节点压入节点栈。
11. 下一个字符是d，此时同样需要插入一个连接运算符，在向运算符栈中压入‘+’运算符之前，我们需要检查运算符栈的栈顶运算符和当前想要压栈的运算符的优先级。在这里两个运算符相同，
所以先处理运算符栈栈顶的运算符，‘+’运算符和节点栈中的b,c字符组成新的节点Q压入节点栈，然后运算符栈顶的运算符为‘|’，‘+’的优先级高于‘|’，所以不在处理运算符栈的栈顶运算符。
将‘+’压入运算符栈，将字符d包装为节点压入节点栈。 
12. 此时词法分析器报告已经到达正则表达式的结尾，所以开始处理运算符栈中剩余的运算符，从栈顶开始依次处理，首先遇到的是‘+’连接符，从节点栈中取出节点Q和字符d生成新的节点R压回节点栈。
13. 继续处理运算符栈，栈顶运算符为‘|’，从节点栈中取出节点P和节点R生成新的节点S压回节点栈。 
14. 此时运算符栈清空，节点栈中只有一个节点S，S就是最终生成的语法树的根节点。（至此大功告成、功德圆满^_^呼呼） 可以看出，我们遇到一个非运算符时，需要检查是否需要添加cat连接符，
在向运算符栈中添加一个新的运算符时，需要比较栈顶运算符和将要添加的运算符之间的优先级，以决定是否先进行栈顶运算符的运算

如何选择

首先应该明确以下问题

• 模式是用户输入还是常量？
• 是搜索模式或匹配模式？
• 模式平均有多长？
• 单一模式的话，使用频次是多少
• 我们真的需要正则表达式的全部功能吗？
• 我们真的需要不确定性（捕获组、lookarounds）吗？

如果模式是用户输入的构建，那么手动优化的空间很小。建议转换为更快的自动机（Thompson NFA、Bitparallel NFA 或 DFA）。常量正则表达式可以手动优化，通常会达到性能提升。

是搜索还是匹配的决定很重要，因为搜索需要更复杂的自动机。回溯 NFA 对搜索非常不利。使用位并行 NFA（短预处理）可以有效地搜索较小的表达式，较大的表达式可能需要 DFA。

短的简单模式的优化效果远小于长的复杂模式。恶意正则表达式包含嵌套在重复部分中的替代项（转换时的高性能提升）。非常简单的是flat expressions （没有替代品），它只包含通配符、字符类和可选字符（转换时性能提升低）。

模式应用得越频繁，对 DFA 的优化就越重要。没有重用的模式可能会被排除在进一步优化之外，因为在这种情况下，DFA 的生成时间占主导地位。

通常我们并不真正需要正则表达式的全部功能。有时我们可以将问题限制为多字符串搜索（不允许使用 Kleene-Star (*)）或通配符搜索（不允许替代），这两种方法在没有正则表达式的情况下都很有效。

“非确定性”正则表达式有一些不容易模仿的特征：捕获组和反向引用。这意味着我们需要一个 NFA。在正则表达式搜索的情况下，使用更有效的等效 DFA 收集匹配项然后使用 NFA 应用验证和子匹配提取可能是有效的。

还有一些可以避免的功能：环视。在日常工作中可能很方便（我们通常不会处理数十亿字节）。然而，在大多数情况下，我们可以找到一个等价的正则表达式而无需环顾四周。这不仅更有效（不考虑使用的自动机），而且通常也更容易理解。即使正则表达式是根据用户输入计算的，我们也应该考虑是否授予用户这种灵活性。