8

我遇到了一个我觉得很有趣的问题。我主要通过正则表达式对文本文件进行一些基本解析，并且在匹配此行时它总是冻结

ftrect 0.7031 57.0313 9.8561 55.5313 "FREIGABE \nQ09_SV01"

不抛出异常；该程序只是挂起。我正在发布重现这种情况的程序片段；评论的一种是可能的标准情况，但另一种是有问题的。如果您删除 \n 它可以工作，但是这些解析的文件来自“黑盒”系统。

我当然可以做一个解决方法，我只是发现它实际上冻结并希望有人能解释正在发生的事情很有趣。我在JDK6u22和JDK7u21上试过...

public static Pattern FTRECT_PATTERN = Pattern.compile(
    "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)+)\\s*\"?([\\w\\s\\.\\%\\/\\=]*)?\"?\\s*"
);

public static void main(String[] args) {

//  Matcher m = FTRECT_PATTERN.matcher( "FOX_BACKGROUND: ftrect 46.1719 18.0556 54.8633 16.5556 \"Schicht\" " );
    Matcher m = FTRECT_PATTERN.matcher( "ftrect 0.7031 57.0313 9.8561 55.5313 \"FREIGABE \\nQ09_SV01\"" );
    System.out.println( m.matches() );

    for (int i = 0; i <= m.groupCount(); i++) {
        String string = m.group( i );
        System.out.println( string );
    }
}

好吧，我发现如果我将正则表达式修改为此（添加\\\\到最后一组）：

public static Pattern FTRECT_PATTERN = Pattern.compile(
    "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)+)\\s*\"?([\\w\\\\\\s\\.\\%\\/\\=]*)?\"?\\s*"
);

我仍然不知道为什么没有抛出异常。

4

1 回答 1

10

这是因为灾难性的回溯。您的测试字符串包含"...\\n..."与字符类不匹配的文字反斜杠 (in) [\w\s\.\%\/\=]*。

这意味着正则表达式引擎必须先尝试 "FREIGABE违规字符之前的字符串的所有可能排列，然后才能确定不匹配。

这是一个非常高的数字，可能会使引擎忙碌几个小时。将反斜杠添加到字符类后，正则表达式就可以匹配。

预防：使用所有格量词（*+和++）来避免无用的回溯：

public static Pattern FTRECT_PATTERN = Pattern.compile( "\\s*([\\w]+)?\\:?\\s*ftrect\\s+((\\d*\\.?\\d*\\s?)++)\\s*\"?([\\w\\s\\.\\%\\/\\=]*+)?\"?\\s*" );

一个更好、更干净的解决方案是：

public static Pattern FTRECT_PATTERN = Pattern.compile("\\s*(\\w*):?\\s*ftrect\\s+((\\b\\d*(?:\\.\\d+)?\\b\\s?)+)\\s*\"?([\\\\\\w\\s.%/=]*+)?\"?\\s*");
于 2013-05-23T15:52:11.707 回答