使用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

回答

相关问题