Pattern.matches（）給StackOverflowError

我使用java的Pattern.matches來匹配一個數據塊到正則表達式。數據塊可以是單行或多行。問題是，一旦我的數據超過15行（通常超過17-18行），我開始越來越stackoverflowerror。對於少於15行的數據，正則表達式工作正常。Pattern.matches（）給StackOverflowError

在正則表達式的格式如下：
域名 - >空間 - > - >空間 - >數 - >空間 - > - >空間 - >數 - >換行

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$";

數據塊i使用測試針對此正則表達式是本

abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456 
abc.com, 123, 456

這是代碼：

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
boolean valid = Pattern.matches(regex, data); //fails here

來源

2011-10-05 Purav Shah

+1實際上在野外遇到這個同名的錯誤。 :) – Xion

提示1）你不必在這裏轉義'-'：'[a-zA-Z0-9 \\ - ]'（即：'a-zA-Z-]'）2）在那裏在使用'.matches（）'時，無需使用'^'和'$'' – NullUserException

您是否需要組或非捕獲組？如果是這樣，替換'（'用'（？：'。 – Thomas

我不能告訴你這個錯誤的原因;正則表達式本身很好，不會遭受災難性的回溯或任何其他明顯的錯誤。

或許可以減少回溯位置的正則表達式引擎節省使用possessive quantifiers（++而不是+，*+代替*，而不是{2,}+{2,}等）的數量。此外，您不需要捕獲組（感謝托馬斯），所以我他們變成非捕獲的：

"(?:(?:[a-zA-Z0-9][a-zA-Z0-9-]*+\\.)++([a-zA-Z]{2,}+)\\s*+,\\s*+\\d++\\s*+,\\s*+\\d++(\r?+\n)?+)++"

這不會改變正則表達式的行爲（除去除不必要的錨點，因爲你使用的是Pattern.matches()），但也許它有助於避免StackOverflows。我沒有安裝Java SDK，所以我不能自己測試它。

來源

2011-10-05 14:18:28

我用你的正則表達式，它幾乎使錯誤的行數增加了一倍（現在大約有30行清除了）。但之後我仍然得到相同的錯誤:( –

@NullUserExceptionఠ_ఠ：你說得對，我們需要看一些代碼。但是，我很感興趣的是Xion的評論，說正則表達式引擎可能存在一個已知問題。如果不在堆棧中，回溯的位置是否存儲？ –

如果將最後一個「+」（在正則表達式的末尾）更改爲「++」，是否會發生任何變化？ –

我已經轉載了這個問題，但只有更大的字符串。

$ java -version 
java version "1.6.0_22" 
OpenJDK Runtime Environment (IcedTea6 1.10.2) (6b22-1.10.2-0ubuntu1~11.04.1) 
OpenJDK 64-Bit Server VM (build 20.0-b11, mixed mode)

我的測試代碼：

public class Testje 
{ 
    public static void main(String... args) 
    { 
     String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$"; 
     String data = ""; 
     for (int i = 0; i<224; i++) data += "abc.com, 123, 456\n"; 
     System.out.println(data.matches(regex)); 
    } 
}

對於在for循環任何比224更小，代碼運行正常。對於該行的224個或更多副本，我會得到一個巨大的堆棧跟蹤。

哦，注意使用（？：集團不會更改仍然有效字符串的大小

來源

2011-10-05 14:23:10

你可以嘗試使用原子團（(?>expression)），以防止回溯：

這是一個測試失敗與使用您正則表達式1000線塊，但現在成功了（需要一段時間，所以我只能用 20000 :)測試）：

String regex = "(?>(?>[a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+(?>[a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(?>\\r?\\n)?)+"; 

StringBuilder input = new StringBuilder(); 

for(int i = 0; i < 1000000; ++i) { 
    input.append("abc.com, 123, 456\n"); 
} 

Pattern p = Pattern.compile(regex); 
Matcher m = p.matcher(input); 

System.out.println(m.matches());

所以畢竟，它仍然可能是一個回溯問題。

更新：只是讓該測試運行20000行，仍然沒有失敗。這至少是以前的20倍。 :)

更新2：再次看我的測試我發現緩慢的部分，字符串連接。（o..O）。我已經更新了測試並使用了100萬行，仍然沒有失敗。 :)

來源

2011-10-05 14:33:58 Thomas

您的正則表達式允許我清除200行數據（這是我需要的最大值）..但我仍然不明白是什麼問題:( –

@Purav：我不知道，但它可能確實是[災難性的回溯] – Thomas

這很漂亮有趣的是，[Python]（http://ideone.com/zgII7）可以處理20000行就好了，但[Java]（http://ideone.com/6j83i）在200失敗。 – NullUserException

問題是，你的正則表達式太複雜了。你處理的每一行輸入結果（我認爲）10回溯點，至少其中一些似乎由正則表達式引擎遞歸處理。這可能是幾百個棧幀，足以給你StackOverflowError。

IMO，你需要修改模式，以便它將匹配一組數據/行。然後重複調用Matcher.find來解析每一行。我希望你會發現這樣更快。

以其他方式優化正則表達式，同時仍嘗試一次匹配整個塊可能無法正常工作。您可能可以使其匹配N倍以上的數據行，但隨着您增加輸入行數，您可能會再次遇到同樣的問題。

即使您確實將其作爲多行正則表達式工作，也有可能無法與Java正則表達式庫的其他實現一起使用;例如在較舊的Oracle JRE或非Oracle實現中。

我同意其他答案，這不是一個「災難性的回溯」的例子。相反，它是正則表達式引擎處理回溯點的方式與當它給出多行輸入時只有太多這樣的事實之間的交互。

來源

2011-10-05 14:38:33

Pattern.matches（）給StackOverflowError

回答

相關問題