使用递归实现正则匹配

很久之前就读到 Brain 的文章¹，讲怎么写优雅的代码。作者在文中讲了 Rob Pike² 的故事，Rob 用一个多小时的时间实现了一个简的的正则匹配函数， 所有代码加上注释也才三十多行。Rob 的实现不但简洁而优雅，而且还充分展示了递归函数和指针的强大魅力。今天就结合自己的理解分享给大家。

什么样的代码能算优雅呢？Brain 给出了如下几条标准：

优雅的代码通常都很简洁，清晰易懂。

优雅的代码通常又很简短，代码量刚刚好，不多也不少。

优雅的代码应该很通用，可以解决一大类相似的问题。

而 Rob 实现的简单的正则匹配函数就是非常好的例子。

正则表达式是一类特殊的字符匹配语法³，是 Stephen Kleene 在 1950 年代中期发明的。到了 1960 年中期，UNIX 之父 Ken Thompson 在自己实现的 QED 编辑器添加了正则表达式匹配功能。后续 UNIX 系统上的 ed/vim/grep/sed/awk/prel 等软件都受其影响支持用正则表达式搜索文本。

Brain 和 Rob 也有深厚的 UNIX 背景。它们在 1998 年合著 The Practice of Programming (TPOP) 是想给出一个简单的正则匹配实现，主要用于编程教学目的。但当时的实现功能比较多，代码比较长。像是 grep 代码超过 500 行，印在纸上大约需要十页。

所以 Bran 建议 Rob 搞一个简化版，代码不能太长，但还要展示正则表达式的核心思想，而且新的方案要有实用价值，不能只写玩具代码。然后 Rob 默默关上办公室的门，一小时后 Rob 用大约 30 行 C 代码实现了简化版的正则匹配程序。他支持如下正则语法子集：

• c 匹配任意字符字面量，比如 c 匹配字符 c，b 匹配字符 b 等
• . 匹配任意单个字符
• ^ 匹配字符的开头
• $ 匹配字符的结尾
• * 表示它前面的字符出现零次或多次

Rob 精心选择出这些功能子集，不但覆盖了多数的字符串搜索场景，而且非常易于实现。所以说要想写出漂亮的代码，首先要找出问题的核心。

先给出核心代码，连同注释一共 34 行：

/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
  if (regexp[0] == '^')
    return matchhere(regexp+1, text);
  do {  /* must look even if string is empty */
    if (matchhere(regexp, text))
    return 1;
  } while (*text++ != '\0');
  return 0;
}

/* matchhere: search for regexp at beginning of text a.c */
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;
}

/* matchstar: search for c*regexp at beginning of text */
int matchstar(int c, char *regexp, char *text)
{
  do {  /* a * matches zero or more instances */
    if (matchhere(regexp, text))
    return 1;
  } while (*text != '\0' && (*text++ == c || c == '.'));
  return 0;
}

入口函数是match，它接受两个 char 指针，分别指向正则表达式和要搜索的字符串内容。 c 语言使用[]char数组保存字符串，结尾额外保存一个\0字符。在 c 语言中，可以用 char *指针指向[]char中具体的位置。

match逻辑非常简单，主要是根据正则中是否有^进行分流。如果正则表达式为^xyz，那么xyz只有出现在text的开头才算匹配成功，这里调用了另一个函数matchhere；如果正则只没有^，那么该匹配模式可能出现在输入字符串的任意位置，为此需要遍历 text的每一个子串来检查是否匹配。

在match函数中的循环条件为*text++ != '\0'，会从左向右不断扫描输入字符串的子串。如果有匹配则返回1，否则返回0。

最核心的匹配逻辑由matchhere实现。这里的here表示就地比较，不需要考虑子串的开始位置。因为这个问题已经在上一层的match函数中处理过了。

matchhere是典型的递归函数，也是本例的亮点核心。该函数每次处理一组正则单元。假设正则表达式为ab*c.*$，那它的处理顺序为：

1. a
2. b*
3. c
4. .*
5. $

注意，因为已经在match函数做了分流，所以matchhere不需要处理有^的情况。

matchhere每次只处理一组正则单元。如果匹配失败，则直接返回0，可个递归过程结束。

如果所有正则单元都能匹配成功，那么最后regexp一定会指向正则字符串的结尾，也就是 \0字符，所以此时应该返回1并结束递归。这里用了一个if来实现：

if (regexp[0] == '\0')
    return 1;

如果没到结尾，则有三种情况需要处理。先处理两种特殊情形。

第一种就是正则中包含$结尾，表示对应的模式必须出现在输入内容的结尾。也就是说，当程序扫描到最后$模式时，前面的都已匹配，最后只需检查text还有没有后续内容。如果有，则说明该匹配位置不在结尾，应该返回0并退出循环。所以对应的代码为：

if (regexp[0] == '$' && regexp[1] == '\0')
  return *text == '\0';

因为 c 语言中字符串最后一定有\0字符。前面的判断已经排除regexp[0]为\0的情况，所以这里可以安全地比较regexp[0] == '$'，后面的联合条件regexp[1] == '\0'确保只处理$在最后出现的情形。这个时候如果是出现在输入字符串的最后，则必然有 *text == '\0'。但无论是否匹配，都要结束当前递归。

另一种特殊情况是正则中出现*，这需要单独处理，我们放到最后讲。

if (regexp[1] == '*')
  return matchstar(regexp[0], regexp+2, text);

那第三种情况就是普通情形下的递归匹配了。这里需要检查text还有内容而且该字符与正则中的字符相同或者正则中的字符是.从而可以匹配任意字符。如果当前字符匹配成功，则把两个指针各向前移动一个位置，执行递归匹配逻辑。总得来说，regexp和text都在不断向各自的字符串结尾移动，最终都会指向\0，所以递归一定能结束。

if (*text!='\0' && (regexp[0]=='.' || regexp[0]==*text))
  return matchhere(regexp+1, text+1);

最后说一下matchstar函数。它的调用代码为：

if (regexp[1] == '*')
  return matchstar(regexp[0], regexp+2, text);

如果碰到正则中的*，则需要找到它前面的字符regexp[0]，然后单独调用matchstar 检查是否匹配。如果匹配成功，则需要从*后面的正则继续递归匹配。所以这里的第二个参数是regexp+2就是为了跳过*和它前面的字符。我们再看matchstar的代码：

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

这里用了do-while循环，上来就先做一次matchhere匹配，这是因为*表示前面的字符可以不用出现。如果匹配失败，则需要检查当前text指向的内容是否跟当前的正则单元匹配，每次匹配都递归调用matchhere检查后续模式是否匹配，并且不断移动text指针。所以matchhere一旦进入matchstar就不会返回，直到完成所有的检查。

以上就是 Rob 全部的代码。用 Brain 的话说⁴该实现紧凑、优雅、高效，而且有用。这是展示递归和指针魅力的最佳示例。我深以为然！

当然了，Rob 的实现显然不完美。比如他实现的*匹配是一种非贪心匹配。有时候我们需要贪以匹配，也就是尽可能匹配更长的内容，可以改为如下代码：

int matchstar(int c, char *regexp, char *text)
{
  char *t;

  for (t = text; *t != '\0' && (*t == c || c == '.'); t++)
    ;
  do {  /* * matches zero or more */
    if (matchhere(regexp, t))
      return 1;
  } while (t-- > text);
  return 0;
}

这里的for循环先把当前指针移动到匹配到当前正则单元的最右边的字符上，然后再向左依次检查是否匹配子模式。由此实现了贪心匹配算法。

如果你只想领略一下大师的优雅代码，那读到这里也就可以结束了。但如果你是初学者，那建议做如下练习。

第一个练习是实现+、?语法。这种比较简单，参与matchstar微调一下就能实现。

第二个练习是实现\.语法，这个就比较复杂了，因为 Rob 使用普通的 char [] 保存正则，而且把 . 当成特殊字符，处理起来就很麻烦了。如果想实现类似 [abc] 或者 [0-9] 这类的语法，更是需使用新的数据结构。原文给出一种可能的数据结构，供读者参考：

typedef struct RE {
  int     type;   /* CHAR, STAR, etc. */
  char    ch;     /* the character itself */
  char    *ccl;   /* for [...] instead */
  int     nccl;   /* true if class is negated [^...] */
} RE;

这个例子还给我另外一种启发，那就是 c 语言的指针确实很强大，而且很高效。我也看过 Ben 实现的 Go 语言版本⁵。因为 Go 语言不能实现类似*text++这样的操作，他只能用string来模拟。而string每次传参都需要复制，这会产生额外的内存消耗。

最后附上主函数代码，方便大家测试使用：

#include <stdio.h>
#include <string.h>

int match(char *regexp, char *text);
int matchhere(char *regexp, char *text);
int matchstar(int c, char *regexp, char *text);

int main(int argc, char *argv[]) {
	if (argc < 3) {
		fprintf(stderr, "Error: argument\n");
		return 1;
	}

	FILE *file;
	char buffer[1024*1024];
	file = fopen(argv[2], "r");
	if (file == NULL) {
		perror("Error opening file");
		return -1;
	}

	while (fgets(buffer, sizeof(buffer), file)) {
		buffer[strlen(buffer)-1] = '\0';
		if (match(argv[1], buffer)) {
			printf("%s\n", buffer);
		}
	}

	fclose(file);
	return 0;
}