Разбираем большие строки с помощью Regex для получения java.lang.StackOverflowError ошибки

Question

Это мой Regex

"(?<=\"body\":\")((?=\",|\"$)|.)+" 

Он размечает строку на теле. Например,

"body":its my string 

Результат

its my string 

Но когда я использую большую входную строку я получаю эту ошибку

Exception in thread "main" java.lang.StackOverflowError 
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168) 
at java.util.regex.Pattern$Loop.match(Pattern.java:4295) 
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227) 
at java.util.regex.Pattern$BranchConn.match(Pattern.java:4078) 
at java.util.regex.Pattern$CharProperty.match(Pattern.java:3345) 
at java.util.regex.Pattern$Branch.match(Pattern.java:4114) 
at java.util.regex.Pattern$GroupHead.match(Pattern.java:4168) 
at java.util.regex.Pattern$Loop.match(Pattern.java:4295) 
at java.util.regex.Pattern$GroupTail.match(Pattern.java:4227) 

Как это вызвало и как я могу решить эту проблему?

Answer 1

Похоже, вы пытаетесь захватить содержимое строки RHS и в то же время гарантируете, что ему предшествует "body":", а затем ".

Вы, кажется, используете утверждения lookaround для проверки наличия окружающего текста, но вы также используете группу захвата для захвата содержимого строки RHS. Вам не нужно делать обе эти вещи. Утверждения Lookaround: zero-width, что означает, что они не станут частью окончательной подстроки. Конечная согласованная подстрока всегда доступна как группа захвата 0. В качестве альтернативы вы можете полностью сопоставить все компоненты регулярного выражения (что означает соответствие без нулевой ширины, что означает отсутствие обратных ссылок), и использовать группу захвата для извлечения интересующей подстроки, но это было бы менее эффективны.

Вот как я думаю, что это должно быть написано (соответствие с args[0] для этой демонстрации):

Pattern p = Pattern.compile("(?<=\"body\":\")[^\"]*(?=\")"); 
Matcher m = p.matcher(args[0]); 
if (!m.find(0)) { System.out.println("doesn't match!"); System.exit(1); } 
System.out.println(m.group(0)); 

Вышеперечисленные работы для меня с довольно большими строками.

---

я пытаюсь воспроизвести StackOverflowError исключение, и мне это удалось. Мне кажется, что механизм регулярных выражений Java использует рекурсию для реализации соответствия повторяющихся чередования. Это очень удивительно для меня, поскольку я не знаю, почему рекурсия была бы необходима, чтобы соответствовать повторным чередованиям. Тем не менее, я также немного поработал с регулярными выражениями Perl, которые я всегда считал самым мощным и надежным регулярным выражением, и обнаружил, что Perl терпит неудачу точно так же, как Java обычные выражения.

Ниже приведен пример этого, в котором показаны как ошибки Java, так и ошибки Perl. Для этой демонстрации я сменил атом [^"] на чередование (?:\\.|[^"]), что эффективно добавляет поддержку кодов возврата обратной косой черты, встроенных в строку с двумя кавычками, например \", для кодирования встроенной двойной кавычки, которая обычно поддерживается во многих средах программирования.

Java

Pattern p = Pattern.compile("(?<=\"body\":\")(?:\\\\.|[^\"])*(?=\")"); 
Matcher m = p.matcher(args[0]); 
if (!m.find(0)) { System.out.println("doesn't match!"); System.exit(1); } 
System.out.println(m.group(0)); 

Выходной

Exception in thread "main" java.lang.StackOverflowError 
    at java.util.regex.Pattern$CharProperty.match(Unknown Source) 
    at java.util.regex.Pattern$Branch.match(Unknown Source) 
    at java.util.regex.Pattern$GroupHead.match(Unknown Source) 
    at java.util.regex.Pattern$Loop.match(Unknown Source) 
    at java.util.regex.Pattern$GroupTail.match(Unknown Source) 
    at java.util.regex.Pattern$BranchConn.match(Unknown Source) 
    at java.util.regex.Pattern$CharProperty.match(Unknown Source) 
    at java.util.regex.Pattern$Branch.match(Unknown Source) 
    at java.util.regex.Pattern$GroupHead.match(Unknown Source) 
    at java.util.regex.Pattern$Loop.match(Unknown Source) 
    at java.util.regex.Pattern$GroupTail.match(Unknown Source) 
... 

Perl (из оболочки)

largeString="\"body\":\"$(perl -e 'use strict; use warnings; for (my $i = 0; $i < 2**15; ++$i) { print("x"); }';)\""; 
perl -e 'use strict; use warnings; my $re = qr((?<="body":")(?:\\.|[^"])*(?=")); if ($ARGV[0] !~ $re) { print("didn'\''t match!\n"); } print($&);' "$largeString"; 

Выход

Complex regular subexpression recursion limit (32766) exceeded at -e line 1. 
didn't match! 
Use of uninitialized value $& in print at -e line 1. 

Так, просто уточнить, почему мое решение дается около начала моего ответа позволяет избежать этой ошибки переполнения стека не потому, что я удалил захват группы 1, а потому, что я удалил чередованием. Опять же, я не знаю, почему повторяющиеся чередования реализованы с рекурсией, но, учитывая этот факт, кажется логичным, что большая строка ввода приведет к ошибке переполнения стека.