Java正则表达式出现堆栈溢出错误：需要更好的版本

Question

我正在开发一个JMD（Java MarkDown）（MarkDownSharp的Java移植版），但我遇到了一个特定正则表达式的问题。对于文件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的堆栈空间来解决这个问题（默认为128k / 400k，如果我没记错的话），但上述表达式仍然很慢。

因此，我正在寻找一个正则表达式大师，他可以做得更好（或者至少解释一下这个模式的性能问题）。 C＃版本有点慢，但运行良好。 PHP似乎也没有这个问题。

编辑：这是在Windows 7 64 Ultimate上运行的JDK6u17。

- cletus

---

这个正则表达式的使用非常糟糕。您必须使用正则表达式吗？或者您可以将其重构为真正的递归解析器（LR或递归下降）？ - Jim Garrison

你尝试过将 .*\n 替换为 .*?\n 吗？ - YOU

@Jim：我的第一个目标是获得功能等效的代码版本，并具有广泛的单元测试覆盖率。这些正则表达式来自MarkdownSharp（以及在此之前，可能来自原始的Perl Markdown脚本）。一步步来。 - cletus

@cletus：看起来你的测试类没有包含在jmd-0.8.0-sources.jar下载中。有计划添加吗？ - Bill the Lizard

@Bill：我已上传了一个测试JAR文件。 - cletus

Answer 1

这一部分：

(.*\n)*?

由于嵌套的*和之后必须匹配的字符，将会涉及很多不必要的回溯。

我在一些随意的字符串上快速进行了Perl基准测试，并通过将该部分切换到另一种方式来获得13-15％的改进。

(?>.*\n)*?

这个正则表达式使用了非捕获、独立的子组。这样做有两个好处，一是不再浪费时间捕获匹配的字符串，更重要的是不再在内部的.*上回溯，而这样的回溯是无用的。因为不可能只有这个.*的一部分会得到有效的匹配结果，所以明确地将其全部匹配或全部不匹配应该会更有帮助。

但不确定在这种情况下是否足够改进。

- Rob Van Dam

---

有一个更复杂的正则表达式，但是使用?>查询忽略解决了问题！谢谢。 - Saito Mea

Answer 2

“虽然改善模式可以帮助并且是明智的，但Java的模式匹配器是递归的，通常最好切换到迭代解决方案。当我遇到类似的问题时，我转向了jregex（http://jregex.sourceforge.net/），这对我很有用。尽管通过改进的解决方案可能已经成功匹配了模式，但如果给出10倍大的文本，则可能会失败。 PS：抱歉打扰一个旧话题，但此主题在谷歌上排名很高，如果我将其放在这里，将有益于人们。”

- Harsh

Answer 3

子表达式："(.*\\n)*?"（以及改进的被接受答案版本："(?>.*\n)*?"）都存在一个问题：它们无法匹配写在一行上的块元素。换句话说，它们无法匹配这个：

<div>one-liner</div>

如果这不是期望的行为，一个正确（且更有效）的解决方案是简单地使用：.*? 并打开单行模式。

- ridgerunner