Pattern.matches() 给出 StackOverflowError

Question

我正在使用 java 的 Pattern.matches 将数据块与正则表达式匹配。数据块可以是单行或多行。问题是，一旦我的数据超过 15 行（通常超过 17-18 行），我就会开始出现 stackoverflowerror。对于少于 15 行的数据，正则表达式可以正常工作。

正则表达式的格式如下：
域名->空间-> , ->空间->数量->空间-> , ->空间->数量->换行符

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$";

我用来测试这个正则表达式的数据块是这个

abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456
abc.com, 123, 456

这是代码：

String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$";
boolean valid = Pattern.matches(regex, data); //fails here

Answer 1

我无法告诉你这个错误的原因；正则表达式本身很好，不会出现灾难性的回溯或任何其他明显的错误。

也许您可以通过使用 所有格量词 (< code>++ 代替 +，*+ 代替 *，{2,}+ > 代替{2,} 等）。另外，您不需要捕获组（感谢托马斯），所以我将它们更改为非捕获组：

"(?:(?:[a-zA-Z0-9][a-zA-Z0-9-]*+\\.)++([a-zA-Z]{2,}+)\\s*+,\\s*+\\d++\\s*+,\\s*+\\d++(\r?+\n)?+)++"

这不会改变正则表达式的行为（除了删除不必要的锚点，因为您使用 Pattern.matches())，但也许它有助于避免 StackOverflows。我没有安装Java SDK，所以我无法自己测试。

Answer 2

您可以尝试使用原子组 ((?>expression)) 来防止回溯：

这是一个使用正则表达式进行 1000 行块失败的测试，但现在成功了（需要一段时间，因此我仅使用 5000 20000 进行了测试:) )：

String regex = "(?>(?>[a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+(?>[a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(?>\\r?\\n)?)+";

StringBuilder input = new StringBuilder();

for( int i = 0; i < 1000000; ++i) {
  input.append("abc.com, 123, 456\n");
}

Pattern p = Pattern.compile( regex );
Matcher m = p.matcher( input );

System.out.println(m.matches());

所以毕竟，它可能仍然是一个回溯问题。

更新：只是让该测试运行 20000 行，仍然没有失败。这至少是以前的 20 倍。 :)

更新 2：再次查看我的测试，我发现了缓慢的部分，即字符串连接。 （o..O）。我已经更新了测试并使用了 100 万行，仍然没有失败。 :)

Answer 3

问题是你的正则表达式太复杂了。您处理的每一行输入都会产生（我认为）10 个回溯点，并且至少其中一些似乎是由正则表达式引擎递归处理的。这可能是几百个堆栈帧，足以导致 StackOverflowError。

IMO，您需要修改模式以使其匹配一组/行数据。然后重复调用 Matcher.find 来解析每一行。我希望您会发现这样更快。

---

以其他方式优化正则表达式，同时仍尝试一次性匹配整个块可能行不通。您也许能够让它匹配 N 倍多的数据行，但是当您增加输入中的行数时，您可能会再次遇到相同的问题。

即使您确实让它作为多行正则表达式工作，它也有可能无法与 Java 正则表达式库的其他实现一起工作；例如，在较旧的 Oracle JRE 或非 Oracle 实现中。

---

我同意其他答案，这不是“灾难性回溯”的例子。相反，它是正则表达式引擎处理回溯点的方式与当您给它多行输入时回溯点太多这一事实之间的相互作用。

Answer 4

我已经重现了这个问题，但仅限于更大的字符串。

$ java -version
java version "1.6.0_22"
OpenJDK Runtime Environment (IcedTea6 1.10.2)    (6b22-1.10.2-0ubuntu1~11.04.1)
OpenJDK 64-Bit Server VM (build 20.0-b11, mixed mode)

我的测试代码：

public class Testje
{
    public static void main(String... args)
    {
        String regex = "^(([a-zA-Z0-9][a-zA-Z0-9\\-]*\\.)+([a-zA-Z]{2,})\\s*,\\s*\\d+\\s*,\\s*\\d+(\\r?\\n)?)+$";
        String data = "";
        for (int i = 0; i<224; i++) data += "abc.com, 123, 456\n";
        System.out.println(data.matches(regex));
    }
}

对于 for 循环中任何小于 224 的值，代码运行良好。对于该行的 224 个及更多副本，我得到了巨大的堆栈跟踪。

哦，请注意，使用 (?: groups 不会改变仍然有效的字符串的大小。