java - Java 正则表达式上的 "StackOverflowError"是否总是意味着需要优化正则表达式？

Question

要读取 CSV 文件，我在 Java 中使用以下正则表达式:

Pattern csvline = Pattern.compile("((([^\\\"]|\\\"\\\")+|\\\"([^\\\"]|\\\"\\\")+\\\"))*", Pattern.DOTALL);

该表达式通过 this online Regex test 。然而，当运行它时，它总是抛出一个StackOverflowError。

经过一番研究，我发现解决方案是将表达式替换为

Pattern csvline = Pattern.compile("((([^\\\"]|\\\"\\\")++|\\\"([^\\\"]|\\\"\\\")++\\\"))*", Pattern.DOTALL);

这里我使用所有格量词而不是贪婪量词。在这种情况下，这也算是一种优化。

我的问题是，因为Java无法处理很多回溯(它消耗堆栈空间，我相信一个好的引擎不应该是这样)，所以任何时候当你看到StackOverflowError由于正则表达式导致，你应该考虑以一种减少回溯的方式进行优化？

Answer 1

Java抛出StackOverflowError表明匹配是内部通过递归调用完成的。这很糟糕，但也有其自身的好处，因为它表明您的正则表达式存在潜在问题。

回溯 hell 是由于您在另一个有限多个匹配 * 中执行有限多个匹配 + 的事实引起的:((A+|B))* (这是正则表达式的形式)。

通常，如果您可以编写一个不需要回溯并且不需要堆栈(例如括号匹配问题)的非正则表达式解决方案，那么您可以编写一个带有所有格量词的正则表达式(添加额外的 + 在普通量词之后)执行相同的任务，因为所有格量词不允许(允许)回溯，这与您在非正则表达式解决方案中所做的类似。