使用RegEx匹配大输入时的StackOverflowError

Question

我StackOverflowError在使用RegEx模式匹配结果时得到了.

模式是(\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的经验.

Answer 1

在解决问题之前StackOverflowError......

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

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

   它没有拒绝的情况下23*4*4*;34*434*34,因为看到这里¹.

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

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

正确的正则表达式是:

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

请注意,这将拒绝*,从您的要求中不太清楚您是否要接受或拒绝此.

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

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

放入字符串文字:

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

我已经使用匹配和非匹配输入测试了上面的正则表达式,该输入具有超过3600个令牌(由...分隔;).

脚注

¹:regex101使用PCRE风味,这与Java正则表达风味略有不同.但是,正则表达式中使用的功能在它们之间是通用的,因此不应存在差异.

附录

• 实际上,从我的正则表达式测试(\d\*?(;(?=\d))?)+(根据你的要求是不正确的),使外部+占有率++似乎解决StackOverflowError问题,至少在我的测试中有大约3600个令牌(相隔;,字符串大约20k字符长) .在针对不匹配的字符串进行测试时,它似乎也不会导致执行时间过长.

• 在我的解决方案中,使*群体(?:;\d+\*?)所有权的量词足以解决StackOverflowError.

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

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