前言

该博客记录的是COS333的assignment1，该任务是要我改写TPOP(The practive of programming)中第9章第2节的处理正则表达式的代码，以符合新的匹配规则：glob)。
根据维基百科来看，glob最早是应用于unix上的一个命令，取自global的缩写，最主要的作用就是通过通配符(wildcard)拓展文件名列表。
当然，要我们实现的好像并不是完整的glob，而是一部分子集规则：

  • ?: 任意单个字符
  • *: 任意0个或多个字符
  • \: 对特殊字符进行转义，转义符后没有字符算语法错误
  • $和^并不是特殊字符
  • 匹配的范围是整个输入字符串，可以认为是正则表达式的^input$

思路

根据原有代码的提示不难得出它解析正则表达式的思路是递归解析。
至于为什么采用递归而不是迭代是因为通过分析递归的roadmap发现它们存在相互调用且是根据条件切换的。
更好的方法应该是构造NFA来解析，但是在glob表达式不长的情况下，递归是足够满足性能需求的。
比较麻烦处理的是转义规则的处理，这里我是通过一个变量记录了是否遇见了转义符，其实如果有记录长度的变量会更好办，但是为了这么一个目通过O(n)算法得到长度可能也不是很恰当，所以作罢。
至于*，假设当前指针为globp，那么只需要依次比较(globp+1, text)~(glop+1, text+n)的匹配结果即可，匹配成功了直接返回，全部失败表示匹配失败。
而?只需要将第一个字符过滤了，其余和*的处理方式相同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <string.h>
#include <stdbool.h>
#include <stdio.h>

static int matchhere(char *regexp, char *text);
static bool quoted_occur = false;

#define HANDLE_MATCH_HERE_RETURN(regexp, text) do {\
  int res = matchhere(regexp, text); \
  if (res == 0) continue; \
  return res; \
} while (0)

static int match_star(char *regexp, char *text) {
  quoted_occur = false;
  do {
    HANDLE_MATCH_HERE_RETURN(regexp, text);
  } while (*text++ != '\0');
  return 0;
}

static int match_question(char *regexp, char *text) {
  return match_star(regexp, text);
}

/* matchhere: search for regexp at beginning of text */
int matchhere(char *regexp, char *text) {
  if (regexp[0] == '\0')
    return text[0] == '\0';
  if (regexp[0] == '\\') {
    // The first backslash
    if (!quoted_occur) {
      if (regexp[1] == '\0') return -1;
      quoted_occur = true;
      return matchhere(regexp+1, text);
    }
  }

  if (regexp[0] == '*' && !quoted_occur)
    return match_star(regexp+1, text);
  if (regexp[0] == '?' && text[0] != '\0' && !quoted_occur)
    return match_question(regexp+1, text+1);
  quoted_occur = false;
  if (*text!='\0' && (regexp[0]==*text))
    return matchhere(regexp+1, text+1);

  return 0;
}

/* match: search for regexp anywhere in text */
int match(char *regexp, char *text)
{
  int res = matchhere(regexp, text);
  quoted_occur = false; 
  return res;
}

注意：代码可能存在bug，因为测试用例并不是很多（见下）

Test

测试是通过将存放在文件中的测试用例通过shell工具切割成命令行实参传递给测试进程来完成的。
测试用例是记录在文件中，通过分割符分割每个字段，其中混有空行。既然涉及分割字段，那么用到awk是很典型的运用（彩蛋：kernighan就是awk的创造人之一）。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
\@\@-1@illegal REE
\\\@\\\@-1@illegal RE

x@x@1@easy ones
x@y@0
x@@0
x@xx@0
x@xy@0

\x@x@1@quotes
\*@*@1
\*@x@0
\\@\@1
\\@\\@0
x?y@xxy@1@? tests
x?y@xy@0
x??y@xxyy@1
x**y@xy@1@* tests
x**y@x***y@1
x**y@xyz@0
x***@y***@0

COS333想让通过将每个字段对应一个命令行实参进行测试。所以程序很简单：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/* test.c */
#include <string.h>
#include <stdio.h>
#include <stdlib.h>

extern int match(char *, char *);

int main(int argc, char *argv[])
{
  char *re = argv[1];
  char *str = argv[2];
  int expect = atoi(argv[3]);
  int result = match(re, str);
  if (result != expect) {
    printf("error %s %s %d %d\n", re, str, expect, result);
  }
}

然后通过如下的测试脚本进行测试：

1
2
3
4
5
6
7
8
9
10
#!/bin/bash
gcc -g -o regexp test.c regexp.c

awk 'BEGIN {
  FS="@"
}
{
  if (length($0) > 0)
    print $1" "$2" "$3
}' retests.txt | tr '\n' ' ' | xargs -d ' ' -n 3 ./regexp