Как механизм регулярных выражений анализирует регулярное выражение с рекурсивными подшаблонами?

Это регулярное выражение соответствует палиндромам: ^((.)(?1)\2|.?)$

Не могу понять, как это работает. Когда заканчивается рекурсия и когда регулярное выражение прерывается из рекурсивного подшаблона и переходит в "|.?" часть?

Спасибо.

изменить: извините, я не объяснил \2 и (?1)

(?1) - относится к первому подшаблону (самому себе)

\2 - обратная ссылка на совпадение второго подшаблона, то есть (.)

Выше пример написан на PHP. Соответствует как «abba» (без символа среднего палиндрома), так и «abcba» - имеет средний неотраженный символ.

alexy2k 26.07.2012 источник

comment

Это, вероятно, было бы лучше для программистов, поскольку это действительно не практический вопрос. - Jeff 26.07.2012

comment

.?, вероятно, для строк нечетной длины. - nhahtdh 26.07.2012

comment

Извините, но могу я узнать, что такое (?1) и \2? - Alvin Wong 26.07.2012

comment

Perl имеет лучшие инструменты отладки, чем PCRE, попробуйте: echo 123454321 | perl -Mre=debug -ne '/^((.)(?1)\2|.?)$/x' - ninjalj 26.07.2012

comment

@AlvinWong: (?1) = переход в группу 1, \2 = обратная ссылка для соответствия из группы 2 - ninjalj 26.07.2012

Ответы (3)

arrow_upward
4
arrow_downward

^((.)(?1)\2|.?)$

^ и $ обозначают начало и конец строки соответственно. Давайте посмотрим на промежуточный контент, который более интересен:

((.)(?1)\2|.?)
1------------1 // Capturing group 1
 2-2           // Capturing group 2

Посмотрите на первую часть (.)(?1)\2, мы видим, что она будет пытаться сопоставить любой символ и тот же самый символ в конце (обратная ссылка \2, которая относится к символу, сопоставленному с (.)). В середине он будет рекурсивно соответствовать всей группе захвата 1. Обратите внимание, что существует неявное утверждение (вызванное (.) совпадением одного символа в начале и \2 совпадением того же символа в конце), которое требует, чтобы строка была как минимум 2 персонажа. Цель первой части - рекурсивно перерезать идентичные концы строки.

Посмотрите на вторую часть .?, мы видим, что она соответствует одному или 0 символу. Это будет сопоставлено только в том случае, если строка изначально имеет длину 0 или 1 или после того, как остаток от рекурсивного сопоставления составляет 0 или 1 символ. Цель второй части - сопоставить пустую строку или единственный одинокий символ после того, как строка разрезана с обоих концов.

Рекурсивное сопоставление работает:

Вся строка должна быть палиндромом для передачи, как утверждают ^ и $. Мы не можем начать сопоставление с любой случайной позиции.
Если строка содержит ‹= 1 символ, она проходит.
Если строка содержит более 2 символов, то, будет ли она принята, решает только первая часть. И при совпадении он будет нарезан на 2 конца.
Остаток, если он совпадает, может быть разрезан только двумя концами или пройден, если его длина ‹= 1.

nhahtdh 26.07.2012

comment

Спасибо за ответ. Я отредактировал исходный пост с дополнительными пояснениями. \2 - это не длина. - alexy2k; 26.07.2012

comment

\2 не является длиной, но он заставляет это выражение содержать не менее двух символов, потому что один символ не может соответствовать одновременно (.) и обратной ссылке \2. - Sam Mussmann; 26.07.2012

comment

Каждый раз, когда он повторяется из-за первой части, он обрабатывает строку с удаленными двумя конечными символами. В конце концов он сжимается до 0 или 1 символа, затем соответствует вторая часть и рекурсия останавливается. - Barmar; 26.07.2012

comment

Признаюсь, это немного сбивает с толку. Я отредактировал свой пост, но не уверен, что он понятнее. - nhahtdh; 26.07.2012

comment

Ответ принят. Спасибо! Я админ, у меня все еще проблемы с пониманием этого, возможно, мне нужно изучить автоматы. еще один вопрос: когда функция вызывает себя, она возвращается, когда достигает нижнего состояния (скажем, 1 при вычислении факториала), и умножает это на результаты предыдущего вызова, но когда здесь достигается конечное состояние? В какой момент движок регулярных выражений переходит сейчас, я ищу совпадение \ 2 в обратном порядке, один за другим, если это имеет смысл? - alexy2k; 26.07.2012

comment

@ alexy2k: Я не знаю, как работает движок регулярных выражений. Я предполагаю, что он сначала тупо перейдет в рекурсивное совпадение (?1), затем оно будет соответствовать \2 (поскольку в общем регулярном выражении вы не узнаете, есть ли впереди еще рекурсивные группы). Это скорее предположение, поэтому не воспринимайте этот комментарий слишком серьезно. - nhahtdh; 26.07.2012

arrow_upward
4
arrow_downward

Регулярное выражение по существу эквивалентно следующему псевдокоду:

palin(str) {
    if (length(str) >= 2) {
      first = str[0];
      last = str[length(str)-1];
      return first == last && palin(substr(str, 1, length(str)-2));
    } else
      // empty and single-char trivially palindromes
      return true;
}

Barmar 26.07.2012

arrow_upward
1
arrow_downward

Я не нашел хорошей отладочной утилиты для регулярных выражений PCRE. Больше я смог найти, как сбросить байт-код:

$ pcretest -b
PCRE version 7.6 2008-01-28

  re> /^((.)(?1)\2|.?)$/x
------------------------------------------------------------------
  0  39 Bra
  3     ^
  4  26 CBra 1
  9   6 CBra 2
 14     Any
 15   6 Ket
 18   6 Once
 21   4 Recurse
 24   6 Ket
 27     \2
 30   5 Alt
 33     Any?
 35  31 Ket
 38     $
 39  39 Ket
 42     End
------------------------------------------------------------------

Perl имеет лучшие инструменты отладки, чем PCRE, попробуйте echo 123454321 | perl -Mre=debug -ne '/^((.)(?1)\2|.?)$/x'. Это дает не только некоторый байт-код, похожий на байт-код PCRE, но также показывает каждый шаг, а также потребляемые и оставшиеся части ввода на каждом шаге:

Compiling REx "^((.)(?1)\2|.?)$"
Final program:
   1: BOL (2)
   2: OPEN1 (4)
   4:   BRANCH (15)
   5:     OPEN2 (7)
   7:       REG_ANY (8)
   8:     CLOSE2 (10)
  10:     GOSUB1[-8] (13)
  13:     REF2 (19)
  15:   BRANCH (FAIL)
  16:     CURLY {0,1} (19)
  18:       REG_ANY (0)
  19: CLOSE1 (21)
  21: EOL (22)
  22: END (0)
floating ""$ at 0..2147483647 (checking floating) anchored(BOL) minlen 0 
Guessing start of match in sv for REx "^((.)(?1)\2|.?)$" against "12321"
Found floating substr ""$ at offset 5...
Guessed: match at offset 0
Matching REx "^((.)(?1)\2|.?)$" against "12321"
   0 <> <12321>              |  1:BOL(2)
   0 <> <12321>              |  2:OPEN1(4)
   0 <> <12321>              |  4:BRANCH(15)
   0 <> <12321>              |  5:  OPEN2(7)
   0 <> <12321>              |  7:  REG_ANY(8)
   1 <1> <2321>              |  8:  CLOSE2(10)
   1 <1> <2321>              | 10:  GOSUB1[-8](13)
   1 <1> <2321>              |  2:    OPEN1(4)
   1 <1> <2321>              |  4:    BRANCH(15)
   1 <1> <2321>              |  5:      OPEN2(7)
   1 <1> <2321>              |  7:      REG_ANY(8)
   2 <12> <321>              |  8:      CLOSE2(10)
   2 <12> <321>              | 10:      GOSUB1[-8](13)
   2 <12> <321>              |  2:        OPEN1(4)
   2 <12> <321>              |  4:        BRANCH(15)
   2 <12> <321>              |  5:          OPEN2(7)
   2 <12> <321>              |  7:          REG_ANY(8)
   3 <123> <21>              |  8:          CLOSE2(10)
   3 <123> <21>              | 10:          GOSUB1[-8](13)
   3 <123> <21>              |  2:            OPEN1(4)
   3 <123> <21>              |  4:            BRANCH(15)
   3 <123> <21>              |  5:              OPEN2(7)
   3 <123> <21>              |  7:              REG_ANY(8)
   4 <1232> <1>              |  8:              CLOSE2(10)
   4 <1232> <1>              | 10:              GOSUB1[-8](13)
   4 <1232> <1>              |  2:                OPEN1(4)
   4 <1232> <1>              |  4:                BRANCH(15)
   4 <1232> <1>              |  5:                  OPEN2(7)
   4 <1232> <1>              |  7:                  REG_ANY(8)
   5 <12321> <>              |  8:                  CLOSE2(10)
   5 <12321> <>              | 10:                  GOSUB1[-8](13)
   5 <12321> <>              |  2:                    OPEN1(4)
   5 <12321> <>              |  4:                    BRANCH(15)
   5 <12321> <>              |  5:                      OPEN2(7)
   5 <12321> <>              |  7:                      REG_ANY(8)
                                                        failed...
   5 <12321> <>              | 15:                    BRANCH(19)
   5 <12321> <>              | 16:                      CURLY {0,1}(19)
                                                        REG_ANY can match 0 times out of 1...
   5 <12321> <>              | 19:                        CLOSE1(21)
                                                          EVAL trying tail ... 9d86dd8
   5 <12321> <>              | 13:                          REF2(19)
                                                            failed...
                                                        failed...
                                                      BRANCH failed...
   4 <1232> <1>              | 15:                BRANCH(19)
   4 <1232> <1>              | 16:                  CURLY {0,1}(19)
                                                    REG_ANY can match 1 times out of 1...
   5 <12321> <>              | 19:                    CLOSE1(21)
                                                      EVAL trying tail ... 9d86d70
   5 <12321> <>              | 13:                      REF2(19)
                                                        failed...
   4 <1232> <1>              | 19:                    CLOSE1(21)
                                                      EVAL trying tail ... 9d86d70
   4 <1232> <1>              | 13:                      REF2(19)
                                                        failed...
                                                    failed...
                                                  BRANCH failed...
   3 <123> <21>              | 15:            BRANCH(19)
   3 <123> <21>              | 16:              CURLY {0,1}(19)
                                                REG_ANY can match 1 times out of 1...
   4 <1232> <1>              | 19:                CLOSE1(21)
                                                  EVAL trying tail ... 9d86d08
   4 <1232> <1>              | 13:                  REF2(19)
                                                    failed...
   3 <123> <21>              | 19:                CLOSE1(21)
                                                  EVAL trying tail ... 9d86d08
   3 <123> <21>              | 13:                  REF2(19)
                                                    failed...
                                                failed...
                                              BRANCH failed...
   2 <12> <321>              | 15:        BRANCH(19)
   2 <12> <321>              | 16:          CURLY {0,1}(19)
                                            REG_ANY can match 1 times out of 1...
   3 <123> <21>              | 19:            CLOSE1(21)
                                              EVAL trying tail ... 9d86ca0
   3 <123> <21>              | 13:              REF2(19)
   4 <1232> <1>              | 19:              CLOSE1(21)
                                                EVAL trying tail ... 0
   4 <1232> <1>              | 13:                REF2(19)
   5 <12321> <>              | 19:                CLOSE1(21)
   5 <12321> <>              | 21:                EOL(22)
   5 <12321> <>              | 22:                END(0)
Match successful!
Freeing REx: "^((.)(?1)\2|.?)$"

Как вы можете видеть, Perl сначала использует все рекурсивные входные данные до тех пор, пока (.) не завершится неудачно, затем начинает поиск с возвратом и пробует вторую ветвь от чередования .? и оставшуюся часть первой части \2, когда это терпит неудачу, он выполняет возврат до тех пор, пока, наконец, не завершится успешно.

ninjalj 26.07.2012

comment

Почему в этой отладке шесть OPEN1 и соответственно восемь CLOSE1? Разве не должно быть и шесть CLOSE1? - revo; 28.06.2016

Как механизм регулярных выражений анализирует регулярное выражение с рекурсивными подшаблонами?

Ответы (3)

Вопросы по теме