Java正则表达式在堆栈溢出时死亡:需要更好的版本

Question

我工作的一个JMD(Java的降价)(的渣口MarkDownSharp),但我在遇到一个特别的正则表达式的问题.对于文件Markdown_Documentation_Syntax.text,这个正则表达式会死掉:

private static final String BLOCK_TAGS_1 = "p|div|h[1-6]|blockquote|pre|table|dl|ol|ul|script|noscript|form|fieldset|iframe|math|ins|del";
private static final String BLOCKS_NESTED_PATTERN = String.format("" +
        "(" +                      // save in $1
        "^" +                      // start of line (with MULTILINE)
        "<(%s)" +                  // start tag = $2
        "\\b" +                    // word break
        "(.*\\n)*?" +              // any number of lines, minimally matching
        "</\\2>" +                 // the matching end tag
        "[ \\t]*" +                // trailing spaces/tags
        "(?=\\n+|\\Z)" +           // followed by a newline or end of
        ")", BLOCK_TAGS_1);

转换为:

(^<(p|div|h[1-6]|blockquote|pre|table|dl|ol|ul|script|noscript|form|fieldset|iframe|math|ins|del)\b(.*\n)*?</\2>[ \t]*(?=\n+|\Z))

此模式正在查找锚定到行开头的接受块标记,后跟任意数量的行,然后由匹配标记后跟换行符或字符串终止符终止.这会产生:

java.lang.StackOverflowError
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
    at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227)
    at java.util.regex.Pattern$BmpCharProperty.match(Pattern.java:3366)
    at java.util.regex.Pattern$Curly.match0(Pattern.java:3782)
    at java.util.regex.Pattern$Curly.match(Pattern.java:3744)
    at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168)
    at java.util.regex.Pattern$LazyLoop.match(Pattern.java:4357)
        ...

这可以通过增加Java的堆栈空间来处理(默认为oss/ss IIRC的128k/400k),但无论如何上面的表达式都很慢.

所以我正在寻找能够做得更好的正则表达大师(或者至少用这种模式解释性能问题).C#版本有点慢,但工作正常.PHP似乎也没有问题.

编辑:这是在Windows 7 64 Ultimate上运行的JDK6u17上.

Answer 1

这部分:

(.*\n)*?

因为嵌套*而会涉及很多不必要的回溯,因为之后必须匹配的字符.

我只是在一些任意字符串上运行perl的快速基准测试,只需将该部分切换为13-15%即可

(?>.*\n)*?

这是非捕获,独立的子组.这给你带来了两个好处,它不再浪费时间捕获匹配的字符串,更重要的是,它不再在最里面回溯,.*这无论如何浪费时间.没有办法只有那部分.*会产生有效的匹配,所以明确地将它全部或全部都没有帮助.

但是,不知道在这种情况下这是否足够改进.