时间戳

首页 > 解决方案 > 简单的正则表达式在 Scala/Java 中的大字符串上出现 stackoverflow 失败

java - 简单的正则表达式在 Scala/Java 中的大字符串上出现 stackoverflow 失败

问题描述

我需要一个正则表达式来检查它是否是一个带引号的（由'）字符串，里面可能有转义的\'。所以，我想出了以下正则表达式，\'(\\.|[^\'])*\'.

"""\'(\\.|[^\'])*\'""".r.findFirstIn(s"'${"a"*100}'")

它适用于小字符串，但stack overflow在大小 > 3000 字节时失败。

"""\'(\\.|[^\'])*\'""".r.findFirstIn(s"'${"a"*5000}'")

这是 Scala 片段。它在内部运行java.util.regex，所以这是 java/jvm 问题。

据我所知，那些简单的正则表达式不应该导致stack overflow，它是一个简单的 DFA/NFA，内部没有任何递归。

如何解决这个问题？

我需要正则表达式（这是解析器组合器代码的一部分，我不能只编写检查属性的自定义代码）。

为什么里面有递归？

标签： javaregexscala

解决方案

您可以尝试J. Friedl 概述的经典展开循环技术：

'                              # the start delimiter
 ([^\\']*                      # anything but the end of the string or the escape char
         (?:\\.                #     the escape char preceding an escaped char (any char)
               [^\\']*         #     anything but the end of the string or the escape char
                      )*)      #     repeat
                             ' # the end delimiter

正则表达式 101 演示

推荐阅读