java - 使用 RegEx 匹配大输入时出现 StackOverflowError

Question

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

Answer 1

在解决 StackOverflowError 问题之前...

1. 我想指出，您当前的正则表达式 (\d\*?(;(?=\d))?)+ 无法验证此条件。

   Each value could include one * at the end (used as wildcard for other matching)

   它无法拒绝 23*4*4*;34*434*34 的情况，如 here 所示¹.

2. 您的正则表达式将对不匹配的输入进行不必要的回溯。

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

正确的正则表达式是:

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

请注意，这将拒绝*，这从您的要求中不太清楚您是要接受还是拒绝。

这并没有解决 StackOverflow 问题，因为 (?:;\d+\*?) 组的每次重复也会用完堆栈。要解决这个问题，请使所有量词占有，因为不需要回溯，因为语法没有歧义:

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

放入字符串文字:

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

我已经用匹配和非匹配输入测试了上面的正则表达式，它有超过 3600 个标记(由 ; 分隔)。

脚注

¹:regex101 使用 PCRE flavor，与 Java regex flavor 略有不同。但是，您的正则表达式中使用的特征在它们之间是通用的，因此应该没有差异。

附录

• 实际上，根据我对您的正则表达式 (\d\*?(;(?=\d))?)+ 的测试(不正确根据您的要求)，使最外层的 + 所有格 ++ 似乎可以解决 StackOverflowError 问题，至少在我对 3600 左右的测试中标记(由 ; 分隔，字符串长度约为 20k 个字符)。在针对不匹配的字符串进行测试时，它似乎也不会导致执行时间过长。

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

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

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