Java 正则表达式匹配 start/end 标签导致堆栈溢出

Question

Java Pattern class 的标准实现使用递归来实现多种形式的正则表达式（例如，某些运算符、交替）。

对于超过（相对较小的）长度的输入字符串，这种方法会导致堆栈溢出问题，根据所涉及的正则表达式，该长度甚至可能不超过 1,000 个字符。

这方面的一个典型示例是以下正则表达式，它使用交替从周围的 XML 字符串中提取可能的多行元素（名为 Data），该字符串已提供：

<Data>(?<data>(?:.|\r|\n)+?)</Data>

上面的正则表达式与 Matcher.find() 方法一起使用来读取 "data" 捕获组并按预期工作，直到提供的输入字符串的长度超过 1,200 个字符左右，其中如果它导致堆栈溢出。

是否可以重写上述正则表达式以避免堆栈溢出问题？

Answer 1

关于 origin of the stack overflow issue 的更多详细信息：

Sometimes the regex Pattern class will throw a WhosebugError. This is a manifestation of the known bug #5050507, which has been in the java.util.regex package since Java 1.4. The bug is here to stay because it has "won't fix" status. This error occurs because the Pattern class compiles a regular expression into a small program which is then executed to find a match. This program is used recursively, and sometimes when too many recursive calls are made this error occurs. See the description of the bug for more details. It seems it's triggered mostly by the use of alternations.

您的正则表达式（具有交替）匹配两个标签之间的任何 1+ 个字符。

您可以使用带有 Pattern.DOTALL 修饰符（或等效的嵌入标志 (?s)）的惰性点匹配模式，这将使 . 也匹配换行符：

(?s)<Data>(?<data>.+?)</Data>

见this regex demo

但是，惰性点匹配模式在大量输入的情况下仍然会消耗大量内存。最好的出路是使用 unroll-the-loop method:

<Data>(?<data>[^<]*(?:<(?!/?Data>)[^<]*)*)</Data>

见regex demo

详情:

<Data> - 文字 <Data>
(?<data> - 捕获组开始 "data"
- [^<]* - <
- (?:<(?!/?Data>)[^<]*)* - 0 个或多个序列：
  - <(?!/?Data>) - < 后面没有跟 Data> 或 /Data>
  - [^<]* - <
) - "data" 组结束
</Data> - 结束分隔符

Java 正则表达式匹配 start/end 标签导致堆栈溢出

Java regex to match start/end tags causes stack overflow

java

regex

stack-overflow

matcher

pattern-matching