Expressões recursivas

Considere o problema de corresponder a uma string entre parênteses, permitindo parênteses aninhados ilimitados. Sem o uso de recursão, o melhor que pode ser feito é usar uma expressão que corresponda a uma profundidade fixa de aninhamento. Não é possível lidar com uma profundidade de aninhamento arbitrária. O Perl 5.6 forneceu um recurso experimental que permite a recursividade de expressões regulares (entre outras coisas). O item especial (?R) é fornecido para o caso específico de recursão. Esta expressão PCRE resolve o problema dos parênteses (suponha que a opção PCRE_EXTENDED esteja definida para que o espaço em branco seja ignorado): \( ( (?>[^()]+) | (?R) )* \)

Primeiro, ela corresponde a um parêntese de abertura. Em seguida, ela corresponde a qualquer número de substrings que podem ser uma sequência de não-parênteses ou uma correspondência recursiva da própria expressão (ou seja, uma substring colocada de forma correta entre parênteses). Finalmente há um parêntese de fechamento.

Esta expressão de exemplo em particular contém repetições ilimitadas aninhadas e, portanto, o uso de uma sub-expressão de ocorrência única para correspondência a strings de não-parênteses é importante ao aplicar a expressão em strings que não correspondem. Por exemplo, quando é aplicada a (aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa() ela gera uma "não correspondência" rapidamente. Entretanto, se uma expressão de ocorrência única nao for usada, a correspondência é executada por um longo tempo porque existem muitas formas diferentes das repetições + e * dividirem a string, e todas têm que ser testadas antes que a falha possa ser reportada.

Os valores definidos para quaisquer sub-expressões de captura são aqueles do nível mais externo da recursão no qual o valor da sub-expressão é definido. Se a expressão acima for comparada com (ab(cd)ef), o valor para os parênteses de captura será "ef", que é o último valor considerado no nível mais alto. Se parênteses extras forem acrescentados, resultando em \( ( ( (?>[^()]+) | (?R) )* ) \), a string que eles irão capturar será "ab(cd)ef", o conteúdo dos parênteses do nível mais alto. Se houver mais de 15 parênteses de captura em uma expressão, o PCRE precisa obter memória extra para armazenar dados durante uma recursão, o que ele faz usando pcre_malloc, liberando-a posteriormente via pcre_free. Se nenhuma memória puder ser obtida, ele salva os dados apenas dos primeiros 15 parênteses de captura, pois não há como gerar um erro de falta de memória dentro de uma recursão.

(?1), (?2), e assim por diante, também podem ser usados para sub-expressões recursivas. também é possível usar sub-expressões nomeadas: (?P>nome) ou (?&nome).

Se a sintaxe para uma referência de sub-expressão recursiva (seja por número ou por nome) for usada fora dos parênteses aos quais se refere, ela funcionará como uma sub-rotina em uma linguagem de programação. Um exemplo anterior apontou que a expressão (sens|respons)e and \1ibility corresponde a "sense and sensibility" e "response and responsibility", mas não a "sense and responsibility". Se, em vez disso, a expressão (sens|respons)e and (?1)ibility for usada, ela corresponderá a "sense and responsibility", bem como às outras duas strings. Tais referências devem, contudo, seguir a sub-expressão a que se referem.

O comprimento máximo de uma string de entrada é o maior número positivo que uma variável inteira pode conter. No entanto, o PCRE usa recursão para lidar com sub-expressões e repetições indefinidas. Isso significa que o espaço de pilha disponível pode limitar o tamanho de uma string de entrada que pode ser processada por determinadas expressões.