Рекурсивное регулярное выражение PHP
РЕДАКТИРОВАТЬ: Я выбрал ответ риджераннера, поскольку он содержал информацию, необходимую для решения проблемы. Но мне также захотелось добавить полностью продуманное решение к конкретному вопросу на случай, если кто-то еще тоже захочет полностью понять этот пример. Вы найдете его где-то ниже.
Этот вопрос касается уточнения поведения механизма регулярных выражений php для рекурсивных выражений. (Если у вас есть идеи о том, как правильно сопоставить приведенные ниже строки без использования рекурсивного php регулярное выражение, это очень круто, но вопрос не в этом.)
a(?:(?R)|a?)a
Это простое выражение, которое стремится соответствовать символу "а" или ничего, вложенному в одно или несколько гнезд символа "а". Например, аа, ааа, ааааа, ааааа. Вам не нужно использовать рекурсию для этого:
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 />';
}
?>
В шаблоне две буквы "а" обрамляют чередование. В чередовании мы либо сопоставляем рекурсию всего шаблона (два "а", обрамляющие чередование), либо символ "а", необязательно пустой.
На мой взгляд, для "аааа" это должно соответствовать "аааа".
Но вот результат:
a : no match
aa : aa
aaa : aaa
aaaa : aaa
aaaaa : aaaaa
aaaaaa : aaa
Может ли кто-нибудь объяснить, что происходит на третьей и пятой строках вывода? Я попытался проследить путь, по которому, по моему мнению, должен двигаться двигатель, но, должно быть, я представляю его неправильно. Почему двигатель возвращает "aaa" в качестве совпадение с "ааааа"? Что делает его таким нетерпеливым? Должно быть, я представляю соответствующее дерево в неправильном порядке.
Я понимаю, что
#(?:a|a(?R)a)*#
Вроде бы работает, но мой вопрос в том, почему другой шаблон не работает.
Огромное спасибо!
4 answers
Отличный (и сложный) вопрос!
Во-первых, с механизмом регулярных выражений PCRE (?R) ведет себя как атомарная группа (в отличие от Perl?). Как только он совпадает (или не совпадает), совпадение, которое произошло внутри рекурсивного вызова, является окончательным (и все панировочные сухари, сохраненные в рекурсивном вызове, отбрасываются). Однако механизм регулярных выражений сохраняет то, что было сопоставлено всему выражению (?R), и может вернуть его и попробовать другую альтернативу для достижения полного соответствия. Чтобы описать, что происходит, давайте немного изменим ваш пример, чтобы было легче говорить и отслеживать, что сопоставляется на каждом шаге. Вместо: aaaa в качестве текста темы давайте использовать: abcd. И давайте изменим регулярное выражение с '#a(?:(?R)|a?)a#' на: '#.(?:(?R)|.?).#'. Поведение механизма сопоставления регулярных выражений такое же.
Сопоставление регулярного выражения: /.(?:(?R)|.?)./ с: "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 явно присутствуют, они будут соответствовать a между двумя a или совпадению предыдущей рекурсии всего шаблона между двумя a с. В результате он будет соответствовать только нечетным числам as (среднее число плюс кратное двум).
Длиной в три, aaa - это совпадающий шаблон текущей рекурсии, поэтому при четвертой рекурсии он ищет a между двумя as (т.Е. aaa) или совпадающий шаблон предыдущей рекурсии между двумя as (т.Е., a+aaa+a). Очевидно, что он не может соответствовать пяти a, когда строка не такая длинная, поэтому самая длинная соответствует ей может сделать это три.
Аналогичная сделка с длиной шесть, так как она может соответствовать только "умолчанию" aaa или совпадению предыдущей рекурсии, окруженному as (т.Е., a+aaaaa+a).
Однако он не соответствует всем нечетным длинам.
Поскольку вы сопоставляете рекурсивно, вы можете сопоставлять только литерал aaa или a+(предыдущее повторное совпадение)+a. Поэтому каждое последующее совпадение всегда будет на две a секунды длиннее предыдущего совпадения, или он упадет и вернется к aaa.
При длине семь (совпадение с aaaaaaa) совпадение предыдущей рекурсии было резервным вариантом aaa. Так что на этот раз, даже если их семь a, они будут соответствовать только трем (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
Регулярное выражение: a((?R)|a)a
Начните с базового варианта, aaa.
Соответствует ли входное значение этому значению? Да: aaa
Повторите, поместив aaa в исходное выражение:
a(aaa|a)a
Соответствует ли ввод нашему рекурсивному значению? Да: aaaaa
Повторите, поместив aaaaa в исходное выражение:
a(aaaaa|a)a
Соответствует ли ввод нашему рекурсивному значению? Нет: aaaaaaa
Тогда мы остановимся здесь. Приведенное выше выражение можно было бы переписать (для простоты) следующим образом:
aaaaaaa|aaa
Поскольку он не соответствует aaaaaaa, он должен соответствовать aaa. Мы закончили, aaa - это окончательный результат.
Ладно, наконец-то я понял.
Я присудил правильный ответ риджераннеру, когда он указал мне путь к решению, но я также хотел написать полный ответ на конкретный вопрос на случай, если кто-то еще тоже захочет полностью понять пример.
Сначала решение, затем несколько заметок.
А. Решение
Вот краткое описание шагов, выполняемых двигателем. Шаги должны быть прочитаны сверху вниз. Они не пронумерованы. Глубина рекурсии равна показано в левом столбце, увеличивается от нуля до для и обратно до нуля. Для удобства выражение показано в правом верхнем углу. Для удобства чтения сопоставляемые буквы "а" отображаются на их месте в строке (которая показана в самом верху).
STRING EXPRESSION
a a a a a(?:(?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 a a depth 2 completes as a/empty/a, back to depth 1
1 a[a a] a/[detph 2]a fails to complete, discard depth 2, back to alternation
1 a first a from depth 1
1 a a a from alternation
1 a a a depth 1 completes, back to depth 0
0 a[a a a] depth 0 fails to complete, discard depth 1, back to alternation
0 a first a from depth 0
0 a a a from alternation
0 a a a expression ends with successful match
Б. Примечания
1. Источник путаницы
Вот что было для меня в этом нелогичным.
Мы пытаемся сопоставить a a a a
Я предположил, что глубина 0 рекурсии будет соответствовать как - - a , и эта глубина 1 будет соответствовать как - a a -
Но на самом деле глубина 1 сначала соответствует как - а а а
Таким образом, глубине 0 некуда идти, чтобы закончить матч:
a [D1: a a a]
...тогда что? У нас закончились персонажи, но выражение еще не закончено.
Таким образом, глубина 1 отбрасывается. Обратите внимание, что глубина 1 не повторяется, возвращая символы, что приведет нас к другому совпадению глубины 1 - a a -
Это потому, что рекурсивные совпадения являются атомарными. Один раз глубина совпадает, все или ничего, вы сохраняете все это или отбрасываете все это.
Как только глубина 1 отбрасывается, глубина 0 переходит на другую сторону чередования и возвращает совпадение: а а а
2. Источник ясности
Больше всего мне помог пример, который привел риджераннер. В своем примере он показал, как отследить путь двигателя, что именно то, что я хотел понять.
Следуя этому методу, я проследил полный путь двигатель для нашего конкретного примера. Как я понимаю, длина пути составляет 25 шагов, поэтому он значительно длиннее, чем приведенное выше резюме. Но краткое изложение точно соответствует пути, который я проследил.
Большое спасибо всем остальным, кто внес свой вклад, в частности Wiseguy за очень интригующую презентацию. Я все еще задаюсь вопросом, может быть, я что-то упустил, и ответ Мудреца может быть таким же!
После долгих экспериментов я думаю, что движок регулярных выражений PHP сломан. Точно такой же код в Perl отлично работает и соответствует всем вашим строкам от начала до конца, как я и ожидал.
Рекурсивные регулярные выражения сложны для воображения, но мне кажется, что /a(?:(?R)|a?)a/ должно соответствовать aaaa как a..a пара, содержащая вторую a..a пара, после чего вторая рекурсия завершается неудачей, и вместо этого альтернативный /a?/ совпадает с нулевой строкой.