7

Me dijeron que cuando se usa * o + en las expresiones regulares, existe este proceso de backtracking. Estoy intentando entenderlo, haciendo unas pruebas en regex101.com.

Por ejemplo al usar el patrón (a+)+b sobre "aaaaaaaaaaaaaaaaaazb", ocurre el error de "Catastrophic backtracking".

Pero si uso el patrón b(a+)+ sobre "bzaaaaaaaaaaaaaaaaaa" no ocurre este error.

Entonces:

  • ¿Cómo se produce este error?
  • Para solucionarlo ¿cómo funcionan (?>), (?<=), (?<\!), (?=) y (?!)?
  • ¿Qué significa (*SKIP), (*PRUNE), (*FAIL)? ¿Tienen algún equivalente en Java o .Net?
1
  • Son demasiadas preguntas. Te recomiendo editar eliminando la pregunta de cómo funcionan (?<=), (?<\!), (?=) y (?!), que no tienen nada que ver con tu pregunta principal, así como también evitar la parte de (*SKIP), (*PRUNE) y (*FAIL), que no realmente deberían ir en una pregunta independiente.
    – Mariano
    el 11 ene. 2018 a las 14:20

1 respuesta 1

9

Cómo funciona el motor de expresiones regulares internamente

Antes de hablar de backtracking, tenemos que entender cómo funciona una expresión regular internamente, qué pasos sigue para buscar una coincidencia de un patrón en un texto, y en qué orden. Entender cómo se busca una coincidencia permite entender qué parte del texto va a coincidir, y por qué.

El motor de expresiones regulares busca la primera coincidencia que pueda encontrar, buscando en este orden de jerarquía:

  1. Todas las permutaciones de la expresión regular, recorriendo el patrón de izquierda a derecha.
  2. Todas las posiciones iniciales en el texto, recorriendo el texto de izquierda a derecha.

Esto quiere decir que, para cualquier texto dado, el motor de regex va a intentar todas las opciones de la expresión regular, dentro de su árbol de posibilidades, desde la posición 0 del texto. Solamente si se intentaron todas las posibilidades y no se encontró una coincidencia, recién ahí va a avanzar 1 posición en el texto, intentando desde la posición 1 (y luego la posición 2, y así sucesivamente), hasta encontrar una coincidencia o llegar al final del texto.

Obviamente, apenas encuentra una coincidencia, la devuelve. Y (si se están buscando múltiples resultados -normalmente con el flag /g) los siguientes intentos de búsqueda comienzan desde la posición posterior al texto consumido por esa coincidencia.


El motor de regex siempre devuelve la coincidencia que está más a la izquierda en el texto. Incluso cuando a la derecha puede haber una coincidencia "mejor", el primer valor devuelto es el primero que se encuentra probando todas las permutaciones para cada posición inicial.

Si intentamos buscar la primera coincidencia del patrón /ola/ en "Solamente una ola":

Devuelve el "ola" dentro de "Solamente", por más que luego aparezca "ola" como palabra

Se devuelve la primera ocurrencia de "ola", dentro de la palabra Solamente, por más que no sea la intención. El motor no sigue más allá de este punto para buscar "mejores" coincidencias.

* Obviamente una segunda búsqueda en el texto sí va a devolver la palabra, pero eso ya es otro tema.

Uno puede seguir los pasos que realiza el motor de regex mentalmente. El resultado siempre será lógico y predeterminado.


Las permutaciones de la expresión regular siempre se intentan en el mismo orden. Esto puede parecer algo tonto, totalmente obvio, pero les pido prestar mucha atención porque lo vamos a ir complicando, y es un punto tiene que estar completamente claro.

Tomemos como ejemplo el patrón /a|ab/g en el texto "@ab#". Estos son los pasos teóricos que se intentan dentro del motor de regex:

Descripción paso a paso. Primero intenta /a/, luego /ab/, como no coincide en posición 0, luego intenta /a/ desde posición 1 y devuelve "a"

Como se puede ver, se intenta desde la posición 0 del texto cada alternativa de la expresión regular. Primero se intenta con /a/ y luego con /ab/ porque ese es el orden en el que están en el regex (de izquierda a derecha). Al fallar todas las posibilidades en la posición 0, se intenta desde la posición 1 y coincide.

Si intentáramos una 2da coincidencia, se empezaría desde la posición final del último texto devuelto. Es decir:

No existe una 2da coincidencia

¿Por qué no devolvió "ab" si está en el texto? Porque la primera coincidencia encontrada fue "a", porque ese es el orden en el que el motor de regex hace los intentos. Al encontrar esa "a", el motor consume ese caracter. Lo devuelve como primera coincidencia, pero impide que esa a pueda usarse en un sucesivo intento.

Uno puede pensar a una expresión regular como un árbol de permutaciones, en el cual se intenta cada alternativa de izquierda a derecha hasta encontrar la primera coincidencia válida.


Una permutación a la izquierda antecede a una a la derecha. Al indicar que se intentan todas las permutaciones de la expresión regular, recorriendo el patrón de izquierda a derecha, nos referimos a que primero se busca una coincidencia en el primer subpatrón y, para ese subpatrón, se intentan todas las opciones del subpatrón que esté a la derecha.

Tomemos el regex /(?:a|b)(?:y|z)/. El árbol de permutaciones será:

Árbol de permutaciones, primera rama divide a de b, luego cada hijo se divide en y y z

Intentando la primera permutación de (?:a|b) con todas las alternativas derivadas, y luego la segunda permutación, de nuevo con todas las alternativas derivadas. Es importante ver que el regex es equivalente a /ay|az|by|bz/ en ese orden (y no en otro orden).



Backtracking

Hasta acá vimos en qué orden el motor de expresiones regulares intenta todas las permutaciones para encontrar una coincidencia. Pero es mucho más importante aún visualizar qué sucede cuando un subpatrón no coincide, y se debe retroceder para buscar otra alternativa.

Busquemos una palabra terminada en ra! con /\w+ra!/:

\w+ primero consume todo lo que puede, luego va intentando permutaciones con menos caracteres a medida de que va fallando, hasta coincidir con "palab"

Como se puede ver, el subpatrón \w+ primero intenta con todos los caracteres que puede coincidir. Inicialmente coincide con "palabra", pero en ese estadío los siguientes subpatrones no coinciden. Por consiguiente, se intenta una permutación con menos caracteres de \w+. Ese retroceso se denomina backtracking.

Así, el motor de expresiones regulares se da cuenta de que no hay otra permutación posible de ra! y va haciendo backtracking, intentando con \w+ coincidiendo con "palabr", y luego con "palab", hasta poder generar una coincidencia global. El resultado es la coincidencia en "palabra!".

Backtracking es el retroceso a un subpatrón previo que coincidió, cuando uno posterior no lo hizo, liberando caracteres con los que coincidió previamente para intentar una permutación diferente. Es parte de la lógica normal que ocurre dentro del motor de expresiones regulares para poder intentar todas las alternativas posibles hasta lograr una coincidencia.

El backtracking es una excelente característica de todos los motores de regex modernos: si un subpatrón no coincide, el motor retrocede al primer subpatrón en el que podría haber tomado otro camino. Un cuantificador goloso (avaro o greedy) puede liberar un caracter, un cuantificador no goloso (lazy) puede expandirse para tomar otro caracter, o se puede tomar una alternativa más a la derecha en una alternancia. Si un patrón sigue fallando, el motor explora todos los caminos sistemáticamente. [1]


Backtracking catastrófico

Significa que hay demasiadas permutaciones posibles para intentar antes de poder devolver un resultado. Se utilizan diferentes nombres para esta condición, todos sinónimos:

  • Backtracking catastrófico (catastrophic backtracking) [2]
  • Coincidencias exponenciales (exponential matches) o superlineales [3]
  • Cuantificadores explosivos (explosive quantifiers) [4]
  • Retroceso excesivo [5]

Algunos lenguajes tienen motores de regex que pueden identificar esta situación y devolver el correspondiente error, otros dispararán un stack overflow (desbordamiento de pila), y otros seguirán ejecutando sin devolver un error (que podría ser hasta años). En términos simples, es un loop (o mejor dicho varios loops) que recorre la misma parte del string demasiadas veces, tantas que la rutina se cuelga.

Si bien se debe a un regex "mal construido", la cantidad de permutaciones que se deben recorrer se incrementa exponencialmente(*) con el tamaño del texto que puede coincidir con el subpatrón problemático. Cada caracter extra multiplica el tiempo necesario para evaluarlo. Y por más que sea un subpatrón "mal construido", es muy fácil caer en la trampa.
(*) complejidad O(qn), con q el número de cuantificadores involucrados y n los caracteres en el texto. Normalmente O(2n).

"Alguien con poca experiencia en regex tiene una habilidad extraordinaria para generar una expresión exponencialmente compleja". [2]

Backtracking catastrófico es un problema que normalmente no surge con un texto que coincide. Al contrario, el problema suele presentarse con un texto que no coincide. Se dice que alguien con experiencia no crea un regex para que coincida con un texto, sino que crea una expresión que pueda fallar lo antes posible en textos inválidos.

Basta de definiciones, veamos tu ejemplo con /(a+)+b/ en el texto "aaaaaaaaazb".

En este caso, (a+)+ puede coincidir simplemente como a+, o se puede descomponer infinitamente en a+ a+a+. Está claro que se soluciona cambiando /(a+)+b/ por /a+b/, pero pensemos que es una simplificación en la que a+ representa un subpatrón más complejo que puede coincidir con 1 o más letras "a".

Descomposición de (a+)+ en a+a+a+a+ etc. Se muestra como cada paso de backtracking en el primer a+ va generando cada vez más opciones de a+a+a+ en el texto restante

¿Se puede ver como se van incrementando los pasos? Para cada alternativa del primer a+ con un caracter menos, se van incrementando exponencialmente la cantidad de subpatrones sucesivos sobre los que se tiene que seguir haciendo backtracking. Solamente se muestran las primeras 3 permutaciones del primer a+, y aún quedaban otras 6, cada una con un mayor número de pasos.

Cuantas más "a" consecutivas tenga el texto, habrá exponencialmente más permutaciones a intentar antes de poder devolver que no hay coincidencia. Con 9 "a" son 3063 iteraciones, con 10 "a" son 6134 iteraciones, con 11 son 12277, con 12 son 24564... ¡Y todas estas miles de operaciones están intentando ver si se coincide o no con un texto de 12 caracteres!

El tiempo necesario (o la memoria necesaria) llega a un punto en el que se excede el límite.

Cuando las propias permutaciones de un mismo subpatrón iteran sobre las mismas combinaciones del texto, incrementándose exponencialmente con la cantidad de caracteres con los que pueden coincidir, se llama backtracking catastrófico.


Evitar un backtracking catastrófico. La mejor receta para evitar este problema es poder reproducir mentalmente cada una de los pasos que realizará el motor de regex, intentando ver si se está iterando sobre el mismo texto más de una vez, y modificar la expresión para que no suceda.

Algunas construcciones que casi siempre llevan a un backtracking catastrófico son cuantificadores anidados ((x+)*) o grupos cuya alternancia incluya a uno en el otro ((\d+|\w){4,}).

Únicamente es seguro utilizar un cuantificador anidado cuando el inicio de una alternativa dentro del grupo no es opcional, y es mutuamente exclusiva con el inicio de todas las otras alternativas, así como mutuamente exclusiva con el subpatrón que lo suceda.

Por ejemplo, la expresión /(a+y+|b+z+)+x/ no generará un backtracking catastrófico porque, como cada subpatrón es mutuamente exclusivo, cuando la expresión falle se irá haciendo backtracking linealmente. Es decir, como son mutuamente exclusivos, no va a iterar sobre el mismo texto con otra permutación del patrón.

Cuando se usen cuantificadores anidados, se debe estar completamente seguro de que existe una única forma de llegar a la misma coincidencia.

En la práctica. Un regex de un caso real puede tener una construcción que lleve a un backtracking catastrófico y ser realmente difícil de identificar. Incluso, sin llegar a un extremo, por más que no genere un error, la idea es evitar iteraciones innecesarias. No obstante, no hay una receta mágica para solucionarlo. Lleva práctica identificar el problema, y cada caso tiene una solución diferente (o varias) que depende de con lo que se esté intentando coincidir.



Impedir el backtracking

Existen 2 construcciones que pueden ayudar: grupos atómicos y cuantificadores posesivos. Ambos funcionan de igual manera, y ambos pueden ayudar con los problemas descriptos hasta ahora. Voy a describir cómo funcionan, pero cuándo usarlos va a depender de cada caso y queda en la creatividad de cada desarrollador.

Ambos tienen la particularidad de que, una vez que se haya encontrado una coincidencia parcial, no se intentará una permutación diferente del mismo. Es decir, no habrá otra alternativa cuando se llegue por backtracking.


Grupos atómicos (?>)     -     ()

Teniendo la expresión /a(?>b+)c*/, una vez que b+ haya encontrado una coincidencia, por ejemplo "bbbb", por más que luego c* falle, no se intentará una permutación con menos caracteres de b+. Si el motor de regex sale de un grupo atómico pasando el paréntesis que lo cierra, no puede volver a entrar para hacer backtracking con otra alternativa del mismo. Son grupos que coinciden con todo o nada.

Por ejemplo, el regex /(?>a+)\w+z/ coincide con "aaxz" pero no coincide con "aaz".
En contraste, /(?:a+)\w+z/ hubiese coincidido con ambos.

Los grupos atómicos son útiles cuando se sabe de antemano que las diferentes alternativas de un grupo son mutuamente excluyentes. Por ejemplo, la expresión /\b(?>palabra|palacio|pala)\b/ coincide con una de esas 3 palabras. Es evidente por los límites de palabra (\b) que coinciden con lo mismo que si el grupo no fuese atómico. No obstante, si un subpatrón posterior falla, le ahorran algunos pasos al motor de regex, para que no busque otras alternativas que jamás van a coincidir. Si la lista de palabras fuese larga, el ahorro puede ser significativo.

No obstante, se debe tener cuidado. Una expresión como /\b(?>pala|palabra|palacio)\b/ jamás va a coincidir con el texto "palacio", porque una vez que pala coincide y \b no, no puede intentar las alternativas más hacia la derecha, o sea que jamás va a intentar palabra o palacio.


Cuantificadores posesivos x*+     -     ()

Un cuantificador posesivo (un + de más) cumple la misma función que un grupo atómico. Consiste en un + luego de un cuantificador. Por ejemplo a*+, b?+, c++, d{1,4}+, etc. Una vez que obtenga una coincidencia, si vuelve durante el backtracking, no se intentará otra permutación del mismo.

Normalmente son considerados como una notación abreviada para grupos atómicos.



Lecturas recomendadas



Tus otras preguntas

pero si uso el patron b(a+)+ sobre "bzaaaaaaaaaaaaaaaaaa" no ocurre este error.

Porque el motor de regex jamás llega a intentar diferentes permutaciones de (a+)+. En la primera posición, b coincide pero el primer a+ no. Y a partir de ahí, seguirá intentando posición por posición, siempre fallando en b. Además, al tener a (a+)+ al final del regex, no hay un subpatrón posterior que pueda fallar y hacer que se vuelva en backtracking.

Para solucionarlo ¿como funcionan (?>), (?<=), (?<!), (?=) y (?!)?

Expliqué los grupos atómicos (?>). El resto son inspecciones (lookarounds) que no tienen nada que ver con la pregunta o con backtracking. Las inspecciones son atómicas, pero eso no está relacionado directamente con nada relativo al backtracking catastrófico.

¿que significa (*SKIP), (*PRUNE), (*FAIL)? ¿tienen algun equivalente en java o .net?

Son verbos de control. Cambian el comportamiento del motor de regex cuando se llega a éstos por backtracking. Sin embargo, no están relacionados directamente con tu pregunta principal. Se usan para otros casos específicos. Generalmente hay formas de lograr lo mismo en Java o .Net. Podría mostrarte una sintaxis genérica, pero prefiero recomendarte que no tomes ninguna regla y que logres tus expresiones sin pensar en estos verbos.

3
  • 1
    gracias, eso me aclaró todo
    – Omar
    el 18 abr. 2018 a las 14:24
  • Hola @Mariano, tengo una duda. ¿Esto no dependería un poco de la implementación del motor? Si la implementación estuviera basada en autómatas finitos, el motor minimizará el autómata y en tu sección de "Backtracking catastrófico" nunca se hará backtraking debido a que el autómata asociado inicialmente a la expresión regular será convertido a un autómata finito determinista (aparte de ser minimizado). Puedes ver el proceso completo en los primeros capítulos del conocidísimo libro "Compiladores: principios técnicas y herramientas". el 5 sep. 2018 a las 9:35
  • 1
    Una gran respuesta! Muchas gracias por compartirla @Mariano !!!
    – Borjinha10
    el 6 feb. 2019 a las 10:43

Tu Respuesta

Al pulsar en “Publica tu respuesta”, muestras tu consentimiento a nuestros términos de servicio, política de privacidad y política de cookies

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.