Backtracking: conceptos

Cuando un cuantificador codicioso "se excede", el motor retrocede: retroceder un paso, probar con otra configuración, intentarlo de nuevo. vamos los patrones simples son invisibles; en patrones mal escritos puede convertirse exponencial y bloquea el navegador por segundos. Es la raíz de ReDoS (Expresión regular Denegación de Servicio).

Pattern: .*\d
Sample:  abc123def
Steps:
  1.  .*  consuma tutto: "abc123def"
  2.  \d  fallisce (fine stringa).
  3.  Backtrack: .* lascia 'f' -> "abc123de", \d fallisce su 'f'.
  4.  Backtrack: .* lascia 'ef' -> "abc123d", \d fallisce su 'e'.
  5.  ... e cosi' via finche' \d trova una cifra: match = "abc123" + "?"... in realta'
       il pattern matcha "abc123" perche' .* lascia "def" e \d cerca su '3'? No: il backtrack
       continua e .* finisce per essere "abc12", \d=3.  Match finale: "abc123".

El motor siempre llega allí, pero si el cuantificador codicioso lo tiene dentro un otro cuantificador codicioso (por ejemplo, (a+)+), el número de Las configuraciones a probar pueden explotar.

Patrones catastróficos

Pattern: (a+)+b
Sample:  aaaaaaaaaaaaaaaaaaaaa

Nada final b → el patrón falla, pero el motor intenta llegar allí todas las particiones posibles de a. crecimiento exponencial: con 30 a puedes esperar horas.

Peligros de retroceso y ReDoS

Cuando un patrón incluye cuantificadores superpuestos o anidados (por ejemplo, (a+)+), el motor evalúa un número exponencial de combinaciones antes de fallar. Reemplazar comodines genéricos con clases de caracteres excluyentes reduce drásticamente las rutas de retroceso.

Pruébalo tú mismo

Ejercicio de revisión

Desafío adicional