Rob Pike 编写的正则表达式程序

正则表达式先是从QED移植到了Unix的编辑器ed中，然后又被移植到UNIX非常（译注：quint印刷错误？疑是quite）基本的工具grep中，这是Thompson对ed进行了彻底改造时创建的一个工具。通过早期的Unix社区，正则表达式得以被人熟知。

Thompson最初写的匹配器是很快的，因为它包含了两种独立的思想。其一是在匹配过程中动态地生成机器指令，这样就可以以机器指令执行的速度 而不是解释执行的速度来运行。另一种思想是在每个阶段中都尽可能地执行匹配操作，这样无需回朔就可以查找可能的匹配。在 Ken后来写的文本编辑器，例如ed中，匹配代码使用了更简单的算法，在必要的时候才会进行回朔。理论上，这样的运行速度要慢一些，但在实际情况中，这种模式很少需要进行回朔，因此，ed和grep中的算法和代码足以应付大多数的情况。

编程实践

在1998年，Rob Pike和我还在编写《程序设计实践（The Practice of Programming）》("TPOP")一书。书中的最后一章是“标记法”，在这一章中收录了许多例子，这些示例可以带来良好的程序和更好的编程方式。其中包括使用简单的数据规范（例如printf的格式）以及从表中生成代码。

由于我们有着深厚的Unix技术背景，以及在使用基于正则表达式记法的工具上有着多年的经验，我们很自然地希望包含一些对正则表达式的讨论，似乎也必须包含一个实现。同时由于我们强调了工具，最好应该把重点放在grep中的正则表达式类型上，而不是类似shell的通配符那样的，随后我们还可以讨论grep本身的设计。

问题是任何存在的正则表达式包都太大了。grep的代码超过500行（差不多得占10页纸).开源正则表达式包几乎得占整本书，因为它们被设计的通用、灵活和高效；没有一个适合教学。
我告诉Rob我们需要一个小的正则表达式包，这个包可以阐明基本的思想，同时可以识别相当一类模式。理想情况下所以的代码仅占一页纸。

Rob回去了他的办公室，不超过一到两个小时之后，他带着30行C代码回来了，这30行代码随后出现在了TPOP的第9章。这些代码实现了处理下述句法结构的正则表达式匹配器：

 c 匹配任意原义字符c
 . 匹配任意单个字符
 ^ 匹配输入字符串的开始端
 $ 匹配输入字符串的结束端
 * 匹配零个或多个前一字符

这是非常有用的一类模式；按照我日常使用正则表达式的经验，这占了95%的情况。在很多情况下，解决正确的问题是通往优美的程序的重要一步。Rob从很多选项中选出了这样一个小而美的子集是值得高度赞扬的。

实现

在书中，正则表达式匹配器是模仿grep的一段程序，但是正则表达式代码是可以完全分离出来的。我们这里不关心主程序——它仅仅从标准输入或者文件中读数据，输入匹配正则表达式的行，就像grep和很多其它Unix工具做的那样。
这是匹配代码：

方法match(regexp,text)检查text中是否有匹配正则表达式的情况；如果匹配返回1，否则返回0。如果有不止一个匹配，返回最左边最短的那一个。

match的基本操作是很直观的。如果正则表达式的第一个字符是^（一个定位匹配），那么任意可能的匹配发生在字符串的开始位置。也就是，如果正则表达式是^xyz，那么只有xyz出现在字符串开头的时候它才匹配xyz，在中间的某位置就不会匹配。这种情况通过用剩下的正则表达式从头开始匹配字符串来检查，从其它位置开始的字符串子串就不用检查。

否则，如果正则表达式的第一个字符不是^，那么正则表达式可能匹配字符串的任意位置。这通过依此用正则表达式匹配字符串每个位置来测试。如果有多个匹配，只有第一个（最左边的）匹配会被识别到。也就是，如果正则表达式是xyz，那么它将会匹配第一个出现的xyz子串，而不关心出现的位置。

注意程序中是通过do-while循环来推进输入字符串的，这在C语言程序中是一个相对不寻常的构造。用do-while而不是用while，这就引出一个问题：为什么循环终止条件不趁早在循环结构开始的时候检查，而是在循环结构结束的时候？但是这样检查在这里是正确的：因为*符号允许零长度的匹配，所以我们首先不得不检查是不是空匹配。

程序大部分工作是在函数matchhere(regexp,text)中做的，这个函数检查从此处开始的字符串是否匹配正则表达式。方法matchhere尝试匹配正则表达式第一个字符与字符串第一个字符。如果匹配失败，那么从字符串这个位置开始没有匹配，所以matchhere返回0。如果匹配成功，那么就继续检查正则表达式下一个字符与字符串下一个字符是否匹配。通过递归调用matchhere完成上述工作。

由于一些特殊的情况，处理起来就有点儿复杂了。最简单的情况是如果正则表达式读完了（regexp[0] == ''），那么之前所有的检查都是成功的，因此正则表达式匹配字符串。

如果正则表达式是跟着*号的字符，那么调用matchstar检查闭包是否匹配。函数matchstar(c,regexp,text)试图匹配重复出现的字符c，从零次重复开始增加，在剩下的字符串中寻找匹配，或者匹配不成功，那就表示没有匹配。这样识别的是一个“最短匹配”，对grep这种简单模式匹配，“最短匹配”还是是蛮好的，这样可以尽快找到一个匹配。“最长匹配”相对更直观，对于文本编辑器的替换匹配功能更适合。大部分现代正则表达式库同时提供两种模式，TPOP提供了matchstar的最长匹配版本，稍后将会展示。

如果正则表达式最后一个字符是$，字符串也到了末尾,那么就匹配了。

否则，如果不是在字符串的末尾（也就是，*text!=''），字符串第一个字符匹配了正则表达式第一个字符，那么就递归调用matchhere检查正则表达式下一个字符是否匹配字符串下一个字符。递归调用是算法的核心也是算法如此紧凑简洁的原因。

如果所有的匹配尝试都失败了，那么正则表达式和字符串没有匹配，所有matchhere返回0。

代码使用了C指针。在递归的每个阶段，如果某部分匹配了，接下来的递归调用使用了指针运算（比如，regexp+1和text+1）使得接下来的函数调用传入正则表达式和字符串的下一个字符。递归的深度不超过模式的深度，在通常的使用中都很短，所有没有空间不足的风险。

其他方案

这是一段优雅的写的很好的代码，但是它并不完美。有人可能会按照其他的方式来写。在这里我可能重新组织匹配的顺序，将$匹配的探测置于*之前，尽管这两种处理方式本质上并没有区别，但是这样做看起来更自然些。在处理难题之前先做一些容易的事是一个很好的习惯。

一般情况下，匹配测试的顺序是非常重要的。比如下面的frommatchstar测试：