我正在阅读有关NFA和DFA的阅读，似乎最受欢迎，最快的实现Regex Matcher的方法是从Regex创建NFA，将其转换为DFA，将DFA最小化，实现它，实现它用任何语言使用它。
dfa比NFA是一个更好的选择，因为它只有一个转换输入，而NFA可以有很多。因此，DFA只有一条遵循的途径，而nfa -许多。
但是，这是我不明白的地方。为什么我们必须跟踪NFA状态并回到慢慢我们的情况下，当遇到多个状态的输入并并行计算每个路径时，我们可以分为不同的线程吗？DFA不会更快吗？还是我错过了什么？
一般来说，DFA更快，但NFA更紧凑。NFA与正则表达式的大小成正比。（非正式的证明：正则表达式语法中的每个运算符节点只是在NFA图中添加了一个新节点。）因为DFA是由NFA状态集的子集形成的，因此在某些情况下可能很大。在最坏的情况下，DFA的正则表达式成倍大小。一个例子是 (a|b)(a|b)(a|b)(a|b)...(a|b)形式的表达式，其中有n (a|b)单元转化为大小为o（2 ** n）的DFA。它包含通过唯一状态的a和b组合的过渡。如果在模拟等效NFA拟合到缓存的数据结构的情况下，退化的DFA可能会超过CPU缓存的大小。
由于额外的步骤，DFA的成本更高。因此适用权衡：NFA模拟器是否会处理足够的数据来证明构建DFA的合理性。
NFA模拟完全可以完全避免触摸正则表达式的部分，而正则表达式根本不适用于输入。例如，假设一个正则具有R1 | R2的形式，其中R1非常简单且小，R2是一个巨大的复杂野兽。假设输入通常仅适用R1和R2（如某些不匹配的前缀，根本没有任何部分）。这会影响权衡：编译到DFA意味着所有内容都已编译，简单的R1部分和可怕的R2部分。
最后，实现不必严格是NFA或DFA。NFA模拟器可以缓存其计算的状态集。那些缓存的国家等同于DFA国家，并提供了与DFA的汇编相似的好处。您可以认为这是"为NFA的JIT"。缓存可以修剪成固定尺寸，并受到替换策略的影响，以便可以在较小的内存中处理完整DFA的表达式（如果数据显示出良好的参考位置，则可以在缓存中显示出良好的位置）。。