浅谈正则表达式工作原理（一）

1.1 介绍

这个系列的文章是为了向你介绍正则表达式引擎的工作原理，懂得这些原理是写出高效的正则表达式的关键。不仅如此这还将帮助你避免很多常见的错误，减少你花在猜测正则表达式的行为的时间。

2.1. 字面量字符(Literal Characters)

最基础的正则表达式由一个字面量字符组成，例如a。它将匹配一个字符串中第一个a出现的位置。如果它匹配的是 Jack is a boy，那么它将匹配到J后面的a。事实上即使a出现在字符串的中间也不影响这个正则，如果你想控制a是否出现在字符串的开头或者结尾，那么你需要使用文字边界。我们会在后面的章节展开讨论。

事实上这个正则同样可以匹配字符串中的第二个a，但是你必须通过函数调用通知正则引擎开始第二次匹配。

相类似的，表达式cat可以匹配About cats and dogs中的cat。这个表达式由三个字面量字符组成，对于正则引擎而言，它的意义是：查找一个c它的后面紧接着一个a，a的后面紧接着一个t。

2.2 元字符

为了处理更复杂的正则匹配，我们需要把一些字符作为特殊字符使用。以下列出正则表达式中的12个元字符：

• \
• ^
• &
• .
• |
• ?
• *
• +
• (
• )
• [
• {

通常来说，这些特殊字符在单独使用时会引发错误。

如果你想把以上的字符作为字面量字符来使用，你必须使用\进行转义。例如，如果你想匹配1+1=2，那么正确的表达式为/1\+1=2/，因为加号有特殊的含义。

如果你忘记对元字符进行转义，那么在有些情况下会导致正则表达式非法，例如/+1/。这时程序会抛出异常。

2.2.1 {的转义

在大多数正则引擎中，我们可以直接把{作为字面量字符使用，除了作为重复操作使用例如a{1,3}。所以在一般情况下我们不需要对{进行转义，当然转义也不会报错。在一些特殊的正则引擎中，我们可能需要对它进行转义，例如在java中，}需要转义，在Boost和std::regex中{、}都需要转义。

2.2.2 ]的转义

]在字符类以外的情况下使用时，它是一个字面量字符。在字符类中使用的时候，则有不同的规则。具体的规则我们会在字符类专题的展开讨论。

2.2.3 其它字符

除了以上这些元字符以外，其它的字符都不需要使用反斜杠转义。这是因为转移符和字面量字符的组合将成为一个正则指令（regex token），它具有特殊的含义。例如\d可以匹配0~9中任意一个字符。

2.3. 特殊字符与编程语言

在正则表达式中'和"并不是特殊字符，如何你是一个程序员的话你一定对此十分意外。在你编程或是使用文本编辑器的高级搜索功能时，你不需要对单引号和双引号进行转义。

当你在代码中使用正则表达式的时候，你应当注意有些字符在你所使用的编程语言中有特殊的含义。这是因为这些字符在进入正则引擎之前，先要经过编译器的处理。在c++代码中，表达式1\+1=2 需要写成1\\+1=2，c++编译器会在编译过程中去掉一个反斜杠，并把编译后的结果传递给正则引擎。再举一个例子，正则表达式c:\\temp可以匹配字符串c:\temp，但是在c++中你需要这么写c:\\\\temp。简单来说就是用四个反斜杠代替一个正则中的斜杠。

有关正则在编程语言中的使用，我们对在后面的章节中展开讨论。

3.1 行终结符（Line Breaks）

你可以在正则表达式的特殊字符匹配非打印字符。

• \t：匹配制表符
• \r：匹配回车
• \n：匹配换行
• \a：匹配响铃
• \e：匹配esc键
• \f：匹配分页符

\R是一个特殊的转义符，它将匹配所有的行终结符，也包括Unicode行终结符。相对于\r或者\n，\R比较特殊的一点是它会把[CRLF对]作为一个整体去匹配，而不会匹配把CR和LF分开匹配（作者译：如果他们同时出现的话）。当\R在一个CRLF对之前出现的话，单个\R将匹配整个CRLF对。在对一个CRLF进行匹配的时候，\R不会向前回溯从而匹配到CR。\R可以匹配到单独的CR或是单独的LF，但是\R{2}或者\R\R不会匹配到一个CRLF对，因为第一\R已经匹配到了整个CRLF对，另一个\R就不能和任何字符匹配。

但是在一些语言中，\R的行为并不遵循这个规范。例如在java9中\R\R可以匹配一个CRLF对，在Perl中\R{2}可以匹配一个CRLF对。

\R只能向前搜索，并且匹配一个完整的CRLF对。\r\R也可以匹配到一个CRLF对，这是因为\r匹配到了CR，而\R匹配了LF，这一规则在所有的引擎中都是一致的。

4.1 引擎的分类

理解正则引擎的内部原理将帮助你写出更高效的表达式，并且帮助你快速调试正则表达式中的异常。

在接下去的每一个章节中我们介绍一个新的正则特性，之后我们会解释引擎处理这个特性的详细过程。理解这些原理之后，我们便可以脱离正则可视化工具快速编写正则表达式。虽然理解引擎的原理有些难度，但是它可以帮助我们避免一些常见的错误。

在了解了这些基础知识之后，我们会介绍许多有意思的应用实例，你可以快速的把这些例子应用到你的项目中去。

虽然正则引擎有很多种不同的实现，但是大体可以分为两类：文本驱动的引擎（text-directed）和正则驱动的引擎（regex-directed）。几乎所有的现代正则引擎都采用正则驱动引擎，这是因为一些非常有用的特性只能在这种引擎上实现，例如lazy quantifiers和backreferences

4.1.1 正则驱动的引擎（regex-directed engine）

一个正则表达式引擎通过遍历正则表达式完成匹配，它尝试将表达式中的下一个token和字符串中的下一个字符进行匹配。如果当前token可以匹配成功，那么引擎将移动至下一个token，并且把这个token和字符串中的下一个字符进行匹配。如果匹配失败，那么正则引擎会在正则和字符串中进行回溯，并且重新进行路径搜索。关于正则的回溯之后的章节会详细展开。

4.1.2 文本驱动的引擎（text-directed engine）

一个文本驱动的引擎通过遍历文本完成匹配。在匹配下一个字符之前，他会尝试表达式中的所有排列。一个文本驱动的引擎没有回溯过程，所以他的匹配过程相对简单。在大多数情况下两种引擎的匹配结果是相同的。

本教程主要讨论正则驱动的引擎，所以默认情况下我们提到的引擎都是正则驱动引擎，除非两种引擎的匹配结果不一致。只有当我们使用选择符，并且两个选项匹配到同一个位置时才会发生这种情况。

4.2 正则表达式总是匹配最左端的匹配结果

正则表达式总是匹配最左端的匹配结果，无论后面是否有更好的匹配结果，这是一个非常重要的特性。当正则引擎匹配一个字符串的时候，它将从字符串的最左边开始搜索。引擎将正则中所有的排列与字符串的第一个字符相匹配。如果有一种排列匹配成功，引擎将继续匹配字符串中的下一个字符。下一步引擎将字符串中的下一个字符与正则中的所有排列进行匹配。最终引擎将返回最靠左的匹配结果。

现在我们来举一个例子。我们使用表达式 cat 去匹配字符串 He captured a catfish for his cat 。首先引擎使用 c 去匹配字符串中第一个字符 H ，此时匹配不成功而且没有其他的排列（因为c只包含一个字面量字符）。之后引擎匹配token c 和字符 e ，同样也失败了，后面的空格也是如此。当引擎尝试匹配第四个字符的时候token c 匹配 c 成功了，所以引擎继续把第二个token a 与字符串中第5个字符 a 匹配，匹配也成功了。但是第三个token t 不能和第六个字符 p 匹配。此时引擎已经知道表达式无法和字符串中的前四个字符匹配，因此引擎将重新把第一个token c 和第5个字符 p 进行匹配，直到第15个字符时 c 才匹配成功，接下来 a 和 t 也匹配成功。

此时这个正则可以从字符串的第15个字符开始匹配成功，于是引擎非常“急切”的报告匹配成功。引擎不会继续向后搜索（即使后面会出现更好的匹配结果），因为它认为这个结果已经足够好了。

在这个例子当中两种正则引擎的搜索结果是相同的。正则的这种工作模式很大程度上决定了它的匹配结果，在之后例子中有一些匹配结果可能使你感到意外，但是只要你牢记这个搜索规则，你就可以用逻辑推导引擎的匹配结果。

5.1 字符类（字符集）

字符类（也叫字符集），它的作用是匹配一组字符中的一个字符。字符集的语法很简单，只要把字符写到方括号中间就可以了。例如[ae]可以匹配a或者e。你可以用gr[ae]y匹配gray或者grey。gray是美式英语，grey是英式英语。

一个字符集只能匹配一个字符。例如gr[ae]y不能匹配graay或者graey。字符集中的字符排序是不分先后的，不同的顺序匹配结果是一样的。

你可以使用-来表示一个范围。例如[0-9]可以匹配数字字符。你可以同时使用多个范围，例如[0-9a-fA-F]可以匹配一个十六进制字符。你也可以把单个字符和范围组合起来，例如[0-9a-fxA-FX]可以匹配一个十六进制字符或者一个x。和之前一样组合的顺序对最终的结果没有影响。

字符集是正则表达式中最常用的特性之一。你可以用它来匹配一个存在拼写错误的单词，例如sep[ae]r[ae]te和li[cs]en[cs]e。你可以用他来查找一个变量名，例如[A-Za-z_][A-Za-z_0-9]*。或者是一个C语言风格的十六进制数0[xX][A-Fa-f0-9]+

5.2 字符集取反操作（Negated Character Classes）

在[后面加上一个脱字符^可以把字符集反向使用。它的作用是匹配任何一个不属于字符集的字符。和.符号不同，反向字符集可以匹配到不可见的行终结符，如果你不想匹配行终结符可以在字符集中加上行终结符，例如[^0-9\r\n]它可以匹配除了换行和数字以外的任何字符。

反向字符集任然需要匹配一个字符。q[^u]的含义并不是匹配一个后面不是u的q，它的含义是q的后面紧接着一个字符但是这个字符不是u。q[^u]并不能匹配Iraq中的q，它可以匹配Iraq is a country中的q空格，因为空格正好能和[^u]匹配。如果你只想匹配到q而不想匹配到后面的空格，你可是使用negative lookahead：q(?!u)。之后我们再讨论这个特性。

5.3 字符集中的元字符

在大多数正则引擎中，如果你在字符集中使用]、\、^、-这四个元字符，那么你需要对这些元字符进行转义。其它的元字符则不需要转义。例如你可以使用[+*]匹配加号和星号，当然你也可以对所有的元字符进行转义，这并不会导致错误，只是这么做的话会降低正则表达式的可读性。

5.3.1 反斜杠转义

如果你要在字符集中匹配一个\，那么你需要对\进行转义。例如[\\x]可以匹配一个\或者一个x。对于]、^、-来说只要他们使用的位置不会造成歧义就不需要转义。

5.3.2 脱字符转义

对于脱字符^来说，只要他不是直接跟在[的后面就不需要转义。例如[x^]可以匹配一个x或者一个^。

5.3.3 右侧方括号转义

对于]来说，只要他是紧跟着[或者^它就不需要转义。例如[]x]可以匹配]或者x，[^]x]可以匹配除了]和x以外的任何字符。

5.3.4 -的转义

在以下情况下-不需要转义：

• 紧接着[的-，例如[-x]
• ]前面的-，例如[x-]
• 紧接着^的-，例如[^-x]、[^x-]

在其他的地方使用-，如果不能形成一个范围的话，有可能导致一个错误，也有可能把-作为字面量字符处理。这这一点上，各种引擎的处理方式并不统一。

如果你使用的引擎支持Unicode，你也可以在字符集中使用Unicode，例如[\u20AC]。

待翻译：

5.4 字符集的量词匹配

如果你在字符集的后面使用量词（例如?、*、+），那么你会对整个字符集进行重复，而不是仅仅重复字符集匹配到的字符。例如[0-9]+可以同时匹配837和222。

如果你想对字符集的匹配结果使用量词，那么你可以使用backreferences。例如([0-9])\1+可以匹配222但是不能匹配837。如果用它匹配833337，它会匹配到3333，如果这不是你要的结果，可以使用lookaround

5.5 字符集的原理

在这一节中我们通过一个例子来解释字符集的解说过程。我们使用gr[ae]y去匹配Is his hair grey or gray?，结果将匹配到grey。之前我们学习过字面量字符的匹配过程，现在我们来看一下具有多种排列方式的字符集是如何匹配的。

在匹配的过程中，前12个字符都没有匹配成功，因为它们都不能和g匹配。直到第13个字符字符g终于和正则表达式的第一tokeng匹配成功。下一步引擎将表达式的剩余部分和字符串匹配，这时r也匹配成功了。接下来引擎将[ae]和字符e匹配，因为这个token是字符集，所以引擎会把字符集中的所有组合与字符串中的下一个字符e匹配。首先是用a和字符e匹配，这一次没有匹配成功，但是此时还不能确定这个字符串的第13个字符作为起始是否能和表达式匹配，因为还有另一个排列需要尝试。接下来引擎使用字符集中的第二个tokene，这一次匹配成功了。接下来正则引擎进行下一个tokeny的匹配，同样也匹配成功了。

到这一步位置整个正则表达式已经匹配完成了。你可能已经注意到字符串中的gray也可以匹配成功，但是根据正则引擎的最左原则，引擎不会继续匹配下一个可能的结果。除非你通过函数调用告诉引擎进行第二次匹配。