NFA,DFA,and POSIX
最左最長規則
\"The Longest-Leftmost\"
之前我們說過：如果傳動裝置在文本的某個特定位置啟動DFA引擎，而在此位置又有一個或多個匹配的可能，DFA 就會選擇這些可能中最長的。因為在所有同樣從最左邊開始的可能的匹配文本中它是最長的，所以叫它「最左最長的（longest-leftmost）」匹配。
絕對最長
這裡說的「最長」不限於多選結構。看看 NFA 如何用「one（self）？（selfsufficient）？」來匹配字符串 oneselfsufficient。NFA 首先匹配「one」，然後是匹配優先的「（self）？」，留下「（selfsufficient）？」來匹配sufficient。它顯然無法匹配，但整個表達式並不會因此匹配失敗，因為這個元素不是必須匹配的。所以，傳統型NFA返回
，放棄沒有嘗試的狀態（POSIX NFA的情況與此不同，我們稍後將會看到）。
與此相反，DFA 會返回更長的結果：
。如果最開始的「（self）？」因為某些原因無法匹配，NFA 也會返回跟 DFA 一樣的結果，因為「（self）？」無法匹配，「（selfsufficient）？」就能成功匹配。傳統型NFA不會這樣，但是DFA則會這樣，因為會選擇最長的可能匹配。DFA 同時記錄多個匹配，在任何時候都清楚所有的匹配可能，所以它能做到這一點。
我選這個簡單的例子是因為它很容易理解，但是我希望讀者能夠明白，這個問題在現實中很重要。舉例來說，如果希望匹配連續多行文本，常見的情況是，一個邏輯行（logical line）可以分為許多現實的行，每一行以反斜線結尾，例如：
讀者可能希望用「^w+=.＊」來匹配這種「var=value」的數據，但是正則表達式無法識別連續的行（在這裡我們假設點號無法匹配換行符）。為了匹配多行，讀者可能需要在表達式最後添加「（\\n.＊）＊」，得到
。顯然，這意味著任何後繼的邏輯行都能匹配，只要他們以反斜線結尾。這看起來沒錯，但在傳統型NFA中行不通。「.＊」到達行尾的時候，已經匹配了反斜線，而表達式中後面的部分不會強迫進行回溯（☞152）。但是，DFA 能夠匹配更長的多行文本，因為它確實是最長的。
如果能夠使用忽略優先的量詞，也許可以考慮用它們來解決問題，例如「^w+=.＊？（\\n.＊？）＊」。這樣點號每次實際匹配任何字符之前，都需要測試轉義的換行符部分，這樣「\\」就能夠匹配換行符之前的反斜線。不過這也行不通。如果忽略優先量詞匹配某些可選的部分，必然是在全局匹配必須的情況下發生。但是在本例中，「=」後面的所有部分都不是必須匹配的，所以沒有東西會強迫忽略優先量詞匹配任何字符。忽略優先的正則表達式只能匹配『SRC=』，這顯然不是我們期望的結果。
這個問題還有其他的解決辦法，我們會在下一章繼續這個問題（☞186）。
POSIX和最左最長規則
POSIX and the Longest-Leftmost Rule
POSIX標準規定，如果在字符串的某個位置存在多個可能的匹配，應當返回的是最長的匹配。
POSIX標準文檔中使用了「最左邊開始的最長匹配（longest of the leftmost）」。它並沒有規定必須使用DFA，那麼，如果希望使用NFA來實踐POSIX，程序員應該如何做？如果你希望執行POSIX NFA，那麼必須找到完整的
和所有的連續行，雖然這個結果是違反NFA「天性」的。
傳統型NFA引擎會在第一次找到匹配時停下來，但是如果讓它繼續嘗試其他分支（狀態）會怎樣呢？每次匹配到表達式的末尾時，它都會獲得另一個可能的匹配結果。如果所有的分支都窮盡了，就能從中選擇最長的匹配結果。這樣，我們就得到了一台POSIX NFA。在上面的例子中，NFA 匹配「（self）？」時保存了一個備用狀態：
ficient）？」在
。傳統型NFA在
之後停止匹配，
而POSIX NFA仍然會繼續檢查餘下的所有狀態，最終得到那個更長的結果（其實是最長的）
。
第7章有一個例子，可以讓Perl模擬POSIX的做法，返回最長的匹配字符（☞225）。
速度和效率
Speed and Efficiency
如果傳統型NFA的效率是我們應當關注的問題（對提供回溯的傳統型NFA來說，這確實是一個問題），那麼POSIX NFA的效率就更值得關注，因為它需要進行更多的回溯。POSIX NFA需要嘗試正則表達式的所有變體（譯注4）。第6章告訴我們，正則表達式寫得糟糕的話，匹配的效率就會很低。
DFA的效率
文本主導的DFA巧妙地避免了回溯造成的效率問題。DFA同時記錄了所有可能的匹配，這樣來提高速度。它是如何做到這一切的呢？
DFA 引擎需要更多的時間和內存，它第一次遇見正則表達式時，在做出任何嘗試之前會用比NFA詳細得多的（也是截然不同的）辦法來分析這個正則表達式。開始嘗試匹配的時候，它已經內建了一張路線圖（map），描述「遇到這個和這個字符，就該選擇這個和那個可能的匹配」。字符串中的每個字符都會按照這張路線圖來匹配。
有時候，構造這張路線圖可能需要相當的時間和內存，不過只要建立了針對特定正則表達式的路線圖，結果就可以應用到任意長度的文本。這就好像為你的電動車充電一樣。首先，你得把車停到車庫裡面，插上電源等待一段時間，但只要發動了汽車，清潔的能源就會源源而來。
小結：NFA與DFA的比較
Summary:NFA and DFA in Comparison
NFA與DFA各有利弊。
DFA與NFA：在預編譯階段（pre-use compile）的區別
在使用正則表達式搜索之前，兩種引擎都會編譯表達式，得到一套內化形式，適應各自的匹配算法。NFA的編譯過程通常要快一些，需要的內存也更少一些。傳統型NFA和POSIX NFA之間並沒有實質的差別。
DFA與NFA：匹配速度的差別
對於「正常」情況下的簡單文本匹配測試，兩種引擎的速度差不多。一般來說，DFA 的速度與正則表達式無關，而NFA中兩者直接相關。
傳統的NFA在報告無法匹配以前，必須嘗試正則表達式的所有變體。這就是為什麼我要用整章（第6章）來論述提高NFA表達式匹配速度的技巧。我們將會看到，有時候一個NFA永遠無法結束匹配。傳統型NFA如果能找到一個匹配，肯定會停止匹配。
相反，POSIX NFA必須嘗試正則表達式的所有變體，確保獲得最長的匹配文本，所以如果匹配失敗，它所花的時間與傳統型NFA一樣（有可能很長）。因此，對POSIX NFA來說，表達式的效率問題更為重要。
在某種意義上，我說得絕對了一點，因為優化措施通常能夠減少獲得匹配結果的時間。我們已經看到，優化引擎不會在字符串開頭之外的任何地方嘗試帶「^」錨點的表達式，我們會在第6章看到更多的優化措施。
DFA不需要做太多的優化，因為它的匹配速度很快，不過最重要的是，DFA在預編譯階段所作的工作提供的優化效果，要好於大多數NFA引擎複雜的優化措施。
現代DFA引擎經常會嘗試在匹配需要時再進行預編譯，減少所需的時間和內存。因為應用的文本各異，通常情況下大部分的預編譯都是白費工夫。因此，如果在匹配過程確實需要的情況下再進行編譯，有時候能節省相當的時間和內存（技術術語就是「延遲求值（lazy evaluation）」）。這樣，正則表達式、待匹配的文本和匹配速度之間就建立了某種聯繫。
DFA與NFA：匹配結果的差別
DFA（或者POSIX NFA）返回最左邊的最長的匹配文本。傳統型NFA可能返回同樣的結果，當然也可能是別的文本。針對某一型具體的引擎，同樣的正則表達式，同樣的文本，總是得到同樣的結果，在這個意義上來說，它不是「隨機」的，但是其他NFA引擎可能返回不一樣的結果。事實上，我見過的所有傳統型NFA返回的結果都是一樣的，但並沒有任何標準來硬性規定。
DFA與NFA：能力的差異
NFA引擎能提供一些DFA不支持的功能，例如：
●捕獲由括號內的子表達式匹配的文本。相關的功能是反向引用和後匹配信息（after-match information），它們描述匹配的文本中每個括號內的子表達式所匹配文本的位置。
●環視，以及其他複雜的零長度確認（注8）（☞133）。
●非匹配優先的量詞，以及有序的多選結構。DFA很容易就能支持選擇最短的匹配文本（儘管因為某些原因，這個選項似乎從未向用戶提供過），但是它無法實現我們討論過的局部的忽略優先性和有序的多選結構。
●佔有優先量詞（☞142）和固化分組（☞139）。
DFA與NFA：實現難度的差異
儘管存在限制，但簡單的DFA和NFA引擎都很容易理解和實現。對效率（包括時間和空間效率）和增強性能的追求，令實現越來越複雜。
用代碼長度來衡量的話，支持NFA正則表達式的ed Version 7（1979年1月發佈）只有不到350行的C代碼（所以， 整個grep只有區區478行代碼）。Henry Spencer1986年免費提供的Version 8正則程序差不多有1 900行C代碼，1992年Tom Lord的POSIX NFA package rx（被GNU sed和其他工具採用）長達9 700行。
為了糅合DFA和NFA的優點，GNU egrep Version 2.4.2使用了兩個功能完整的引擎（差不多8 900行代碼），Tcl的DFA/NFA混合引擎（請看上一頁的補充內容）更是長達9 500行。
某些實現很簡單，但這並不是說它們支持的功能有限。我曾經想要用 Pascal 的正則表達式來處理某些文本。從畢業以後我就沒用過Pascal了，但是寫個簡單的NFA引擎並不需要太多工夫。它並不追求花哨，也不追求速度，但是提供了相對全面的功能，非常實用。