使用RegEx匹配大輸入時出現StackOverflowError

當使用RegEx模式匹配結果時，我得到StackOverflowError。使用RegEx匹配大輸入時出現StackOverflowError

該模式是(\d\*?(;(?=\d))?)+。此正則表達式是用來驗證輸入：

12345;4342;234*;123*;344324

輸入是一個字符串由通過;分隔值（僅位）。每個值最後可以包含一個*（用作其他匹配的通配符）。字符串的末尾沒有;。

問題是，這個正則表達式工作正常，其中少數值。但是，如果數值太大（超過300），則會導致StackOverflowError。

final String TEST_REGEX = "(\\d\\*?(;(?=\\d))?)+"; 

// Generate string 
StringBuilder builder = new StringBuilder(); 
int number = 123456; 
for (int count = 1; count <= 300; count++) { 
    builder.append(Integer.toString(number).concat(";")); 
    number++; 
} 
builder.deleteCharAt(builder.lastIndexOf(";")) 

builder.toString().matches(TEST_REGEX); //<---------- StackOverflowError

而且堆棧跟蹤：

java.lang.StackOverflowError 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556) 
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556) 
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$Ques.match(Pattern.java:4079) 
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3715) 
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4556) 
    at java.util.regex.Pattern$Loop.match(Pattern.java:4683) 
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4615) 
    ...

我想先行的格局造成這個錯誤，因爲有很多的查找，但我還沒有想出如何降低它或解決。

我真的很感激任何建議，因爲我沒有RegEx的經驗。

來源

2013-02-26 Genzer

與StackOverflowError解決了這個問題之前...

我想指出的是，當前的正則表達式(\d\*?(;(?=\d))?)+無法驗證這個條件。

每個值可以包括在端部（用作通配符其他匹配）一種*

它沒有拒絕的情況下23*4*4*;34*434*34，如圖here 。
您的正則表達式將對不匹配的輸入做不必要的回溯。
Java對組(\d\*?(;(?=\d))?)（重複一次或多次重複+）的每個重複使用一個堆棧幀。

正確的正則表達式是：

\d+\*?(?:;\d+\*?)*

注意，這會拒絕*，你是否要接受或拒絕這裏面是不是從你的要求太清楚。

這並不能解決StackOverflow問題，因爲組(?:;\d+\*?)的每個重複也將用完堆棧。爲了解決這個問題，讓所有的量詞佔有慾，因爲沒有必要回溯，因爲語法也不含糊：

\d++\*?+(?:;\d++\*?+)*+

投入字符串文字：

"\\d++\\*?+(?:;\\d++\\*?+)*+"

我已經測試過的正則表達式以上具有匹配和不匹配的輸入，其具有超過3600個令牌（由;分隔）。

腳註

：regex101使用PCRE的味道，這是從Java正則表達式風味略有不同。但是，正則表達式中使用的特徵在它們之間是相同的，所以應該沒有差異。

附錄

其實，從我與您正則表達式(\d\*?(;(?=\d))?)+（根據您的要求是不正確）測試，使得外最+佔有慾++似乎解決StackOverflowError問題，在至少在我的測試中有大約3600個標記（由;分隔，字符串大約爲20K字符）。當對一個不匹配的字符串進行測試時，它似乎也不會導致很長的執行時間。
在我的解決方案中，爲(?:;\d+\*?)組合的*量化器就足以解決StackOverflowError。
```
"\\d+\\*?(?:;\\d+\\*?)*+" 
```
但是，我把所有的東西都放在安全的一邊。

來源

2013-02-26 08:22:58 nhahtdh

我確實知道那些我原來的模式遺漏的案例，因爲我沒有在測試中添加這些案例。 – Genzer 2013-02-26 10:43:51

@Genzer：我的確給你推薦了一個正確的正則表達式。 – nhahtdh 2013-02-26 10:45:27

令人驚訝的是，您的建議剛剛通過了我所有的測試，包括'StackOverflowError'的測試。我不知道「佔有」的東西。你能否建議我可以改進的任何RegEx參考？ – Genzer 2013-02-26 10:45:28

您可能想要做的事情是增加堆棧的最大大小，使其不會溢出。 You can read about how to do that here.

基本上，你用-Xss選項開始你的程序。例如，-Xss4m當我用-Xss4m開始你的代碼時，你的程序運行時沒有堆棧溢出（它返回true）。

來源

2013-02-26 05:42:09

感謝您的建議。但我其實不想調整JVM選項，但我會認爲它是最後的選擇。 – Genzer 2013-02-26 06:45:46

您正則表達式有點無效，與您的描述不符。你有'\ d \ *？' - 這是一個數字由可選*覆蓋。然後可選';（？= \ d）' - ';'與前瞻數字。字符串'1 * 2 * 3 *'將與您的正則表達式匹配，但不會與您的描述匹配。你可以使用follow regexp。它匹配你的輸入並且更有效。

final String TEST_REGEX = "(\\d+\\*?)(?:;\\d+\\*?)+";

當計數爲< 300時它會通過測試，但對於較大的值仍然失敗。使用普通字符串操作如indexOf和子字符串驗證輸入。

來源

2013-02-26 06:50:43 ijrandom

感謝您的正則表達式。是的，我剛剛在我的正則表達式中發現了一些錯誤。但真正的問題是StackOverflowError仍然發生。 – Genzer 2013-02-26 06:55:52

使用RegEx匹配大輸入時出現StackOverflowError

回答

相關問題