使用RegEx匹配大输入时的StackOverflowError

使用RegEx模式匹配结果时，我得到了StackOverflowError 。

模式是(\d\*?(;(?=\d))?)+ 。 此正则表达式用于validation输入：

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的经验。

Answer 1

在使用StackOverflowError修复问题之前…

1. 我想指出你当前的正则表达式(\d\*?(;(?=\d))?)+无法validation这种情况。

   每个值最后可以包含一个*（用作其他匹配的通配符）

   它无法拒绝案例23*4*4*;34*434*34 ，如此处所示¹ 。

2. 你的正则表达式会对不匹配的输入做不必要的回溯。

3. Java为组的每次重复使用一个堆栈帧(\d\*?(;(?=\d))?) （重复1次或更多次+ ）。

正确的正则表达式是：

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

请注意，这将拒绝* ，根据您的要求，您是否要接受或拒绝这一点并不太清楚。

这不能解决StackOverflow问题，因为组的每次重复(?:;\d+\*?)也会用尽堆栈。 要解决这个问题，请使所有量词都具有占有性 ，因为不需要回溯，因为语法不含糊：

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

放入字符串文字：

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

我已经使用匹配和非匹配输入测试了上面的正则表达式，该输入具有超过3600个令牌（以;分隔）。

脚注

¹ ：regex101使用PCRE风味，这与Java正则表达风味略有不同。 但是，正则表达式中使用的function在它们之间是通用的，因此不应存在差异。

附录

• 实际上，从我的正则表达式测试(\d\*?(;(?=\d))?)+ （根据您的要求这是不正确的 ），使外部+占有性++似乎修复了StackOverflowError问题，至少在我的测试中有大约3600个令牌（以;分隔，字符串长约20k字符）。 在针对不匹配的字符串进行测试时，它似乎也不会导致执行时间过长。

• 在我的解决方案中，使组的*量词(?:;\d+\*?)占有足以解决StackOverflowError 。

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

  但是，为了安全起见，我把所有的一切都占有欲。

Answer 2

你的regexp有点无效，与你的描述不符。 你有’\ d \ *？’ – 它是一个由可选*组成的数字。 然后可选’;（？= \ d）’ – ‘;’ 与前瞻数字。 字符串’1 * 2 * 3 *’将匹配您的正则表达式，但不符合您的描述。 你可以使用follow regexp。 它匹配您的输入和更多的感觉。

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

当count <300时它将通过测试，但是对于较大的值仍然会失败。 使用像indexOf和substring这样的纯字符串操作来validation输入。

Answer 3

您可能想要做的是增加堆栈的最大大小，使其不会溢出。 你可以在这里阅读有关如何做到这一点。

基本上，您使用-Xss选项启动程序。 例如， -Xss4m当我使用-Xss4m启动代码时，程序运行时没有堆栈溢出（它返回true ）。