正則表達式引擎分成兩類，一類稱為DFA(確定性有窮自動機)，另一類稱為NFA(非確定性有窮自動機)。兩類引擎要順利工作，都必須有一個正則式和一個文本串，一個捏在手里，一個吃下去。DFA捏著文本串去比較正則式，看到一個子正則式，就把可能的匹配串全標(biāo)注出來，然后再看正則式的下一個部分，根據(jù)新的匹配結(jié)果更新標(biāo)注。而NFA是捏著正則式去比文本，吃掉一個字符，就把它跟正則式比較，匹配就記下來：“某年某月某日在某處匹配上了！”，然后接著往下干。一旦不匹配，就把剛吃的這個字符吐出來，一個個的吐，直到回到上一次匹配的地方。

DFA與NFA機制上的不同帶來5個影響：

1. DFA 對于文本串里的每一個字符只需掃描一次，比較快，但特性較少；NFA要翻來覆去吃字符、吐字符，速度慢，但是特性豐富，所以反而應(yīng)用廣泛，當(dāng)今主要的正則表達式引擎，如Perl、Ruby、Python的re模塊、Java和.NET的regex庫，都是NFA的；

2. 只有NFA才支持lazy和backreference等特性；

3. NFA急于邀功請賞，所以最左子正則式優(yōu)先匹配成功，因此偶爾會錯過最佳匹配結(jié)果；DFA則是“最長的左子正則式優(yōu)先匹配成功”；

4. NFA缺省采用greedy量詞(見item 4)；

5. NFA可能會陷入遞歸調(diào)用的陷阱而表現(xiàn)得性能極差。

我這里舉一個例子來說明第3個影響。

例如用正則式/perl|perlman/來匹配文本'perlman book'。如果是NFA，則以正則式為導(dǎo)向，手里捏著正則式，眼睛看著文本，一個字符一個字符的吃，吃完'perl'以后，跟第一個子正則式/perl/已經(jīng)匹配上了，于是記錄在案，往下再看，吃進一個'm'，這下糟了，跟子式/perl/不匹配了，于是把m吐出來，向上匯報說成功匹配'perl'，不再關(guān)心其他，也不嘗試后面那個子正則式/perlman/，自然也就看不到那個更好的答案了。

如果是DFA，它是以文本為導(dǎo)向，手里捏著文本，眼睛看著正則式，一口一口的吃。吃到/p/，就在手里的'p'上打一個鉤，記上一筆，說這個字符已經(jīng)匹配上了，然后往下吃。當(dāng)看到/perl/之后，DFA不會停，會嘗試再吃一口。這時候，第一個子正則式已經(jīng)山窮水盡了，沒得吃了，于是就甩掉它，去吃第二個子正則式的/m/。這一吃好了，因為又匹配上了，于是接著往下吃。直到把正則式吃完，心滿意足往上報告說成功匹配了'perlman'。

由此可知，要讓NFA正確工作，應(yīng)該使用/perlman|perl/模式。

通過以上例子，可以理解為什么NFA是最左子式匹配，而DFA是最長左子式匹配。實際上，如果仔細分析，關(guān)于NFA和DFA的不同之處，都可以找出道理。而明白這些道理，對于有效應(yīng)用正則表達式是非常有意義的。

總結(jié)

以上是生活随笔為你收集整理的java nfa dfa_DFA与NFA的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。