用于匹配开始/结束标记的Java正则表达式会导致堆栈溢出

Question

Java Pattern该类的标准实现使用递归来实现许多形式的正则表达式(例如,某些运算符,交替).

这种方法导致堆栈溢出问题,输入字符串超过(相对较小)长度,甚至可能不超过1,000个字符,具体取决于所涉及的正则表达式.

一个典型的例子是以下正则表达式,使用交替Data从周围的XML字符串中提取可能的多行元素(命名),该字符串已经提供:

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

上面的正则表达式用于Matcher.find()读取"数据"捕获组并按预期工作的方法,直到提供的输入字符串的长度超过1,200个字符左右,在这种情况下,它会导致堆栈溢出.

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

Answer 1

关于堆栈溢出问题的原因的更多细节:

有时候正则表达式Pattern会抛出一个StackOverflowError.这是已知错误#5050507的一种表现形式,java.util.regex自Java 1.4以来一直存在于包中.这个错误就在这里,因为它有"不会修复"的状态.发生此错误是因为Pattern类将正则表达式编译为一个小程序,然后执行该程序以查找匹配项.此程序以递归方式使用,有时当进行过多的递归调用时会发生此错误.有关更多详细信息,请参阅错误说明.它似乎主要是由交替使用引发的.

你的正则表达式(有替代)匹配两个标签之间的任何1+个字符.

您可以使用延迟点匹配模式与Pattern.DOTALL修饰符(或等效的嵌入标志(?s)),这将使.匹配换行符号:

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

看到这个正则表达式演示

但是,在巨大输入的情况下,惰性点匹配模式仍会占用大量内存.最好的方法是使用unroll-the-loop方法:

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

请参阅正则表达式演示

细节:

• <Data> - 文字文字 <Data>
• (?<data> - 开始捕获组"数据"
  • [^<]* - 除零之外的零个或多个字符 <
  • (?:<(?!/?Data>)[^<]*)* - 0个或更多序列:
    • <(?!/?Data>)- a <后面没有Data>或/Data>
    • [^<]* - 除零之外的零个或多个字符 <
• ) - "数据"组的结尾
• </Data> - 结算分隔符