比對行為

.NET Framework 規則運算式引擎為回溯的規則運算式比對器,它結合了傳統的非決定性有限自動化 (Nondeterministic Finite Automaton,NFA) 引擎,例如 Perl、Python、Emacs 和 Tcl 所使用的引擎。這使得它與較快速、但限制較多的純規則運算式 (Regular Expression) 決定性有限自動化 (DFA,Deterministic Finite Automaton) 引擎有所區別,例如 awk、egrep 或 lex 中的引擎。這也和標準的但較緩慢的 POSIX NFA 有差異。

規則運算式引擎的三個類型

這個章節提供三種引擎優缺點的概觀,並且說明 .NET Framework 引擎為何實作傳統的 NFA 比對器。

DFA 引擎以線性時間執行,因為它們不需要回溯 (如此它們從不測試相同字元兩次)。它們也可以保證比對最長的可能字串。然而,既然 DFA 引擎只包含有限狀態,它不能以反向參考比對模式,並且因為它不建構明確的展開,所以不能擷取子運算式。

傳統 NFA 引擎執行所謂「窮盡」比對回溯演算法,依特定順序測試規則運算式的所有可能展開,並接受第一個相符比對。因為傳統 NFA 為成功的比對建構規則運算式的特定展開,它可以擷取子運算式比對和比對的反向參考。然而,因為傳統 NFA 會回溯,它可以多次造訪完全相同狀態,如果這狀態經由不同路徑達到的話。結果,最壞的情況下它可能以指數方式緩慢執行。因為傳統 NFA 接受它找到的第一個相符比對,它也可能讓其他 (可能是更長的) 比對無法被發現。

POSIX NFA 引擎很像傳統 NFA 引擎,只是它繼續回溯直到它們能夠保證已經找到最長的可能比對。結果,POSIX NFA 引擎比傳統 NFA 引擎更緩慢,而且當使用 POSIX NFA 時,您不能經由變更回溯搜尋的順序來使較短比對優先於較長比對。

程式設計人員偏愛傳統 NFA 引擎,因為它們較 DFA 或 POSIX NFA 引擎更明確達意。雖然在最壞的情況中它們可能執行緩慢,您可以使用減低模稜兩可並限制回溯的模式,操縱它們以線性或多項式時間尋找相符比對。

.NET Framework 引擎的功能

由於傳統 NFA 引擎的優點,.NET Framework 規則運算式引擎包含了完整的建構集合,讓程式設計人員可以操縱回溯引擎。這些建構可被用來更快速尋找相符比對,或讓特定展開優先於其他展開。

其他功能包括下列能力:

  • 「省略」數量詞: ??、*?、+?、{n,m}?。這些數量詞告訴回溯引擎要首先搜尋最小數目的重複。反之,一般的窮盡數量詞則試圖首先比對最大數目的重複。

  • 右合樣 (Positive Lookahead):這允許回溯引擎在比對子運算式之後返回到文字的相同地方。這對於自相同位置開始驗證多個模式以全面搜尋文字的場合很有用處。

  • 右不合樣 (Negative Lookahead):這加入只有在子運算式未能成功比對時才會比對運算式的功能。這在刪除搜尋時特別有功用,因為在應該排除情況的運算式經常是遠比必須要包含情況的運算式簡單 (例如,為不以 "non" 開頭的字組撰寫運算式即很困難)。

  • 條件評估:這允許引擎根據前面子運算式比對的結果,使用一個以上替代模式來搜尋。這允許更強大的反向參考形式,例如在左括號事先於子運算式中被擷取時,容許比對右括號。

  • 非回溯子運算式 (也稱為窮盡子運算式):這允許回溯引擎保證子運算式只比對為該子運算式找到的第一個相符比對,就好像運算式將不受它的包含運算式的影響而執行。除掉這個建構,較大型運算式中的回溯搜尋即可變更子運算式的行為。

  • 由右至左的比對:當由右至左搜尋取代由左至右搜尋時,或在從右手邊部分 (而非自左邊) 開始比對模式較有效率的情況中,這將很有用處。

  • 左合 (Positive Lookbehind) 和左不合樣 (Negative Lookbehind):與向右合樣類似,因為規則運算式引擎允許完整的由右至左比對,規則運算式允許無限制的向左合樣。

請參閱

其他資源

.NET Framework 規則運算式