第 1 章 正则表达式匹配器
Brian Kernighan
正则表达式是描述文本模式的表示法,它可以有效地构造一种用于模式匹配的专用语言. 虽然正则表达式可以有多种不同的形式,但它们都有着共同的特点:模式中的大多数字符都是 匹配字符串中的字符本身,但有些元字符(metacharacter)却有着特定的含义,例如*表示某 种重复,而[...]表示方括号中字符集合的任何一个字符. 实际上,在文本编辑器之类的程序中,所执行的查找操作都是查找文字,因此正则表达式 通常是像"print"之类的字符串,而这类字符串将与文档中所有的"printf"或者"sprintf" 或者"printer paper"相匹配.在Unix和Windows中可以使用所谓的通配符来指定文件名,其 中字符*可以用来匹配任意数量的字符,因此匹配模式*.c就将匹配所有以.c结尾的文件.此外, 还有许许多多不同形式的正则表达式,甚至在有些情况下,这些正则表达式会被认为都是相同 的.Jeffrey Friedl编著的《Mastering Regular Expressions》一书对这一方面问题进行了广 泛的研究. Stephen Kleene在20世纪50年代的中期发明了正则表达式,用来作为有限自动机的表示法, 事实上,正则表达式与其所表示的有限自动机是等价的.20世纪60年代年代中期,正则表达式 最初出现在Ken Thompson版本的QED文本编辑器的程序设置中.1967年Thompson申请了一项基于 正则表达式的快速文本匹配机制的专利.这项专利在1971年获得了批准,它是最早的软件专利 之一[U.S. Patent 3,568,156, Text Matching Algorithm, March 2, 1971]. 后来,正则表达式技术从QED移植到了Unix的编辑器ed中,然后又被移植到经典的Unix工具 grep中,而grpe正是由于Thompson对ed进行了彻底地修改而形成的.这些广为应用的程序使得 正则表达式为早期的Unix社群所熟知. Thompson最初编写的匹配器是非常快的,因为它结合了两种独立的思想.一种思想是在匹 配过程中动态地生成机器指令,这样就可以以机器指令执行的速度而不是解释执行的速度来运 行.另一种思想是在每个阶段中都尽可能地执行匹配操作,这样无需回朔(backtrack)就可以 查找可能的匹配.在Thompson后来编写的文本编辑器程序中,例如ed,匹配代码使用了一种更 为简单的算法,这种算法将会在必要的时候进行回朔.从理论上来看,这种方法的运行速度要 更慢,但在实际情况中,这种模式很少需要进行回朔,因此,ed和grep中的算法和代码足以应 付大多数的情况. 在后来的正则表达式匹配器中,例如egrep和fgrep等,都增加了更为丰富的正则表达式类 型,并且重点是要使得匹配器无论在什么模式下都能够快速执行.功能更为强大的正则表达式
1
正在被越来越多地使用,它们不仅被包含在用C语言开发的库中,而且还被作为脚本语言如Awk 和Perl的语法的一部分.
1.1
编程实践
在1998年,Rob Pike和我还在编写《The Practice of Programming》(Addison-Wesley) 一书.书中的最后一章是"记法",在这一章中收录了许多示例代码,这些示例都很好地说明 了良好的记法将会带来更好的程序以及更好的设计.其中包括使用简单的数据规范(例如 printf)以及从表中生成代码. 由于我们有着深厚的Unix技术背景以及在使用基于正则表达式记法的工具上有着近30年的 经验,我们很自然地希望在本书中包含一个对正则表达式的讨论,当然包含一个实现也是必须 的.由于我们强调了工具软件的使用,因此似乎最好应该把重点放在grep中的正则表达式类型 上——而不是,比方说,在shell的通配符正则表达式上——这样我们还可以在随后再讨论grep 本身的设计. 然而,问题是现有的正则表达式软件包都太庞大了.grep中的代码长度超过500行(大约10 页书的长度),并且在代码的周围还有复杂的上下文环境.开源的正则表达式软件包则更为庞 大——代码的长度几乎布满整本书——因为这些代码需要考虑通用性,灵活性以及运行速度; 因此,所有这些正则表达式都不适合用来教学. 我向Rob建议我们需要一个最小的正则表达式软件包, 它可以很好地诠释正则表达式的基本 思想,并且能够识别出一组有用的并且重要类的模式.理想的情况是,所需代码长度只有一页 就够了. Rob听了我的提议后就离开了他的办公室.我现在还记得,一,两个小时后他回来了,并且给了 我一段大约30行的C代码,在《The Practice of Programming》一书的第9章中包含了这段代码. 在这段代码实现了一个正则表达式匹配器,用来处理以下的模型. 字符 c 含义 匹配任意的字母c 匹配任意的单个字符

下一页