Книга: Выразительный JavaScript

Откаты

Откаты

Регулярка /b([01]+b|d+|[da-f]h)b/ совпадает либо с двоичным числом, за которым следует b, либо с десятичным числом без суффикса, либо шестнадцатеричным (цифры от 0 до 9 или символы от a до f), за которым идёт h. Соответствующая диаграмма:

В поисках совпадения может случиться, что алгоритм пошёл по верхнему пути (двоичное число), даже если в строке нет такого числа. Если там есть строка “103”, например, понятно, что только достигнув цифры 3 алгоритм поймёт, что он на неправильном пути. Вообще строка совпадает с регуляркой, просто не в этой ветке.

Тогда алгоритм совершает откат. На развилке он запоминает текущее положение (в нашем случае, это начало строки, сразу после границы слова), чтобы можно было вернуться назад и попробовать другой путь, если выбранный не срабатывает. Для строки “103” после встречи с тройкой он вернётся и попытается пройти путь для десятичных чисел. Это сработает, поэтому совпадение будет найдено.

Алгоритм останавливается, как только найдёт полное совпадение. Это значит, что даже если несколько вариантов могут подойти, используется только один из них (в том порядке, в каком они появляются в регулярке).

Откаты случаются при использовании операторов повторения, таких, как + и *. Если вы ищете /^.*x/ в строке "abcxe", часть регулярки .* попробует поглотить всю строчку. Алгоритм затем сообразит, что ему нужен ещё и “x”. Так как никакого “x” после конца строки нет, алгоритм попробует поискать совпадение, откатившись на один символ. После abcx тоже нет x, тогда он снова откатывается, уже к подстроке abc. И после строчки он находит x и докладывает об успешном совпадении, на позициях с 0 по 4.

Можно написать регулярку, которая приведёт ко множественным откатам. Такая проблема возникает, когда шаблон может совпасть с входными данными множеством разных способов. Например, если мы ошибёмся при написании регулярки для двоичных чисел, мы можем случайно написать что-то вроде /([01]+)+b/.

Если алгоритм будет искать такой шаблон в длинной строке из нолей и единиц, не содержащей в конце “b”, он сначала пройдёт по внутренней петле, пока у него не кончатся цифры. Тогда он заметит, что в конце нет “b”, сделает откат на одну позицию, пройдёт по внешней петле, опять сдастся, попытается откатиться на ещё одну позицию по внутренней петле… И будет дальше искать таким образом, задействуя обе петли. То есть, количество работы с каждым символом строки будет удваиваться. Даже для нескольких десятков символов поиск совпадения займёт очень долгое время.

Оглавление книги