Простое регулярное выражение завершается ошибкой со стеком потока на большой строке в Scala / Java

Question

Мне нужно регулярное выражение, которое проверяет, является ли оно строкой в ​​кавычках ('') с возможным экранированием \ 'внутри.Итак, я придумаю следующее регулярное выражение, \'(\\.|[^\'])*\'.

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

, которое отлично работает на небольших строках, но не работает с stack overflow для размера> 3000 байт.

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

Это фрагменты Scala.Внутренне он работает java.util.regex, так что это проблема java / jvm.

Насколько мне известно, эти простые регулярные выражения не должны вызывать stack overflow, это простой DFA / NFA без какой-либо рекурсии внутри.

Как обойти эту проблему?

Мне нужно для этого регулярное выражение (это часть кода синтаксического анализатора, я не могу просто написать собственный код, который проверяет свойство).

Почему внутри есть рекурсия?

Answer 1

Это может быть связано с RegEx DOS .

Java использует традиционный алгоритм NFA [1] для поддержки таких функций, как отложенное выполнение, возврат и обратная ссылка.NFA «съедает» персонажа каждый раз и пытается сопоставить его с регулярным выражением, и «выплевывает» его, если он не совпадает.Он будет плевать до тех пор, пока не найдет другое совпадение (аналогично глубокому первому поиску), и, таким образом, некорректные выражения могут привести к тому, что механизм RegEx встретится с DOS RegEx, и, в частности, в Java, он, наконец, вызовет переполнение стека для длинных строк.

Согласно OWASP, выражения злого регулярного выражения содержат: Шаблон злого регулярного выражения содержит:

• Группировка с повторением (1)
• Внутри повторяемой группы:
  • Повтор
  • Чередование с перекрытием (2)

После краткого изучения выражения регулярного выражения,кажется, что у вас есть (1) и (2), поскольку у вас есть ()* (повторение) и \\.|[^\'] (перекрытие), поэтому я полагаю, что вам, возможно, придется реструктурировать выражение RegEx, чтобы избежать RegEx DOS.

Answer 2

Вы можете попробовать классическую технику Unrolling the Loop , изложенную Дж. Фридлом:

'                              # 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

Regex101 Demo