Regular Expression Matching Can Be Simple and Fast

作者 Russ Cox 为 Google Code Search 编写了 RE2。

正则表达式运算符的优先级从高到低：

repetition operators:   *+?
concatenation operator: Thompson 用“ .” 表示，现在则直接连写。
alternation operator:   |

理论上讲，带有向后引用的正则表达式不是正则表达式。

向后引用在最坏情况下性能很糟糕，需要做指数级别的搜索。

正则表达式与 NFA (非确定性有穷自动机)等价。

有很多方式将正则表达式转换成 NFA，其中一种是 Thompson 在他的 1968 年 CACM 论文上描述的。

利用 NFA 匹配的两种做法： (1)回溯 (Perl, Python, Ruby, Java, PCRE) 由于 NFA 从一个状态可以转到多个状态，因此很自然可以用回溯，在不匹配时回到当初那个分叉点寻找下一个路径，但这样就要反复读取输入串。这种情况下状态机永远只处于一种状态下。

(2)多状态 (by Thompson) (ed, sed, grep, awk, lex, tcl: DFA) 另一个办法是从输入串中读取一个字符时，同时走所有可能的路径，这样状态机可以同时处于多个状态下，而且每个输入字符只读一次。这种做法最糟糕情况下，状态机每次都处于所有状态上，但由于状态机的总状态数只取决于正则表达式，而跟输入串没关系，因此其复杂度是一个常数，在处理长输入串时可以在线性时间内完成，而回溯法最差情况需要指数时间。

(2) 的做法是纪录可达的状态， (1)是纪录达到目前状态的路径，对于一个有 n 个节点的 NFA，前者最多 n 个可达状态，而后者有 2^n 个路径。

回溯法需要编写者注意正则表达式的编写，比如在多个 | 分隔时将出现频率高的模式放在前面，不要用 (.*) (.*) (.*) (.*) (.*) 这样的模式匹配五个空格分隔的域。而多状态法不需要担心这些。

由于 DFA 从一个状态只能跳到另一个状态，因此 DFA 比 NFA效率更高。任何 NFA 都能转换到一个 DFA，前者的多个状态对应到后者的一个状态。Thompson 的多状态法其实是构造了一个对应的 DFA，且 DFA 中的状态是按需创建的。

多状态法不支持反向引用(backreference)，并且实现复杂点，但平均性能很好，回溯法实现比较简单，但某些情况下性能非常差。

基于 DFA：RE2, TRE(支持模糊匹配), PCRE-DFA
基于 NFA：oniguruma / onigmo(Ruby 2.0 开始采用)，PCRE，绝大多数语言的正则表达式实现
DFA+NFA: Hyperscan
性能：hyperscan > PCRE-JIT ~ RE2 > onig > TRE > PCRE > PCRE-DFA

参考：