regex - ¿Por qué// w+:/y// S+:/manejan el retroceso de manera diferente?

pcre backtracking

Question

Analicé estas dos expresiones regulares utilizando regex101 . Creo que el retroceso de //S+:/ es correcto. Pero no puedo entender esa diferencia. ¿Me equivoco?

Answer 1

Esta es una optimización pcre llamada auto-possessification .

De http://pcre.org/pcre.txt :

La optimización de "auto-posesificación" de PCRE generalmente se aplica a las repeticiones de caracteres al final de un patrón (así como internamente). Por ejemplo, el patrón " a/d+ " se compila como si fuera " a/d++ " porque no tiene sentido, incluso considerando la posibilidad de retroceder en los dígitos repetidos.

y

Esta es una optimización que, por ejemplo, convierte a+b en a++b para evitar que las pistas de retroceso se conviertan en a+ que nunca pueden tener éxito.

Dado que : no está incluido en /w , su patrón se interpreta como /w++: (el segundo + evita el retroceso, consulte los cuantificadores posesivos ). Los estados de retroceso adicional se evitan porque no hay otro estado en el que pueda coincidir.

Por otro lado : se incluye en /S , por lo que esta optimización no se aplica para el segundo caso.

PCRETEST

Puede ver la diferencia usando pcretest (hay una versión de Windows que puede descargar here ).

El patrón //w+:/ toma 11 pasos y produce:

//w+:/
--->get accept:
 +0 ^               /w+
 +3 ^  ^            :
 +0  ^              /w+
 +3  ^ ^            :
 +0   ^             /w+
 +3   ^^            :
 +0    ^            /w+
 +0     ^           /w+
 +3     ^     ^     :
 +4     ^      ^    .*
 +6     ^      ^    
 0: accept:

Sin embargo, si usamos el verbo de control (*NO_AUTO_POSSESS) , que deshabilita esta optimización, el patrón /(*NO_AUTO_POSSESS)/w+:/ toma 14 pasos y produce:

/(*NO_AUTO_POSSESS)/w+:/
--->get accept:
+18 ^               /w+
+21 ^  ^            :
+21 ^ ^             :
+21 ^^              :
+18  ^              /w+
+21  ^ ^            :
+21  ^^             :
+18   ^             /w+
+21   ^^            :
+18    ^            /w+
+18     ^           /w+
+21     ^     ^     :
+22     ^      ^    .*
+24     ^      ^    
 0: accept:

^{- Lleva 1 paso menos que /S+ , como se esperaba, porque /w+ no coincide :}

Desafortunadamente regex101 no soporta este verbo.

Actualización: regex101 ahora admite este verbo, aquí está el enlace a los 3 casos para comparar:

1. //S+:/ (14 pasos) - https://regex101.com/r/cw7hGh/1/debugger

2. //w+:/ (10 pasos) - https://regex101.com/r/cw7hGh/2/debugger

3. /(*NO_AUTO_POSSESS)/w+:/ (13 pasos) - https://regex101.com/r/cw7hGh/3/debugger

depurador regex101:

Answer 2

Si bien esto parece ser específico de la implementación (RegexBuddy no muestra este comportamiento), se puede explicar de la siguiente manera:

/w no puede coincidir : pero /S puede. Por lo tanto, /S+: necesita verificar más variaciones de la cadena de entrada antes de asegurarse de que get no pueda coincidir.

Los motores de expresiones regulares más optimizados excluirán las coincidencias imposibles más rápido (por ejemplo, cuando la expresión regular contiene un carácter literal que no está presente en la parte actual de la coincidencia), pero aparentemente el motor que está utilizando la expresión regular101 no lo está haciendo.