正则表达式匹配可以更快更简单 (but is slow in Java, Perl, PHP, Python, Ruby, ...) (2)

单字符正则表达式对应的NFA：

表示连接关系的NFA：

表示合并关系的NFA：

e?对应的NFA：

e*对应的NFA：

e+对应的NFA：

细数上面的对应关系可以发现，我们需要为每个操作符都新建一个NFA，其中不包括括号操作符，因此一个完整的NFA包含的状态数至多与原正则表达式的长度相等。
你可以在这些局部的NFA中发现许多无符号的箭头，正如我们上一节末尾所说的，为NFA设置一些无符号的箭头是合理的（我们的算法就是这样干的），同时这些无符号的箭头会帮助我们阅读和理解，并且让我们的C语言代码更简洁。

正则表达式搜索算法 现在我们有了匹配正则表达式的方法：首先将正则表达式转化为NFA，然后将待匹配字符串作为输入，运行NFA，查看结果。在面对多种状态转移的选择时，我们需要NFA有做出正确选择的能力，因此我们必须寻找一种可靠的方式来模拟NFA的猜测过程。

一种方式就是：尝试其中一个选项，如果这条路走不通，那就选择另一条路。例如，考虑abab|abbb的NFA在匹配字符串abbb的过程：

在step 0中，我们必须选择往上走还是往下走，往上走匹配abab，往下走匹配abbb。在图中，NFA尝试往上走，结果在step 3失败了，于是便回溯到了step 0，尝试往下走，从step 4到step 8完成了匹配。这种回溯的方式可以通过简单的递归实现。但是，我们容易发现，当一个不匹配的字符串输入时，自动机将会尝试所有的可能。在这个例子中，NFA仅仅尝试了两条路，但是在更糟糕的情况中，自动机将会做出大量的尝试，这就导致了自动机变得异常缓慢。
另一个更高效但更复杂的方式就是同步地进行尝试。这种方式允许自动机一次可以进入多种状态，当读入一个字符时，自动机会同时转移到所有可能的状态。

如图所示，在匹配字符串的过程中，自动机会同时尝试两条路径，在step 3时，仅剩下一条亦然匹配成功的路径。这种多状态并存的方式可以在同一时间尝试两种可能，也仅仅读取输入的字符串一次。即使在最坏的情况下，NFA也许会同时尝试所有状态，但是这也仅仅花费O(1)的时间，因此任意长的字符串也能在O(N)的时间内解决。这种方式把回溯花费的指数时间降为线性时间，是一种巨大的提升。效率的提升在于，这种方式尝试的是所有可能的状态，而不是所有可能的路径。在一个有N个结点的自动机里，每一步最多有N个转移状态，但是却有2^n条路。

实现 Thompson在1968年的论文里介绍了这种多状态并存的方式，在他的实现方案中，NFA的状态被表示为一组机器码序列，下一步可能的转移状态被表示为一组函数调用。实质上，Thompson是将正则表达式编写为一组聪明的机器码。四十年之后，计算机已经变得非常快了，他那种机器码的方式已经不在需要了。在接下来的章节中，我们会看到一个不到400行的C语言版本的代码。[source code]() 实现NFA 第一步就是将正则表达式转化为等价NFA。在代码中，状态的数据结构如下： struct State { int c; State *out; State *out1; int lastlist; }; 状态有三种表示，具体依赖与c的值：