Regular Expressions Perché il backtracking può essere una trappola?


Esempio

Il backtracking può essere causato da quantificatori o costrutti di alternanza opzionali, perché il motore regex cercherà di esplorare ogni percorso. Se esegui regex a+b contro aaaaaaaaaaaaaa non c'è corrispondenza e il motore lo troverà piuttosto veloce.

Ma se cambi la regex in (aa*)+b il numero di combinazioni crescerà abbastanza velocemente, e la maggior parte dei motori (non ottimizzati) cercheranno di esplorare tutti i percorsi e impiegheranno un'eternità per cercare di trovare una corrispondenza o lanciare un eccezione di timeout. Questo è chiamato backtracking catastrofico .

Certo, (aa*)+b sembra un errore newbie ma è qui per illustrare il punto e a volte si finirà con lo stesso problema ma con schemi più complicati.

Un caso più estremo di backtracking catastrofico si verifica con la regex (x+x+)+y (probabilmente lo avete visto prima qui e qui ), che ha bisogno di tempo esponenziale per capire che una stringa che contiene x nient'altro (es. xxxxxxxxxxxxxxxxxxxx ) non corrispondono.

Come evitarlo?

Sii il più specifico possibile, riduci il più possibile i possibili percorsi. Nota che alcuni reenerx matcher non sono vulnerabili al backtracking, come quelli inclusi in awk o grep perché sono basati su Thompson NFA .