Regular Expressions
Retroceso

¿Qué causa el Backtracking?

Para encontrar una coincidencia, el motor de expresiones regulares consumirá caracteres uno por uno. Cuando comienza una coincidencia parcial, el motor recordará la posición de inicio para que pueda retroceder en caso de que los siguientes caracteres no completen la coincidencia.

• Si la coincidencia es completa, no hay retroceso.
• Si la coincidencia no está completa, el motor retrocederá la cadena (como cuando rebobinó una cinta vieja) para tratar de encontrar una coincidencia completa.

Por ejemplo: \d{3}[az]{2} contra la cadena abc123def buscará como tal:

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

Ahora cambiemos la expresión regular a \d{2}[az]{2} contra la misma cadena ( abc123def ):

abc123def
^ Does not match \d
abc123def
 ^ Does not match \d
abc123def
  ^ Does not match \d
abc123def
   ^ Does match \d (first one)
abc123def
    ^ Does match \d (second one)
abc123def
     ^ Does not match [a-z]
abc123def
    ^ BACKTRACK to catch \d{2} => (23)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

¿Por qué el retroceso puede ser una trampa?

El retroceso puede ser causado por cuantificadores opcionales o construcciones de alternancia, porque el motor de expresiones regulares intentará explorar cada ruta. Si ejecuta la expresión regular a+b contra aaaaaaaaaaaaaa no hay coincidencia y el motor lo encontrará bastante rápido.

Pero si cambia la expresión regular a (aa*)+b la cantidad de combinaciones crecerá bastante rápido, y la mayoría de los motores (no optimizados) intentarán explorar todos los caminos y tomarán una eternidad para tratar de encontrar una coincidencia o lanzar una excepción de tiempo de espera. Esto se llama retroceso catastrófico .

Por supuesto, (aa*)+b parece un error de novato, pero está aquí para ilustrar el punto y, a veces, terminará con el mismo problema pero con patrones más complicados.

Un caso más extremo de retroceso catastrófico ocurre con la expresión regular (x+x+)+y (probablemente lo haya visto antes aquí y aquí ), que necesita un tiempo exponencial para descubrir que una cadena que contiene x s y nada más (por ejemplo, xxxxxxxxxxxxxxxxxxxx ) no coinciden.

¿Cómo evitarlo?

Sea lo más específico posible, reduzca lo más posible los caminos posibles. Tenga en cuenta que algunos comparadores de expresiones regulares no son vulnerables al retroceso, como los incluidos en awk o grep porque se basan en Thompson NFA .