java - 多行字符串文字的正则表达式产生 `StackOverflowError`
问题描述
我想匹配包含在三"
引号中的字符串,这些字符串可能包含换行符,并且"""
除了开头和结尾之外不包含任何子字符串。
有效示例:
"""foo
bar "baz" blah"""
无效示例:
"""foo bar """ baz"""
我尝试使用以下正则表达式(作为 JavaString
文字):
"(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*\"\"\""
它似乎适用于简短的例子。但是,在较长的示例中,例如在hello world
包含StackOverflowError
.
重现错误的 Scala 片段
import java.util.regex.{Pattern, Matcher}
val text = "\"" * 3 + "hello world \n" * 1000 + "\"" * 3
val p = Pattern.compile("(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*\"\"\"")
println(p.matcher("\"\"\" foo bar baz \n baz bar foo \"\"\"").lookingAt())
println(p.matcher(text).lookingAt())
(注意:在本地测试,Scastie 超时;或者可能将 1000 减少到更小的数字?)。
产生相同错误的 Java 片段
import java.util.regex.Pattern;
import java.util.regex.Matcher;
class RegexOverflowMain {
public static void main(String[] args) {
StringBuilder bldr = new StringBuilder();
bldr.append("\"\"\"");
for (int i = 0; i < 1000; i++) {
bldr.append("hello world \n");
}
bldr.append("\"\"\"");
String text = bldr.toString();
Pattern p = Pattern.compile("(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*\"\"\"");
System.out.println(p.matcher("\"\"\" foo bar baz \n baz bar foo \"\"\"").lookingAt());
System.out.println(p.matcher(text).lookingAt());
}
}
问题
StackOverflowError
任何想法如何使这个“堆栈安全”,即有人可以找到一个接受相同语言的正则表达式,但在提供给 Java 正则表达式 API 时不会产生?
我不在乎解决方案是使用 Scala 还是 Java(或其他),只要使用相同的底层 Java regex 库即可。
解决方案
下面的完整答案优化了正则表达式的性能,但为了防止堆栈溢出,作为一个简单的解决方案,只需将重复组设为所有格即可。
具有选择的非占有重复组需要递归调用以允许回溯。使其具有所有格可以解决问题,因此只需在:+
之后添加一个*
:
"(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*+\"\"\""
另请注意,如果要匹配整个输入,则需要调用matches()
,而不是lookingAt()
。
性能提升
注意:快速性能测试表明这比x4rf41 回答的正则表达式快 6 倍以上。
而不是匹配其中之一
- 不是报价单:
[^\"]
- 正好一个报价:
(?:\"[^\"])
- 正好两句:
(?:\"\"[^\"])
在一个循环中,首先将所有内容与报价相匹配。如果那是单引号或双引号,但不是三引号,则匹配 1-2 个引号,然后所有内容直到下一个引号,根据需要重复。最后匹配结尾的三引号。
这种匹配是确定的,所以使重复具有所有格。如果输入有许多嵌入式引号,这也可以防止堆栈溢出。
"{3} match 3 leading quotes
[^"]*+ match as many non-quotes as possible (if any) {possesive}
(?: start optional repeating group
"{1,2} match 1-2 quotes
[^"]++ match one or more non-quotes (at least one) {possesive}
)*+ end optional repeating group {possesive}
"{3} match 3 trailing quotes
由于您不使用^
or $
,因此不需要(?m)
( MULTILINE )
作为 Java 字符串:
"\"{3}[^\"]*+(?:\"{1,2}[^\"]++)*+\"{3}"
推荐阅读
- node.js - Node.js 操作系统包 CPUS [对象] [对象]
- google-chrome - 有没有办法在 Chrome 开发者工具中隐藏 Box-Model 图形?
- java - 如何仅在 java 中将 13 位 unix 毫秒转换为小时
- python - 将字符串与前一行和连续行进行比较以检查是否按字母顺序
- java - 如何设计带圆角的 JButton?
- java - 使用Docx4j将.docx逐页转换为.png,将其他格式转换为png
- compiler-construction - 如何用 Python 或 GoLang 为静态类型 DSL(领域特定语言)编写解释器?
- hadoop - Sqoop 作业被自动终止
- java - Java初学者-试图让玩家退出游戏
- ios - 通用链接未重定向到 iOS 应用