正则表达式(5)

主题

正则表达式(5)

DFA/NFA

为何会有 REDoS，就是因为绝大部分正则表达式的实现，都是基于 NFA。

什么是 NFA

非确定有限状态自动机(Non-deterministic Finite Automaton,NFA).

对于同一输入转移到多个不同的状态或者存在空字符串 ε 的状态转移的 FA.

什么是 DFA

确定性有限状态自动机(Deterministic Finite Automaton,DFA).

对于任何确定的输入都只有唯一确定的转移且不存在空字符串 ε 的状态转移的 FA.

图解

对于正则表达式：(a|b)*abb来说，NFA 和 DFA的示意图如下：

NFA

DFA

编译速度：
通过上述的 NFA 和 DFA 的原理我们可以看到，NFA 的状态数与正则表达式的长度有关系，而 DFA 的状态数最大可能是 NFA 状态数的排列组合之和。因此 DFA 编译起来要比 NFA 复杂的多。

匹配速度：
在输入一个字符之后，NFA 可能到达的状态不一样，这时候需要进行选择，加入刚开始选择的分支最终无法匹配，那么我们需要重新回退到这个选择，选择另一个分支进行匹配。这就产生了回溯。而 DFA 到达的状态是确定的，因此只需要匹配一遍字符串就可以得到结果。虽然 DFA 有编译上的损耗，但是通常情况下回溯的损耗比较大，因此匹配上速度上 DFA 胜。

最终两者的比较如下表：

比较	编译速度	匹配速度	匹配结果	匹配速度与正则相关性	能力
DFA	慢	快	最左最长	无	部分不支持
NFA	快	慢	依赖NFA实现	有	全面