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

发表于   |  

前言

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

正文

介绍

　　说出几个如今被广泛应用的字节码解释器或者虚拟机：Sun公司的JVM？Adobe公司的Flash？.NET或者Mono？Perl？Python？PHP？这些的确都很流行，但是还有一个比上述这些加起来都还要广泛使用的，那便是Henry Spencer的正则表达式库的字节码解释器以及它的众多衍生。
　　该系列的第一篇文章介绍了实现正则匹配的两种主要的方法：一个是在awk和egrep中使用的，最坏情况为线性时间复杂度的基于NFA或DFA的策略，另一个是广泛使用的，包括sed，Perl，PCRE和Python，最坏情况为指数级时间复杂度的基于回溯的策略。
　　这篇文章介绍两种实现虚拟机的方法，该虚拟机执行已经被编译成为字节码的正则表达式，正如.NET和Mono是两种不同的方法去实现执行已经被编译成为CLI字节码的程序的虚拟机一样。
　　将正则表达式的匹配过程看作是虚拟机的执行使得我们可以仅仅通过加入（并实现）新的机器指令来加入新的特性。特别的，我们可以加入局部匹配（Submatching）的指令，当我们使用(a+)(b+)匹配abbbb之后，程序可以知道括号表达式(a+)（通常用\1或$1引用）与aa匹配，而(b+)与bbbb匹配。局部匹配可以既可通过回溯的虚拟机亦可通过非回溯的虚拟机实现。

正则表达式的虚拟机

　　在开始之前，我们需要定义一个正则表达式的虚拟机（回想一下Java VM）。虚拟机执行一个或多个线程，每一个都会运行一个正则表达式的程序，该程序仅仅由一系列的正则表达式指令组成。每一个线程在运行的时候都会维护两个寄存器：一个程序计数器（PC）和一个字符串指针（SP）。
　　正则表达式指令如下：
　　char c：如果SP指向的不是字符c，终止这个线程：匹配失败了。否则SP移到下一个字符，PC移到下一条指令。
　　match：终止该线程：它匹配成功了。
　　jmp：调到位于x处的指令。（即将PC指向该指令）
　　split：分列操作：从x和y处继续。创建一个SP和原线程相同的新线程。一个从PC为x处继续执行，另一个从y处继续执行。
　　虚拟机在运行初期只会有一个线程，该线程的PC指向程序的开始处，而它的SP则指向输入字符串的开始处。为了运行线程，虚拟机会执行PC所指向的那一条指令；执行完当前的这条指令之后PC会被改变为指向下一条指令。这样不断重复直到一条指令（匹配失败或成功）终止该线程。如果有任意一个线程到达匹配状态，那正则表达式就匹配成功。
　　将正则表达式编译成为递归执行的字节码取决于正则表达式的形式。回忆一下前一篇文章，正则表达式有四种基本的形式：单一的字符，如a，串联如e1e2，并联如e1|e2，或者重复，例如e?，e*，e+。
　　单字符a被编译为一条指令char a。串联的形式会将两个子正则表达式的指令放到一起。并联符会编译成为split，这样允许两个选择均可以匹配成功。一个零一重复e？使用split构成了一个与空字符串的并联关系。零个或多个重复e*以及一个多个重复e+使用split来选择是匹配e还是跳出重复。
　　具体的代码如下：

achar a
e1e2codes for e1
codes for e2
e1|e2 split L1, L2
L1:codes for e1
jmp L3
L2:codes for e2
L3:
e?split L1, L2
L1:codes for e
L2:
e*L1: split L2, L3
L2:codes for e
jmp L1
L3:
e+L1:codes for e
split L1, L3
L3:

　　当整个正则表达式被编译完毕，整个代码的最后会被加上一句match指令。
　　例如，正则表达式a+b+会被编译成如下指令：
1
2
3
4
5
char a
split 0,2
char b
split 2,4
match

　　当匹配字符串abb时，虚拟机会按如下的步骤运行：

Thread PC SP Execution
T1 char a aab 匹配到字符
T1 split 1,3 aab 创建线程T2，PC=3 SP=a
T1 char a aab 匹配到字符
T1 split 1,3 aab 创建线程T3，PC=3 SP=b
T1 char a aab 匹配失败：T1终止
T2 char b aab 匹配失败：T2终止
T3 char b aab 匹配到字符
T3 split 3,5 abb_ 创建线程T4，PC=5 SP=字符末尾
T3 char b abb_ 匹配失败（字符串末尾）：T3终止
T4 match abb_ 匹配成功

　　在这个例子中，虚拟机等待当前的线程结束后才创建新的线程，并且现成的运行是遵循先后的顺序的（旧线程先运行）。但这并不是虚拟机的实现细则所要求的，线程的安排是取决于具体的实现方式。另外的实现方式可能会采用其他的方式运行线程甚至会让线程交替运行。

虚拟机接口的C实现

　　文章接下来的部分会考察一系列的虚拟机实现方式，并使用C代码进行说明。正则表达式的程序使用一系列的Inst结构体进行实现，在C中定义如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
enum 
{    /* Inst.opcode */
    Char,
    Match,
    Jmp,
    Split
};

struct Inst 
{
    int opcode;
    int c;
    Inst *x;
    Inst *y;
};

　　这种形式的字节码与我们上一篇文章的NFA图的表现形式极其相似。我们可以将字节码看作是将NFA图编码成为一系列的机器码，或者将NFA看作是字节码的控制流图。两种不同的视角都会将这两样不同的事物联系在一起。而这篇文章主要从编码为机器码的角度看待这两种事物。
　　任何的虚拟机的实现形式都会将程序和输入的字符串作为参数并返回一个标志着匹配成功与否的整数（0表示失败；1表示成功）。
int implementation(Inst *prog, char *input);

递归回溯实现

　　一个可能的最简单的实现方式并不直接的模拟线程。相反的，在它需要创建一个新的线程并运行的时候它会递归的调用它自身，利用了prog和input参数在调用时会在初始线程的pc和sp的基础上拷贝一份的原理。（即此时函数调用时的传参是值传递而不是引用传递）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int recursive(Inst *pc, char *sp)
{
    switch(pc->opcode)
    {
    	case Char:
        	if(*sp != pc->c)
            	return 0;
        	return recursive(pc+1, sp+1);
    	case Match:
        	return 1;
    	case Jmp:
        	return recursive(pc->x, sp);
    	case Split:
        	if(recursive(pc->x, sp))
            	return 1;
        	return recursive(pc->y, sp);
    }
    assert(0);
    return -1;  /* not reached */
}

　　上边的版本使用了非常多的递归，经常使用重递归的语言如Lisp，ML，Erlang的程序员应该不会感到不适。带大多数的C程序员会将return recursive(...);这种形式（尾递归）的语句重写成为一个返回到程序开头的跳转语句，因此上边的语句就被改成如下形式：

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
int recursiveloop(Inst *pc, char *sp)
{
    for(;;)
	{
        switch(pc->opcode)
	    {
        	case Char:
            	if(*sp != pc->c)
                	return 0;
            	pc++;
            	sp++;
           	 continue;
        	case Match:
            	return 1;
        	case Jmp:
            	pc = pc->x;
            	continue;
        	case Split:
            	if(recursiveloop(pc->x, sp))
                	return 1;
           	 pc = pc->y;
            	continue;
        }
        assert(0);
        return -1;  /* not reached */
    }
}

　　其中的递归均被改为了直接的循环。
　　注意到上边的这个版本依然需要一个递归，在case Split中我们会在尝试pc->y之前尝试pc->x。
　　Henry Spencer早期的库函数以及Java, Perl, PCRE, Python中的回溯实现以及ed，sed，grep的早期版本均是以上边的实现作为核心的。当只有少量的回溯时，这种实现方式运行得非常快，但是当有许多的可能性需要尝试的时候，花费的时间就相当可观了，正如我们在上一篇文章中所看到的那样。
　　而这种回溯的实现方式有一个工业级的实现常常不会有的缺点：(a*)*这样的正则表达式会在编译后的程序中造成死循环，而这个虚拟机无法检测到这种循环。要修复这个问题很简单，但由于我们关注的重点不是回溯，因此我们简单的忽略这个问题。