NFA在编译器设计中的意义

Question

在我研究编译器设计的时候，它告诉我，在设计像DFA或NFA这样的词法分析器时，我们需要“有限自动机”。因此，我想知道NFA是否只用于(正则表达式转换为NFA，然后转换为DFA)。实现NFA是可能的吗？或者NFA的使用是因为它比DFA更有效？

Answer 1

在实践中实现NFA意味着回溯，因为程序流不能同时处于多个不同的状态。(当然，有并行处理器，但很难将用户编写的正则表达式的不规则和混乱行为映射到矢量化单元设计的简单、有规则的数据流。)因此，对于判定一个纯粹的“这匹配吗？”问题是，将NFA进一步转换为DFA并运行它几乎总是更好。但是NFA仍然在实践中使用，因为DFAs不能做一些用户确实想做的事情，比如捕获表达式的子组。