《代码之美》（一）－－正则表达式匹配器

Brain Kernighan

正则表达式是描述文本模式的记法（notation），它由Stephen Kleen在上世纪50年代中期发明，最初出现在Ken Thompson的QED文本编辑器中，之后移植到Unix的编辑器ed中，然后又被移植到Unix工具grep中。Jeffrey Friedl的《Mastering Regular Expression》对其进行了详细研究。

Rob Pike在1998年与Brain Kernighan编写《The Practice of Programming》时，给出了用于教学的示例代码：一个最小的正则表达示软件包，它可以处理以下的模型：

字符	含义
c	匹配任意的字母c
.（句点）	匹配任意的单个字符
^	匹配输入字符串的开头
$	匹配输入字符串的结尾
*	匹配前一个字符的零个或多个出现

下面是Rob的（C语言）代码：

int match(char* regexp, char* text)
{
    if (*regexp == '^')
        return matchhere(regexp+1, text);
    do {
        if (matchhere(regexp, text))
            return 1;
    } while (*text++ != '\0');
    return 0;
}

int matchhere(char* regexp, char* text)
{
    if (regexp[0] == '\0')
        return 1;
    if (regexp[1] == '*')
        return matchstar(regexp[0], regexp+2, text);
    if (regexp[0] == '$' && regexp[1] == '\0')
        return *text == '\0';
    if (*text != '\0' && (regexp[0] == '.' || regexp[0] == *text))
        return matchhere(regexp+1, text+1);
    return 0;
}

int matchstar(int c, char* regexp, char* text)
{
    do {
        if (matchhere(regexp, text))
            return 1;
    } while (*text != '\0' && (*text++ == c || c == '.'));
    return 0;
}

函数match首先判断输入的正则表达式是否以“^”开头，如果是则尝试匹配整个字符串，否刚迭代地尝试匹配其所有子字符串。do...while形式的 迭代保证了text为空时仍可以进行匹配。matchhere里，只要它的首字符匹配，则继续递归调用matchhere来匹配下一字符，当regexp 为空时便表示完全匹配。对于特殊符号"*"，单独使用函数matchstar来匹配。matchstar可以识别“最短匹配”。

为了实现最长匹配，可以修改matchstar：

int matchstar(int c, char* regexp, char* text)
{
    char* t;
    for (t = text; *t != '\0' && (*t == c || c == '.'); t++)
        ;
    do {
        if (matchhere(regexp, t))
            return 1;
    } while (t-- > text);
    return 0;
}

它首先将尽可能多的匹配字符c，而后每次匹配失败再回退进行下一次尝试。

 

Brian对Rob的代码的紧凑性和优雅性高度赞扬，认为这段代码短小而且强大，并分析了它为什么能如此短小：
首先，它很好地选择了一个功能集合，挑选了正则表达式中最核心而又最具代表性的东西。比如，它挑选了“*”，但没有实现“+”和“?”这些类似的字符。

其次，它成功地使用了递归。从正则表达式的开头和text的开头剥离匹配字符，对剩余的字符进行递归。这样比显示循环产生更短，更整洁以及更优雅的代码。

最后，它使用了（C语言）基本的语法来实现良好的效果。利用指针提取单个字符和传递下一个字符。
 

：1942年1月生，加拿大计算机科学家，现任普林斯顿计算机科学的教授。曾在贝尔实验室与Unix创始人Ken Thompson和Dennis Ritchie同共开发Unix。代表作有《C programming language》、《AWK》、《AMPL programming languages》等。