使用递归实现正则匹配

2023-06-27 ⏳6.1分钟(2.4千字) g

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

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

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

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

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

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

正则表达式是一类特殊的字符匹配语法3,是 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 代码实现了简化版的正则匹配程序。他支持如下正则语法子集:

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 的话说4该实现紧凑、优雅、高效,而且有用。这是展示递归和指针魅力的最佳示例。我深以为然!

当然了,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 语言版本5。因为 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;
}