Regex - Grupos atômicos e quantificadores possessivos

PHPPerl
Enviado por Eclesiastes em Dom, 15/10/2006 - 00:31.PHP | Perl

Para entendermos os grupos atômicos e quantificadores possessivos precisamos saber como funciona a Regex Engine.
Imagine utilizar a expressão /\d+foo/ na string "12345bar", a Regex Engine irá casar todos os 5 dígitos mas irá falhar na string "bar", sendo assim, irá tentar casar com 4 dígitos, quando falhar tentará casar com 3 dígitos, ... até falhar com todos.

Isto é conhecido como catastrophic backtracking e há um caminho para você prevenir que isso ocorra.
Esse método é chamado de grupo atômico. A expressão seria /(?>\d+)foo/

Para maiores informações sobre (?>pattern), eu tentei traduzir da Perl doc:
http://www.phpavancado.net/node/356

Isso pode ser feito também de uma forma reduzida com o quantificador possessivo "+", basta adicionar outro "+" após ele.
A expressão seria /\d++foo/

Quando usado um desses métodos a Regex Engine irá somente tentar casar \d+foo uma vez, assim que ele visualizar "1234567890" não seguido de "foo" informará falha.

No exemplo acima não é vista muita diferença, então veja abaixo um exemplo onde você poderá notar a diferença:

String: aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa (50 caracteres)

ER: /(\D+|)*[!?]/
Tempo de execução: 2.63513898849

Repare bem o tempo que levou (quase 3 segundos), pois a Regex Engine percorreu analisando toda a string.

Agora veja o resultado utilizando os 2 métodos apresentados:

ER: /((?>\D+)|)*[!?]/
Tempo de execução: 0.00168991088867

ER: /(\D++|)*[!?]/
Tempo de execução: 0.00266790390015

Ambos instantâneamente reportam falha. (não casam)

Às vezes há casos que um quantificador normal irá casar, mas o quantificador possessivo não irá.
Veja um exemplo:

String: "12345"

ER: /\d+./
>> Casa!

ER: /\d++./
>> Não casa

O motivo do ++ (quantificador possessivo) falhar é por que ele procura todos 5 digitos e então olha para outro caractere, quando não encontra outro caractere ele não irá cair no mesmo processo do backtracking (descrito no começo do texto), enquanto o + (quantificador normal) irá.

++ pode somente ser usado em um único item, ou seja, ele não pode ser usado em (\d+\D{3,})++.

Nota: Grupo atômico e quantificadores possessivos são tipicamente usados para otimização.

Créditos:

  • Manual PCRE - http://www.pcre.org/pcre.txt
  • FiberOPtics e qwerty- (Texto original em inglês)
  • Felipe Nascimento Silva Pena (Tradução e adaptação)