Por defecto, cuando un subpatrón con un cuantificador impide que el patrón global tenga éxito, se produce un backtrack. Hay ocasiones en las que esta conducta da lugar a ineficiencia.
Perl 5.10 provee los cuantificadores posesivos: Un cuantificador posesivo actúa como un cuantificador greedy pero no se produce backtracking.
*+ |
Casar 0 o mas veces y no retroceder |
++ |
Casar 1 o mas veces y no retroceder |
?+ |
Casar 0 o 1 veces y no retroceder |
{n}+ |
Casar exactamente n veces y no retroceder (redundante) |
{n,}+ |
Casar al menos n veces y no retroceder |
{n,m}+ |
Casar al menos n veces y no mas de m veces y no retroceder |
'aaaa'
no casa con /(a++a)/
porque no
hay retroceso después de leer las 4 aes:
pl@nereida:~/Lperltesting$ perl5.10.1 -wde 0 main::(-e:1): 0 DB<1> x 'aaaa' =~ /(a+a)/ 0 'aaaa' DB<2> x 'aaaa' =~ /(a++a)/ empty array
Los operadores posesivos sirven para poder escribir expresiones regulares mas eficientes en aquellos casos en los que sabemos que el retroceso no conducirá a nuevas soluciones, como es el caso del reconocimiento de las cadenas delimitadas por comillas dobles:
pl@nereida:~/Lperltesting$ cat -n ./quotedstrings.pl 1 #!/usr/local/lib/perl/5.10.1/bin//perl5.10.1 2 use v5.10; 3 4 my $regexp = qr/ 5 " # double quote 6 (?: # no memory 7 [^"\\]++ # no " or escape: Don't backtrack 8 | \\. # escaped character 9 )*+ 10 " # end double quote 11 /x; 12 13 my $input = <>; 14 chomp($input); 15 if ($input =~ $regexp) { 16 say "$& is a string"; 17 } 18 else { 19 say "does not match"; 20 }
Los paréntesis posesivos (?> ...)
dan lugar a un reconocedor
que rechaza las demandas de retroceso.
De hecho, los operadores posesivos pueden ser reescritos
en términos de los paréntesis posesivos:
La notación X++
es equivalente a (?>X+)
.
El siguiente ejemplo reconoce el lenguaje de los paréntesis balanceados:
pl@nereida:~/Lperltesting$ cat -n ./balancedparenthesis.pl 1 #!/usr/local/lib/perl/5.10.1/bin//perl5.10.1 2 use v5.10; 3 4 my $regexp = 5 qr/^( 6 [^()]*+ # no hay paréntesis, no backtrack 7 \( 8 (?> # subgrupo posesivo 9 [^()]++ # no hay paréntesis, + posesivo, no backtrack 10 |(?1) # o es un paréntesis equilibrado 11 )* 12 \) 13 [^()]*+ # no hay paréntesis 14 )$/x; 15 16 my $input = <>; 17 chomp($input); 18 if ($input =~ $regexp) { 19 say "$& is a balanced parenthesis"; 20 } 21 else { 22 say "does not match"; 23 }Cuando se ejecuta produce una salida como:
pl@nereida:~/Lperltesting$ ./balancedparenthesis.pl (2*(3+4)-5)*2 (2*(3+4)-5)*2 is a balanced parenthesis pl@nereida:~/Lperltesting$ ./balancedparenthesis.pl (2*(3+4)-5))*2 does not match pl@nereida:~/Lperltesting$ ./balancedparenthesis.pl 2*(3+4 does not match pl@nereida:~/Lperltesting$ ./balancedparenthesis.pl 4*(2*(3+4)-5)*2 4*(2*(3+4)-5)*2 is a balanced parenthesis
El uso de los operadores posesivos nos permite reescribir la solución al problema de encontrar los bloques maximales de un código dada en la sección 3.2.5 de la siguiente manera:
1 pl@nereida:~/Lperltesting$ cat blocksopti.pl 2 #!/usr/local/lib/perl/5.10.1/bin//perl5.10.1 -w 3 use v5.10; 4 use strict; 5 #use re 'debug'; 6 7 my $rb = qr{(?x) 8 ( 9 \{ # llave abrir 10 (?: 11 [^{}]++ # no llaves 12 | 13 (?1) # recursivo 14 [^{}]*+ # no llaves 15 )*+ 16 \} # llave cerrar 17 ) 18 }; 19 20 local $/ = undef; 21 my $input = <>; 22 my@blocks = $input =~ m{$rb}g; 23 my $i = 0; 24 say($i++.":\n$_\n===") for @blocks;