EDIT: я выбрал ответ ridgerunner, поскольку в нем содержится информация, необходимая для решения проблемы. Но мне также хотелось добавить полностью определенное решение к конкретному вопросу, если кто-то еще захочет полностью понять пример. Вы найдете его где-то внизу.
Этот вопрос касается уточнения поведения движка regex php для рекурсивных выражений. (Если вы идете о том, как правильно соответствовать строкам ниже, не используя рекурсивное регулярное выражение php, это очень круто, но это не вопрос.)
a(?:(?R)|a?)a Это простое выражение, которое нацелено на совпадение символа «a» или ничего, вложенного в одно или несколько гнезд символа «a». Например, aa, aaa, aaaa, aaaaa. Для этого вам не нужно использовать рекурсию:
aa*a
будет отлично работать. Но дело в том, чтобы использовать рекурсию.
Вот фрагмент кода, который вы можете запустить, чтобы проверить мой неудачный шаблон:
<?php $tries=array('a','aa','aaa','aaaa','aaaaa','aaaaaa'); $regex='#a(?:(?R)|a?)a#'; foreach ($tries as $try) { echo $try." : "; if (preg_match($regex,$try,$hit)) echo $hit[0]."<br />"; else echo 'no match<br />'; } ?>
В шаблоне два «а» сгенерируют чередование. При чередовании мы либо сопоставляем рекурсию всего шаблона (два «а» с чередованием), либо символ «а», необязательно пустые.
На мой взгляд, для «aaaa» это должно соответствовать «aaaa».
Но вот вывод:
a : no match aa : aa aaa : aaa aaaa : aaa aaaaa : aaaaa aaaaaa : aaa
Может кто-нибудь объяснить, что происходит на третьей и пятой строках вывода? Я попытался проследить путь, который, как я полагаю, должен принимать двигатель, но я должен вообразить это неправильно. Почему двигатель возвращает «aaa» в соответствие с «aaaa»? Что заставляет его так стремиться? Я должен вообразить совпадающее дерево в неправильном порядке.
Я понимаю, что
#(?:a|a(?R)a)*#
но мой вопрос в том, почему другой шаблон не делает.
Спасибо, кучи!
Отличный (и сложный) вопрос!
Во-первых, с двигателем regex PCRE (?R) ведет себя как атомная группа (в отличие от Perl?). Когда он совпадает (или не совпадает), совпадение, которое произошло внутри рекурсивного вызова, является окончательным (и все патчи с возвратом назад, сохраненные в рекурсивном вызове, отбрасываются). Однако механизм регулярных выражений сохраняет все то, что соответствовало выражению целого (?R) , и может вернуть его и попробовать другую альтернативу для достижения общего соответствия. Чтобы описать, что происходит, слегка измените свой пример, чтобы было легче говорить и отслеживать, что соответствует каждому шагу. Вместо: aaaa как текст темы, позволяет использовать: abcd . И позволяет изменить регулярное выражение из '#a(?:(?R)|a?)a#' to: '#.(?:(?R)|.?).#' . Совпадение поведения регулярного выражения аналогично.
/.(?:(?R)|.?)./ to: "abcd" answer = r''' Step Depth Regex Subject Comment 1 0 .(?:(?R)|.?). abcd Dot matches "a". Advance pointers. ^ ^ 2 0 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 1). ^ ^ 3 1 .(?:(?R)|.?). abcd Dot matches "b". Advance pointers. ^ ^ 4 1 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 2). ^ ^ 5 2 .(?:(?R)|.?). abcd Dot matches "c". Advance pointers. ^ ^ 6 2 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 3). ^ ^ 7 3 .(?:(?R)|.?). abcd Dot matches "d". Advance pointers. ^ ^ 8 3 .(?:(?R)|.?). abcd Try 1st alt. Recursive call (to depth 4). ^ ^ 9 4 .(?:(?R)|.?). abcd Dot fails to match end of string. ^ ^ DEPTH 4 (?R) FAILS. Return to step 8 depth 3. Give back text consumed by depth 4 (?R) = "" 10 3 .(?:(?R)|.?). abcd Try 2nd alt. Optional dot matches EOS. ^ ^ Advance regex pointer. 11 3 .(?:(?R)|.?). abcd Required dot fails to match end of string. ^ ^ DEPTH 3 (?R) FAILS. Return to step 6 depth 2 Give back text consumed by depth3 (?R) = "d" 12 2 .(?:(?R)|.?). abcd Try 2nd alt. Optional dot matches "d". ^ ^ Advance pointers. 13 2 .(?:(?R)|.?). abcd Required dot fails to match end of string. ^ ^ Backtrack to step 12 depth 2 14 2 .(?:(?R)|.?). abcd Match zero "d" (give it back). ^ ^ Advance regex pointer. 15 2 .(?:(?R)|.?). abcd Dot matches "d". Advance pointers. ^ ^ DEPTH 2 (?R) SUCCEEDS. Return to step 4 depth 1 16 1 .(?:(?R)|.?). abcd Required dot fails to match end of string. ^ ^ Backtrack to try other alternative. Give back text consumed by depth 2 (?R) = "cd" 17 1 .(?:(?R)|.?). abcd Optional dot matches "c". Advance pointers. ^ ^ 18 1 .(?:(?R)|.?). abcd Required dot matches "d". Advance pointers. ^ ^ DEPTH 1 (?R) SUCCEEDS. Return to step 2 depth 0 19 0 .(?:(?R)|.?). abcd Required dot fails to match end of string. ^ ^ Backtrack to try other alternative. Give back text consumed by depth 1 (?R) = "bcd" 20 0 .(?:(?R)|.?). abcd Try 2nd alt. Optional dot matches "b". ^ ^ Advance pointers. 21 0 .(?:(?R)|.?). abcd Dot matches "c". Advance pointers. ^ ^ SUCCESSFUL MATCH of "abc" '''
Нет ничего плохого в двигателе регулярных выражений. Правильное совпадение – это abc (или aaa для исходного вопроса.) Аналогичную (хотя и намного более длинную) последовательность шагов можно выполнить для другой более длинной строки результата.
ВАЖНО: Здесь описывается рекурсивное регулярное выражение в PHP (которое использует библиотеку PCRE ). Рекурсивное регулярное выражение работает по-разному в Perl.
Примечание. Это объясняется в порядке, который вы можете концептуализировать. Двигатель регулярных выражений делает это в обратном направлении; он погружается в базовый корпус и возвращается назад.
Поскольку ваш внешний a s явно там, он будет соответствовать a между двумя a s или совпадением предыдущей рекурсии всего шаблона между двумя a s. В результате он будет соответствовать только нечетным числам s (средний плюс плюс два).
При длине трех aaa является совпадающим образцом текущей рекурсии, поэтому на четвертой рекурсии он ищет a между двумя a s (то есть aaa ) или совпадающим шаблоном предыдущей рекурсии между двумя a s (то есть a + aaa + a ). Очевидно, что он не может совпадать с пятью секундами, когда строка не так длинна, поэтому самое длинное совпадение, которое оно может сделать, равно трем.
Аналогичная сделка имеет длину шесть, так как она может соответствовать только «по умолчанию» aaa или совпадению предыдущей рекурсии, окруженной s (то есть a + aaaaa + a ).
Однако он не соответствует всем нечетным длинам.
Поскольку вы совпадаете с рекурсивно, вы можете сопоставлять только литералы aaa или a + (prev recurs match) + a . Поэтому каждый последующий матч будет всегда на два больше, чем предыдущий матч, или он будет плуть и вернуться к aaa .
На протяжении семи (совпадение с aaaaaaa ) предыдущий матч рекурсии был резервным aaa . Так что на этот раз, хотя есть семь секунд, он будет соответствовать только трем ( aaa ) или пяти ( a + aaa + a ).
При переходе на более длинные длины (80 в этом примере) просмотрите шаблон (показывая только совпадение, а не вход):
no match aa aaa aaa aaaaa aaa aaaaa aaaaaaa aaaaaaaaa aaa aaaaa aaaaaaa aaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaaa aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaa aaa aaaaa aaaaaaa aaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaaa aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaa aaaaa aaaaaaa aaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaaa aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaa aaaaa aaaaaaa aaaaaaaaa aaaaaaaaaaa aaaaaaaaaaaaa aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaa
Что тут происходит? Хорошо, я вам скажу! 🙂
Когда рекурсивное совпадение будет на один символ дольше, чем входная строка, он, как мы видели, отбрасывает обратно на aaa . На каждой итерации после этого шаблон начинается с соответствия двух других символов, чем предыдущий. Каждая итерация, длина ввода увеличивается на единицу, но длина совпадения увеличивается на два. Когда размер совпадения, наконец, подхватывает резервную копию и превосходит длину входной строки, она отбрасывает обратно на aaa . И так далее.
В качестве альтернативы, здесь мы видим, сколько символов дольше вход сравнивается с длиной совпадения на каждой итерации:
(input len.) - (match len.) = (difference) 1 - 0 = 1 2 - 2 = 0 3 - 3 = 0 4 - 3 = 1 5 - 5 = 0 6 - 3 = 3 7 - 5 = 2 8 - 7 = 1 9 - 9 = 0 10 - 3 = 7 11 - 5 = 6 12 - 7 = 5 13 - 9 = 4 14 - 11 = 3 15 - 13 = 2 16 - 15 = 1 17 - 17 = 0 18 - 3 = 15 19 - 5 = 14 20 - 7 = 13 21 - 9 = 12 22 - 11 = 11 23 - 13 = 10 24 - 15 = 9 25 - 17 = 8 26 - 19 = 7 27 - 21 = 6 28 - 23 = 5 29 - 25 = 4 30 - 27 = 3 31 - 29 = 2 32 - 31 = 1 33 - 33 = 0 34 - 3 = 31 35 - 5 = 30 36 - 7 = 29 37 - 9 = 28 38 - 11 = 27 39 - 13 = 26 40 - 15 = 25 41 - 17 = 24 42 - 19 = 23 43 - 21 = 22 44 - 23 = 21 45 - 25 = 20 46 - 27 = 19 47 - 29 = 18 48 - 31 = 17 49 - 33 = 16 50 - 35 = 15 51 - 37 = 14 52 - 39 = 13 53 - 41 = 12 54 - 43 = 11 55 - 45 = 10 56 - 47 = 9 57 - 49 = 8 58 - 51 = 7 59 - 53 = 6 60 - 55 = 5 61 - 57 = 4 62 - 59 = 3 63 - 61 = 2 64 - 63 = 1 65 - 65 = 0 66 - 3 = 63 67 - 5 = 62 68 - 7 = 61 69 - 9 = 60 70 - 11 = 59 71 - 13 = 58 72 - 15 = 57 73 - 17 = 56 74 - 19 = 55 75 - 21 = 54 76 - 23 = 53 77 - 25 = 52 78 - 27 = 51 79 - 29 = 50 80 - 31 = 49
По причинам, которые теперь должны иметь смысл, это происходит с кратным 2.
Я немного упростил исходный шаблон для этого примера. Помни это. Мы вернемся к этому.
a((?R)|a)a
То, что автор Джеффри Фридль означает «конструкцией (? R), делает рекурсивную ссылку на все регулярное выражение », заключается в том, что механизм регулярных выражений будет заменять весь шаблон вместо (?R) столько раз, сколько это возможно.
a((?R)|a)a # this a((a((?R)|a)a)|a)a # becomes this a((a((a((?R)|a)a)|a)a)|a)a # becomes this # and so on...
Прослеживая это вручную, вы можете работать изнутри. В (?R)|a , a – ваш базовый случай. Поэтому мы начнем с этого.
a(a)a
Если это соответствует входной строке, верните это соответствие ( aaa ) обратно в исходное выражение и поместите вместо (?R) .
a(aaa|a)a
Если входная строка соответствует нашему рекурсивному значению, подставьте подзаголовок, который соответствует ( aaaaa ) обратно в исходное выражение, чтобы снова выполнить повторную процедуру.
a(aaaaa|a)a
Повторяйте до тех пор, пока вы не сможете сопоставить свой вход с результатом предыдущей рекурсии.
пример
Вход: aaaaaa
Regex: a((?R)|a)a
Начните с базового футляра, aaa .
Соответствует ли вход с этим значением? Да: aaa
Recurse, положив aaa в исходное выражение:
a(aaa|a)a
Соответствует ли вход с нашим рекурсивным значением? Да: aaaaa
Рекурсивно, положив aaaaa в исходное выражение:
a(aaaaa|a)a
Соответствует ли вход с нашим рекурсивным значением? Нет: aaaaaaa
Тогда мы остановимся здесь. Вышеприведенное выражение может быть переписано (для простоты) следующим образом:
aaaaaaa|aaa
Поскольку он не соответствует aaaaaaa , он должен соответствовать aaa . Мы закончили, aaa – окончательный результат.
Ладно, у меня наконец есть.
Я вернул правильный ответ на вопрос, как он поставил меня на путь решения, но я также хотел написать полный ответ на конкретный вопрос, если кто-то еще хочет полностью понять пример.
Сначала это решение, затем несколько заметок.
Ниже приведено краткое описание шагов, за которыми следует двигатель. Эти шаги следует читать сверху донизу. Они не пронумерованы. Глубина рекурсии отображается в левом столбце, поднимаясь с нуля на дюйм и обратно до нуля. Для удобства это выражение показано в правом верхнем углу. Для удобства чтения «совпадающие« a »отображаются на своем месте в строке (которая показана на самом верху).
STRING EXPRESSION aaaaa(?:(?R|a?))a Depth Match Token 0 a first a from depth 0. Next step in the expression: depth 1. 1 a first a from depth 1. Next step in the expression: depth 2. 2 a first a from depth 2. Next step in the expression: depth 3. 3 a first a from depth 3. Next step in the expression: depth 4. 4 depth 4 fails to match anything. Back to depth 3 @ alternation. 3 depth 3 fails to match rest of expression, back to depth 2 2 aa depth 2 completes as a/empty/a, back to depth 1 1 a[aa] a/[detph 2]a fails to complete, discard depth 2, back to alternation 1 a first a from depth 1 1 aaa from alternation 1 aaa depth 1 completes, back to depth 0 0 a[aaa] depth 0 fails to complete, discard depth 1, back to alternation 0 a first a from depth 0 0 aaa from alternation 0 aaa expression ends with successful match
1. Источником путаницы
Вот что было противно интуитивно для меня.
Мы пытаемся сопоставить aaaa
Я предположил, что глубина 0 рекурсии будет соответствовать как – – a, а эта глубина 1 будет соответствовать как – aa –
Но на самом деле глубина 1 сначала совпадает с aaaa
Так что глубина 0 не должна идти, чтобы закончить матч:
a [D1: aaa]
…и что? У нас нет персонажей, но выражение еще не закончено.
Таким образом, глубина 1 отбрасывается. Обратите внимание, что глубина 1 не повторится, возвращая символы, что приведет нас к другой глубине 1 совпадения – aa –
Это потому, что рекурсивные совпадения являются атомарными. Как только глубина совпадает, это все или ничего, вы держите все это или отбрасываете все это.
Когда глубина 1 отбрасывается, глубина 0 перемещается на другую сторону чередования и возвращает совпадение: aaa
2. Источник ясности
То, что помогло мне больше всего, было примером того, что дал хладнокровник. В своем примере он показал, как проследить путь двигателя, и это именно то, что я хотел понять.
Следуя этому методу, я проследил весь путь к движку для нашего конкретного примера. Как и у меня, путь имеет длину 25 шагов, поэтому он значительно длиннее приведенного выше. Но сводка точно соответствует пути, который я проследил.
Большое спасибо всем, кто внес вклад, в частности Wiseguy за очень интригующую презентацию. Я все еще задаюсь вопросом, может ли я как-то что-то упустить, а ответ Виземи может быть таким же!
После много экспериментов я думаю, что механизм регулярных выражений PHP сломан. Точный же код в Perl отлично работает и соответствует всем вашим строкам от начала до конца, как и следовало ожидать.
Рекурсивные регулярные выражения сложны для воображения, но мне кажется, что /a(?:(?R)|a?)a/ aaaa /a(?:(?R)|a?)a/ должно соответствовать aaaa как a .. пара, содержащая вторую a .. пару, после что вторая рекурсия терпит неудачу, а альтернативный / a? / вместо этого используется как пустая строка.