摘要：让我来告诉你所谓 DFA 和 NFA 的区别，听好：「DFA 引擎」就是严格按照类似龙书里的方法构建的正则表达式引擎，此时正则表达式会惨遭肢解变成一大堆的状态（所谓米利机），正则表达式的原有结构不会被保留到 DFA 里，它能做的惟一事情就是在正则表达式匹配字符串的时候返回「匹配」，因此无法实现分组捕获。而且 DFA 的能力是被严格限制的，所以无法匹配任何超出正则语言范围的语言——很不幸，使用了反向
让我来告诉你所谓 DFA 和 NFA 的区别，听好：
「DFA 引擎」就是严格按照类似龙书里的方法构建的正则表达式引擎，此时正则表达式会惨遭肢解变成一大堆的状态（所谓米利机），正则表达式的原有结构不会被保留到 DFA 里，它能做的惟一事情就是在正则表达式匹配字符串的时候返回「匹配」，因此无法实现分组捕获。而且 DFA 的能力是被严格限制的，所以无法匹配任何超出正则语言范围的语言——很不幸，使用了反向引用的「正则」表达式并不属于正则语言，它们实际上是上下文相关语言。
而「NFA」的实现就有趣多了。现代「正则」引擎里 NFA 实际上是一个特化的递归下降分析器，这个分析器允许使用回溯（和 LL(*) 这种依赖「向前看」的分析器并不相同），同时分析器的内部结构保留了原有正则表达式的结构特点，因此它很容易扩展来匹配非正则语言，也很容易扩展来记录匹配时的内部状态——这两点使得 NFA 类匹配器得以实现捕获处理以及反向引用。
而题主提及的「非贪婪星号」是个很有趣的概念。表达式 的真正含义是 ，这个集合很可能也不是正则的（没找到论文证明），不过即使它是正则集合，构造出它的 DFA 也是很困难的事情，而对于 NFA，想实现它，改下处理星号时回溯的顺序就行了。
