java - 使用正则表达式解析大字符串以获取 java.lang.StackOverflowError 错误

Question

这个问题已经有答案了:

java.lang.StackOverflowError while using a RegEx to Parse big strings (3 个回答)

已关闭 6 年前。

这是我的正则表达式

"(?<=\"body\":\")((?=\",|\"$)|.)+"

它标记了主体上的字符串。例如，

"body":its my string

结果是

its my string

但是当我使用较大的输入字符串时，我收到此错误

Exception in thread "main" java.lang.StackOverflowError
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078)
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345)
at java.util.regex.Pattern$Branch.match(Pattern.java:4114)
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
at java.util.regex.Pattern$Loop.match(Pattern.java:4295)
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)

这是怎么造成的，如何解决？

Answer 1

看起来您正在 try catch RHS 字符串的内容，同时强制其前面为 "body":" ，后面为 ".

您似乎正在使用环视断言来测试周围文本是否存在，但您还使用捕获组来捕获 RHS 字符串的内容。您不需要做这两件事。环视断言是零宽度，这意味着它们不会形成最终匹配子字符串的一部分。最终匹配的子字符串始终可以作为捕获组 0 进行访问。或者，您可以完全匹配所有正则表达式组件(意味着非零宽度匹配，意味着没有环视)并使用捕获组来提取感兴趣的子字符串，但这将是效率较低。

我认为应该这样写(与此演示的 args[0] 匹配):

Pattern p = Pattern.compile("(?<=\"body\":\")[^\"]*(?=\")");
Matcher m = p.matcher(args[0]);
if (!m.find(0)) { System.out.println("doesn't match!"); System.exit(1); }
System.out.println(m.group(0));

上面的方法对我来说适用于相当大的字符串。

<小时/>

我确实尝试重现 StackOverflowError 异常，并且成功了。在我看来，Java 正则表达式引擎正在使用递归来实现重复交替的匹配。这对我来说非常令人惊讶，因为我不知道为什么需要递归来匹配重复的交替。话虽这么说，我还使用 Perl 正则表达式做了一些测试，我一直认为 Perl 正则表达式是现有的最强大、最健壮的正则表达式风格，并且令我更加惊讶的是，Perl 的失败方式与 Java 完全相同正则表达式。

下面是一个示例，显示了 Java 失败和 Perl 失败。在此演示中，我将 [^"] 原子更改为交替 (?:\\.|[^"])，这有效地添加了对嵌入的反斜杠转义码的支持在双引号字符串中，例如 \" 来编码嵌入的双引号，这在许多编程环境中普遍支持。

Java

Pattern p = Pattern.compile("(?<=\"body\":\")(?:\\\\.|[^\"])*(?=\")");
Matcher m = p.matcher(args[0]);
if (!m.find(0)) { System.out.println("doesn't match!"); System.exit(1); }
System.out.println(m.group(0));

输出

Exception in thread "main" java.lang.StackOverflowError
  at java.util.regex.Pattern$CharProperty.match(Unknown Source)
  at java.util.regex.Pattern$Branch.match(Unknown Source)
  at java.util.regex.Pattern$GroupHead.match(Unknown Source)
  at java.util.regex.Pattern$Loop.match(Unknown Source)
  at java.util.regex.Pattern$GroupTail.match(Unknown Source)
  at java.util.regex.Pattern$BranchConn.match(Unknown Source)
  at java.util.regex.Pattern$CharProperty.match(Unknown Source)
  at java.util.regex.Pattern$Branch.match(Unknown Source)
  at java.util.regex.Pattern$GroupHead.match(Unknown Source)
  at java.util.regex.Pattern$Loop.match(Unknown Source)
  at java.util.regex.Pattern$GroupTail.match(Unknown Source)
...

Perl(来自 shell)

largeString="\"body\":\"$(perl -e 'use strict; use warnings; for (my $i = 0; $i < 2**15; ++$i) { print("x"); }';)\"";
perl -e 'use strict; use warnings; my $re = qr((?<="body":")(?:\\.|[^"])*(?=")); if ($ARGV[0] !~ $re) { print("didn'\''t match!\n"); } print($&);' "$largeString";

输出

Complex regular subexpression recursion limit (32766) exceeded at -e line 1.
didn't match!
Use of uninitialized value $& in print at -e line 1.

所以，只是为了澄清一下，我在答案开头附近给出的解决方案避免此堆栈溢出错误的原因不是因为我删除了捕获组 1，而是因为我删除了交替。再说一次，我不知道为什么用递归来实现重复的交替，但考虑到这一事实，大输入字符串会导致堆栈溢出错误似乎是合乎逻辑的。