正則表達式進入無限循環

Question

我解析形式的（種）名稱：

Parus Ater 
H. sapiens 
T. rex 
Tyr. rex 

通常具有兩個術語（二項式），但有時有3個或更多。

Troglodytes troglodytes troglodytes 
E. rubecula sensu stricto 

我寫

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

其工作的大部分時間，但偶爾走進一個無限循環。它花了一些時間來追查，這是在正則表達式匹配，然後我意識到這是一個錯字，我應該寫

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s+[a-z]+)* 

執行正常。

我的問題是：

• 爲什麼會發生這種循環發生的呢？
• 有沒有辦法在運行程序之前檢查類似的正則表達式錯誤？否則，可能難以在發佈prgram之前將其陷入困境並導致問題。

[注意：我不需要一個更一般的表達式 - 對於物種名稱有一個正式的100+行正則表達式規範 - 這只是一個初始過濾器]。

注意：問題出現了，因爲雖然大多數名字被精確地提取到2或偶爾3/4的術語（如它們在斜體中），但有一些誤報（如"Homo sapiens lives in big cities like London"），並且匹配在「L」處失敗。 ]

注意：在調試中，我發現正則表達式經常完成，但速度很慢（例如，在較短的目標字符串上）。我通過一個病理案例發現了這個錯誤是很有價值的。我學到了重要的一課！

Answer 1

要解決問題的第一部分，您應該閱讀catastrophic backtracking。從本質上講，發生的事情是有太多的方法來將你的正則表達式與你的字符串進行匹配，並且解析器不斷地回溯以試圖使其工作。

就你而言，它可能是嵌套重排：(\s*[a-z]+)*這可能會導致一些非常非常奇怪的循環。正如Qtax擅長指出的，沒有更多信息很難說清楚。

不幸的是，你的問題的第二部分無法回答。它基本上是Halting problem。由於正則表達式本質上是一個有限狀態機器，其輸入是一個字符串，所以不能創建一個通用解決方案來預測哪些正則表達式會出現災難性回溯，哪些不會。

至於使您的正則表達式運行速度更快的一些技巧？這是一大堆蠕蟲。我花了很多時間在我自己的學習正則表達式，以及一些時間來優化它們，這裏就是我發現通常有助於：

1. 編譯你的循環之外的正則表達式，如果你的語言支持它。
2. 只要有可能，只要知道它們有用，就加上anchors即可。尤其是^爲字符串的開頭。另請參見：Word Boundaries
3. 避免重複嵌套像瘟疫。如果你必須擁有它（你會這麼做），盡最大努力向發動機提供提示，以便將任何意外回溯短路。
4. 利用風味構造來加快速度。我偏好Non-Capturing groups和possessive quantifiers。它們不會出現在每一種味道中，但是當它們出現時，就應該使用它們。還檢查了Atomic Groups
5. 我一直覺得這是正確的：的時間越長你的正則表達式得到，你會更麻煩已經使其有效。正則表達式是一個偉大而強大的工具，它們就像一個超級聰明的錘子。 Don't fall into the trap of seeing everything as a nail。有時你正在尋找的字符串功能正好在你的鼻子下面。

希望這有助於你。祝你好運。

Answer 2

對於第一個正則表達式：

[A-Z][a-z]*\.?\s+[a-z][a-z]+(\s*[a-z]+)* 

災難性回溯發生，因爲在評論中指出，由於(\s*[a-z]+)*。但是，只有當你與String.matches()驗證字符串也是如此，因爲這是遇到無效的字符將導致引擎試圖原路返回，而不是返回匹配（Matcher循環）的唯一案例。

讓我們對(\s*[a-z]+)*匹配無效的字符串：

inputstringinputstring; 

(Repetition 1) 
\s*=(empty) 
[a-z]+=inputstringinputstring 
FAILED 

Backtrack [a-z]+=inputstringinputstrin 
(Repetition 2) 
\s*=(empty) 
[a-z]+=g 
FAILED 

(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstri 
(Repetition 2) 
\s*=(empty) 
[a-z]+=ng 
FAILED 

Backtrack [a-z]+=n 
(Repetition 3) 
\s*(empty) 
[a-z]+=g 
FAILED 

(End repetition 3 since all choices are exhausted) 
(End repetition 2 since all choices are exhausted) 
Backtrack [a-z]+=inputstringinputstr 

到現在爲止，你應該有注意到這個問題。讓我們將T(n)定義爲檢查長度爲n的字符串與模式不匹配的工作量。從回溯的方法來看，我們知道T(n) = Sum [i = 0..(n-1)] T(i)。由此，我們可以得出T(n + 1) = 2T(n)，這意味着回溯過程在時間複雜度上是指數的！

更改*到+可以避免這個問題完全，因爲重複的實例可以在一個空格字符和英文字母字符之間的邊界纔開始。相比之下，第一個正則表達式允許重複實例在任意兩個字母字符之間開始。

爲了演示這個，(\s+[a-z]+\s*)*會給你回溯地獄當無效的輸入字符串包含許多單詞由多個連續的空格分隔，因爲它允許重複實例啓動多個地方。這遵循式b^d其中b是連續的空格的最大數目（減1），並d是空格序列的數量。這是不太嚴重的比你的第一個正則表達式（這至少需要一個字母ENGLSH每重複一個空格字符，如你的第一個正則表達式不是每一個重複的英文字母），但它仍然是一個問題。