Рекурсивные шаблоны

Рассмотрим задачу поиска соответствия со строкой, находящихся внутри неограниченного количества круглых скобок. Без использования рекурсии лучшее, что можно сделать - написать шаблон, который будет решать задачу для некоторой ограниченной глубины вложенности, так как обработать неограниченную глубину не предоставляется возможным. В Perl 5.6 предоставлены некоторые экспериментальные возможности, которые в том числе позвояляют реализовать рекурсию в шаблонах. Специально обозначение (?R) используется для указания рекурсивной подмаски. Таким образом, приведем PCRE шаблон, решающий поставленную задачу (подразумевается, что используется модификатор PCRE_EXTENDED, незначащие пробелы игнорируются): \( ( (?>[^()]+) | (?R) )* \)

Вначале он соответствует открывающей круглой скобке. Далее он соответствует любому количеству подстрок, каждая из которых может быть последовательностью не-скобок, либо строкой, рекурсивно соответствующей шаблону (т.е. строкой, корректно заключенной в круглые скобки). И, в конце, идет закрывающая круглая скобка.

Приведенный пример шаблона использует вложенные неограниченные повторения, поэтому использование однократных шаблонов значительно ускоряет процесс сопоставления, особенно в случаях, когда строка не соответствует заданной маске. Например, если его применить к строке: (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa(), то несоответствие будет обнаружено достаточно быстро. Но в случае, если однократные шаблоны не используются, сопоставление будет затягиваться на длительное время, так как существует множество способов разделения строки между квантификаторами + и *, и все они должны быть проверены, прежде чем будет выдано сообщение о неудаче.

Значение, устанавливаемое для захватывающей подмаски будет соответствовать значению, захваченному на наиболее глубоком уровне рекурсии. В случае, если приведенный выше шаблон сопоставляется со строкой (ab(cd)ef), захваченным значением будет 'ef', которое является последним значением, принимаемым на верхнем уровне. В случае, если добавить дополнительные скобки \( ( ( (?>[^()]+) | (?R) )* ) \), захваченным значением будет "ab(cd)ef". В случае, если в шаблоне встречается более, чем 15 захватывающих скобок, PCRE требуется больше памяти для обработки рекурсии, чем обычно. Память выделяется при помощи функции pcre_malloc, и освобождается соответственно функцией pcre_free. Если память не может быть выделена, сохраняются данные только для первых 15 захватывающих скобок, так как нет способа выдать ошибку out-of-memory изнутри рекурсии.

(?1), (?2) и так далее могут быть использованы для рекурсивных подмасок. Также возможно использовать именованные подмаски: (?P>name) или (?&name).

Если синтаксис ссылки на рекурсивную подмаску (как по имени, так и по числовому индексу) используется вне скобок, к которым он относится, он отрабатывает аналогично подпрограмме в языке программирования. Возьмем более ранний пример, указывающий что шаблон (sens|respons)e and \1ibility соответствует "sense and sensibility" и "response and responsibility", но не "sense and responsibility". Если вместо этого использовать шаблон (sens|respons)e and (?1)ibility, он совпадет с "sense and responsibility" так же, как и с другими двумя строками. Однако, такие ссылки должны быть указаны после подмаски, на которую они ссылаются.

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