正则表达式(四):正则表达式的与或非

  • 余晟

2011 年 4 月 4 日

话题:Java.NETRuby语言 & 开发架构

我们使用正则表达式,熟练掌握各种功能和结构只是手段,解决实际的问题才是真正的目的。要解决真正的问题,就必须有解决问题的思路,正则表达式的功能,说到底,可以归纳为三种逻辑,为了表述方便,我们分别称为与、或、非。

逻辑关系

说明

在某个位置,某些元素(字符、字符组或者子表达式)必须出现

在某个位置,某个元素或许不出现,或许不出现,或许长度不固定;要出现的,是某几个元素中的一个

在某个位置,某些元素不能出现

一般来说,正则表达式千变万化,总是这三种逻辑的组合。比如匹配双引号字符串

"quoted string"

逻辑关系

分析

首尾的双引号字符必须出现

两个双引号之间的字符个数是不确定的(如果是空字符串””,则两个双引号之间没有字符)

两个双引号之间不能出现双引号字符

再比如匹配 html 中的 open-tag(比如 <h1>)和 close-tag(比如 </h1>):

逻辑关系

分析

首尾必须分别是 < 和 >,如果是 close-tag,则 < 之后必须出现 /

< 和 > 之间必须出现至少一个字符(<> 不是一个合法的 tag)

< 之后不能是 / 字符,如果是 open-tag,< 之后不能出现 /

下面我们来讲解三种逻辑的对策。

“与”是正则表达式中最普通的逻辑关系。一般来说,如果正则表达式中的元素没有任何量词(quantifier,比如 *、?、+)修饰,就是“与”关系。比如『<』,就表示“这里必须出现 < 字符”;『cat』,就表示“这里必须依次出现 c、a、t,3 个字符”。

不过“与”的情况并没有这么简单,有时候,“必须出现”的是若干个元素,或者说,几个元素必须同时出现,但它们之间并不相连,这是非常容易犯错的时候,不过现在我们不举具体的例子,稍晚一点再说。

“或”是正则表达式中最灵活的逻辑关系。正则表达式能应对各种不同的文本,“或”功能不可或缺。

如果“或”的意思是,元素可以出现,也可以不出现,或者出现的次数不确定,可以用量词来表示“或”关系。比如表达式『a?』,表示在此处,字符 a 可以出现,也可以不出现;表达式『(ab)+』,表示在此处,字符串 ab 必然要出现 1 次,也可以出现无限多次。

如果“或”的意思是,可以出现的是某几个元素中的一个,则应该使用字符组或者多选结构。当元素都是单个字符时,就应该使用字符组『[…]』:比如匹配单词 cat 或者 cut,除去开头的 a、结尾的 t 是固定的,之中“或许出现 a,或许出现 u”,所以应当使用字符组『[au]』,整个正则表达式就是『c[au]t』。当元素不只单个字符(只要有一个元素不只单个字符)时,就应该使用多选结构『(…|…)』:比如不但要匹配单词 cat 或者 cut,还要匹配单词 chart、conduct 和 court,出去开头的 a、结尾的 t 是固定的,之中“或许出现 a,或许出现 u,或许出现 har,或许出现 onduc,或许出现 our”,这时候就应该使用多选结构『(a|u|har|onduc|our)』,整个正则表达式就是『c(a|u|har|onduc|our)t』。

当然,多选分支也可以表示字符组,比如『[au]』就可以表示为『(a|u)』,两者的功能是完全等价的,但是字符组的效率更高,也更直观(毕竟,大家都习惯了简单的『[au]』,而看到『(a|u)』则多半要想一想。

在实践中,“与”和“或”经常同时出现,而且关系不那么简单,下面举一个例子说明:为了隐藏真实的结构,我们需要用 URL 进行伪装,比如这个 URL pattern:/foo/bar_tmp.php。

在真正的系统里,foo 是模块名,bar 是控制器名,tmp 是方法名。合法的 URL 并不要求 3 个名字每次都出现,可以只出现控制器名(/foo),也可以只出现控制器名和模块名(/foo/bar.php),也可以 3 者都出现(/foo/bar_tmp.php)。

这里的模块名、控制器名、方法名,都可以用『[a-z]+』匹配,这里为说明方便,我们暂且用 foo、bar、tmp 代替对应的表达式。初看起来,这个表达式只包含“与”和“或”两种关系:

逻辑关系

分析

/foo 必须出现

/bar、_tmp、.php 都是可选出现的

所以,正则表达式是『/foo(/bar)?(_tmp)?(\.php)?』。

这个表达式确实可以匹配 /foo、/foo/bar.php 和 /foo/bar_tmp.php,但是,它也可以匹配 /foo_tmp、/foo/bar_tmp 等形式,虽然这些形式并不是合法的。

仔细研究之后,我们发现,“与”和“或”的关系并没有那么简单,而应该是这样的:

逻辑关系

分析

/foo 必须出现

/bar 和.php 是可选出现的,但必须同时出现,或同时不出现(与)

在 /bar 和.php 都出现的前提下,_tmp 才可以出现(或)

/foo 必须出现,这很好表示,暂且不去管它;/bar 和.php 如果出现,必须同时出现,所以它们应该作为一个元素,写作『(/bar.php)』;整个元素可选出现,所以给它添加量词,得到『(/bar.php)?』;最后,在 /bar 和.php 都出现的前提下,_tmp 才可以出现,所以将『(_tmp)?』填充到『(/bar.php)?』,得到『(/bar(_tmp)?.php)?』,最后加上开头的 /foo,整个表达式就是『(/bar(_tmp)?.php)?』。到此,整个关系终于完整表达出来,表达式也不会发生错误匹配。

“非”是正则表达式中最难处理的逻辑关系。因为没有直接对应的结构,“非”的处理比较吃力。

最简单的“非”,意思是此处不能出现某个字符,这一点通常很直观,似乎用排除型字符组『[^…]』就可以解决。比如双引号字符串的匹配,首尾两个双引号很容易匹配,其中的内容肯定不是双引号(暂时不考虑转义的情况),所以可以用『[^"]』表示即可,其长度不确定,所以用 * 来限定,所以整个表达式就是『"[^"]*"』,非常简单。

但是,事情果真都如此简单吗?我们仍然举 cat 和 cut 的例子,如果仍然希望匹配 c 开头、t 结尾的单词,但不希望匹配 cut,可以写成『c[^u]t』,是否就可以了?

这个表达式的意思是:最开头的字母是 c,之后是一个不为 u 的字符,之后是 t。没错,它确实不会匹配 cut,也可以匹配 cat。但是,chart、conduct、court 等等,它也没法匹配,因为 [^u] 的意思是:匹配一个不是 u 的字符。

那么,把『[^u]』改成『[^u]+』好了,这样应该就可以解决问题了。但是真的如此吗?『[^u]+』的意思是,一个或若干(最多到无穷)个字符,但每一个字符都不能是 u。所以,尽管『c[^u]+t』能匹配 cat 和 chart,却不能匹配 conduct 和 court。

看来,“非”真是比较难对付,让人非常纠结。好在,也不是没有办法解决它。回复到与 - 或 - 非的观点,分析要实现的功能:

逻辑关系

分析

以 c 开头,以 t 结尾

c 和 t 之间可以出现的字母必须多于一个,没有上限

c 和 t 之间不能只有一个字符 u

如果只考虑“与”和“或”两个逻辑,表达式很好写,是『c[a-z]+t』,再把剩下的条件附加上去,就可以解决问题了。我们仔细看“非”的条件:c 和 t 之间不能只有一个字符 u。既然『[^u]+』表达的并不是这个意思,我们不妨换一种表述法:在 c 之间的位置向后看,不能出现 cut。这一点,正好对应否定顺序环视(positive look-ahead)功能,『(?!cut)』就是用来进行这种判断的,它判断之后的字符串能不能由 cut 匹配,但并不真正真正进行匹配,也不会移动“当前位置”。所以我们将它放在表达式的最开头,得到『(?!cut)c[a-z]+t』。这个表达式的逻辑是:只有在当前位置右侧字符串不能由 cut 匹配的情况下,才从这里开始,向右尝试用 c[a-z]+t。

如果我们更进一步,需要排除掉 cat 和 cut,可以把否定顺序环视改为『(?!c[au]t)』。这样就能保证,匹配到的肯定不是 cat 或者 cut。

更复杂一点,如果我们要验证这样一个字符串:它全部由小写字母构成,长度不超过 12 位,其中不能包含 unfavored 或者 unwanted。也可以照章处理,先匹配“长度不超过 12 位”的小写字母『[a-z]{,12}』,然后写出匹配“不需要匹配内容”的正则表达式,『(unfavored|unwanted)』,再用否定顺序环视将它“排除”即可,只是这次要注意,不能直接写『(?!(unfavored|unwanted))』,因为它只能排除『(unfavored|unwanted)』出现在字符串开头的情况,为了排除它出现在字符串中的情况,我们要把否定顺序环视改为『(?![a-z]*(unfavored|unwanted))』,这样就确保完整的“排除”,整个表达式就是『(?![a-z]*(unfavored|unwanted))[a-z]{,12}』。

总结一下,正则表达式中的“非”,除去能用排除型字符组直接表示的,复杂一点的“非”逻辑都是按照这样的思路进行的:先用一个正则表达式准确匹配需要“排除”的字符串,再用环视功能排除掉它——“非”确实是正则表达式中,最难处理的逻辑关系,好在它并不复杂,而且,除去一些比较古老的工具(比如 Apache 1.3),现在各种工具和语言,基本都支持这种功能。

Java.NETRuby语言 & 开发架构