多行字符串文字的正则表达式产生“StackOverflowError”

Question

我想匹配包含在三重 " 引号中的字符串，这些引号可能包含换行符，并且不包含任何 """- 子字符串，除了开头和结尾.

有效示例：

"""foo
bar "baz" blah"""

无效示例：

"""foo bar """ baz"""

我尝试使用以下正则表达式（如 Java String 文字）：

"(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*\"\"\""

它似乎适用于简短的示例。然而，在更长的例子中，比如在一个由带有 hello world 的千行组成的字符串上，它给了我一个 WhosebugError.

重现错误的 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());
  }
}

问题

知道如何制作这个 "stack safe"，即有人能找到一个接受相同语言的正则表达式，但在输入 Java 正则表达式时不会产生 WhosebugError API?

我不在乎解决方案是用 Scala 还是 Java（或其他），只要使用相同的底层 Java 正则表达式库即可。

Answer 1

使用否定前瞻的解决方案基本上找到以 """ 开头并以 """ 结尾且包含不包含 """

的内容的字符串

作为普通正则表达式：^"""((?!""")[\s\S])*"""$

作为 Java 转义正则表达式："^\"\"\"((?!\"\"\")[\s\S])*\"\"\"$"

\s\S 包括换行符（它基本上是 . + 换行符或带有单行标志的 .）

这应该在没有多行标志的情况下使用，以便 ^ 和 $ 匹配字符串的开始和结束而不是行的开始和结束

否则这个：

""" ab """abc""" abc """

会匹配

我还以此为参考如何排除 """：Regular expression to match a line that doesn't contain a word?

Answer 2

下面的完整答案优化了正则表达式的性能，但为了防止堆栈溢出，作为一个简单的解决方案，只需将重复组设为 possessive.

具有选择的非占有性重复组需要递归调用以允许回溯。使其具有所有格可以解决问题，因此只需在 *:

之后添加一个 +

"(?m)\"\"\"(?:[^\"]|(?:\"[^\"])|(?:\"\"[^\"]))*+\"\"\""

另请注意，如果要匹配整个输入，则需要调用matches(), not lookingAt()。

性能提升

注意：快速性能测试表明这比 .[中的正则表达式快 6 倍 =26=]

而不是匹配

之一

不是引号：[^\"]
只有一个引号：(?:\"[^\"])
正好两个引号：(?:\"\"[^\"])

在一个循环中，首先将所有内容匹配到引号。如果那是单引号或双引号，但不是三引号，则匹配 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

因为你不使用^或$，所以不需要(?m) (MULTILINE)

作为Java字符串：

"\"{3}[^\"]*+(?:\"{1,2}[^\"]++)*+\"{3}"

多行字符串文字的正则表达式产生“StackOverflowError”

Regex for multiline string literals produces `StackOverflowError`

java

regex

stack-overflow

scala