正規表示式引擎（regex engine）

當你在文字編輯器、grep 指令或網頁表單的驗證欄位裡輸入一個搜尋樣式時，幕後有某個東西接過你的樣式並拿它去比對文字。那個東西就是正規表示式引擎：把樣式字串編譯成匹配器、再讓它在輸入上執行的軟體。它是數學正規表示式在日常、實務上的後代。

引擎大致有兩種設計，而其差別很重要。以自動機為基礎的引擎（建立在 Thompson 構造法加上 NFA 或 DFA 模擬之上的那種）對每個輸入字元處理的次數有上界，提供保證的線性時間匹配；grep 與 RE2 函式庫就是這樣運作的。回溯式引擎則改為先嘗試一種匹配方式，若失敗就退回再試另一種，很像用試誤法探索迷宮；多數語言函式庫（Perl、Python 的 re、Java、JavaScript）採用回溯，因為它能乾淨地支援額外功能。引擎也處理錨點、字元類別、捕捉群組，以及其他疊加在三個核心運算之上的便利功能。

誠實的部分在這裡：正規表示式引擎通常接受比真正正規更多的樣式。反向參照與前瞻在回溯式引擎中很常見，它們讓你能描述任何有限自動機都無法識別的語言，所以程式設計裡的「regex」是那個與它同名的數學物件的超集。這份額外能力是有代價的：回溯式引擎在某些樣式與輸入上可能花費指數時間（災難性回溯），而以自動機為基礎的引擎則保持快速，卻拒絕那些非正規的功能。選擇引擎是表達力與最壞情況速度之間實實在在的工程權衡。