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

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

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