深入浅出 Hyperscan:高性能正则表达式算法原理与设计
上QQ阅读APP看书,第一时间看更新

正则表达式的元字符

下面列举了一些常见正则表达式的元字符,这里仅做简要的说明。此外,不同的流派支持的元字符和这些元字符代表的意义存在着细微的差异,这里参考了 Perl 兼容正则表达式(Perl Compatible Regular Expression,PCRE)的语法。关于PCRE的内容,请参考1.2.1小节。类似于数学运算符,正则表达式的元字符之间也有优先权顺序。在匹配过程中,按照正则表达式中从左到右、不同优先权先高后低来匹配相应的元字符。下面列举了优先权从高到低的正则表达式元字符的类型:转义符、字符组、分组、匹配量词、锚点和零宽断言,以及多选结构和嵌入条件等。

1.转义符

转义符用来清晰简便地表示一些特定的字符,包括一些不可打印字符。转义符和相关元字符,如表1.1所示。

表1.1 转义符和相关元字符

(1)利用转义符来匹配具有特殊含义的元字符本身。举例说明,*在正则表达式中是一个量词元字符,表示匹配前面的子表达式零次或任意次,但是转义之后*匹配的是*这个元字符本身。同样地,要匹配\元字符本身,需要写成\。

(2)利用字符缩略表示法来匹配其他方式很难描述的ASCII控制字符和不可打印字符,最常见的就是\n匹配换行符LF,\r匹配回车符CR。其中一个特别的用法是用\cX来匹配X指明的控制字符,X的值为A~Z或者a~z,例如\cJ匹配换行符LF,\cM匹配回车符CR。

(3)八进制转义和十六进制转义。\0dd表示八进制数dd所代表的字符,\xhh表示十六进制数hh所代表的字符。

2.字符组

字符组指在正则表达式中的某个位置表示一组指定的字符。常见的字符组表示方法有点号、普通字符组和字符组简记法,如表1.2所示。

表1.2 字符组

(1)点号可以匹配除了换行符之外的任意一个字符,如果设置了点号通配模式(dot-match-all),则可以匹配任意一个字符。

(2)普通字符组指通过[…]来匹配方括号中所列字符组合中的任意一个字符,或者通过[^…]来匹配方括号中所列字符组合之外的任意一个字符。

(3)字符组简记法指对一些常见字符更简便的表示方法。例如\d匹配任意一个数字,等价于[0-9],\D匹配任意一个非数字字符,等价于[^0-9]。

需要强调的是,元字符的规定在字符组内外是有差别的。例如在字符组内部,*不是元字符,而-是元字符。此外,有些元字符在字符组内外的含义是不同的,例如\b匹配ASCII退格符,仅在字符组内部有效,在字符组外部则匹配单词边界。

3.分组

分组主要包括捕获型分组和非捕获型分组,如表1.3所示。

表1.3 捕获型分组和非捕获型分组

捕获型分组指的是以(…)标记的一个子表达式作为分组并捕获这个子表达式的匹配结果,这个捕获的结果可以利用前文提到的\1、\2……编号的方式来引用。这种分组并捕获匹配结果的(…)称之为捕获型分组。分组编号的规则是按照左括号(从左往右出现的顺序,从1开始编号。

还有一种命名捕获型分组(?<name>…)能够为捕获的内容命名,捕获的结果可以利用\1、\ 2……编号的方式来引用,也可以通过\k<name>的方式来引用。注意,如果捕获型分组和命名捕获型分组都用编号来引用,分组编号的规则是先只对普通捕获型分组按照左括号顺序编号,然后再对命名捕获型分组从左往右累计编号。

除此之外,(?:…)只支持分组,而不会捕获子表达式的匹配结果,因而也无法反向引用,这种称为非捕获型分组。非捕获型分组的作用主要是把复杂的表达式变得清晰,并且可以避免一些无用的捕获来提高正则表达式的效率。

还有一种特殊的分组(?>…)称为原子分组。也就是分组内的子表达式匹配之后,匹配的内容就固定下来不会交还已匹配的字符。原子分组也是非捕获型分组。

4.匹配量词

匹配量词能够用来限制前面子表达式的匹配次数。匹配量词又可以分为标准匹配量词、忽略优先量词和占有优先量词,如表1.4所示。

表1.4 匹配量词

(1)标准匹配量词包括*、+、?、{n}、{n,}和{n, m}。标准匹配量词都是贪婪(greedy)的,会尽可能地匹配更多的内容。举例来说,当正则表达式ab+去匹配字符串abbbb时,量词+会尽可能多地匹配字母b,所以最终的匹配结果是abbbb。

(2)忽略优先量词是在标准匹配量词之后紧跟?修饰符,即*?、+?、??、{n}?、{n,}?和{n,m}?。忽略优先量词和匹配优先量词正好相反,是非贪婪(non-greedy)的,会尽可能少地匹配内容。举例来说,当正则表达式ab+?去匹配字符串abbbb时,量词+?会尽可能少地去匹配字母b,所以最终的匹配结果是ab。

(3)占有优先量词是在标准匹配量词之后接+字符,即*+、++、?+、{n}+、{n,}+和{n,m}+。占有优先量词类似于标准匹配量词,但是匹配的结果不会“交还”或者说回溯。举例来说,当正则表达式a.*b和a.*+b同时去匹配字符串acccb时,a.*b会匹配成功,而a.*+b会匹配失败。原因是不管是.*还是.*+,它们都是匹配优先的,并且“贪婪”地匹配到了字符串acccb中的cccb, 但是.*+不会回溯已匹配到的结果,所以正则表达式 a.*+b 中的b会发现这时候字符串中已经没有b可以匹配,从而整个正则表达式匹配失败。占有优先量词能够控制匹配和不能匹配的内容,在某些场合下使用占有优先量词能够提高匹配效率。原子分组的概念类似于占有优先量词,例如,(?>\d+)的含义等价于\d++。

5.锚点和零宽断言

正则表达式中的锚点和零宽断言都不会匹配实际的字符,而是寻找和定位字符在文本中的位置,可以认为都是定位符,如表1.5所示。

表1.5 锚点和零宽断言

6.多选结构和嵌入条件

多选结构…|…能够在同一位置测试多个子表达式,每个子表达式被称为一个多选分支。在匹配时,整个多选结构被视为单个元素,只要其中某个子表达式能够匹配,整个多选结构的匹配就成功;如果所有子表达式都不能匹配,则整个多选结构匹配失败。

多选结构常常和嵌入条件一起使用,如表1.6所示。常用的嵌入条件形式是(?(ref)yes_exp|no_exp),表示如果编号ref引用的捕获型分组存在,则匹配yes_exp,否则匹配no_exp。例如,上海地区固定电话号码一般写成021-12345678或者(021)12345678,可以用正则表达式(()?021(?(\1))|-)\d{8}来匹配这两种写法。其中(?(\1))|-)部分表示如果前面(()捕获到了匹配,那么继续匹配一个右括号),否则匹配一个横线-。

表1.6 多选结构和嵌入条件

7.模式修饰符

除了常用的元字符以外,正则表达式也经常可以通过模式修饰符(?modifier)来设置匹配的模式,如表1.7所示。常见的模式modifier的值如下。

(1)i:表示忽略大小写的模式。

(2)s:表示点号通配模式,即点号可以匹配换行。

(3)m:表示多行模式,在这种模式下^、$、\A和\Z这些锚点符匹配的是行起始位置。

表1.7 模式修饰符

模式修饰符设置模式打开之后可以通过(?-modifier)来停用。此外,模式修饰符的作用范围局限于一个括号分组内。还有一种更简单的指定模式修饰符作用范围的方法是(?modifier:…),表示其作用范围只在当前这个括号内有效。