1

要读取 CSV 文件，我在 Java 中有以下正则表达式：

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

这个表达式通过了这个在线 Regex 测试。但是，在运行它时它总是抛出一个StackOverflowError.

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

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

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

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

4

2 回答 2

1

是的，Java 正则表达式引擎坏了。它使用回溯，因此它可以支持反向引用，因此具有所有类似 perl 的正则表达式引擎所共有的病态指数空间/时间问题。你是对的，它可能会分析表达式以确定它实际上是正则的，并使用你期望的多项式空间/时间算法。

在这种情况下，我总是建议使用级联正则表达式，最好是通过JFlex，尽管如果您坚持 2 或 3 个级别，手动执行它们并不会太痛苦。不仅如此，如果您使用词法分析器，它将更易于维护并且更容易编写和调试。

这个想法是您通过重复应用简单的正则表达式来解析行。在您的情况下，第一个标识下一个字段的开始；第二个标识字段的结尾（捕获内容）；第三个检查“下一个字段”；重复。

这些几乎与您使用 JFlex 识别的 3 个标记相同，唯一的区别是字段分隔符标记非常简单，您可能会在手动执行时将其包含在“字段结束”正则表达式中。

于 2013-02-21T06:47:50.747 回答
1

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

+回溯地狱是由您在另一个有限多次匹配中进行有限多次匹配的事实引起的*：（((A+|B))*这是您的正则表达式的形式）。

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

于 2013-02-21T06:35:53.200 回答