java - 有趣的 Java 正则表达式限制

Question

我在 Python 中尝试过相同的表达式，这里似乎没问题，而 Java 因堆栈溢出而失败。

这是演示问题的简化测试用例:

// 10k whitespace.
char[] buf = new char[10000];
Arrays.fill(buf, ' ');
String post = new String(buf);
// All whitespace - works
System.out.println(Pattern.compile(" +").matcher(post).matches());
// All whitespace, or whitespace - Stack Overflow
System.out.println(Pattern.compile("(?: | )+").matcher(post).matches());

第一个正则表达式 "+" 工作正常。第二个，"( | )+" - 显然也应该匹配这个字符串，但是会导致堆栈溢出。

我想这是由于正则表达式(特别是:备选方案)在 Java 中的实现方式的限制...基于状态机的正则表达式匹配器似乎没问题(它们将保持在接受状态)；还是 python 正则表达式引擎只是有一个更大的堆栈？

通过原子组禁用回溯也有效:"(?> | )+" - 我猜在这种情况下，Java 将不再在每个匹配项上添加 6 个堆栈帧(显然，堆栈默认情况下无法容纳 60000 帧)。

这不仅仅是一个理论上的例子。考虑例如“(苹果|香蕉)+”:

StringBuilder buf = new StringBuilder();
for (int i = 0; i < 10000; i++)
    buf.append(Math.random() < .5 ? "apple" : "banana");
String s = buf.toString();
System.out.println(s.replaceAll("(apple|banana)+", "lots of fruits"));

使用 "(?>apple|banana)+" 它将根据需要打印 lots of fruits；如果没有回溯预防，它会导致堆栈溢出。

是的，我知道这是一种灾难性的回溯...让我感到惊讶的是 Java 很早就失败了，而 Python 仍然愉快地嗡嗡作响，富有成效地删除了不需要的文本... python 更聪明，并且认识到可以在不回溯的情况下“贪婪”地处理它吗？或者它只是更好地利用内存？

Answer 1

( | )+ 是可能的 catastrophic backtracking 的一个非常基本的例子.在这种情况下，它可能更适合称为灾难性分支，因为不涉及回溯。

看起来 Java 似乎可以使用递归实现分支，尽管我不确定 10000 级深度是否足以触发溢出。它也有可能试图深入 2^10000 层，但由于我对内部结构一无所知，这纯粹是猜测。 更新:你说 1000 不足以溢出，所以它看起来绝对是线性的而不是指数的。

您为什么不尝试缩短您的字符串，看看它究竟需要多长时间才能溢出？另外，尝试像 (apple|banana)+ 这样的东西，看看它是否遇到同样的问题。 更新:该问题似乎出现在任何分支场景中。这绝对是 Java 正则表达式引擎中的一个弱点，尽管我无法告诉您确切原因。除了 Python，我可以确认它在 .NET 和 JavaScript(无论如何，我的浏览器)中工作正常。

我不认为这在 NFA 驱动的引擎中是个问题。我假设 Java 使用另一种方法，但我找不到任何地方对此进行记录。