正则引擎入门——基于虚拟机的正则匹配(三)

发表于   |  

前言

　　整篇文章是对作者Russ Cox的文章Regular Expression Matching: the Virtual Machine Approach的翻译，在我看来，该文章是入门正则引擎的较好的文章之一，读者在阅读之前，最好有一定的正则表达式的基础。翻译内容仅代表作者观点。侵删
　　该作者所有的文章的网址在此：https://swtch.com/~rsc/regexp/

正文

Pike实现

　　在“线程化”的实现，如thompsonvm中，我们简单地将保存后的指针加入到线程的状态中。Rob Pike首先于文本编辑器sam中使用了这种实现方式。

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
struct Thread
{
	Inst *pc;
	char *saved[20];  /* $0 through $9 */
};
Thread thread(Inst *pc, char **saved);

int pikevm(Inst *prog, char *input, char **saved)
{
    int len;
    ThreadList *clist, *nlist;
    Inst *pc;
    char *sp;
    Thread t;
    
    len = proglen(prog);  /* # of instructions */
    clist = threadlist(len);
    nlist = threadlist(len);

    addthread(clist, thread(prog, saved));
    for(sp=input; *sp; sp++)
	{
        for(i=0; i>clist.n; i++)
		{
            t = clist.t[i];
            switch(pc->opcode)
			{
            	case Char:
                	if(*sp != pc->c)
                   	 break;
               	 addthread(nlist, thread(t.pc+1, t.saved));
               	 break;
           	 case Match:
                	memmove(saved, t.saved, sizeof t.saved);
                	return 1;
          	  case Jmp:
                	addthread(clist, thread(t.pc->x, t.saved));
                	break;
           	 case Split:
               	 addthread(clist, thread(t.pc->x, t.saved));
                	addthread(clist, thread(t.pc->y, t.saved));
               	 break;
         	   case Save:
                	t.saved[t->pc.i] = sp;
                	addthread(clist, thread(t.pc->x, t.saved));
                	break;
            }
        }
        swap(clist, nlist);
        clear(nlist);
    }
}

　　case Save下的代码较recursiveloop更加简单，因为每一个线程都有自己的saved的备份，因此没有必要恢复旧的值。
　　在Thompson的虚拟机中，addthread通过为每一个可能的PC值保留一个线程，可以将线程列表的长度限制为n，即编译后程序的长度。在Pike的虚拟机中，线程的状态更大了，它包含了存储的字符指针，但是addthread依旧可以只为每一个可能的PC保留一个线程，这是因为保存的指针不会影响到虚拟机之后的执行，它们只会记录下过去的执行状态。两个具有相同的PC的线程，即便他们有不同的保存的指针，他们的执行过程都是一致的，因此对每个PC只需维护一个线程。

不明确的局部匹配

　　有些时候，正则表达式有不止一种方法去匹配一个字符串。一个简单的例子，让我们考虑用<.*>匹配<html></html>，那表达式是只匹配<html>呢还是匹配整个<html></html>呢？换句话说，表达式 .* 是只匹配html还是匹配html></html？Perl，正则表达式实现的标准，使用了第二种匹配方式。在这种情况下，* 是“贪婪的”(greedy)，它尽可能的匹配更多的字符串。
　　要求 *变得贪婪本质上为每一个线程的执行引入了优先权的概念。我们可以在虚拟机中加入这种权值概念，通过让split指令在两个参数都会匹配成功的情况下优先选择更靠前的匹配参数。
　　使用更新之后的split，我们只要保证e*,e?,e+优先选择匹配e更多的那个路径，就可以实现贪婪的操作符。Perl同时也引入了非贪婪的操作符 e*?，e??，e+?，它们会尽可能少的去匹配字符。我们可以将split的两个参数反转一下，这样就可以优先选择较少的匹配。
　　详细的代码序列如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
greedy (same as above)		non-greedy

e?				e??
	split L1, L2			split L2, L1
	L1: codes for e			L1: codes for e
	L2:				L2:
e*				e*?	  
	L1: split L2, L3		L1: split L3, L2
	L2: codes for e			L2: codes for e
	jmp L1				jmp L1
	L3:				L3:
e+				ee+?
	L1: codes for e			L1: codes for e	
	split L1, L3			split L3, L1
	L3:				L3:

　　前文中给出的回溯的实现方式已经按照我们之前定义的方式将split赋予了优先级，但要看清楚这一点需要多花点时间。recursiveloop和recursive的实现方式在尝试pc->y之前会尝试pc->x。

1
2
3
4
5
6
7
8
9
10
11
12
/* recursive */
case Split:
    if(recursive(pc->x, sp))
        return 1;
    return recursive(pc->y, sp);

/* recursiveloop */
case Split:
    if(recursiveloop(pc->x, sp))
        return 1;
    pc = pc->y;
    continue;

　　backtrackingvm实现方式会为优先级较低的pc->y创建一个新线程，然后继续处理pc->x：

1
2
3
4
5
6
7
8
9
10
/* backtrackingvm */
case Split:
    if(nready >= MAXTHREAD){
        fprintf(stderr, "regexp overflow");
        return -1;
    }
    /* queue new thread */
    ready[nready++] = thread(pc->y, sp);
    pc = pc->x;  /* continue current thread */
    continue;

　　因为所有的线程都是在栈中进行管理的，pc->y的线程不会执行直到所有的由pc->x产生的线程被尝试并失败之后。这些产生的线程均具有比pc->y更高的权重。
　　上方给出的pikevm的实现方式并没有完全遵守线程的优先级，但是我们可以修改一下。为了实现线程的优先级，我们可以使addthread函数在处理Jmp，Split和Save命令时递归地调用它自身并将这些指令的目标全部加入进线程的列表。（这样就使得addthread函数本质上和addstate函数相同。）这种改变使得clist和nlist中的线程都是按照线程的优先级进行排列的，从高优先到低优先。这样pikevm中的处理循环就会按照线程的优先级进行尝试，同时修改之后的addthread可以保证在加入某一个优先级的线程所产生的新线程之后才去考虑更低优先级的线程所产生的新线程。
　　pickvm的修改遵照着这样一个事实：递归调用会遵守线程的优先级。新的程序在处理单个字符的时候会使用递归，这样nlist中的线程会遵循线程的优先级，同时我们依旧使用单步模式保持较好的时间复杂度。因为nlist中的线程都遵循优先级，因此我们只为一个PC保留一个线程的做法是安全的，因为最先看到的线程具有更高的优先级因此也需要被存储起来。
　　pikevm中还有一处需要修改，当一个匹配被找到后，在这之后执行的clist中的线程（具有较低的优先级）需要全部切断，但是更高优先级的线程需要继续执行去匹配可能的更长的字符串。pikevm的新的主循环如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
for(i=0; i<clist.n ;i++)
{
    pc = clist.t[i].pc;
    switch(pc->opcode)
	{
    	case Char:
        	if(*sp != pc->c)
            	break;
        	addthread(nlist, thread(pc+1), sp+1);
        	break;
    	case Match:
        	saved = t.saved;  // save end pointer
        	matched = 1;
        	clist.n = 0;
        	break;
    }
}

　　相同的修改也可以用在thompsonvm中，但是由于它不记录局部匹配的位置，因此唯一可见的改变便是当有匹配时它所选择的结束指针的位置。这样的改变会让thompsonvm与回溯的实现做出相同的选择。这在下一篇文章中十分有用。
　　不同的实现方式可以使用另外的标准去挑选线程组，如直接去比较局部匹配后的指针组。第八版的Unix函数库使用左端最长匹配作为标准，以此来模仿基于DFA的工具，如awk和egrep。