佳音的博客

2007/08/14

正则表达式快速入门二【http://www.chinaz.com/Server/Linux/041M0442007.html】

Filed under: Uncategorized — 佳音 @ 10:56 上午

  在上篇文章里,我们介绍了正则表达式的模式修正符与元字符,细心的读者也许会发现,这部分介绍的非常简略,而且很少有实际的例子的讲解。这主要是因为网上现有的正则表达式资料都对这部分都有详细的介绍和众多的例子,如果觉得对前一部分缺乏了解可以参看这些资料。本文希望可以尽可能多涉及一些较高级的正则表达式特性。

  在本文里,我们主要介绍子模式(subpatterns),逆向引用(Back references)和量词(quantifiers),其中重点介绍对这些概念的一些扩展应用,例如子模式中的非捕获子模式,量词匹配时的greedy与ungreedy。

  子模式(subpatterns)与逆向引用(Back references)

  正则表达式可以包含多个字模式,子模式由圆括号定界,可以嵌套。这也是两个元字符“(”和“)”的作用。子模式可以有以下作用:

  1. 将多选一的分支局部化。

  例如,模式: cat(aract|erpillar|)匹配了 “cat”,”cataract” 或 “caterpillar” 之一,没有圆括号的话将匹配 “cataract”,”erpillar” 或空字符串。

  2. 将子模式设定为捕获子模式(例如上面这个例子)。当整个模式匹配时,目标字符串中匹配了子模式的部分可以通过逆向引用进行调用。左圆括号从左到右计数(从 1 开始)以取得捕获子模式的数。

  注意,子模式是可以嵌套的,例如,如果将字符串 “the red king” 来和模式 /the ((red|white) (king|queen))/进行匹配,捕获的子串为 “red king”,”red” 以及 “king”,并被计为 1,2 和 3 ,可以通过“\1”,“\2”,“\3”来分别引用它们,“\1”包含了“\2”和“\3”,它们的序号是由左括号的顺序决定的。

  在一些老的linux/unux工具里,子模式使用的圆括号需要用反斜线转义,向这种\(subpattern\),但现代的工具已经不需要了,本文中使用的例子都不进行转义

非捕获子模式(non-capturing subpatterns)

  用一对括号同时完成上面提到的子模式的两个功能有时会出现一些问题,例如,由于逆向引用的数目是有限的(通常最大不超过9),而且经常会遇到无需捕获的子模式定义。这时,可以在开始的括号后加上问号和冒号来表示这个子模式无需捕获,就向下面这样:((?:red|white) (king|queen))。

  如果将“the white queen”作为模式匹配的目标字符串,则捕获的字串有“white queen”和“queen”,分别作为“\1”和“\2”,white虽然符合子模式“(?:red|white)”,但并不被捕获。

  我们前面已经介绍过用括号与问号表示模式修正符的方法,为方便起见,如果需要在非捕获子模式中插入模式修正符,可以把它直接放在问号和冒号之间,例如,下面两个模式是等效的。

  /(?i:saturday|sunday)/和/(?:(?i)saturday|sunday)/。

  逆向引用(Back references)

  前面介绍反斜线作用时,已经提到它的一个作用就是表示逆向引用,当字符类之外的反斜线后跟一个大于0的十进制数时,它很有可能是一个逆向引用。它的含义正如它的名称如言,它表示对它出现之前已经捕获的子模式的引用。这个数字代表了它引用的左括号在模式中出现的次序,我们在介绍子模式时已经看到过逆向引用的一个例子,那里的过“\1”,“\2”,“\3”分别表示所捕获的第一,第二,和第三个小括号定义的子模式的内容。

  值得注意的是,当反斜线后的数字小于10时,可以确定此为一个逆向引用,这样,这个逆向引用就可以出现在之前有相应数目的左圆括号被捕获前而不会出现混淆,只有整个模式能提供那么多的捕获子模式,就不会报错。说起来似乎很混乱,还是让我们来看下面这个例子。把介绍子模子时举的例子拿来修改一下,前面讲过字符串 “the red king” 来和模式 /the ((red|white) (king|queen))/匹配,捕获的子串为 “red king”,”red” 以及 “king”,并被计为 1,2 和 3 ,现在把字符串,修改为” king,the red king”,模式改为/\3,the ((red|white) (king|queen))/,这个模式应该也是可以匹配的。不过,并非所有的正则表达式工具都支持这种用法,安全的做法是在相应序号的左括号之后使用与之相关的逆向引用。

  需要注意的另一点是逆向引用的值是在目标字符串中实际捕获的符合子模式的字符串片段而非该子模式本本身。例如/ (sens|respons)e and \1ibility/会匹配“sense and sensibility” 和 “response and responsibility”,但不会是 “sense and responsibility”。当被逆向引用的子模式后面有量词从而被重复匹配了多次,逆向引用的值会以最后一次匹配的值为准。例如/([abc]){3}/匹配字符串“abc”时,逆向引用“\1”的值将是最后一次匹配的结果“c”。

  命名子模式(named subpattern)

  一些工具(例如Python)可以为逆向引用命名,从而定义出命名子模式。在Python中对正则表达式的使用是以函数或方法调用的格式,语法与这里举的例子有较大差别。有兴趣的朋友可以参看一下自己使用的工具来看看是否支持命名子模式。

  

重复(Repetition)和量词(quantifiers)

  在前面介绍逆向引用的部分里我们已经接触到了量词(quantifiers)的概念,例如前面的例子/([abc]){3}/表示三个连续的字符,每个字符都必然是 “abc”这三个字符中的一个。在这个模式里,{3}就属于量词。它表示一个模式需要重复匹配(repetition)的数目。

  量词可以放在下面这些项目之后:

  ●单个字符(有可能是被转义的单个字符,如\xhh)

  ●“.”元字符

  ● 由方括号表示的字符类

  ● 逆向引用

  ●由小括号定义的子模式(除非它是个断言,我们会在以后介绍)

  最通用的量词使用形式是用花括号括起的两个由逗号分隔的数字,如这样的格式{min,max},例如,/z{2,4}/ 可以匹配 “zz”, “zzz”, 或者 “zzzz”,花括号中的最大值以及前面的逗号可以省略,例如/\d{3,}/可以匹配三个以上的数字,数字的数目没有上限,而/\d{3}/(注意,没有逗号)则精确的匹配3个数字。当花括号出现在不允许量词的位置或者语法与前面提到的不符时,这里它仅仅代表花括号字符本身而不再具有特殊的含义。例如{,6}不是量词,它仅仅代表这四个字符本身的含义。

  为了方便,三个最常用的量词有它们的单字符缩写形式,它们的的含义如下表:

*
相当于 {0,}
+
相当于 {1,}
?
相当于 {0,1}

  这也是以上三个元字符做为量词使用含义。

  在使用量词特别是没有上限限制的量词时,应该特别注意不要构成无限循环,例如/(a?)*/,在有的正则表达式工具里。这会形成一个编译错,不过有的工具却允许这种结构,但不能保证各种工具都可以很好的处理这种结构量词匹配的“greedy”与“ungreedy”

  在使用带量词的模式时,我们常会发现对同一模式而言,同一个目标字符串可以有多种匹配方式。例如/\d{0,1}\d/,可以匹配两个或三个十进制数字,如果目标字符串是123,当量词取下限0里,它匹配“12”,当量词取上限1里,它匹配“123”整个字符。这两种匹配结果都是正确的,如果我们取它的子模式/(\d{0,1}\d)/,则匹配的结果\1到底是“12”还是“123”?

  实际的运行结果一般会是后者,因为默认情况下,大多数正则表达式工具的匹配是按“greedy”原则匹配的。“greedy”单词的中的含义是“贪吃的, 贪婪的”的意思,它的行为也如此单词的含义,所谓greedy匹配意指在量词限制范围内,只要能保持后续模式的匹配,匹配总是尽可能的重复下去,直到不匹配的情况发生为止。为便于理解,我们看下面这个简单的例子。

  /(\d{1,5})\d/匹配“12345”这个字符串,这个模式表示在1到5个数字后面跟上一个数字,量词范围从1到5,当它的值在1-4时,整个模式都是匹配的,\1的值可以是“1”,“12”,“123”,“1234”,而在greedy匹配的情况下,它取匹配时的量词最大值,因此最终匹配的结果是”1234”。

  在大多数情况下,这就是我们想要的结果,但情况并不总这样。例如,我们希望用下面这个模式提取出c语言的注释部分(在c语言中,注释语句放在字符串/*和*/之间)。我们使用的正则表达式是/\*.*\*/,但匹配的结果却完全和需要的不同。当正则表达式解析到“/\*”这后的“.*”时,因为“.”可以代表任意字符,这也包含了其后需要匹配的“*/”,在量词的作用下,这个匹配将一直进行下去,超过下一个“*”/直到文本的结束,这显然不是我们需要的结果。

  为了完成如上例我们想要的那种匹配,正则表达式引入了ungreedy匹配方法,与greedy匹配相反,在满足整个模式匹配的前提下,它总是取最小的量词数目结果。Ungreedy匹配用在量词后面加上问号“?”来表示。例如在匹配C语言的注释时,我们把正则表达式写成如下形式:/\*.*?\*/,在量词“*”后加上问号就可以达成想要的结果。还有前面那个例子用/(\d{1,5})\d/匹配“12345”这个字符串,如果改写为ungreedy模式向这样/(\d{1,5}?)\d/,、\1的值将为1。

  上面的解释也许有些不准确,量词后的问号的作用实际上是反转当前的正则表达式的greedy与ungreedy行为。你可以通过模式修正符“U”将正则表达式设成ungreedy模式然后在模式中通过量词后的问号将之反转为greedy。

  一次性子模式(Once-only subpatterns)

  关于量词的另一个有趣的话题是一次性子模式(Once-only subpatterns)。要理解它的概念需要先了解一下含有量词的正则表达式的匹配过程。我们这里举个例子。

  现在,让我们用模式/\d+foo/来匹配字符串“123456bar”,当然,它的结果是没有匹配。但正则表达式引擎是如何工作的呢?它先分析前面的\d+,这代表一个以上的数字,然后检查目标字符串的对应位置的第一个字符“1”,符合模式,然后根据量词重复这个模式对字符串进行匹配直到“123456”始终符合“\d+”模式,接着它在目标字符串中遇到字符“b”无法与“\d+”匹配,于是查看“\d+”的后续模式“foo”,与目标字符串的后续部分“bar”无法匹配,这时,有趣的事情出现了,解释引擎会对前面已经解析过的“\d+”模式进行回溯,将量词数目减少一,看剩余部分能否匹配,此时“\d+”的值改为“12345”,然后解释引擎看目标字符串剩余的部分“6bar”能否与剩余的模式“foo”相匹配,如果不行,就把量词数再减一,直到达到最小的量词限制,如果仍无法匹配,则表明目标字符串无法匹配,返回无法匹配的结果。

  现在,我们就可以来接触一次性子模式了。所谓一次性子模式就是定义在正则表达式解析时不需要上述回溯过程的子模式。它用左圆括号后面的问号和小于号来表示,向这样(?>)。如果将上面提到的例子改为一次性子模式,可以这样书写:

  /(?>\d)+foo/,这时,当解析器遇到后面不匹配的bar时,会立即返回不匹配的结果,而不会进行前面提到的回溯过程。

  需要了解的是,一次性子模式属于非捕获子模式,它的匹配结果不能被逆向引用。

  当一个没有设定重复上限的子模式中包含了同样没有设定重复上限的模式时,使用一次性子模式是唯一可以避免让你的程序陷入长时间等待的方法。例如你用“/(\D+|<\d+>)*[!?]/”这个模式去匹配一长串的a字符,向这样“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa”,在返回最终无匹配的结果前,你会等待很长的一段时间。这个模式表示一串非数字字符或者用尖括号括着的一串数字后跟随着叹号或者问号,把这段字符串分成两个重复的部分会有很多种分法,而无论是子模式本身还是子模式之内的量词的各可能值都要经过逐一测试,这将使最终的运算量达到一个很大的程度。这样,你将在电脑前等待相当长的时间才会看到结果。而如果用一次性子模式来改写刚才的模式,改成这样/ ((?>\D+)|<\d+>)*[!?]/,你就可以很快得到运算的结果。

]]>

Powered by 00RZ