A Casual Stroll Across the Regex Landscape

我喜欢在故事的开头讲讲某些正则表达式的流派以及相应程序的演变过程。所以，请准备一杯你最喜欢的热（或凉的）饮料，放轻松，我们一起来看看今天的正则表达式背后古怪的发展史。这样做是为了让你全面了解正则表达式，培养追问“为什么会如此”的习惯。我们为有兴趣的读者准备了一些脚注，不过大部分脚注只能算是博得读者一笑的花絮。

正则表达式的起源

The Origins of Regular Expressions

关于正则表达式，最初的想法来自20世纪40年代的两位神经学家，Warren McCulloch和Walter Pitts，他们研究出一种模型，认为神经系统在神经元层面上就是这样工作的（注1）。若干年后，数学家Stephen Kleene在代数学中正式描述了这种被他称为“正则集合”（regular sets）的模型，正则表达式才成为现实。Stephen 发明了一套简洁的表示正则集合的方法，他称之为“正则表达式”（regular expressions）。

20世纪50年代和60年代，理论数学界对正则表达式进行了充分的研究。Robert Constable的文章为那些对数学感兴趣的读者提供了很不错的简介（注2）。

尽管存在更古老的应用正则表达式的证据，但我能找到的是，关于在计算方面使用正则表达式的资料，最早发表的是 1968 年 Ken Thompson 的文章 Regular Expression Search Algorithm（注 3），在文中，他描述了一种正则表达式编译器，该编译器生成了 IBM 7094的object代码。由此也诞生了他的qed，这种编辑器后来成了Unix中ed编辑器的基础。

ed的正则表达式并不如qed的先进，但是这是正则表达式第一次在非技术领域大规模使用。ed 有条命令，显示正在编辑的文件中能够匹配特定正则表达式的行。该命令“g/Regular Expression/p”，读作（应用正则表达式的全局输出）。这个功能非常实用，最终成为独立的工具grep（之后又产生了egrep——扩展的grep）。

Grep中的元字符

相比egrep，grep和其他早期工具所支持的元字符相当有限。元字符＊是受支持的，但是+和？则不受支持（不支持问号是很严重的缺陷）。Grep中用于捕获元字符的是（…），而未转义的括号会当作普通字符（注4）。grep支持行锚点（line anchors），但方式十分有限。如果^出现在正则表达式的开头，它就是匹配行开头的元字符。否则它就不是一个元字符，而只是一个普通的脱字符。同样，$只有出现在正则表达式的末尾时才被当作元字符。结果，用户没法使用「end$|^start」这样的表达式。不过这不要紧，因为grep不支持多选结构。

元字符的作用规则也很重要。例如，grep 的最大问题或许在于，星号无法用来限定括号内的子表达式，而只能用于限定普通的字符、字符组，或者点号。所以，在grep中，括号的作用仅限于捕获已匹配的文本，而不能用来进行普通的分组。实际上，某些早期版本的grep甚至不支持括号嵌套。

Grep的发展历程

尽管今天的许多系统都有对应的grep，但你会注意到，本书中提到grep时使用的都是过去时态（译注1）。过去时对应旧版本所属的流派，它们的历史都超过30年了。在这段时间中，技术在不断进步，旧的程序也会加入新的特性，grep也不例外。

在最老版本的grep之上，AT&T的贝尔实验室加入了一些新的特性，例如从lex程序中借鉴来的{min，max}。他们还修正了-y选项，早期版本的grep通过-y进行不区分大小写的匹配，但此功能并不正常。同时，Berkeley 的人加入了表示单词开头和结束的元字符，把-y改为-i。不幸的是，星号或其他量词仍然无法作用于括号内的表达式。

Egrep的发展历程

此时，Alfred Aho（同样是AT&T的贝尔实验室）写出了egrep，它提供了第1章介绍的各种元字符中的大部分元字符。更重要的是，它以一种全然不同（但总的来说更好）的方式实现了这些功能。不但加上了「+」和「？」，还容许量词作用于括号内的表达式，这大大增强了egrep的表达能力。

同时，多选结构加入了，行锚点也升级到“基础级别”，可以在正则表达式的任何地方使用。不过，egrep也不够完美——有时候它能匹配，但不会显示结果，而且它缺乏某些当今流行的特性。不过无论如何，它都比grep有用得多。

其他工具的发展历程

就在egrep演变的同时，其他程序，例如awk、lex和sed，也在按各自的脚步前进。通常，开发人员会把某个程序中自己喜欢的特性添加到其他程序中。有时候，结果并不尽如人意。例如，如果要在 grep 中增加对「+」的支持，就不能直接使用‘+’，因为长期来以来在 grep中‘+’都不是元字符，突然进行这种修改会让大家感到不适应。因为‘+’可能是 grep的用户在正常情况下不会输入的，把它作为“重现一次或多次”的元字符可能更合适。

有时候，添加新特性也会带来新的bug。另外一些时候，新添加的特性不久后又被删除了。构成流派的各个细微的方面，几乎都没有什么文档，所以新的工具软件要么形成了自己的流派，要么尝试模仿其他工具，提供“看来相似”的功能。

这一切，加上漫长的发展史，众多的程序员，结果就是巨大的谜局（注5）。

POSIX——标准化的尝试

诞生于1986年的POSIX是Portable Operating System Interface（可移植操作系统接口）的缩写，它是一系列标准，确保操作系统之间的移植性。该标准的某些部分关乎正则表达式和使用他们的传统工具，所以值得我们关注。不过，本书涉及的各种流派无一严格地遵守了所有的相关规定。为了厘清正则表达式的混乱局面，POSIX把各种常见的流派分为两大类：Basic Regular Expressions（BREs）和Extended Regular Expressions（EREs）。POSIX程序必须支持其中的任意一种。下页的表3-1简要介绍了这两种流派的元字符。

POSIX标准的主要特性之一是locale，它是一组关于语言和文化传统——例如日期和时间的格式、货币币值、字符编码对应的意义等——的设定。locals的目的在于让程序变得国际化。它们不是正则表达式相关的概念，尽管它们会影响正则表达式的使用。举例来说，工作于Latin-1编码（也称为“ISO-8859-1”）之中时，à 和À（分别对应十进制编码224和160）也被认为是“字符”，任何不区分大小写的正则表达式都会认为这两个字符是相等的。

表3-1：POSIX正则表达式流派概览

另一个例子是w，通常用于表示“构成单词的字符”（在很多流派中，它等价于[a-zA-Z0-9_]）。这个特性并不是POSIX中必须的，但容许出现。如果支持的话，w就能对应locale中的所有字母和数字，而不仅仅限于ASCII编码的字符和数字。

如果程序支持Unicode，那么关于locale的问题就极大地简化了。Unicode的详细讨论从106页开始。

Henry Spencer的正则表达式包

同样是在1986年，发生了于一件更重要的事情，Henry Spencer发布了用C语言写的正则表达式包，这个包可以毫无困难地置入其他程序中——这在当时具有开创性的意义。每一个使用 Henry 的包的程序——的确存在很多——都属于相同的流派，除非程序的作者费尽周折去修改。

Perl的发展历程

差不多在同时，Larry Wall开始开发一种工具，也就是日后的Perl语言。他的patch程序已经大大促进了分布式软件开发（distributed software development），但是Perl注定要产生重大的影响。

1987年12月，Larry发布了Perl Version 1。Perl很快引起了关注，因为它糅合了其他语言的众多特性，但指向一个明确的目的：就是我们日常所说的“实用（useful）”。

Perl的特性中值得一提的是，它提供了传统上只有专用工具sed和awk才提供的正则表达式操作符——这在通用脚本语言中是个首创。正则引擎的代码来自一个早期的项目——Larry的新闻阅读器rn（其中的正则表达式代码来自James Gosling的Emacs（注6））。Perl的正则流派，用当时的标准衡量是很强大的，但功能不如今天那样齐全。它主要的问题在于，最多只能支持 9 组括号，9 个多选结构，最糟糕的是，括号内不容许出现「|」，也不能进行不区分大小写的匹配，不支持字符组中的w（完全不支持d和s）。也不支持区间量词{min，max}。

Perl 2发布于1988年6月。Larry完全放弃了原有的正则表达式代码，而采用了前面提到过的Henry Spencer的正则表达式包的增强版。括号的数目仍然只有9个，但是括号中可以使用「|」了。d和s的支持也加了进来，w现在可以匹配下画线了，从这时开始，w能够匹配 Perl 的变量名中容许出现的字符。此外，字符组之内也可以出现元字符（表示否定的元字符、D、W和S，也可以支持，但不能使用在字符组内部，而且总在有些情况下无法正常工作）。很重要的一点是，添加了/i量词，能够进行不区分大小写的匹配。

Perl 3发布于一年多以后的1989年10月。它添加了/e量词，这样极大地增强了替换运算符的能力，同时修正了之前版本中的一些与回溯相关的bug。也添加了{min，max}区间量词。虽然很不幸，这些量词不能保证在任何情况下都可以正常工作。还有，这时候 Perl 的正则引擎本不应该停留在只处理8位编码数据的水平，但是面对非ASCII输入时，会产生无法预料的结果。

Perl 4的发布是在一年半以后，1991年3月，在接下来的两年间，Perl 4一直在改进，直到1993年2月发布最终升级。到此时，之前的bug已经修正，原有的限制也被突破（D之类可以应用在字符组中，而括号的数目也不再有限制），正则引擎也花了很多功夫来优化，不过真正的突破是在1994年。

Perl 5正式发布于1994年10月。这一版的Perl经历了全面的修整，在各个方面都比原来强上许多。就正则表达式来说，它进行了更多的内部优化，添加了少量元字符（G增强了迭代匹配的能力☞130）、非捕获的括号（☞45）、忽略优先（lazy）的量词（☞141）、顺序环视功能（☞60），以及/x量词（☞72）（注7）。

这些新增功能的意义并不限于功能本身，更重要的是，这些“新增”的修改使正则表达式本身成为一种强大的编程语言，并为它提供了进一步的发展空间。

新增的非捕获型括号和顺序环视结构都需要新的表达方式。而（…）、[…]、＜…＞和{…}都已经有了含义，所以Larry采用了我们今天使用的‘（？’表示法。这个表示法并不好看，不过在之前的Perl正则表达式中这是不合规则的组合，所以添加起来完全没有障碍。Larry也预见到，将来可能还需要新增其他的功能，所以他对‘（？’之后的字符做了限制，这样就能保留某些字符，用于将来更多的功能。

之后的各版 Perl 越来越健壮，错误越来越少，内部优化越来越棒，添加了越来越多的新特性。我相信，本书的第一版也为此做了小小的贡献，因为鄙人研究和测试了正则表达式相关的特性，并将结果告知Larry和Perl Porters group，为改进提供了反馈。

后来添加的新特性包括逆序环视功能（☞60），“固化”分组（“atomic” grouping☞139），和Unicode支持。新添加的条件判断结构更是把正则表达式提升到了一个新的层次（☞140），它容许用户在正则表达式中进行if-then-else的条件判断和控制。如果这些还不够强大的话，新的结构甚至容许程序员在正则表达式中运行 Perl 代码，正则表达式和程序代码之间的界限已经不复存在了 （☞327）。本书中使用的Perl的版本为5.8.8。

流派的部分整合

具有先见之明的Perl 5完全契合了互联网革命的节拍。Perl的初衷是文本处理，而Web页的生成其实正是文本处理，所以Perl迅速成为了开发Web程序的语言。Perl广受欢迎，其中强大的正则流派也是如此。

其他语言的开发人员当然不会视而不见，最终在某种程度上“兼容Perl”（Perl compatible）的正则表达式包出现了。Tcl、Python、.NET、Ruby、PHP、C/C++都有各自的正则表达式包，Java语言中还有多个正则表达式包。

另一种形式的整合始于1997年（凑巧的是，本书的第一版也在当年面世），当时Philip Hazel开发了PCRE，这是一套兼容Perl正则表达式的库，PCRE的正则引擎质量很高，全面仿制Perl 的正则表达式的语法和语义。其他的开发人员可以把 PCRE 整合到自己的工具和语言中，为用户提供丰富而且极具表现力（也是众所周知）的各种正则功能。许多流行的软件都使用了PCRE，例如PHP、Apache 2、Exim、Postfix和Nmap（注8）。

本书对应的版本

表3-2列出了本书中使用的工具和库的版本信息。更老的版本可能功能更少，bug更多，新的版本则会提供更多的特性，并修正之前的bug（当然也可能多出新的bug）。

表3-2：本书中提到的一些工具的版本

最初印象

At a Glance

我们用一张表格来比较常见工具软件在几方面的功能，以便理解仍然存在的差异。表 3-3提供了若干工具软件的正则表达式所属流派在各方面的简要信息。

其他书籍通常在比较各款工具软件时，也会包含表3-3之类的表格。但是，这张表只是冰山一角——列出的每一种特性的背后，都有许多重要的知识。

最重要的是程序会不断变化。举例来说，Tcl以前是不支持反向引用和单词分界符的，但是现在支持。最开始，用来表示单词分界符的是难看的[：＜：]和[：＞：]，至今仍是这样，尽管这种表示法已经废弃，取代它的是后来添加的m、M和y（单词起始、单词结束，或者两者皆是）。

同样，grep和egrep并没有单一的作者，只要愿意，任何人都可以开发，也能修改到符合到作者期望的任何流派。人人都希望按照自己的意愿来，人性就是如此（例如，许多常用工具的GNU版本，比其他版本更强大，也更健壮）。

表3-3：若干常用工具的Flavor的（非常）简要考察

或许与列出的特性一样重要的是流派之间的许多细微（有些并非细微）差别。从表格来看，Perl、.NET 和 Java 的正则表达式似乎是一样的，而实际情况却远不是这样。针对表 3-3，读者可能提出的问题包括：

●星号之类的量词能否作用于括号之内的子表达式？

●点号能否匹配换行符？排除型字符组能否匹配换行符？以上两者能否匹配 NUL 字符？

●行锚点（line anchor）是名符其实的吗（例如，他们能否识别目标字符串内部的换行符）？它们算正则表达式中的基础级别（first-class）的元字符吗？还是只能应用在某些结构中？

●字符组内部能出现转义字符吗？字符组内部还容许或不容许出现哪些字符？

●括号能够嵌套吗？如果是，嵌套的深度是否有限制呢（还有个问题是，一共容许出现多少括号呢）？

●如果容许反向引用，在进行不区分大小写的匹配时，反向引用能顺利进行吗？在极端的情况下，反向引用的“行为”有意义吗？

●是否可以出现八进制的转义字符123？如果是，怎么区分它和反向引用呢？十六进制的转义字符呢？这种支持是正则引擎提供的，还是由其他工具提供的？

●w只支持数字和字符，还是包括其他字符？（表 3-3 列出的支持w的工具对w有不同的解释）。不同的单词分界符元字符对构成“单词分界符”的字符的定义不一样，w是否与它们保持一致？它们是按照locale的定义呢，还是支持Unicode？

即使表3-3这样的介绍这样简单，我们仍然必须记得这些问题。如果你能意识到，在看起来光鲜的外表下面潜藏着许多问题，就容易保持清醒的头脑来应付它们。

在本章开头我们已经提到，许多问题只是语法的差异，但也有许多并非如此。比方说，了解到egrep的「（Jul|July）」在GNU Emacs中必须写成「（Jul|July）」之后，你或许会认为所有的问题都是这样，但事实并非如此。在匹配尝试过程中的语义差异（或者，至少是看起来是在匹配尝试过程中的）通常被忽视，但极其重要的问题是，它也解释了为什么两个看起来一样的表达式会获得截然不同的结果：一个总是匹配‘Jul’，即使目标文本是‘July’。这些看起来毫无区别的语义也解释了，为什么两个顺序相反的正则表达式：「（July|Jul）」和「（July|Jul）」能够取得同样的匹配结果。其实，整个下一章都在讲解这类问题。

当然，一款工具软件能够利用正则表达式实现的功能，通常比它所属的正则流派更重要。例如，就算Perl的正则表达式功能不及egrep，在使用正则表达式时，Perl所具有的简便性却更有价值。我们会在本章逐个介绍各种特性，并在后面各章深入讲解几种编程语言。