Почему это рекурсивное регулярное выражение совпадает только тогда, когда персонаж повторяется 2^n - 1 раз?

Question

После прочтения серии статей Polygenelubricants о передовых методах регулярных выражений (в частности, Как этот регулярный код Java обнаруживает палиндромы?), Я решил попытаться создать свой собственный регулярный выражения PCRE для анализа палиндрома, используя рекурсию (в PHP).

То, что я придумал, было:

^(([a-z])(?1)\2|[a-z]?)$

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

К сожалению, похоже, что это не работает, как вы можете видеть на http://www.ideone.com/a9T3F. Вместо этого только строки 2 ⁿ - 1 (т.е. пустая строка, a, aaa, aaaaaaa, ¹⁵) повторяющиеся символы соответствуют регулярному выражению.

Странно, если я изменю свой шаблон так, чтобы рекурсия была необязательной (т.е. ^(([a-z])(?1)?\2|[a-z]?)$ см. http://www.ideone.com/D6lJR, он соответствует только строкам с символом, повторенным 2 ⁿ раз (т.е. пустая строка, a, aa, aaaa, aaaaaaaa ¹⁶).

Почему мое регулярное выражение не работает так, как я ожидаю?

Примечание для людей, которые жаждут предложить не использовать регулярные выражения:
Задача этого вопроса - научиться правильно использовать рекурсивные регулярные выражения. Я знаю, что это не эффективный способ определить, является ли строка палиндромом, и я бы не использовал рекурсивное регулярное выражение, если бы мне по какой-то причине пришлось определять палиндромы в производственном коде; Мне просто интересно узнать больше о продвинутых аспектах регулярных выражений.

Answer 1

Явление, которое вы наблюдаете, связано с тем, что рекурсия PCRE-субпаттерна является атомарной, в отличие от Perl. Страница man на самом деле подробно описывает эту проблему:

В PCRE (как в Python, но в отличие от Perl) рекурсивный вызов подшаблона всегда обрабатывается как атомарная группа. То есть, после того, как он сопоставил некоторую строку темы, он никогда не будет введен повторно, даже если он содержит непроверенные альтернативы и последующий сбой сопоставления.

Это можно проиллюстрировать следующим шаблоном, который подразумевает совпадение с палиндромной строкой, содержащей нечетное количество символов (например, "a", "aba", "abcba", "abcdcba"):

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

Идея состоит в том, что он соответствует либо одному символу, либо двум одинаковым символам, окружающим подпалиндром. В Perl этот шаблон работает; в PCRE этого не происходит, если шаблон длиннее трех символов.

Рассмотрим строку темы "abcba":

На верхнем уровне первый символ сопоставляется, но, поскольку он не находится в конце строки, первая альтернатива завершается неудачно; вторая альтернатива берется и рекурсия запускается. Рекурсивный вызов subpattern 1 успешно соответствует следующему символу ("b"). (Обратите внимание, что тесты начала и конца строки не являются частью рекурсии).

Вернуться на верхний уровень, следующий персонаж ("c") сравнивается с тем, что соответствует подшаблону 2, который был "a", Это не удается. Поскольку рекурсия рассматривается как атомарная группа, теперь нет точек возврата, и поэтому все совпадение не выполняется. (В этот момент Perl может повторно войти в рекурсию и попробовать второй вариант.) Однако, если шаблон написан с альтернативами в другом порядке, все будет иначе:

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

На этот раз сначала проверяется рекурсивная альтернатива, и она продолжает повторяться до тех пор, пока не закончатся символы, после чего рекурсия завершится неудачно. Но на этот раз у нас есть другая альтернатива, чтобы попробовать на более высоком уровне. Это большая разница: в предыдущем случае оставшаяся альтернатива находится на более глубоком уровне рекурсии, который PCRE не может использовать.

Чтобы изменить шаблон так, чтобы он соответствовал всем палиндромным строкам, а не только тем, которые имеют нечетное количество символов, заманчиво изменить шаблон на такой:

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

Опять же, это работает в Perl, но не в PCRE, и по той же причине. Когда более глубокая рекурсия соответствует одному символу, она не может быть введена снова, чтобы соответствовать пустой строке. Решение состоит в том, чтобы отделить два случая и записать нечетные и четные варианты в качестве альтернатив на более высоком уровне:

    ^(?:((.)(?1)\2|)|((.)(?3)\4|.))$

---

ПРЕДУПРЕЖДЕНИЕ!!!

Приведенные выше шаблоны соответствия палиндрому работают только в том случае, если строка субъекта не начинается с палиндрома, который короче всей строки. Например, хотя "abcba" правильно подобран, если предмет "ababa"ПКЭ находит палиндром "aba" в начале, затем не удается на верхнем уровне, потому что конец строки не следует. Еще раз, он не может вернуться в рекурсию, чтобы попробовать другие альтернативы, поэтому весь матч не удался.

Дополнительные ссылки

• регулярные выражения.info/Атомная группировка
  • (?>…) в некотором роде синтаксис атомной группировки
  • Lookarounds (?=…), (?!…), (?<=…), (?<!…) Все атомные
  • Притяжательный квантификатор (например, a*+) также атомный
  • PCRE рекурсивные вызовы подшаблонов и подпрограмм также являются атомарными

---

Присмотритесь к шаблону

Аргумент атомности верен, но, возможно, не очевидно, как он объясняет, почему модель ведет себя так, как наблюдается. Давайте внимательнее посмотрим, как все это подходит:

Мы будем использовать первый шаблон:

^(([a-z])(?1)\2|[a-z]?)$

Я буду использовать следующие обозначения для обозначения рекурсии:

• 1 означает, что персонаж был захвачен в группу 2 в первом заместителе
• 2 означает, что персонаж был подобран вторым заместителем
  • Или если 2 не выше символа, опция нулевого повторения ? осуществляется
• \ означает, что символ соответствует обратной ссылке на группу 2 в первой альтернативе
• _ обозначает дно рекурсивной ветви
  • Эта ветвь НЕ будет возвращена, даже если есть другие альтернативы!

Теперь давайте рассмотрим "aaa" как вход:

      _
1 1 1 2 
a a a   # This is the first bottom of the recursion,
        # now we go back to the third 1 and try to match \.
        # This fails, so the third 1 becomes 2.
    _
1 1 2
a a a   # Now we go back to the second 1 and try to match \.
        # This fails, so the second 1 becomes 2.
  _
1 2
a a a   # The second level matched! now we go back to the first level...

_____
1 2 \
a a a   # Now the first 1 can match \, and entire pattern matches!!

---

Теперь рассмотрим "aaaaa":

          _
1 1 1 1 1 2
a a a a a  # Fifth 1 can't match \, so it becomes 2. 
        _
1 1 1 1 2
a a a a a  # Fourth 1 can't match \, so it becomes 2.
    _____
1 1 1 2 /
a a a a a  # Here's a crucial point. The third 1 successfully matched.
           # Now we're back to the second 1 and try to match \, but this fails.
           # However, since PCRE recursion is atomic, the third 1 will NOT be
           # reentered to try 2. Instead, we try 2 on the second 1.
_____
1 2 \
a a a a a  # Anchors don't match, so the first 1 becomes 2, and then also the
           # anchors don't match, so the pattern fails to match.

Обратите внимание, что при совпадении уровня рекурсии для первой альтернативы вторая альтернатива не будет предприниматься в будущем (даже если это может привести к совпадению), поскольку рекурсия PCRE-подшаблона является атомарной.

---

Теперь рассмотрим "aa":

    _
1 1 2 
a a
  _
1 2
a a  # The second level matched by taking the one repetition option on ?.
     # We now go back to the first level, and we can't match \.
     # Since PCRE recursion is atomic, we can't go back to the second level
     # to try the zero repetition option on ?.
_    
2
a a  # Anchors don't match, trying zero option on ? also doesn't help,
     # so the pattern fails to match!

Обратите внимание, что как только уровень рекурсии совпадает с одним повторением ? по второму варианту опция нулевого повторения не будет использоваться в будущем (даже если это может привести к совпадению), потому что рекурсия PCRE подшаблона является атомарной.

---

Теперь давайте рассмотрим aaaaaaa

              _
1 1 1 1 1 1 1 2  
a a a a a a a 
            _
1 1 1 1 1 1 2  
a a a a a a a 
        _____
1 1 1 1 1 2 \  
a a a a a a a  # A crucial point: the fifth level matched and now the fourth
               # level can't match \, but it does NOT reenter the fifth level to
               # try 2. Instead, the fourth level tries 2.
    _____    
1 1 1 2 \  
a a a a a a a 
  _________    
1 1 1 2 \ \ 
a a a a a a a 
_____________    
1 1 1 2 \ \ \
a a a a a a a  # Entire pattern is a match! 

Обратите внимание, что хотя рекурсия PCRE-подшаблона является атомарной, она все равно может успешно соответствовать палиндрому, состоящему из символов, повторяющихся 2 ⁿ -1 раз.

---

Теперь просто для удовольствия, давайте попробуем "abcba":

          _
1 1 1 1 1 2
a b c b a
        _
1 1 1 1 2
a b c b a

1 1 1 2 
a b c b a   # Third level attempts \, but c does not match a!
            # So we go back to third 1 and try 2.
  _____
1 1 2 \ 
a b c b a 
_________
1 1 2 \ \
a b c b a   # Entire pattern is a match!

То есть шаблон не просто совпадает "только когда персонаж повторяется 2 ⁿ -1 раз". Это действительно может соответствовать "abcba" ( как видно на ideone.com). Это не может, однако, соответствовать "ababa" и не может совпадать "aaaaa" (см. ПРЕДУПРЕЖДЕНИЕ на странице руководства!), потому что рекурсия подшаблона в PCRE является атомарной.

Вы можете применить этот же процесс трассировки, чтобы объяснить поведение шаблона на любом входе.

Answer 2

Если вы хотите, чтобы полнофункциональное выражение PCRE соответствовало палиндромам, вы можете использовать следующее:

/^(?:(.)(?=.*(\1(?(2)\2))$))*+.?\2?$/