可以處理機器生成的正則表達式的正則表達式實現：非回溯，O(n)？
***編輯 2：***對於為什麼這仍然很重要的實際展示，只需看看stackoverflow 自己的正則表達式導致的中斷今天（2016-07-20）！
***編輯：***自從我第一次提出這個問題以來，這個問題已經有了很大的發展。請參閱下面的兩個快速+兼容但不完全功能的實現。如果您知道更多或更好的實現，請提及它們，這裡還沒有理想的實現！
我在哪裡可以找到可靠快速的正則表達式實現？
有誰知道.NET或本機的正常非回溯（回溯）線性時間正則表達式實現，並且可以從.NET合理使用？
System.Text.RegularExpressions為了有用，它需要：
- 正則表達式評估的最壞情況時間複雜度為O ( m*n)，其中 m 是正則表達式的長度，n 是輸入的長度。
- 具有O(n) 的正常時間複雜度，因為幾乎沒有正則表達式實際上觸髮指數狀態空間，或者，如果可以，僅在輸入的一分鍾子集上這樣做。
- 具有合理的建構速度（即沒有潛在的指數 DFA）
- 旨在供人類使用，而不是數學家 - 例如，我不想重新實現 unicode 字元類： .NET 或 PCRE 樣式字元類是一個加號。
獎勵積分：
- 如果它實現了基於堆棧的功能，可以讓它以消耗 O(n+m) 記憶體而不是 O(m) 記憶體為代價來處理嵌套，那麼它的實用性就會得到加分。
- 擷取子表達式或替換的獎勵積分***（*如果有可能的子表達式匹配的指數數量，那麼列舉所有它們本質上是指數的 - 但列舉前幾個不應該是，替換也是如此）。您可以通過使用另一個功能來解決缺少任何一個功能的問題，因此擁有一個就足夠了。
- 將正則表達式視為一流值的很多獎勵積分（因此您可以採用並集、交集、連接、否定 - 特別是否定和交集，因為這些很難通過正則表達式定義的字元串操作來完成）
- 惰性匹配，即在無限流上匹配而不將其全部放入記憶體是一個優點。如果流不支持查找，則（通常）不可能一次擷取子表達式和/或替換。
- 反向引用已經過時了，它們根本不可靠；即在給定病態輸入案例的情況下，總是可以表現出指數行為。
存在這樣的算法（這是基本的自動機理論……） - 但是是否有任何可從 .NET 訪問的實際可用的實現？
背景：（可以跳過）
我喜歡使用正則表達式進行快速而骯髒的文本清理，但我反复遇到 perl/java/python/.NET 使用的常見回溯 NFA 實現顯示指數行為的問題。不幸的是，一旦您開始自動生成正則表達式，這些情況就很容易觸發。當您在匹配相同前綴的正則表達式之間交替使用時，即使是非指數性能也會變得非常差 - 例如，在一個非常基本的範例中，如果您將字典轉換為正則表達式，預計性能會很糟糕。
要快速了解為什麼存在以及自 60 年代以來存在更好的實現，請參閱正則表達式匹配可以簡單快速。
不太實用的選擇：
- 幾乎是理想的：FSA 工具包。可以將正則表達式編譯為 DFA + NFA 的快速 C 實現，也允許轉換器（！），具有一流的正則表達式（封裝耶！），包括交集和參數化的語法。 但它在序言中……（為什麼具有這種實用功能的東西在主流語言中不可用？？？）
- 快速但不切實際：完整的解析器，例如優秀的ANTLR ，通常支持可靠的快速正則表達式。但是，antlr 的語法要冗長得多，並且當然允許可能無法生成有效解析器的構造，因此您需要找到一些安全的子集。
好的實現：
- RE2 - 一個Google開源庫，旨在實現合理的 PCRE 兼容性減去反向引用。我認為這是作者給出的 plan9 正則表達式庫的 unix 埠的繼承者。
- TRE - 也主要與 PCRE 兼容，甚至可以進行反向引用，儘管使用那些你會失去速度保證。並且它有一個超級漂亮的近似匹配模式！
不幸的是，這兩種實現都是 C++，並且需要從 .NET 使用互操作。
首先，你的建議是可能的，你當然知道你的主題。您還知道不使用反向引用實現的代價是記憶體。如果您對環境進行了足夠的控制，這可能是一種合理的方法。
在繼續之前，我唯一要評論的是，我鼓勵您質疑使用 RegEx 的選擇。您顯然更熟悉您的具體問題以及您試圖解決的問題，因此只有您才能回答問題。我不認為 ANTLR 會是一個好的選擇。但是，自製規則引擎（如果範圍有限）可以根據您的特定需求進行高度調整。這完全取決於您的具體問題。
對於那些閱讀本文並“錯過重點”的人，這裡有一些背景閱讀：
從同一個站點，此頁面上鍊接了許多實現。
上述文章的整個討論的要點是，最好的答案是兩者都使用。為此，我所知道的唯一廣泛使用的實現是 TCL 語言使用的實現。據我了解，它最初是由 Henry Spencer 編寫的，它採用了這種混合方法。有一些嘗試將其移植到 ac 庫，但我不知道有什麼被廣泛使用。Walter Waldo’s 和Thomas Lackner’s均在此處提及和連結。還提到了boost 庫，儘管我不確定實現。您還可以查看 TCL 程式碼本身（從他們的網站連結）並從那裡開始工作。
簡而言之，我會選擇TRE或Plan 9，因為它們都受到積極支持。
顯然，這些都不是 C#/.Net，我不知道有一個。