我爱正则表达式

原文：How will my regular expression match?
作者：hv
译文：正则表达式的匹配过程
译者：rex

rex译注：在《Programming Perl》第三版第五章，讲了正则匹配的六条规则，深入，透彻，但是不易理解。可以将本文当作是该章的简化版。另外，一定的正则式调试经验也有助于理解正则式的匹配过程。可以参考《Programming Perl》第五章“正则表达式编译器”一节，或阅读这篇文章《Debugging Regular Expressions》。建议阅读例程序时，先默想输出结果，然后再上机测试，最后再看本文的答案。

经常见到关于正则表达式“偏好”的讨论，即，正则表达式引擎“喜欢”更长的、更短的，还是最左端的匹配。

事实非常简单：正则表达式引擎总是返回它所匹配到的第一个结果，如果你理解了正则表达式尝试匹配的顺序，你就再也不会对找到哪一个匹配而困惑了。

下面是一些简单规则（次序无关），阐释正则引擎尝试匹配的顺序。

1．从最左端的字符开始

引擎从目标字串的第一个字符开始，对正则模式进行匹配测试。只有当在第一个字符位置测试完整个正则模式且匹配失败时，引擎才会移动到目标字串的下一个字符，重新开始匹配测试。这样依次测试，直到字串的结束位置。

例子：

1
2

($match) = "The longest word" =~ /(\w+)/;
  print $match;

其输出结果是“The”（请先自行猜测，再使用鼠标选定，查看结果；下同。），原因是匹配是从字串的最左端开始的。这个单词之后，还有一个更长的单词可以匹配，但是正则引擎却对其视而不见：只要从字串开始处进行匹配且成功，它就返回这个结果，匹配过程就结束了。

Rex:如果正则式是以$结尾的，例如abc$，该正则在试图匹配字串“xyzabc”是否会首先跳到最后一个字符开始比较呢？我的理解是，就常规的正则引擎的正常的匹配过程而言，虽然有$符，但是该$符与普通字符一样，不会特殊处理，整条正则式会在x,y,z处失败3次，然后在a处再开始匹配测试并最终成功。$不会加速匹配过程，只是保证了最终匹配位置。但是不排除具体的正则引擎，会对定位锚点进行优化，从而实现early exit，即只要不符合某一条件，就提前退出，从而减少真正的比较次数，提升效率。看一下abc$ 的perl代码：

Perl引擎对该正则式的分析是：精确匹配普通文本abc；之后是行尾结束符；结束。在匹配时，它直接就“猜”到了匹配结果。

2. 最左边的备选项优先

如果正则模式中含备选项，那么首先测试左边的选项。如果最左侧的备选项成功匹配，那么就继续使用剩余的正则表达式剩余的字串进行匹配测试；只有在最左边的备选项不能匹配时才依次尝试下一个备选项。

例子：

1
2

($match) = "Mrs Smith" =~ /(Mr|Mrs)/;
 print $match;

其输出结果是“Mr”，因为最左端的正则备选项匹配成功，在本例中也就意味着整个正则表达式匹配成功。此时第二个备选项就被完全无视了。

3. 贪婪模式

对于任何常规的量词（即? * + {1,3}），引擎首先会尝试允许范围内最大数量的重复次数（如果实际文本不足，则尽可能多地重复），然后继续使用剩余的正则表达式剩余的字串进行匹配测试。只有当剩余的正则匹配失败时，引擎才不情愿地“吐出”一次重复的文本，尝试进行后续的匹配，直到匹配成功，或到达允许重复的最小次数。
例子：

1
2

($match) = "/foo/bar" =~ m[.*/(.*)];
print $match;

其输出结果是”bar“。匹配过程是：

.*先匹配完整个字串/foo/bar；此时发现.*之后还需要匹配一个/，此时只好回退字串，.*此时是/foo/ba，然后是/foo/b，/foo/，/foo。此时，后续的正则式得到了/，得以继续匹配并最终成功，返回它认为正确的结果。看图：

Rex: 如果我们想把下面的英文字串

At this point the remaining pattern matches, so this is the match returned

提取出最后一个单词和其它部分，应该怎样写正则呢？(.*)(\w+)$吗？这样的话，$2中只有d这个字母。正确的写法包括：

.*\b(\w+)$        # .*先用完整个字符，再一个字符一个字符地回退，直到遇到一个单词边界，然后开始找\w+。

4. 懒惰模式

在量词之后加上问号?（即?? *? +? {1,3}?），就由贪婪模式变为懒惰模式，匹配的过程也随之改变：引擎先尝试允许范围内最少次数的重复，随即使用后续的正则对后续的字串作匹配测试。只有当后续的正则匹配失败时，引擎才懒洋洋地再吃进一次重复，再进行后续匹配测试，直到匹配成功，或到达所允许的匹配次数上限。
例子：

1
2

($match) = "foo/bar/baz" =~ m[.*?/(.*)];
print $match;

显而易见，输出结果是bar/baz。匹配过程中，.*?先匹配空字串”"，然后是”f”，”fo”，”foo”，此时匹配成功，并返回相应结果。

Rex:继续思考上节的问题，另一种将At this point the remaining pattern matches, so this is the match returned中最后一个单词与其余部分分开的正则式还可以是：

.*?\w+$

5. 正则式各部分的匹配次序：从左到右

上面一些例子中的暗含前提是正则模式之间的匹配次序是从左到右。因此在“贪婪模式”例子中有两个.*，基于本条规则，只有当第一个.*的条件满足之后，它才会考虑后续的正则表达式该如何匹配。

6. 嵌套

其实这只是“从左到右”规则的引申。参见下面的例子：

($outer, $inner) = "/foo/bar" =~ m[(/(.+))*];
print $inner;

其输出结果是“foo/bar”。正则引擎先遇到外层的量词，意识到该部分正则要尽可能多地重复，然后开始尝试匹配内层的正则。嵌于内层的量词是贪婪的，因此也会尽可能多地重复，它抓到的字串是foo/bar这部分。此时，外层量词没有机会再重复一次匹配了，但是没有关系——整个正则表达式已经成功匹配，因此返回相应结果。

本文概括了绝大部分常规正则表达式的匹配规则。其余不常见的情况，仍需留心（例如锚点，pos()，以及各种各样的零宽断言）。同时，正则表达式优化器有时会让引擎略过某些步骤，但前提条件是目标匹配结果不变。

Rex注：将何伟平先生译的《Programming Perl》中的正则匹配规则也抄录在这里。只列提纲，需要详细内容的请自行翻书。

• 规则1：引擎试图尽可能地匹配字符串的左边，这样整个正则表达式按照规则2匹配。
  引擎从字符串的第一个字符开始，然后从那里开始尝试匹配整个模式。只有引擎在到达字符串的终点之前先到达模式的终点才是整个模式的匹配。如果匹配，引擎马上退出——它不会继续寻找“更好的”匹配，即便模式可能以几种不同的方式匹配也如此。
• 规则2：当引擎碰到一个候选集合时（用|符号分隔），不管是在顶层还是在当前“群集”层次中，它都从左向右尝试这些候选项，并且在第一个可以成功完成整个模式匹配的候选项处停止。
• 规则3：如果根据规则4和5（这样整个正则表达式就可以满足了），某个候选项里顺序列出的每个项都匹配，那么这个候选项就是匹配项。
  

  （rex注：列出的每个项，觉得这里说“子项”，层次更清晰。）

• 规则4：如果一个断言不出猎在当前位置匹配，引擎将回溯到规则3并重新以不同的选择试验高强弱顺序的项。
• 规则5：一个量化的原子只有在其本身匹配了其量词许可的次数才算匹配。（原子本身是按照规则6匹配的）。
• 规则6：每个原子都根据它的类型指定的语义来匹配。如果该原子 不匹配（或者它匹配而模式的其余部分不匹配），那么引擎将回溯到规则5,然后尝试该原子 的数量的下一选择。