abstract：讓我來告訴你所謂 DFA 和 NFA 的區(qū)別，聽好：「DFA 引擎」就是嚴(yán)格按照類似龍書里的方法構(gòu)建的正則表達(dá)式引擎，此時正則表達(dá)式會慘遭肢解變成一大堆的狀態(tài)（所謂米利機(jī)），正則表達(dá)式的原有結(jié)構(gòu)不會被保留到 DFA 里，它能做的惟一事情就是在正則表達(dá)式匹配字符串的時候返回「匹配」，因此無法實現(xiàn)分組捕獲。而且 DFA 的能力是被嚴(yán)格限制的，所以無法匹配任何超出正則語言范圍的語言——很不幸，使用了反向

讓我來告訴你所謂 DFA 和 NFA 的區(qū)別，聽好：

「DFA 引擎」就是嚴(yán)格按照類似龍書里的方法構(gòu)建的正則表達(dá)式引擎，此時正則表達(dá)式會慘遭肢解變成一大堆的狀態(tài)（所謂米利機(jī)），正則表達(dá)式的原有結(jié)構(gòu)不會被保留到 DFA 里，它能做的惟一事情就是在正則表達(dá)式匹配字符串的時候返回「匹配」，因此無法實現(xiàn)分組捕獲。而且 DFA 的能力是被嚴(yán)格限制的，所以無法匹配任何超出正則語言范圍的語言——很不幸，使用了反向引用的「正則」表達(dá)式并不屬于正則語言，它們實際上是上下文相關(guān)語言。
而「NFA」的實現(xiàn)就有趣多了。現(xiàn)代「正則」引擎里 NFA 實際上是一個特化的遞歸下降分析器，這個分析器允許使用回溯（和 LL(*) 這種依賴「向前看」的分析器并不相同），同時分析器的內(nèi)部結(jié)構(gòu)保留了原有正則表達(dá)式的結(jié)構(gòu)特點，因此它很容易擴(kuò)展來匹配非正則語言，也很容易擴(kuò)展來記錄匹配時的內(nèi)部狀態(tài)——這兩點使得 NFA 類匹配器得以實現(xiàn)捕獲處理以及反向引用。
而題主提及的「非貪婪星號」是個很有趣的概念。表達(dá)式  的真正含義是 ，這個集合很可能也不是正則的（沒找到論文證明），不過即使它是正則集合，構(gòu)造出它的 DFA 也是很困難的事情，而對于 NFA，想實現(xiàn)它，改下處理星號時回溯的順序就行了。