使用正则表达式解析大字符串时出现java.lang.StackOverflowError错误

Question

这是我的正则表达式

((?:(?:'[^']*')|[^;])*)[;]

它在分号上对字符串进行标记。例如，

Hello world; I am having a problem; using regex;

结果是三个字符串

Hello world
I am having a problem
using regex

但是当我使用一个较大的输入字符串时，我会遇到这个错误

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)

这是什么原因导致的？我该如何解决？

- Ali

---

你要解析的字符串有多大？ - NullUserException

这个问题很旧了，然而我可以使用所有格量词（*+ 而不是 *）来避免回溯，解决一个类似的问题。 - Nahuel Fouilleul

另外，我应该始终使用原子组 (?>..) 而不是组 (?:..) 来防止回溯。 - Nahuel Fouilleul

Answer 1

不幸的是，Java内置的正则表达式支持在处理包含重复选项路径（即(A|B)*）的正则表达式时存在问题。 这会编译成一个递归调用，当在非常大的字符串上使用时会导致StackOverflow错误。

一种可能的解决方案是重写正则表达式以不使用重复的替代项，但是如果你的目标是根据分号将一个字符串分词，你实际上根本不需要复杂的正则表达式，只需使用带有简单参数";"的String.split()函数即可。

- Jeen Broekstra

---

大多数正则表达式引擎都会有这个问题。 - NullUserException

我觉得我没有清楚地阐述我的情况，对此感到抱歉。字符串不仅仅在分号上进行标记化，而是同时在许多模式上进行标记化，分号上的标记化只是一个简单的情况。 - Ali

@Ali，一般来说：尽量避免在通配符中使用替代方案。你也可以尝试使用其他正则表达式库，比如jregex，但我不确定这是否能解决问题... - Jeen Broekstra

@NullUserException 至少不是 JavaScript。 我在一个包含1600多个字符的字符串上进行相同的操作。它在 Java 中导致了 StackOverflowError。然而，在 JavaScript 中，我可以在1毫秒内获得正确的结果。说实话，在这个简单的任务中，编译语言与其所有可能的优化相比，在性能方面竟然表现更差，这令我感到震惊。您可以尝试自己测试（在F12中的浏览器控制台）：function test(str){console.time("test");console.log(/^([^']|'[^']*')*'[^']*$/.test(str));console.timeEnd("test")} 然后 test("1000+ char string") - zypA13510

Answer 2

如果你真的需要使用一个超出栈容量的正则表达式，你可以通过向JVM传递类似于-Xss40m的参数来增加堆栈大小。

- Andrew

---

通过 Xss 属性增加堆栈大小会增加 OutOfMemoryError 的可能性。虽然这将解决当前问题，但与其增加 Xss，不如参考顶部答案。 - 100rabh

帮助我解决了在启动Eclipse时遇到的堆栈溢出错误。我看到的错误是：无法为org.robotframework.red.robotsuitefile_robot创建内容描述器。内容类型已被禁用。 java.lang.StackOverflowError - ChandraSPola

Answer 3

可能在 [^;] 之后添加一个 + 可以帮助减少重复。

难道没有一种构造方法可以说“如果正则表达式匹配到这个点，请不要回溯”吗？也许这也很有用。(更新：它被称为占有量词)

另一种完全不同的选择是编写一个名为 splitQuoted(char quote, char separator, CharSequence s) 的实用程序方法，该方法显式地迭代字符串并记住是否已经看到了奇数引号。在该方法中，您还可以处理引号字符在引号字符串中出现时可能需要取消转义的情况。

'I'm what I am', said the fox; and he disappeared.
'I\'m what I am', said the fox; and he disappeared.
'I''m what I am', said the fox; and he disappeared.

- Roland Illig