java.util.regex.Pattern$BmpCharProperty.match 处的 java.lang.StackOverflowError(Pattern.java :3715)

Question

我在使用时收到 StackOverflowError以下 Reg Ex:

"([A-Z][A-Z]\\d\\d[A-Z]\\[(\\*|(((\\d|\\d\\d)-(\\d|\\d\\d))|(\\d|\\d\\d)))\\](,|$))+";

匹配这样的String:

RA01D[1-1],RA01D[17-17],RA01D[2-2],RA01D[18-18]

Answer 1

什么 stribizhev's answer已经指出并修复了正则表达式中的低效率。这里没有灾难性的回溯。此更改只会稍微延迟 StackOverflowError 而不会解决它(请参阅附录)。

在原始正则表达式中，如果第一个分支 (\d|\d\d)-(\d|\d\d) 失败，第二个分支将做额外的工作来匹配 (\d|\d\d) 又是第一个分支的前缀。

(
  (
    (\d|\d\d)-(\d|\d\d)
  )
  |
  (\d|\d\d)
)

重写时(如他的回答所示)，前缀(\d|\d\d)只会匹配一次，引擎只需要检查2个不同的续集(匹配 -(\d|\d\d) 或只是一个空字符串)。

(\d|\d\d)(?:-(\d|\d\d))?

这就是他的回答如何提高正则表达式的效率。同样的方法也适用于\d|\d\d。

---

回到StackOverflowError的问题。如果您对包含 1000 个元素的字符串运行正则表达式，上述任何正则表达式都会导致 StackOverflowError。这是由于Sun/Oracle/OpenJDK中Pattern类的实现，对贪婪和惰性量词使用了递归。

由于正则表达式没有歧义，您可以通过使最外层组的量词具有所有格来解决这个问题。正则表达式是从 stribizhev 的回答中复制的，并做了一些修改:

"(?:[A-Z][A-Z]\\d\\d[A-Z]\\[(?:\\*|\\d{1,2}(?:-\\d{1,2})?)\\](?:,|$))++"
                                                                     ^^

由于实现使用循环来实现所有格量词(因为不需要回溯)，所以无论输入字符串有多长，都不会发生StackOverflowError。堆栈使用量仅与单次重复一样多，这与问题中的情况相反，在这种情况下，堆栈使用量随字符串中元素的数量线性增长。

附录

测试程序

下面是一个测试程序，显示了正则表达式可以处理的元素数量。在我的系统(Oracle JRE，版本 1.8.0_25)上，问题中的正则表达式在崩溃前仅设法达到 104 * 4 = 416 个元素，stribizhev 的答案设法达到 137 * 4 = 548，stribizhev 的答案修改为删除不必要的组管理达到 150 * 4 = 600，具有所有格量词的版本通过所有测试(500 * 4 = 2000 个元素)。

public class SO29758814 {
    public static void main(String[] args) {
        String s = "";
        for (int i = 1; i <= 500; i++) {

            s += "RA01D[1-1],RA01D[17-17],RA01D[2-2],RA01D[18-18],";

            System.out.print(i);

            try {
                // Question
                System.out.print(" 1 " + s.matches("([A-Z][A-Z]\\d\\d[A-Z]\\[(\\*|(((\\d|\\d\\d)-(\\d|\\d\\d))|(\\d|\\d\\d)))\\](,|$))+"));
            } catch (Throwable e) { }

            try {
                // stribizhev's answer
                System.out.print(" 2 " + s.matches("([A-Z]{2}\\d{2}[A-Z]\\[(\\*|((\\d{1,2})(?:-(\\d{1,2}))?))\\](?:,|$))+"));
            } catch (Throwable e) { }

            try {
                // stribizhev's answer, remove unnecessary groups
                System.out.print(" 3 " + s.matches("(?:[A-Z][A-Z]\\d\\d[A-Z]\\[(?:\\*|\\d{1,2}(?:-\\d{1,2})?)\\](?:,|$))+"));
            } catch (Throwable e) { }

            try {
                // stribizhev's answer, remove unnecessary groups, use possessive quantifier
                System.out.print(" 4 " + s.matches("(?:[A-Z][A-Z]\\d\\d[A-Z]\\[(?:\\*|\\d{1,2}(?:-\\d{1,2})?)\\](?:,|$))++"));
            } catch (Throwable e) { }

            System.out.println();

        }
    }
}