正则表达式学习笔记

正则表达式编译

检查正则表达式的语法正确性，如果正确，就将其编译为内部形式
传动开始

传动装置将正则引擎“定位”到目标字符串的起始位置

P.S.简单解释一下“传动”，就是正则引擎内部的一种机制，例如，将[abc]应用到串family上，首先尝试首位的f，失败，接着到第二位的a，成功，匹配结束。注意，这个过程中是谁在控制这种“按位”处理（先第一位，失败后尝试第二位…）？没错，正是所谓的传动装置
元素检测

正则引擎开始尝试匹配正则表达式和文本，不仅有按位向前进行，还有回溯过程（回溯是一个重点，会在后面详细解释）
得出匹配结果

确定匹配结果，成功或者失败，其具体过程与正则引擎的类型有关，例如找到第一个完全匹配的串就返回成功结果，或者找到第一个合格的串后继续寻找，返回最长的合格串
驱动过程

如果在当前位置没有找到合适的匹配，那么传动装置会驱动引擎，从当前位置的下一个字符处开始新的一轮尝试
匹配彻底失败

如果传动装置驱动引擎到指定串尾，仍然没有找到合适的匹配，那么匹配宣告失败（简单点说就是，从头到尾都没匹配上的话就算失败，这里之所以描述的那么艰涩，是为了更贴近其内部原理）

二.正则引擎

所谓的正则引擎类型其实是一种分类，前面说过了，正则是一种技术，所有人都可以运用它来解决问题，而大家解决问题的思路都不同，换言之就是正则表达式的具体实现都不同，规则各不相同。于是经过长期的发展，最终形成了一些流派，各个流派推行的规则不同。

常见的流派（正则引擎类型）有以下几种：

NFA（中文是“非确定型有穷自动机”，不用理会这奇怪的名字…）
DFA
POSIX NFA
DFA，NFA混合型

我们不必知道各个引擎的分类标准是什么，只需要明白相互之间的区别以及我们常用的工具所属分类就好了，非常简单：

NFA

此类工具：Java，GUN Emacs，grep，dotNet，PHP，Python，Ruby等等

区别：NFA，我们可以称之为正则表达式主导型引擎，因为其匹配效率与正则表达式密切相关（例如表达式中多选分支的顺序）
DFA

此类工具：awk，egrep，flex，lex，MySQL，Procmail等等

区别：DFA，我们称之为文本主导的引擎，其匹配效率之与文本（目标串）有关（等价但不同形式的表达式效率相同，例如[a-d]与[abcd]，注意，在NFA中这两者效率是不同的，一般来说前者更好一些）
POSIX NFA

此类工具：mawk，Mortice Kern System’s utilities等等

区别：无论匹配成功与否，都要尝试所有可能，试图找出能够匹配的最长串
DFA，NFA混合型

此类工具：GUN awk，GUN grep/egrep，Tcl

区别：此类引擎应该说是最好最成熟的，引擎内部优化做的相对完善，集DFA与NFA二者的优点与一身，但目前应用此类引擎的工具很少

说了这么多，其实我们要知道的是：

使用一个支持Regex的工具之前，首先要知道它的引擎所属类型，这是极其重要的，因为不同的引擎具体工作机制不同，比如，PHP的三套正则库都属于NFA型，其匹配与表达式密切相关，所以我应该对表达式进行合理优化，以提高效率。

三.正则环视（lookaround）

[其实这个东西没有必要单独列出来，因为它只是正则表达式很小的一部分内容，但鉴于一部分人不知道“环视”，也有一部分人听过，但不了解，觉得这东西很高深…所以还是单独拿出来讨论一下（绝对不难）]

1.什么是“环视”？

单纯理解汉字，“环视”就是向四周观望，正则环视其实也就是这个道理——驱动到一个位置，先向左右看看这个位置是不是我们要找的位置

举个例子，用(this|that)来匹配there is a boy lying under that tree.很明显，这个表达式在NFA引擎下效率很低，它是这样工作的：

首先，遇到第一位t，按位检查this，发现i与e不匹配，就按位检查that，发现a与e不匹配；
驱动前进一位，到h，按位检查this…按位检查that…；
驱动前进一位，到e，…….
。。。

做了很多无用功，那么要怎么优化？

可以把前缀提取出来（常用的优化方式之一，后面有总结），变成th(is|at)

当然，我们在这里讨论的是环视，就用环视来解决，变成(?=th)(this|that)，哎呀，前面的(?=)看不懂怎么办？

没关系，这个就是肯定顺序环视，表示的意思是：我从开头向后走，遇到th就停下来，比对(?=th)后面的表达式部分——(this|that)【注意，反之就是说如果没遇到th就不停，直接向后继续走…效率是不是有点变化呢？】

优化后比较的次数明显降低，当然这里用环视似乎有些小题大作了，我们只是举个应用环视的简单例子而已，不必较真

2.正则环视的种类极其作用

类型	正则表达式	匹配成功的条件
肯定顺序环视	(?=…)	子表达式能够匹配右侧文本
肯定逆序环视	(?<=…)	___________________左______
否定顺序环视	(?!…)	子表达式不能匹配右侧文本
否定逆序环视	(?<!…)	___________________左______

P.S.上面的左右侧指的是匹配进行的当前位置的左右侧，这与一般的匹配不同，举个例子：

用肯定顺序环视(?=a)abc匹配串family，初始位置是f的前面而不是f所在位置，为什么会这样？

因为【环视结构不匹配任何字符，只匹配文本中的特定位置】，如果当前位置是f与a之间的话，肯定顺序环视匹配成功，开始按位检测abc。

我们发现：肯定顺序环视能够限制真正开始比较的位置，从而减少尝试次数

3.环视的应用

环视多用于表达式的优化，与其他一些特殊的场合（不用环视不行的场合，当然，一般来说，环视都可以用其他复杂一些的结构来代替）

例如，要匹配the land blongs to these animals中的单词the，如何避免匹配到these中的the？

我们很容易想到单词分界符（如果引擎支持的话），用\bthe\b进行全局匹配就可以了

其实针对此例，我们还可以用the(?!\w)来完成目标，前面的the即便匹配了these中的the也不要紧，后面的否定顺序环视(?!\w)会将these排除（这里的否定顺序环视限定了e的后面不能是单词的字母，具体的说\w等价于[a-zA-Z0-9]，在这里或许不是很合适，但勉强能说明问题）

四.回溯（在提及优化之前，回溯是绝对是一个重点问题）

简单的说，回溯就是倒退到未尝试过的分支（或者说是回到备用状态，当然，对不熟悉正则的人来说第一种说法更容易理解，而第二种说法则更确切一些）

举个简单的例子，用.*!来匹配串”An idel youth, a needy age!”, an old saying said.

首先，*修饰.可以匹配任意多个任意字符（点号表示任意字符，*表示任意数量），而且*是匹配优先的（就是*会尽可能长的匹配串）
所以.*匹配了整个串（从A到.），这时检测发现!无法匹配了，怎么办？
.*匹配的串必须交还一部分来让!有机会匹配，交还了句末的点号，!还是无法匹配
继续交还，这次是d，无法匹配
。。。
到age后面的!被交还，匹配成功

整个过程中从.*占有整个串到被迫交还!的时间里，进行的动作就是回溯（简单的说就是引擎的驱动在往回走）

类似这样的回溯显然是毫无意义而且浪费时间的，我们要做的优化很大一部分工作就是减少回溯次数。

从另一个角度看，减少回溯的作用是提高了匹配的效率，或者说是缩短了引擎从开始工作到反馈匹配结果（成功/失败）的时间，这不正是优化吗？

五.正则表达式的优化

效率指标

考察一个正则表达式的效率，参考指标主要有两个：尝试（比较）次数与回溯次数

在保证表达式正确性的基础上，尝试次数与回溯次数越少越好，次数少意味着能够更快速的找到合适的匹配（或者更快速的反馈匹配失败）
优化操作

优化操作有两个方向：
1. 加快某些操作
  
  这需要结合具体的引擎内部实现来考虑，例如，一般来说，在NFA引擎下，[\d]要比[0-9]快，[0-9]要比[0123456789]快
2. 避免冗余操作
  
  也就是精确限制，比如上面提到的正则环视的例子，对匹配开始位置加以限制，就能大大提高效率
  
  当然，做此类优化时需要权衡，如果花费了很大一部分时间用来限定位置，而匹配的效率却下降了，那么这样的优化是不可取的
要不要优化？优化到什么程度？这都需要我们结合具体应用场景来权衡

常用优化方法

优化方法非常多，这里只列举出最常用的一些优化方法（有兴趣的可以参考相关书籍）
1. 消除不必要的括号
  
  在很多场合，添加()只是为了限定两次的作用范围，而不是为了捕获匹配文本，这时应该用非捕获型括号(?:)代替捕获型括号()，不仅能减少内存开销，还能大大提高效率
2. 消除不需要的字符组
  
  有的人习惯用[.]这样的字符组来表示单个特殊字符，其实可以用.来替换，类似的有[*] -> \*等等
3. 避免反复编译
  
  这一点是说在其它工具中应用正则时需要注意的，比如，用Java来将一个正则表达式应用到一串文本上，首先需要对正则表达式进行编译，不同的正则表达式只需要编译一次，所以编译的部分不应该放在循环内部，以此避免反复编译，节省额外的时间
4. 使用起始锚点
  
  这是应当养成的一个良好习惯，例如，大多数以.*开头的正则表达式都可以在前面加上^或者\A来表示行或者段落的开头，这样做有什么好处？
  
  在一些落后的引擎中，这样的优化效果非常明显，设想一下，如果.*对目标串进行一轮尝试后发现没有合适的匹配，那么如果表达式前面没有^或者\A，那么引擎要做的工作就是从目标串的第二个字符位置开始进行一轮新的尝试…当然，很明显这样做没有意义（我们很清楚地一轮匹配结束后匹配结果就出来了，根本不需要第2轮甚至第n轮）
  
  而一些发展比较成熟的引擎可以对这样的表达式做自动优化，如果检测到.*开头的表达式前面没有^或者\A，引擎会自动为表达式加上起始位置标志，避免无意义的尝试
  
  对于我们而言，在.*前面加上起始标志应当成为一个习惯
5. 将文字文本独立出来
  
  例如[xx*]比[x+]更快，x{3, 5}没有xxxx{0, 2}快，th(?:is|at)比(?:this|that)快

六.如何写出高效的正则表达式？

写正则表达式应当遵循以下步骤：

匹配期望文本
排除不期望的文本
易于控制和理解
保证效率，尽快得出结果（匹配成功/匹配失败）

前两点保证了表达式的正确性，后两点需要在效率与易用性之间做出恰当的取舍，这就是写正则表达式的原则

这里有一句非常经典的话，基本可以说明一般原则——不要把孩子连同洗澡水一起倒掉

七.几个易错点

[-./]与[.-/]与[./-]的区别

乍看好像没什么区别，其实第一个和第三个是等价的，表示当前位置上的字符必须是中划线，点号或者斜杠

第二个表达式是错误的，表示当前位置上的字符必须是从点号到斜杠之间所有字符中的任意一个（简单的说就是这里的-表示范围，类似于[a-z]），但明显点号到斜杠之间存在什么字符与字符集环境有关，如果是Unicode字符集，则会出现很多奇怪的字符，与我们的原意不符

所以在字符组中使用-时，必须仔细查看-所处的位置，避免此类错误
^在[]内外的区别

^在外面表示行的开头，$表示行的末尾，^在里面表示“非”（[^…]即所谓的排除型字符组）或者普通字符（[…^]）
[ab]*与(a*|b*)的区别

二者看似等价，其实存在一种特殊情况：前者能够匹配aba而后者不能，除此之外，前者的效率要更高一些
使用量词修饰符（?+*）时的易错点

当存在嵌套使用的量词时，应当仔细揣摩语义，避免造成循环（无限回溯），例如用”(\.|[^\”]+)*”来匹配文本中的连续双引号部分，引号中的部分可以包括用反斜杠转义的双引号，这个表达式就会造成循环，几乎永远得不到匹配结果

而存在量词嵌套并不一定导致循环，总之，表达式中出现量词嵌套时应当非常谨慎的对待

八.总结

个人对正则表达式的看法是：

如果对正则理解的不是很透彻，那么尽量不要尝试用正则去解决复杂的问题（或者说是尝试应用很长的正则表达式），因为其中存在的一些陷阱会让你百思不得其解，构造一个完美的正则表达式需要相当缜密的思维，而在一般应用中，我们用程序进行串的匹配要更易于控制一些。

当然，也不是说尽量不要用正则（不能因噎废食），不得不承认在某些场合，正则有着不可替代的神奇作用（例如从文本中提取URL…）

而且，即便自己不用，也应该充分理解正则表达式，因为别人会用，所以我们总会遇到

引用匹配

一种不常见的用法，可以在正则表达式中引用已匹配的部分，示例如下：

// js code
var regex = /(\w{2,4}).+\1.+\1/i;
console.log(regex.test('qwer11qwe213234qw'));   // true
console.log(regex.test('qwer11qwe213234q'));    // false

用于检测含有未知重复序列的串（只知道重复序列出现的次数，不知道重复序列具体是什么），上例中的重复序列是qw

九.附表【元字符表】【模式控制符表】【特殊元字符表】

1.元字符表（此处提供大多数工具共同支持的元字符）

元字符	名称	含义
^	脱字符	表示行开始位置
$	美元符	表示行结束位置
.	点号	表示任意字符（一般不能表示行尾的\n）
[]	字符组	表示括号中字符的任意一个（必须要匹配一个字符）
[^]	排除型字符组	表示除括号中字符外的任意一个字符（必须要匹配一个字符）
\char	转义字符	表示char的另一种含义，例如\^表示普通字符^而不再表示行开始位置
()	（捕获型）括号	表示量词的作用范围或者捕获匹配的文本（可以在反向引用中获取捕获到的文本）
(?:)	非捕获型括号	与括号功能相同，但不捕获文本
?	问号	量词，表示左边的部分可有可无
	星号	量词，表示左边的部分可以有任意多个（当然，也可以一个都没有）
+	加号	量词，表示左边的部分至少出现一次，至多不限
{min, max}	区间	量词，表示左边的部分至少出现min次，至多出现max次
{num}	特殊区间	量词，表示左边的部分必须出现num次
\|	竖线	表示或者，用来实现多选结构
\<	单词分界符	表示单词开始位置
\>	单词分界符	表示单词结束位置
\num	反向引用	表示第num个捕获型括号捕获的文本（括号计数是按照左括号出现的顺序算的，注意嵌套括号）

2.模式控制符表（此处提供一些模式控制符例子，在具体的工具中可能不同）

控制符	含义
i	匹配忽略大小写
g	全局匹配，找出目标文本中所有能够匹配的部分，默认只找出第一个
x	宽松排列，正则表达式可以分散到多行并且可以包含注释
m	增强的行锚点模式，把段落分割成逻辑行，使得^和$可以匹配每一行的相应位置，而不是整个串的开始和结束位置
s	点号通配模式，在此模式下，点号可以匹配任意字符（默认点号只能匹配除换行符外的任意字符）

3.特殊元字符表（此处提供某些工具支持的特殊元字符）

元字符	含义
\d	数字，等价于[0-9]
\D	非数字字符，等价与[^0-9]
\w	数字及字母，等价于[a-zA-Z0-9]
\W	非数字和字母，等价于[^a-zA-Z0-9]
\s	空白字符，例如空格符，制表符，进纸符，回车符，换行符等等
\S	非空白字符
\b	单词分界符，表示单词的开始或者结束位置
(?>…)	固化分组，不交还任何与之匹配的字符，例如(?>\w+!)不能匹配Hi!
??与+?与?与{min, max}?	忽略优先量词，尽可能少的匹配内容（在能够匹配的情况下只匹配最短的内容）
?+与++与*+与{min, max}+	占有优先量词，语义同固化分组

声明，上面的所有内容来自笔者对参考书籍内容的理解

参考书籍：《精通正则表达式》(Jeffrey E.F Friedl著)

书评：这本书在章节进度安排，内容穿插强调，甚至排版方面都很不错（特殊的排版方式：书中提出的所有思考问题，都必须翻一页才能看到答案），对于深入理解正则很有帮助，有兴趣的朋友可以参阅

黯羽轻扬

正则表达式学习笔记

写在前面：（一点题外话，点我跳过>>）

一.正则表达式工作原理

正则表达式编译

传动开始

元素检测

得出匹配结果

驱动过程

匹配彻底失败

二.正则引擎

NFA

DFA

POSIX NFA

DFA，NFA混合型

三.正则环视（lookaround）

四.回溯（在提及优化之前，回溯是绝对是一个重点问题）

五.正则表达式的优化

效率指标

优化操作

加快某些操作

避免冗余操作

常用优化方法

消除不必要的括号

消除不需要的字符组

避免反复编译

使用起始锚点

将文字文本独立出来

六.如何写出高效的正则表达式？

七.几个易错点

[-./]与[.-/]与[./-]的区别

^在[]内外的区别

[ab]与(a|b*)的区别

使用量词修饰符（?+*）时的易错点

八.总结

引用匹配

九.附表【元字符表】【模式控制符表】【特殊元字符表】

写在前面：（一点题外话，点我跳过>>）

一.正则表达式工作原理

正则表达式编译

传动开始

元素检测

得出匹配结果

驱动过程

匹配彻底失败

二.正则引擎

NFA

DFA

POSIX NFA

DFA，NFA混合型

三.正则环视（lookaround）

四.回溯（在提及优化之前，回溯是绝对是一个重点问题）

五.正则表达式的优化

效率指标

优化操作

加快某些操作

避免冗余操作

常用优化方法

消除不必要的括号

消除不需要的字符组

避免反复编译

使用起始锚点

将文字文本独立出来

六.如何写出高效的正则表达式？

七.几个易错点

[-./]与[.-/]与[./-]的区别

^在[]内外的区别

[ab]*与(a*|b*)的区别

使用量词修饰符（?+*）时的易错点

八.总结

引用匹配

九.附表【元字符表】【模式控制符表】【特殊元字符表】

[ab]与(a|b*)的区别