Явление, которое вы наблюдаете, связано с тем, что рекурсия 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", PCRE находит палиндром "aba" в начале, но завершается ошибкой на верхнем уровне, потому что конец строки не следует.Еще раз, он не может вернуться в рекурсию, чтобы попробовать другие альтернативы, поэтому все совпадения не удаются.
Дополнительные ссылки
- регулярные-выражения.info /Атомная группировка
(?>…) в некотором роде имеет синтаксис атомной группировки - Внешний вид
(?=…), (?!…), (?<=…), (?<!…), все атомные - Асессивный квантификатор (например,
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 n -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 n -1 раз". Это может действительно соответствовать "abcba" (, как видно на ideone.com ). Однако он НЕ МОЖЕТ совпадать с "ababa" и не может совпадать с "aaaaa" (см. ПРЕДУПРЕЖДЕНИЕ на странице руководства!), Поскольку рекурсия подшаблона в PCRE является атомарной.
Вы можете применить этот же процесс трассировки для объяснения поведения шаблона на любом входе.