首页 > 代码库 > 刨根究底正则表达式之二——正则表达式基础

刨根究底正则表达式之二——正则表达式基础

正则表达式基础

技术分享

 

一、正则表达式构成

1.

正则表达式中的语法元素,从是否具有特殊含义的角度进行分类,可分为下列两大类、共五种语法元素:

1)不具有特殊含义的语法元素

(1)  字面字符(文本字符)不具有特殊含义的单个字符,代表字符自身(即字符字面值);

(2)  普通转义序列:由转义前导符\后跟元字符所组成的字符序列,将具有特殊含义的元字符,转义为(即转换为)不具有特殊含义的字符本身(即字符字面值);

2)具有特殊含义的语法元素

(1)  元字符:具有特殊含义的单个字符,包括:\、(、)、[、]、{、}、.、-、*、+、?、|、^、$;

(2)  元转义序列:由转义前导符\后跟单个字符或多个字符组成,具有特殊含义,包括:\0octal-num、\num、\a、\A、\b、\b{}、\B、\B{}、\cX、\C、\d、\D、\e、\E、\f、\F、\g{}、\gnum、\G、\h、\H、\k{}、\k<>、\k‘‘、\K、\l、\L、\n、\N、\N{}、\o{octal-num}、\pP、\p{}、\PP、\P{}、\Q、\r、\R、\s、\S、\t、\u、\U、\v、\V、\w、\W、\xhex-num、\x{hex-num}、\X、\z、\Z等;

(3)  特殊构造(特殊结构)由多个元字符和/或普通字符组成,具有特殊含义,包括:字符组[xyz]或[^xyz]、捕获分组(sub-regex)、命名捕获分组(?<name>sub-regex)、非捕获分组(?:sub-regex)、预查分组(即环视分组)(?=sub-regex)或(?!sub-regex)或(?<=sub-regex)或(?<!sub-regex)、固化分组(即原子分组)(?>sub-regex)、嵌入条件分组(?(condition)true_sub-regex|false_sub-regex)、内联修饰选项与取消内联修饰选项分组(?modifier-modifier)、注释分组(?#comment)、分支复位分组(?|sub-regex)、表达式引用分组(?R)或(?num)、平衡分组(?<-name>sub-regex)等。

(笨笨阿林原创文章,转载请注明出处)

2.

从匹配的是位置还是字符的角度来分类,可分为如下四大类:

1)匹配字符的语法元素

(1)  字面字符(文本字符)代表字符自身(即字符字面值);

(2)  普通转义序列:将具有特殊含义的元字符,转义为(即转换为)不具有特殊含义的字符本身(即字符字面值);

(3)  元字符:.;

(4)  下面这些元转义序列:

固定字符:\a、\b(字符组内部)、\e、\f、\n、\r、\t、\v(非Perl系);

字符组简记:\d、\D、\h、\H、\N{}、\p{}与\pP、\P{}与\PP、\s、\S、\v(仅Perl系)、\V、\w、\W

进制转义字符:\octal-num(Perl系中也可写作\o{octal-num})、\xhex-num(Perl系中也可写作\x{hex-num})、\uhex-num(非Perl系,Ruby1.9+等个别语言中还可写作\u{hex-num});

控制字符:\cX系列;

其他:\C、\N、\R、\X。

2)匹配位置的语法元素

(1)  下面这些元字符:

^、$

(2)  下面这些元转义序列:

锚点:\A、\z、\Z、\b(字符组外部)、\b{}、\B、\B{}、\G;

其他:\<、\>。

(3)  预查分组:

(?=sub-regex)、(?!sub-regex)、(?<=sub-regex)、(?<!sub-regex)。

3)既可能匹配字符,也可能匹配位置的语法元素

(1)  由下限次数为0的量词所限定的子表达式,下限次数为0的量词包括:?、*、{0,}、{0,m}、{,m}(逗号“,”前面为空的这种写法仅部分正则引擎支持,不推荐这种写法);

(2)  下面这些元转义序列:

引用:\num、\g{num}、\gnum、\k{name}、\k<name>、\k‘name‘(如果引用的是文本,则匹配字符,如果引用的是位置或空字符串,则匹配的是位置);

(3)  特殊构造(特殊结构)捕获分组(sub-regex)、命名捕获分组(?<name>sub-regex)、非捕获分组(?:sub-regex)、固化分组(即原子分组)(?>sub-regex)、嵌入条件分组(?(condition)true_sub-regex|false_sub-regex)等,当这些分组中的sub-regex为空时,匹配的是位置;不为空时,若sub-regex匹配字符,则这些分组匹配的是字符,否则匹配的是位置。

4)既不匹配字符,也不匹配位置的语法元素

除上述语法元素之外的其他语法元素,这包括:\K、内联修饰选项与取消内联修饰选项分组(?modifier-modifier)、注释分组(?#comment)等。

3.

注意,语法元素有时也会称之为子表达式;当然,子表达式的概念要比语法元素更为丰富,涵盖面更广。因此,需根据上下文予以准确理解。

 

二、字符串构成

1.

从正则表达式的角度来看,字符串通常由位置和字符所共同构成,但空字符串仅由单个位置构成(该位置既是空字符串的起始位置,也是空字符串的结束位置,可同时匹配表示字符串起始位置的元字符^和表示字符串结束位置的元字符$)。

 技术分享

对于字符串“Regex”而言,是由五个字符以及六个位置构成的,理解这一点对于正则表达式的匹配原理的理解很重要。

2.

字符串中的位置,其实也是组成该字符串的字符的索引,因此,位置0就是用来索引(即定位)字符R的索引0。字符串“Regex”始于索引0(即位置0)处,止于索引5(即位置5)处。

当正则引擎在字符串中查找匹配时,可以认为在字符串中有一个匹配定位指针,该指针可以在字符串中的各个位置之间移动(一般是从左到右依次移动,但回溯时也会从右向左移动;另外,.Net中还支持从右向左匹配)。

3.

查找匹配过程中,下一次匹配的起始位置与前一次匹配的结束位置往往是相同的:

正则式:/regex/

字符串:regexregex

找到第一个子字符串"regex",开始于位置0结束于位置5

找到第二个子字符串"regex",开始于位置5结束于位置10

(笨笨阿林原创文章,转载请注明出处)

 

三、匹配过程与匹配定位指针、匹配控制权

1.

匹配过程从字符串的角度来看的话,必然总是从字符串中的一个位置开始匹配的,可能是从字符串的起始位置匹配,也可能是从字符串中间的某两个字符之间的位置开始匹配,甚至可能是从字符串的结束位置开始匹配(.Net中支持从右向左匹配)。当然,绝大部分情况下,均是从字符串的起始位置开始匹配的。

当在某个位置尝试匹配失败,正则引擎将移动字符串中的匹配定位指针到字符串中的下一个位置开始继续尝试匹配。这样逐个位置尝试,直到获得匹配,或者一直到字符串结尾仍未获得匹配则报告匹配失败。

2.

匹配过程从正则表达式的角度来看的话,必然总是从正则表达式的起始位置从左至右逐个语法元素开始尝试匹配的(但多选分支结构中的情况稍微复杂些:传统型NFA正则引擎由于遵循“最左先到先得原则”,一旦其中某个分支获得了匹配,将不会继续尝试匹配剩下的分支;而DFA和POSIX NFA正则引擎由于遵循“最左最长原则”,必须选择各个分支中所获得的最长匹配,因此会逐个分支尝试匹配)。

正则表达式中的某个语法元素一旦在字符串中获得了匹配(若该语法元素后面有量词限定的话,需满足其重复次数,且有可能存在回溯,详见后文解释),则表示该语法元素成功获得了匹配,于是匹配控制权转移到下一个语法元素,重复该过程。

原则上,匹配控制权一旦从某个语法元素转移出去,则该语法元素不能再次重新获得。不过,懒惰量词形成的回溯例外(懒惰量词所限定的语法元素一旦获得了该量词的下限次匹配之后,会先将匹配控制权转移给紧随其后的语法元素,若紧随其后的语法元素无法匹配,则会将匹配控制权返回给该语法元素)。(如果暂时看不明白没关系,后文都会有详细解释)。

若正则表达式中的某个必须匹配的语法元素(而由下限次数为0的量词所限定的语法元素则为可选匹配)一旦在字符串中无法获得匹配,则该正则表达式匹配失败。

 

四、占有字符(消费字符与消耗字符)匹配和不占有字符(零宽度)匹配

1.

正则表达式匹配过程中,若其中的某个语法元素匹配到的是字符,而非位置,并且在字符串中移动了匹配定位指针,此时可分为两种情况:

1)  所匹配的字符被保存到了最终的匹配结果中(即返回了所匹配到的字符),那么就认为该子表达式消费了这些字符;

2)  所匹配的字符未被保存到最终的匹配结果中(即没返回所匹配到的字符),那么就认为该子表达式消耗了这些字符(比如位于元转义序列\K之前的子表达式)。

无论是消费了字符,还是消耗了字符,均属于占有了字符。

如果该子表达式匹配的仅仅是位置,或者虽然匹配了字符,但最终并不实际移动字符串中的匹配定位指针(比如预查分组),那么就认为这个语法元素是不占有字符的,即属于零宽度的。

占有字符还是不占有字符,最终以是否实际移动了字符串中的匹配定位指针为准。

2.

占有字符是互斥的,不占有字符是非互斥的。

所谓互斥指的是一个字符,只能由一个语法元素匹配,一旦被某个语法元素匹配后占有了,则不能为其他语法元素所匹配占有;所谓非互斥指的是一个位置,可以同时由多个不占有字符(即零宽度)的语法元素匹配。

(笨笨阿林原创文章,转载请注明出处)

 

五、八大原则简介

1.

受《精通正则表达式》一书中“最左原则”、“最长原则”以及衍生的“最左最长原则”的启发,在此基础上我进一步推广扩展,总结为八大原则。其中包括六大基本原则与两大衍生原则,先简要介绍如下(后文结合语法元素会有详细解释):

六大基本原则:

1)  最左原则:在一个字符串中,若一个正则表达式可能有多个匹配结果时,其中最靠近字符串左边的起始位置的那个匹配结果总是会优先于其他的匹配结果被返回;

2)  最长原则(即长度优先原则)如果在字符串中的某个位置存在多个可能的匹配,将返回最长文本(即最多字符)的那个匹配;

3)  先到先得原则(即顺序优先原则)在同一个位置上,如果有多个长度不同的匹配结果,将返回最先获得匹配的结果,或前后两个由贪婪量词或懒惰量词所限定的子表达式发生匹配冲突时,后者仅获得其下限次数的匹配,而前者将获得超过其上限次数的尽可能多的匹配;

4)  逐位置依次尝试匹配原则:匹配总是从字符串的起始位置(即位置0)开始,从左到右地逐个位置尝试匹配整个正则表达式;

5)  整体匹配优先原则:整个正则表达式获得匹配的优先级要高于贪婪量词所限定的子表达式;

6)  占有匹配优先原则:整个正则表达式获得匹配的优先级要低于占有量词所限定的子表达式。

两大衍生原则:

1)  最左最长原则:非全局模式下,如果在字符串中的多个位置中的每个位置均有多个可能的匹配文本,DFA和POSIX NFA引擎会优先选择最靠左边位置的所有可能的匹配文本当中最长的文本;

2)  最左先到先得原则:非全局模式下,如果在字符串中的多个位置中的每个位置均有多个可能的匹配文本,传统型NFA引擎会优先选择最靠左边位置的所有可能的匹配文本当中最先获得匹配的文本。

2.

这些原则看似平淡无奇,但正如“两点间直线距离最短”这样显而易见的几何学公理,却是支撑起整个宏伟的欧几里得几何学的基石一样,这八大原则也是正则引擎匹配机制的基础,理解它们是理解正则引擎匹配行为的关键。

(笨笨阿林原创文章,转载请注明出处)

(未完待续)

 

预告:《刨根究底正则表达式》系列的下一篇将正式开始逐个介绍各正则表达式语法元素;而《刨根究底字符编码》系列的下一篇将重点介绍UTF-16编码,敬请关注!】

 

刨根究底正则表达式之二——正则表达式基础