Pattern.matches（）给StackOverflowError

我使用java的Pattern.matches来匹配一个数据块到正则表达式。数据块可以是单行或多行。问题是，一旦我的数据超过15行（通常超过17-18行），我开始越来越stackoverflowerror。对于少于15行的数据，正则表达式工作正常。Pattern.matches（）给StackOverflowError

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

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

数据块i使用测试针对此正则表达式是本

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

来源

2011-10-05 Purav Shah

+1实际上在野外遇到这个同名的错误。 :) – Xion

提示1）你不必在这里转义'-'：'[a-zA-Z0-9 \\ - ]'（即：'a-zA-Z-]'）2）在那里在使用'.matches（）'时，无需使用'^'和'$'' – NullUserException

您是否需要组或非捕获组？如果是这样，替换'（'用'（？：'。 – Thomas

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

或许可以减少回溯位置的正则表达式引擎节省使用possessive quantifiers（++而不是+，*+代替*，而不是{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，所以我不能自己测试它。

来源

2011-10-05 14:18:28

我用你的正则表达式，它几乎使错误的行数增加了一倍（现在大约有30行清除了）。但之后我仍然得到相同的错误:( –

@NullUserExceptionఠ_ఠ：你说得对，我们需要看一些代码。但是，我很感兴趣的是Xion的评论，说正则表达式引擎可能存在一个已知问题。如果不在堆栈中，回溯的位置是否存储？ –

如果将最后一个“+”（在正则表达式的末尾）更改为“++”，是否会发生任何变化？ –

我已经转载了这个问题，但只有更大的字符串。

$ 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个或更多副本，我会得到一个巨大的堆栈跟踪。

哦，注意使用（？：集团不会更改仍然有效字符串的大小

来源

2011-10-05 14:23:10

你可以尝试使用原子团（(?>expression)），以防止回溯：

这是一个测试失败与使用您正则表达式1000线块，但现在成功了（需要一段时间，所以我只能用 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万行，仍然没有失败。 :)

来源

2011-10-05 14:33:58 Thomas

您的正则表达式允许我清除200行数据（这是我需要的最大值）..但我仍然不明白是什么问题:( –

@Purav：我不知道，但它可能确实是[灾难性的回溯] – Thomas

这很漂亮有趣的是，[Python]（http://ideone.com/zgII7）可以处理20000行就好了，但[Java]（http://ideone.com/6j83i）在200失败。 – NullUserException

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

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

以其他方式优化正则表达式，同时仍尝试一次匹配整个块可能无法正常工作。您可能可以使其匹配N倍以上的数据行，但随着您增加输入行数，您可能会再次遇到同样的问题。

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

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

来源

2011-10-05 14:38:33

Pattern.matches（）给StackOverflowError

回答

相关问题