Regular Expressions
Откат

Что вызывает обратное отслеживание?

Чтобы найти совпадение, механизм регулярных выражений будет потреблять символы один за другим. Когда начинается частичное совпадение, двигатель запомнит начальную позицию, чтобы вернуться в случае, если следующие символы не совпадают.

• Если совпадение завершено, то нет возврата
• Если совпадение не завершено, движок будет возвращать строку (например, когда вы перематываете старую ленту), чтобы попытаться найти целое совпадение.

Например: \d{3}[az]{2} против строки 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 match \d (third one)
abc123def
      ^ Does match [a-z] (first one)
abc123def
       ^ Does match [a-z] (second one)
           MATCH FOUND

Теперь изменим регулярное выражение на \d{2}[az]{2} на ту же строку ( 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

Почему возвращение может быть ловушкой?

Откат может быть вызван дополнительными кванторами или альтернативными конструкциями, поскольку механизм регулярных выражений будет пытаться исследовать каждый путь. Если вы запустите регулярное выражение a+b против aaaaaaaaaaaaaa нет, и двигатель найдет его довольно быстро.

Но если вы измените регулярное выражение на (aa*)+b количество комбинаций будет расти довольно быстро, и большинство (не оптимизированных) движков будут пытаться исследовать все пути, и у них будет целая вечность, чтобы попытаться найти совпадение или бросить исключение тайм-аута. Это называется катастрофическим отступлением .

Конечно, (aa*)+b кажется ошибкой новичка, но здесь здесь, чтобы проиллюстрировать этот момент, и иногда вы столкнетесь с той же проблемой, но с более сложными шаблонами.

Более экстремальный случай катастрофического обратного следования происходит с регулярным выражением (x+x+)+y (вы, вероятно, видели его здесь и здесь ), которому требуется экспоненциальное время, чтобы выяснить, что строка, содержащая x s и ничего (например, xxxxxxxxxxxxxxxxxxxx ) не соответствуют этому.

Как этого избежать?

Будьте как можно более конкретными, максимально уменьшите возможные пути. Обратите внимание, что некоторые регулярные выражения не уязвимы для обратного отслеживания, например, в awk или grep поскольку они основаны на Thompson NFA .