爲什麼這個正則表達式會殺死Java正則表達式引擎？

我有這個天真的正則表達式「<（[\ s] | [^ <]）+？>」（不包括引號）。看起來很簡單，但它對下面的HTML文本起作用時確實是邪惡的。它將Java正則表達式引擎發送到無限循環。爲什麼這個正則表達式會殺死Java正則表達式引擎？

我還有另一個正則表達式（「<。+？>」），它的確有些相同的事情，但它並沒有殺死任何東西。你知道爲什麼發生這種情況嗎？

<script language="JavaScript" type="text/javascript"> 
     var numDivs, layerName; 
     layerName = "lnavLayer"; 
     catLinkName = "category"; 
     numDivs = 2; 
     function toggleLayer(layerID){ 
      if (!(navigator.appName == "Netscape" && navigator.appVersion.substr(0, 1) < 5)){ 
       thisLayer = document.getElementById(layerName + layerID); 
       categoryLink = document.getElementById(catLinkName + layerID); 
       closeThem(); 
       if (thisLayer.className == 'subnavDefault'){ 
        thisLayer.className = 'subnavToggled'; 
        categoryLink.className = 'leftnavLinkSelectedSection'; 
       } 
      } 
     } 
     function closeThem(){ 
      for(x = 0; x < numDivs; x++){ 
       theLayer = document.getElementById(layerName + (x 
+ 1)); 
       thecategoryLink = document.getElementById(catLinkName + (x + 1)); 
       theLayer.className = 'subnavDefault'; 
       thecategoryLink.className = 'leftnavLink'; 
      } 
     } var flag = 0; var lastClicked = 0 
    //--> 
    </script>

它甚至保持與在線的Java正則表達式的工具（如www.fileformat.info/tool/regex.htm）或類似RegexBuddy實用循環。

來源

2008-11-13 Martin08

了Java正則表達式引擎崩潰的原因是你的正則表達式，這部分導致堆棧溢出（真的！）：

[\s]|[^<]

這裏會發生什麼事是，通過\ S匹配的每個字符也可以通過匹配[^ <]。這意味着有兩種方法可以匹配每個空格字符。如果我們表示與兩個字符類和B：

A|B

然後三個空格的字符串可以匹配爲AAA，AAB，ABA，ABB，BAA，BAB，BBA，或BBB。換句話說，這部分正則表達式的複雜性是2^N。這將殺死任何對我所謂的catastrophic backtracking沒有任何保護措施的正則表達式引擎。

在正則表達式中使用交替（豎線）時，請務必確保替代項是互斥的。也就是說，至多有一種選擇可以被允許匹配任何給定的文本位。

來源

2008-11-14 10:04:22

對無限循環的很好的解釋 – 2008-11-14 16:11:18

正則表達式([\s]|[^<])以純的術語是指白色空間或不是<字符，因爲空白字符不是<字符這是多餘的任何單個字符。在我看來，那是你真正的意思是：

`"<([^<])+?>"`

我不知道這是否會解決這個無限循環，但我想我指出這一點。

來源

2008-11-14 00:08:09 localshred

`「<([^<>]）+>」`會更好。那麼你不需要最小匹配。 – 2008-11-14 00:44:57

另一個問題（除了何揚說）是你在括號內一個時間匹配一個字符，相當於這個簡單的例子：

(.)+

每次正則表達式的這部分如果需要回溯，正則表達式引擎必須保存任何與子表達式匹配的開始和結束位置。這將是真實的，即使它是一個非捕獲組，即

(?:.)+

...但因爲它是一個捕獲組，甚至更多的信息必須保存。一次只讀一個角色會變得非常昂貴。將括號內組中的單個字符與組中的*或+量詞匹配幾乎是絕對正確的。此外，只有在需要捕獲某些內容時才應使用捕獲組;否則，請使用非捕獲變種。

來源

2008-11-14 21:17:29

爲什麼這個正則表達式會殺死Java正則表達式引擎？

回答

相關問題