3

我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 方面没有经验。

4

3 回答 3

8

在解决问题之前StackOverflowError...

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

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

    它未能拒绝此案23*4*4*;34*434*34，如此处所示1。

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

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

正确的正则表达式是：

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

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

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

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

放入字符串文字：

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

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

脚注

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

附录

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

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

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

    然而，为了安全起见，我让一切都占有欲。

于 2013-02-26T08:22:58.803 回答
1

您的正则表达式有点无效，与您的描述不符。你有 '\d\*?' - 它是一个数字，后跟可选的 *。然后可选 ';(?=\d)' - ';' 与前瞻数字。字符串 '1*2*3*' 将匹配您的正则表达式，但不匹配您的描述。您可以使用跟随正则表达式。它与您的输入相匹配，并且更具影响力。

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

当 count < 300 时它将通过测试，但对于较大的值仍然失败。使用indexOf和substring之类的纯字符串操作来验证输入。

于 2013-02-26T06:50:43.083 回答
0

您可能想要做的事情是增加堆栈的最大大小，使其不会溢出。 您可以在此处阅读有关如何执行此操作的信息。

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

于 2013-02-26T05:42:09.753 回答