这学期的创新实践尝试自己写一个正则表达式引擎,采用Thompson NFA实现,在网上找到了一篇很棒的文章,于是把它编译(Adapted Translation)过来用作原理解析。

正则表达式

正则表达式是一种描述字符串集合的标准。当一个字符串在一个正则表达式描述的字符串集合当中时,我们认为该字符串匹配了该正则表达式。

最简单的正则表达式就是字符。除了特殊的元字符*+?()|之外,所有的字符匹配自身。为了匹配元字符,需要借助\来转义,例如\+匹配加号。

两个正则表达式可以被串联或者并联,组成新的正则表达式:如果e1匹配s并且e2匹配t,那么e1|e2匹配s或者t,e1e2匹配st。

元字符*,+,和?表示重复操作:e1*匹配任意个匹配e1的字符串;e1+匹配一个以上,而e1?匹配至多一个。

对于各种操作,有着优先级之分,优先级最高的是并联,然后是串联,最后是重复。括号可以用来改变优先级。例如ab|cd相当于(ab)|(cd)ab*相当于a(b*)

自动机

另一个描述一个字符串集合的方法是自动机。自动机也称状态机。下面的自动机对应正则表达式a(bb)+a

自动机总是处于一个状态之中,也就是图中的圈圈。在读入字符串的时候,它从一个状态进入另一个状态。自动机有两个特殊的状态:开始开始状态和匹配状态。开始状态始于一个但箭头,匹配状态止于一个双环。

自动机一次读入一个字符串,按照箭头转换状态。假设输入字符串abbbba。当字符串读入第一个字符a,此时的状态为s1。它耕者箭头a到达状态s1。重复过程,直到到达状态s4。

自动机结束于s4,这是一个匹配成功的状态,也就说匹配成功了,如果自动机结束于非匹配成功状态,那么匹配失败。如果在运行过程中,没有办法到达其他状态,那么自动机提前结束。

我们刚才考虑的是确定状态自动机,因为在每一个状态,可达的下一个状态至多只有一个。我也可以创建一个有多种选择的机器。以之前的自动机为例:

机器的状态是不确定的,因为当它读入ab到达s2,它对于下一个状态有多个选择:它可以回到s1或者到达s3。由于机器无法预料接下来的输入,它不知道该选择哪个状态。可以同时保存多种状态的也就是非确定状态自动机。

有时候,NFA的某一条边可能没有需要输入的字符,NFA可以无条件选择这样的边。

把正则表达式转换为NFA

正则表达式和NFA是等价的:每一个正则表达式都有一个等价的NFA,反之亦然。把NFA转换为正则表达式的方法有很多种。Thompson在他1968年的论文当中首次提出一种方法。

正则表达式的NFA由子表达式的NFA构成,每种操作符有不同的构造方法。子NFA没有匹配成功状态,但是有多个空箭头。构造过程会把这些箭头指向匹配成功的状态。

一个单个字符的NFA长这样:

串联:

并联:

e?对应的NFA:

e*对应的NFA:

e+对应的NFA:

我们通过上面的这些方法构造NFA,在大多数情况下,NFA的状态数与正则表达式的长度相近。

正则表达式搜索算法

现在我们有了匹配正则表达式的方法:把正则表达式转换为NFA,然后把字符串作为输入来运行NFA。现在来看一下模拟NFA运行的过程。 一种方法是先猜一个,要是不行,试试另外一个。例如,abab|abbb对应的自动机匹配字符串abbb

在第0步,NFA必须做出选择:尝试abab还是abbb?在图中,NFA尝试了abab,但是匹配失败。NFA需要尝试其他的选择,接着在第4步直到匹配成功。这种回溯可以由递归来实现。缺点是,如果字符串本来无法匹配,那么NFA需要在放弃之前尝试所有的可能。在最坏情况下,这个过程需要指数时间成本。

一种更加高效的方法就是尝试同时保持多个状态。

自动机从开始状态直接可达的状态开始。在第1步和第2步,自动机同时保持着两种状态。当自动机读入一个字符的时候,就可以同时探索两条不同的路径了。这是一个巨大的提升,避免了很多不必要的尝试。在一个节点数为n的NFA中,状态只有n个,但是可能的路径最多有2^n条。