正则表达式实现（三）

去年花了两三个星期的业余时间实现了基于DFA的正则引擎（一 二），时间一晃就过去一年，工作繁忙，兴趣面广，前途未卜什么的耗费太多精力，最近两三个月抽了点时间写了基于NFA的正则引擎，代码放在Github。

正则引擎常见的实现方法

正则的常见实现方式有三种：DFA、Backtracking、NFA：

• DFA是三种实现中效率最高的，不过缺点也明显，一是DFA的构造复杂耗时，二是DFA支持的正则语法有限。在早期正则被发明出来时，只有Concatenation、Alternation、Kleene star，即ab a|b a*，DFA可以轻松搞定。随着计算机的发展，正则像所有其它语言一样发展出各种新的语法，很多语法在DFA中难以实现，比如capture、backreference（capture倒是有论文描述可以在DFA中实现）。

• Backtracking是三种实现中效率最低的，功能确是最强的，它可以实现所有后面新加的语法，因此，大多数正则引擎实现都采用此方法。因为它是回溯的，所以在某些情况下会出现指数复杂度，这篇文章有详细的描述。

• NFA(Thompson NFA)有相对DFA来说的构造简单，并兼有接近DFA的效率，并且在面对Backtracking出现指数复杂度时的正则表达式保持良好的性能。

NFA-based的实现

这里描述的NFA是指Thompson NFA。Thompson NFA实现的核心是对于正则表达式多个可能的匹配并发的向前匹配，此过程是在模拟DFA运行。比如对于正则表达式abab|abbb匹配字符串abbb：

• Backtracking的匹配过程是取正则的第一个子表达式abab匹配，前两个字符匹配成功，匹配第三个字符的时候失败，这时引擎回溯选择第二个子表达式abbb匹配，最终匹配成功。

• Thompson NFA是同时取两个子表达式abab和abbb匹配，前两个字符匹配时，两个子表达式都能匹配成功，当匹配第三个字符时，子表达式abab匹配失败，因此丢弃，abbb匹配成功接着匹配，最终匹配成功。

上面是一个简单的例子，没有出现* + {m,n}这种复杂的metacharacters，在处理这种repeat的metacharacter时Thompson NFA优势更加明显。

在实际复杂的正则表达式中，NFA构造是必然会产生一堆epsilon边，这在第二篇文章中有描述。上面描述Thompson NFA实际是在模拟DFA运行，在每个字符匹配完成之后需要跳过epsilon边得到后面要匹配的并发的状态集合，这样持续的并发匹配下去，当字符串匹配完成时只要有一个达到了接受状态，就是匹配成功，若这个集合为空，那表示匹配失败。

在我的实现中，构造了一组状态和由这组状态加epsilon边集合构造的有向图，每个状态有自己的状态类型，分为两种：

• 一种是匹配状态类型，即用来匹配字符的状态，若字符匹配成功，则进入下一个状态；

• 一种是操作状态类型，即不匹配字符的状态，在每个字符匹配结束之后若到达这些状态，则会进行相应的操作，比如repeat状态，记录匹配计数，并判断匹配计数是否完成再决定是否进入的下面的状态。

repeat是一种会分化的状态，达到最小匹配次数时，可以接着往下走，也可以继续重复匹配repeat的子正则表达式，这样就分化成两条线了，并且每条线都带有自己的状态数据，因此，我的实现中引入的thread来表示一条匹配线，里面有状态数据。

Match和Search

状态构造完成了之后，就要开始匹配了。匹配有两种，一种是match，即一个正则表达式能否完整匹配一个字符串，若完整匹配则匹配成功；另一种是search，要在一个字符串中或者一块buffer中查找每个满足的匹配。这里就有个问题，从第一个字符开始匹配，匹配了几个字符之后发现匹配失败了怎么办呢？回退到第二个字符重新匹配？我们知道对于普通的字符串查找，有KMP算法可以保证不回退字符（其实KMP算法的预处理就是构造DFA），或者有Boyer-Moore算法尽量回退少的字符个数。对于正则这种复杂的匹配该怎么办呢？从上面的Thompson NFA的描述可以知道匹配过程是多条线并发匹配，因此可以构造一个始终产生一条新线的状态，若匹配在前面的线失败被丢弃之后，后面的新线始终可以补上，这样查找的过程就不再需要回退字符了。

我的实现中，状态构造完成后是这样的：

// |-----|--------|---------------|-----|-------------|
// | any | repeat | capture begin | ... | capture end |
// |-----|--------|---------------|-----|-------------|

用repeat-any来产生新的匹配线。若在match模式下，则从第三个状态开始匹配，不会产生新的匹配线，一旦匹配过程失败了就失败了。

结语

正则表达式语法一直在扩展，新的语法有些很难在DFA和NFA中实现，而在Backtracking中的实现又是以牺牲性能为代价。因此有些正则表达式实现会结合多种实现方式，判断正则表达式的类型选择不同的引擎，比如普通字符串加上一些简单的正则语法采用DFA引擎匹配，或者只有普通字符串的匹配可以用Boyer-Moore算法，毕竟Boyer-Moore算法在普通文本查找中要优于KMP算法：），对于复杂的正则表达式采用Backtracking，甚至有些正则引擎使用JIT来加速。