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

Розглянемо задачу пошуку відповідності з рядком, що знаходяться усередині необмеженої кількості круглих дужок. Без використання рекурсії найкраще, що можна зробити — написати шаблон, який вирішуватиме завдання для деякої обмеженої глибини вкладеності, оскільки обробити необмежену глибину неможливо. У 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 використовує рекурсію, це означає, що розмір рядків, що обробляються, в деяких шаблонах також може бути обмежений доступним розміром стека.