关于正则表达式

发表于 2014 年 03 月 18 日 · 归类于代码 · 阅读完需 9 分钟 · 报告错误

所谓正则表达式，就是一种描述字符串结构模式的形式化表达方法。在许多工具（如文本编辑器）及编程语言（如 Perl、JavaScript、awk）中，正则表达式都扮演了极其重要的角色。

正则表达式的起源

关于正则表达式，最初的想法来自 20 世纪 40 年代的两位神经学家研究出一种模型，认为神经系统在神经元层面上就是像现在的正则表达式这样工作的。1968 年 Ken Thompson 开发了他的文本编辑器 ed，其中一个命令是显示正在编辑的文件中能够匹配特定正则表达式的行。这一功能随后成为独立的工具 grep。

正则表达式

完整的正则表达式由两种字符构成：元字符和普通文本字符。

1、元字符

元字符是指那些不表示其本身含义，而具有特殊含义的特殊字符。比如表示匹配字符串开始和结束的 ^、$，匹配除换行之外的任意字符的 .，表示量词的 *、+、? 等等，都属于元字符。

2、字符组

字符组表示匹配若干字符中的一个。例如，正则表达式 gr[ae]y 表示先匹配一个 g，跟着是一个 r，然后是一个 a 或者 e，最后是一个 y。

在字符组内部，连字符 - 是元字符，表示一个范围：h[1-6] 与 h[123456] 是完全一样的，而其他的元字符在字符组中都不是元字符。

用 [^1-6] 取代 [1-6]，就会匹配一个不在字符组中的字符。

3、锚点及零宽断言

锚点和零宽断言只匹配（或者不匹配）文本中的特定位置，不会「占用」任何字符。

i、正则表达式中的常用锚点

起始位置和结束位置：^、$、\A、\Z
单词分界符：\b、\B、\<、\>
上一次匹配结束位置：\G

ii、顺序环视与逆序环视

环视是一种零宽断言，提供了比单词分界符更加通用和强大的功能。顺序环视 (?=...) 及 (?!...) 从左至右查看文本，尝试匹配子表达式，如果能够匹配，就返回匹配成功信息。同样，逆序环视 (?<=...) 及 (?<!...) 则是从右至左查看文本。例：

$pop =~ s/(?<=\d)(?=(\d\d\d)+$)/,/g;
print "The US population is $pop\n";	# The US population is 298,444,215

中使用了环视功能在大数字中插入逗号，可见顺序环视和逆序环视均不「占用」文本的字符。

4、分组和捕获

正则表达式通过分组，分割称为多个子表达式，以提供更加灵活的功能。

i、分组捕获括号

(...) 有两种功能：分组和捕获。捕获型括号的编号是按照开括号出现的次序，从左到右计算的。括号中的子表达式匹配的文本，可以用 \1、\2、\3 来引用。

ii、分组而不捕获括号

仅用于分组的括号 (?:...) 不能用来提取文本，而只能用来规定多选结构或者量词的作用对象。

iii、命名捕获

顾名思义，命名捕获 (?<Name>...) 就是对捕获的分组进行命名，可以提高代码可读性。

iv、固化分组

固化分组 (?>...) 与回溯的关系紧密，常用于对表达式的优化。在固化分组匹配结束时，已经匹配的文本将固化为一个单元，括号内的子表达式中未被尝试的备用状态都不复存在。比如：

"Subject" =~ /^(?>\w+):/

使用固化分组来删除不必要的回溯，可以优化正则表达式的匹配效率。

v、多选结构

正则引擎对于多选分支 ...|...，会从左至右依次尝试所有子表达式，直到匹配成功。

5、匹配优先量词和忽略优先量词

正则表达式中的量词（?、*、+ 等）在默认情况下都是匹配优先的（也叫贪婪模式）。如果要使用忽略优先，需要在标准量词后面加一个 ?，比如 *? 是 * 的忽略优先表示法。

6、模式修饰符

正则表达式允许使用模式修饰符来设定不同的匹配模式。比如常见的 /i 会启用不区分大小写的匹配，下面的列表是几种常见的模式修饰符：

字母	模式
`i`	不区分大小写的匹配模式
`x`	宽松排列和注释模式
`s`	点号通配模式（单行文本模式）
`m`	增强的行锚点模式（多行文本模式）
`g`	全局匹配模式

正则引擎与匹配原理

1、两类引擎

正则引擎主要可以分为基本不同的两大类：一种是 DFA（确定型有穷自动机），另一种是 NFA（非确定型有穷自动机）。判断是哪种引擎的方法是：

"nfanot" =~ /nfa|nfanot/

如果只有 nfa 匹配了，说明正则引擎是 NFA，如果整个 nfanot 都能匹配，则此引擎是 DFA。

NFA 属于表达式主导引擎。在这种引擎中，正则表达式每次检查表达式的一部分，同时检查当前文本是否匹配表达式的当前部分。如果是，则继续表达式的下一部分，如此继续，知道表达式的所有部分都能匹配，即整个表达式能够匹配成功。

与表达式主导的 NFA 不同，DFA 引擎在扫描字符串时，会在表达式中记录当前有效的所有匹配可能。这种方式中字符串中的每个字符都对引擎进行了控制，所以称之为文本主导。

2、优先选择最左端的匹配结果

起始位置最靠左的匹配结果总是优先于其他可能的匹配结果。这条规则的由来是：匹配先从需要查找的字符串的起始位置尝试匹配。尝试匹配的意思是，在当前位置测试整个正则表达式（可能很复杂）能匹配到的每样文本。如果在当前位置测试了所有的可能之后不能找到匹配结果，就需要从字符串的第二个字符之前的位置开始重新尝试。

"The dragging belly indicates that your cat is too fat" =~ /(fat|cat|belly|your)/

匹配到的将是 belly。

3、标准量词是匹配优先的

在含有标准量词的表达式中，正则引擎总是希望获得最长的匹配：.* 经常会匹配到一行文本的末尾，除非有其他的情况需要“被迫”交还一些字符。

Apple published <b>macOS Sierra</b> and <b>iOS 10</b> this fall.

使用 .* 匹配上面的文本，得到的结果是 macOS Sierra and iOS 10 而不是单个标签中内容。

解决上面的问题就需要用到正则引擎中的忽略优先量词。

4、回溯

正则引擎在遇到分支时（需要做出选择的情形包括量词和多选结构），会选择其一，同时记住另一个，以备稍后可能的需要。在做出多次选择之后，正则引擎将会记住多个备用状态（这些状态按照后进先出方式存储），然后在某次匹配失败之后，引擎将会回溯到最近的一个备用状态进行重新匹配。

正则表达式的优化

1、使用固化分组加快匹配失败的速度

在固化分组内的表达式将不会创建备用状态，这样可以加快匹配失败的速度。

"Subject" =~ /^\w+:/
"Subject" =! /^(?>\w+):/

文本 Subject 中不含冒号，所有肯定无法匹配 ^\w+。但是在正则引擎中，必须通过多次回溯的尝试之后才能得出结论。而使用固化分组，\w+ 在成功匹配 t 之后（括号内的子表达式完成匹配）便会将其他的备用状态全部忽略掉。

对不支持固化分组的正则引擎，可以用占有优先量词或肯定环视模拟固化分组。

2、构造有序的多选结构

正则引擎对于多选分支，将会按照分支的顺序进行排列备选。所以根据目标字符串优化多选分支的顺序，也可以对提高匹配效率。其中一条准则是：将最有可能匹配的多选分支放在前面。

3、使用起始位置和结束位置的锚点避免冗余操作

例如一个以 \A 开头的正则表达式只有在字符串开始的位置才能匹配，入宫在此处无法匹配，正则引擎不会再进行徒劳的尝试。

4、提取多选结构开头的必须元素

比如对于表达式 this|that，每个多选分支都以 th 开头，如果第一个分支无法匹配 th，第二个也显然不行，所以不必白费功夫。因此可以用 th(?:is|at)，这样 th 就只要检查一遍。

5、将锚点独立出来

用 ^(?:abc|123) 代替 ^abc|^123，虽然两者在逻辑上是等价的，但是明显前者的效率更高。

参考资料

Jeffrey E. F. Friedl，精通正则表达式，电子工业出版社