正則表示式/實現
< 正則表示式
至少有3種不同的演算法可以確定給定字串是否（以及如何）與正則表示式匹配。它們基於正則表示式作為有限自動機的不同表示以及匹配器中存在的功能數量。
- 一個不包含反向引用和前瞻/後顧的基於NFA的匹配器。大小為O(n)的輸入可以在O(nm)時間內測試與大小為O(m)的正則表示式匹配，並且透過使用湯普森演算法模擬NFA，額外需要O(m)的空間。如果要記錄c個子匹配捕獲組，則執行時間增加到O(nm log c)，但空間需求仍然為O(m)。
- 一個包含反向引用和前瞻/後顧的基於NFA的匹配器。這樣的匹配器需要使用回溯來實現。大小為O(n)的輸入可以在O(2mn)時間內使用回溯測試與大小為O(m)的正則表示式匹配。需要一些努力來確保基於回溯的匹配器不會進入無限迴圈，反覆測試相同的路徑。
- 一個基於DFA的匹配器。基於DFA的匹配器不支援反向引用、子匹配捕獲或前瞻/後顧。這是最古老、最快的匹配器型別，它依賴於形式語言理論中的一項結果，該結果允許將每個非確定性有限狀態機 (NFA) 轉換為確定性有限狀態機 (DFA)。該演算法執行或模擬這種轉換，然後在輸入字串上執行生成的DFA，每次處理一個符號。後一個過程（DFA匹配）所花費的時間與輸入字串的長度成正比。更準確地說，大小為m的正則表示式在大小為S的輸入字母表上可以在O(2mS)時間內轉換為DFA，隨後可以O(n)時間內測試大小為n的輸入字串與任何大小的DFA是否匹配。
基於DFA的演算法在將輸入與正則表示式匹配方面很快，但只能用於匹配，不能用於呼叫分組的子表示式。有一種變體可以呼叫分組的子表示式，但它的執行時間會降至O(n2m) [需要引用]。
基於回溯演算法的執行時間可能是指數級的，當匹配包含交替和無限量化的表示式（例如“(a|aa)*b”）時，簡單的實現會表現出這種行為，迫使演算法考慮指數級的子情況。更復雜的實現會識別並加速各種常見情況，否則它們會執行緩慢。
即使回溯實現只在最壞情況下提供指數級保證，但它們允許更大的靈活性並提供更強大的表達能力。例如，任何允許使用反向引用或實現 Perl 引入的各種改進的實現都必須使用回溯實現。
一些實現嘗試透過首先執行一個快速的 DFA 匹配來檢視字串是否與正則表示式匹配，只有在這種情況下才會執行一個潛在的更慢的回溯匹配，從而提供兩種演算法的最佳效果。