Regular Expressions Cosa causa Backtracking?


Esempio

Per trovare una corrispondenza, il motore regex consumerà i caratteri uno per uno. Quando inizia una partita parziale, il motore ricorderà la posizione di partenza in modo che possa tornare indietro nel caso in cui i seguenti personaggi non completino la partita.

  • Se la partita è completa, non c'è il backtracking
  • Se la partita non è completa, il motore farà retrocedere la stringa (come quando si riavvolge un vecchio nastro) per cercare di trovare un'intera partita.

Ad esempio: \d{3}[az]{2} contro la stringa abc123def sarà sfogliato come tale:

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

Ora lascia cambiare la regex in \d{2}[az]{2} con la stessa stringa ( 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