Brian W. Kernighan and Rob Pike
[说明：本文由phylips@bmy翻译自Regular Expressions Languages, algorithms, and software 1999-01 Author： Brian W. Kernighan and Rob Pike。Brain 和 Rob是朗讯科技贝尔实验室的研究人员，可以通过他们各自的邮件bwk@bell-labs.com and rob@bell-labs.com联系他们。]
原文链接：http://www.ddj.com/architect/184410904?pgno=1，转载请保留全部信息。
正则表达式，作为应用最广泛的程序员工具之一，提供了一种描述文本模式的简练但强有力的表达方式。从算法上来看，它们也是很有趣的，容易实现，用途广泛。Brain和Rob，是贝尔实验室的研究人员，同时也是<<程序设计实践>>的作者，他们在本文中描述了一种grep(使用正则表达式进行文本搜索的工具)的简单版本的实现。
—————————————————————————————————————————————————————–
如果选择恰当的程序设计语言可以让写程序变得相当简单。这也是为什么一个程序员不仅需要掌握一种通用语言比如c语言及其变种，而且需要学习一下可编程脚本语言以及大量的针对具体应用的专门语言。好的记法的力量可以超越传统的编程方法而深入到特殊的问题域。比如html让我们可以创建交互文档，我们也经常在一些程序中使用一些嵌入性的脚本语言比如javascript，postscript可以描述整个打印文档格式内容。表格和字处理器，通常包含一些语言以进行表达式计算，信息访问和布局控制。
正则表达式是被最广泛使用的专门化语言，主要用于描述文本模式。正则表达式有很多种不同的形式，比如在命令行处理器和shell里用来匹配文件名的通配符，"*"被用来代表"任何字符组成的字符串"。下面的这个命令：del *.exe.使用"*.exe"匹配那些所有文件名以.exe结尾的文件。
正则表达式遍及unix的各个方面：编辑器；小工具如grep；脚本语言比如awk，perl，tcl。尽管不同的程序里正则表达式有所不同。实际上从更专业的角度看，语言实际上是一种描述语法结构及对于语言中允许出现的结构的准确含义的形式化定义。更进一步的讲，正确的实现可以具有很高的运行效率，所以说它也是理论与工程实践的紧密结合的混合体。
正则表达式语言
正则表达式是定义模式的一系列字符序列。大部分模式中的字符，仅仅是用来匹配目标字符串中的字符。比如正则表达式"abc"匹配目标串中出现在任何位置的"abc"。除了这些，模式中还有一些叫做元字符的，用来表示重复，分组或者定位。在POSIX正则表达式里，"^"代表字符串的开始，"$"代表字符串的结尾。这样"^x"就匹配字符串开头的x；"x$"匹配字符串结尾的x；"^x$"匹配只有一个字符x的串；"^$"匹配空串。
字符"."匹配任何字符，这样"x.y"匹配"xay","x2y"…这些；但是不匹配xy或者xyxy。"^.$"匹配只包含一个字符的字符串。在"[]"的一组字符集可以匹配出现在该字符集中的任意一个字符。比如[0123456789]可以匹配一个数字，也可以简写成[0-9]。
这些构建块还可以用括号进行分组，"|"表示可选，"+"代表出现一次或更多，"*"代表出现零次或更多，"?"表示出现0或1次。最后"\"被作为转义字符，可以表示那些元字符对应的普通字符并去掉它们的特殊含义。
上面这些元素可以不断组合形成丰富的模式。比如"\.[0-9]+"匹配小数点后跟1个多个数字；"[0-9]+\.?[0-9]*" 可以匹配数字.数字；"(\+|-)"匹配+或-；"[eE](\+|-)?[0-9]+" 匹配"e"或者"E"后面跟可选的正负号，以及一个或多个数字。这些组合起来就可以用来匹配浮点数：
(\+|-)?([0-9]+\.?[0-9]*|\.[0-9]+)([eE](\+|-)?[0-9]+)?
正则表达式搜索函数
一些系统包含正则库，通常叫做"regex"或者"regexp"。然而，如果不存在可用的正则库，也很容易实现一个正则表达式语言的适度的可用子集。这篇文章里描述的正则式就只利用了下面4个元字符：^$.*。这篇文章将通过一种实现复杂度很低的方法实现这种威力强大的正则表达式。使用这些方法实现一个简单但很有用的工具grep的简单版本。
在example1里，函数match用来确定一个字符串与一个正则表达式是否匹配。如果正则式以"^"开头，那么文本比较以与正则式剩余部分匹配的文本开头。否则我们将穷举所有的开始位置，然在这些位置使用matchhere，分别检查这些位置是否匹配。一旦我们找到一个匹配，那么就结束搜索。包含"*"的表达式可以匹配空串(比如".*y"可以匹配y),所以我们们比较调用matchhere,即使文本是空的。
/* match: search for re anywhere in text */
int match(char *re, char *text)
{
if (re[0] == ‘^’)
return matchhere(re+1, text);
do { /* must look at empty string */
if (matchhere(re, text))
return 1;
} while (*text++ != ‘\0’);
return 0;
}
Example 1: The function match determines whether a string matches a regular expression.
在example2里，递归函数matchhere完成绝大多数工作。如果正则表达式是空的，或者我们已经到达正则式串尾，这样我们就找到了一个匹配。如果正则表达式以"$"结尾，只有当文本串也到达串尾才算匹配。如果正则表达式以.开始，它匹配任意字符，否则它以与它相同的一个普通字符开始。如果"^$"出现在正则式的中间，我们就把它们看做是普通字符处理，而不是元字符。
/* matchhere: search for re at beginning of text */
int matchhere(char *re, char *text)
{
if (re[0] == ‘\0’)
return 1;
if (re[1] == ‘*’)
return matchstar(re[0], re+2, text);
if (re[0] == ‘$’ && re[1] == ‘\0’)
return *text == ‘\0’;
if (*text!=’\0′ && (re[0]==’.’ || re[0]==*text))
return matchhere(re+1, text+1);
return 0;
}
Example 2: The recursive function matchhere does most of the work.
注意matchhere每次匹配完正则式和文本中串的一个字符后就会进行一次递归调用。因此递归的深度与patten的长度一致。如果表达式以"字符*"开始，则需要特殊处理一下。比如"x*",这时我们需要调用matchstar-该函数有三个参数：*的操作数x，*后面的模式串，文本串，具体参见example3。因为*可以匹配0个字符，所以循环里除了检查去掉与x匹配后的剩余串之外，还要检查当前文本串是否与剩下的模式串匹配。
/* matchstar: search for c*re at beginning of text */
int matchstar(int c, char *re, char *text)
{
do { /* a * matches zero or more instances */
if (matchhere(re, text))
return 1;
} while (*text!=’\0′ && (*text++==c || c==’.’));
return 0;
}
Example 3: The function matchstar is called when the expression begins with a starred character.
我们的实现并不高级，但是它至少可以工作。而且少于30行代码，这也说明正则表达式并不需要高级的技术才可以使用。
Grep
由Ken Thompson(unix之父)发明的文本匹配程序grep，体现了良好记法的强大威力。他使用正则表达式来匹配输入文件里的每一行，打印出那些包含匹配串的行。这种简单的描述方法加上正则表达式的威力，使它被用来完成很多日常任务。在下面的例子里，可以看到grep使用的正则表达式与表示文件名的通配符模式并不一样。
在一个源文件集合里，搜索一个名字：grep fprintf *.c
在一个文本文件集里，搜一个短语： grep ‘regular expression’ *.txt
过滤其他程序的输出，比如只打印错误信息： gcc *.c | grep Error
为其他程序过滤输入，比如计算非空行数：grep . *.cpp | wordcount
加上flag,就可以控制让它打印匹配行数，匹配数目，忽略大小写，打印不匹配行。grep已经成为基于工具的编程的一个经典实例。
example4 是使用match实现的grep实现的主过程。返回0代表成功，非零代表失败。我们的grep，比如unix版本，把找到匹配行定义为成功，所以如果存在匹配就返回0，如果不存在返回1，如果发生错误返回2。这个返回的状态值，可以被其他的程序检测到，比如shell。
/* grep main: search for re in files */
int main(int argc, char *argv[])
{
int i, nmatch;
FILE *f;
if (argc < 2) {
fprintf(stderr, "usage: grep pattern [file …]\n");
exit(2);
}
nmatch = 0;
if (argc < 3) {
if (grep(argv[1], stdin, NULL))
nmatch++;
} else {
for (i = 2; i < argc; i++) {
f = fopen(argv[i], "r");
if (f == NULL) {
fprintf(stderr, "grep: can’t open %s\n", argv[i]);
continue;
}
if (grep(argv[1], f, argc>3 ? argv[i] : NULL))
nmatch++;
fclose(f);
}
}
return nmatch == 0;
}
Example 4: Main routine of an implementation of grep that uses match. (Assumes command interpreter expands wild cards in file specification on the command line into lists of file names. UNIX shells exhibit this behavior, although MS-DOS COMMAND.COM does not.)
example5 表示，函数grep扫描一个文件，在每一行上调用match函数。这个看起来很直接，但有两点需要注意。首先，如果打开文件失败主程序并不会退出，这是因为人们通常这样写："grep her *.* "。如果发现一个文件不能读取，报告这个错误之后，最好能够继续往下执行而不是放弃，这样可以避免让用户为避免这个问题文件而敲入所有文件名。第2，grep打印出匹配行及其文件名，但是如果是从标准输入或者单个文件中读取输入的话，会不打印文件名。这一点看起来像一个并不对称的设计，实际上它反应了基于用户经验的风格。如果单一输入，实际上文件名就不必要，但是如果是多个输入，输出文件名就很有帮助了。
/* grep: search for re in file */
int grep(char *re, FILE *f, char *name)
{
int n, nmatch;
char buf[BUFSIZ];
nmatch = 0;
while (fgets(buf, sizeof buf, f) != NULL) {
n = strlen(buf);
if (n > 0 && buf[n-1] == ‘\n’)
buf[n-1] = ‘\0’;
if (match(re, buf)) {
nmatch++;
if (name != NULL)
printf("%s:", name);
printf("%s\n", buf);
}
}
return nmatch;
}
Example 5: The function grep scans a single file, calling match on each line.
我们的match会尽快返回一个匹配，对于grep来说这样是没有问题的，可以保证找到所有的匹配。但是对于在一个文本编辑器里实现替换，寻找最左最长匹配应该是更有用的。例如给定文本串"aaaaa"，"a*"匹配空串，但是用户实际上可能想匹配所有的5个字符。为了能让match可以找到最左最长匹配，matchstar必须要重写。不是从左往右开始寻找匹配，而是应该首先跳过最长的那个匹配，看剩余部分，如果剩余部分不匹配则回溯，如果匹配则返回。也就是说，应该从右往左的顺序进行探测，example6就是这个版本的matchstar。这个对于grep来说可能是错误的版本，因为它做了额外的工作，但是对于替换来说，它是必要的。
/* matchstar: leftmost longest search for c*re */
int matchstar(int c, char *re, char *text)
{
char *t;
for (t = text; *t != ‘\0’ && (*t == c || c == ‘.’); t++)
;
do { /* * matches zero or more */
if (matchhere(re, t))
return 1;
} while (t– > text);
return 0;
}
Example 6: A version of matchstar that does leftmost longest matching.
what next?
我们实现的grep与系统提供的版本相比是有一定的竞争力的。比如在一个400-MHz Pentium，搜索一个40-Mb文本文件需要花费6秒。但是一些病态表达式会引起指数性的行为，比如"a*a*a*a*a*b"，当它匹配 "aaaaaaaaac"时，将会花费指数级的时间复杂度，实际上这在很多商业性的实现里也存在这样的问题。一个更数学化的匹配算法可以保证线性性能，避免在部分匹配失败时进行回溯。unix的grep版本就实现了这样的一个算法，很多脚本语言采用了这个算法。
对于包含"()"和"|"的正则表达式，这个实现更加复杂。一种方法就是将正则表达式编译成一个包含其语法结构的解析树，然后这棵树被用来转换成状态机–用一个状态表来表示，每个状态包含给定输入字符下的下一个状态指针。然后将文本串通过状态机扫描，如果到达匹配状态则报告匹配。另一种方法，比较类似于实时编译器，正则表达式被编译成可以扫描字符串的机器指令，在生成指令中实际上包含了一个隐式的状态机。
进一步的阅读
O’J.E.F. Friedl’s Mastering Regular Expressions (O’Reilly & Associates, 1997) is an extensive treatment of the subject. Regular expressions are one of the most important features of some scripting languages; see The AWK Programming Language by A.V. Aho, B.W. Kernighan and P.J. Weinberger (Addison-Wesley, 1988) and Programming Perl, by Larry
Wall, Tom Christiansen, and Randal L. Schwartz (O’Reilly & Associates, 1996).