Regular Expressions
Cofanie

Co powoduje Cofanie?

Aby znaleźć dopasowanie, silnik wyrażeń regularnych zużywa znaki jeden po drugim. Kiedy rozpocznie się częściowe dopasowanie, silnik zapamięta pozycję początkową, aby mógł cofnąć się w przypadku, gdy następujące postacie nie ukończą meczu.

• Jeśli dopasowanie jest zakończone, nie ma powrotu do przeszłości
• Jeśli dopasowanie nie zostanie ukończone, silnik cofnie łańcuch (tak jak podczas przewijania starej taśmy), aby spróbować znaleźć całe dopasowanie.

Na przykład: \d{3}[az]{2} przeciwko ciągowi abc123def będzie przeglądany jako taki:

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

Teraz abc123def wyrażenie regularne na \d{2}[az]{2} stosunku do tego samego łańcucha ( 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

Dlaczego powrót może być pułapką?

Cofanie może być spowodowane przez opcjonalne kwantyfikatory lub konstrukcje alternatywne, ponieważ silnik regex będzie próbował zbadać każdą ścieżkę. Jeśli użyjesz wyrażenia regularnego a+b przeciwko aaaaaaaaaaaaaa nie będzie żadnego dopasowania, a silnik znajdzie go dość szybko.

Ale jeśli zmienisz wyrażenie regularne na (aa*)+b liczba kombinacji będzie rosła dość szybko, a większość (niezoptymalizowanych) silników spróbuje zbadać wszystkie ścieżki i zajmie wieczność, aby znaleźć dopasowanie lub rzucić wyjątek limitu czasu. Nazywa się to katastrofalnym wycofywaniem .

Oczywiście (aa*)+b wydaje się błędem dla początkujących, ale ma to na celu zilustrowanie tego problemu, a czasem możesz spotkać ten sam problem, ale z bardziej skomplikowanymi wzorami.

Bardziej ekstremalny przypadek katastrofalnego cofania występuje w przypadku wyrażenia regularnego (x+x+)+y (prawdopodobnie widziałeś go wcześniej tutaj i tutaj ), który potrzebuje wykładniczego czasu, aby dowiedzieć się, że ciąg zawierający x si nic więcej (np. xxxxxxxxxxxxxxxxxxxx ) nie pasuje.

Jak tego uniknąć?

Bądź tak szczegółowy, jak to możliwe, zmniejsz w możliwie największym stopniu możliwe ścieżki. Zauważ, że niektóre dopasowujące wyrażenia regularne nie są podatne na wycofanie, takie jak te zawarte w awk lub grep ponieważ są oparte na Thompson NFA .