Возвраты и сохраненные состояния
Линейный алгоритм поиска не всегда обеспечивает нахождение совпадения. Рассмотрим такой пример: пусть мы имеем шаблон
\w+bb
и строку
aaabb
При сопоставлении этой строки шаблону модификатор + захватит все символы, и на долю подшаблона bb ничего не останется. Но после этой неудачи не произойдет сразу итерации поиска со следующего символа, т.к. в совпавшей части шаблона имеются квантификаторы, у которых может быть разное число повторов. В этом случае произойдет возврат к последнему подшаблону с таким квантификатором и к позиции в тексте, с которой он совпадал. Но для таких возвратов надо для каждого пройденного подшаблона с квантификатором запоминать значения этого квантификатора и позицию в тексте, с которой совпал этот подшаблон. В нашем случае вначале для подшаблона \w+ будет запомнено 5 состояний: что он захватил с начала текста a, aa, aaa, aaab и aaabb.
Для хранения этих состояний требуется память, поэтому, как мы видели, максимальное значение, которое могут иметь квантификаторы, ограничено. Кроме того, есть ограничение на количество всех сохраненных состояний для всего шаблона.
Т.к. для литерала b в шаблоне не находится соответствия, "жадность" квантификатора будет уменьшена на один символ, и мы будем иметь совпадение подшаблона \w+ с подстрокой aaab, далее подшаблон b совпадет с символом b, а на следующий подшаблон b ничего не останется. На самом деле, литералы сравниваются не по одному символу, а по целому литералу (если не указан модификатор i), а пример выше я привел для наглядности рассуждений.
Лишь при втором уменьшении "жадности" квантификатора + будет найдено совпадение для всего шаблона:
\w+ совпадет с aaa,
подшаблон bb совпадет с bb.
Если бы текст на этом не заканчивался, то все равно было бы зафиксировано совпадение и оператор поиска вернул бы истину. Ведь шаблон поиска не привязан к концу строки якорями $, \z или \Z. Если бы это имело место, то поиск мог бы закончиться успехом только тогда, когда шаблон и текст исчерпываются одновременно. Точнее говоря, после исчерпания шаблона, оканчивающегося на $ или \Z, в тексте может еще остаться единственный символ новой строки \n.
Мы рассмотрели самый элементарный пример возврата при поиске. В шаблоне может находиться много подшаблонов с квантификаторами, и внутри подшаблона с квантификатором могут быть другие такие подшаблоны. Но принцип возвратов остается прежним: в случае локальной неудачи поиска совпадения происходит откат к предыдущему минимальному подшаблону, имеющему переменный квантификатор.
Разумеется, квантификаторы вида a{20} не могут порождать возвратов, это просто иная запись литерала.
Что будет в случае с минимальным квантификатором? В этом случае он начинает захват с наименьшего возможного значения квантификатора (от нуля и далее). А механизм поиска кроме запоминания текущей позиции совпадения для каждого такого подшаблона и его значения, конечно, "знает" о том, какой вид имеет этот квантификатор: минимальный или максимальный.
Если рассмотреть пример шаблона
\w{1,3}?b
и строку
aaaabb
то совпадение с первого символа строки вообще не будет найдено ни при каких значениях квантификатора. Оно будет найдено со второго символа строки и после того, как будут перепробованы значения квантификатора 1, 2 и 3. В результате получим совпадение подшаблона \w{1,3}? с подстрокой aaa, и затем подшаблон b совпадет с символом b. На этом поиск совпадения успешно закончится.
и строку
aaaabb
то совпадение с первого символа строки вообще не будет найдено ни при каких значениях квантификатора. Оно будет найдено со второго символа строки и после того, как будут перепробованы значения квантификатора 1, 2 и 3. В результате получим совпадение подшаблона \w{1,3}? с подстрокой aaa, и затем подшаблон b совпадет с символом b. На этом поиск совпадения успешно закончится.
Рассмотрим еще один пример. Пусть мы имеем шаблон
abcd|abc|ab
и строку
ab
Когда механизм поиска обрабатывает конструкцию выбора, он пытается найти совпадение с одной и той же текущей позиции текста, пробуя для нее последовательно эти подшаблоны в порядке их записи (слева направо). Если какой-то подшаблон совпал, то механизм поиска пропускает оставшиеся подшаблоны из конструкции выбора и далее переходит к подшаблону, стоящему за этой конструкцией.
В нашем примере сначала будет попробован подшаблон abcd, эта проба закончится неудачей. Также неудачей закончится проба следующего подшаблона abc. И только последний подшаблон ab совпадет. Если бы после этой конструкции выбора шаблон продолжался и следующий за ней подшаблон не совпал, то в общем случае произошел бы возврат к этой конструкции выбора и в дело пошел бы следующий за ab подшаблон (если бы он существовал). В этом примере ab - последний подшаблон, поэтому в общем случае возврат продолжился бы еще левее, за конструкцию выбора и так далее до самого начала всего шаблона. И только в случае, когда при всевозможных значениях квантификаторов и номеров подшаблонов в конструкциях выбора совпадение не было бы найдено, произошло бы продвижение начальной позиции поиска в тексте на один символ.
На этом примере надо усвоить одно важное правило использования конструкций выбора: если в такой конструкции есть подшаблоны, которые могут совпасть с текущей позицией текста, то имеет значение порядок следования этих подшаблонов. Представим, что имеется шаблон
(ab|abc)\w*
и строка
abc
Первый, более короткий подшаблон совпадет, и текущая позиция в шаблоне перейдет за конструкцию выбора. А нам, может быть, хотелось бы, чтобы совпал более длинный подшаблон abc. В этом случае его надо ставить раньше подшаблона ab. Вот еще более очевидный пример: в конструкции выбора
.*|abc
первый подшаблон может совпасть с текущей позиции текста всегда при нулевом значении квантификатора *. До попытки применить вторую альтернативу очередь никогда не дойдет, как будто ее нет вовсе!
Когда происходит возврат в шаблоне за подшаблон с квантификаторами, то запомненные состояния для всех квантификаторов в этом подшаблоне сбрасываются, чтобы при следующем движении по шаблону вправо они работали с начала. Аналогично, номера подшаблонов в конструкциях выбора сбрасываются в нуль.
Такой алгоритм поиска называется недетерминированным конечным автоматом (НКА). Этот алгоритм управляется шаблоном, и программист может указать, какое именно совпадение ему нужно. Существуют другие алгоритмы поиска (детерминированный конечный автомат ДКА или смешанные алгоритмы), но в языке Perl и других языках и библиотеках (PHP, PCRE) применяется НКА, хотя он не самый быстрый среди алгоритмов поиска. Программисту, привыкшему к алгоритму НКА, другой язык программирования, который использует другой алгоритм поиска, может преподнести сюрприз. Я уже не говорю о том, что в других языках некоторые метасимволы могут работать иначе, чем в Perl.
Рассмотрим еще примеры:
$_='abcd'; /(\w+)(\w+)/; print "$1|$2";
Сначала первая пара скобок захватит всю строку, но во имя нахождения совпадения для всего шаблона пожертвует одним символом для второй скобки. В результате будет напечатано abc|d. Если во второй паре скобок вместо плюса стояла бы звездочка или вопросительный знак, то на их долю вообще не осталось бы символов - все их поглотил бы квантификатор из первой пары скобок, и переменная $2 получила бы пустое значение. Вот она, "жадность" в действии. Каждый "жадный" квантификатор оставляет остальной части шаблона минимум символов, лишь бы нашлось совпадение.
Минимальные квантификаторы действуют наоборот: берут себе минимум символов, а оставляют максимум для нахождения совпадения. Конструкция же выбора не минимальна и не максимальна, она упорядочена по очереди появления в ней альтернативных подшаблонов.
Возьмем шаблон
12?3
Чтобы избежать этой ошибки, нужно директивой
use re 'eval';
разрешить вставку кода Perl внутрь шаблонов.
Этот код у нас распечатывает текущую позицию поиска pos в строке $_ (позиция отсчитывается от нуля) и значение переменной $1.
Вначале мы видим строку
Starting from 0
Она говорит о старте очередной итерации поиска. Эта итерация в нашем примере единственная. Далее происходит сопоставление \w и символа a, а затем - печать текущей позиции поиска (2) и значения переменной $1. Но т.к. эта печать происходит еще до закрытия захватывающей скобки, когда переменная $1 еще не появилась, то возникает предупреждающее сообщение об использовании неопределенной переменной. Конечно, его можно было бы избежать, если написать
print "$1\n" if defined $1;
Но я не стал излишне загромождать код.
Затем скобки захватывают символ a, и переменная $1 приобретает значение $1='a', а квантификатор * заставляет вернуться за закрывающую скобку и повторить поиск, начиная от \w. Теперь \w соответствует символу b, а распечатывается текущая позиция 2 и текущее значение $1, которое равно a. Затем повторяется тот же самый цикл, который печатает очередные текущие позиции и захваченные символы. После того, как подшаблон \w совпадает с d, печатается последняя позиция этой строки 4 и текущее значение $1, которое равно c. Значение d не вышло на печать, т.к. печать происходит до закрытия захватывающей скобки. А если бы мы вставили печать после нее или следующим оператором за оператором поиска, то увидели бы и значение d.
С помощью такого диагностического вывода можно отследить, как выполняется поиск. Иногда вывод показывает слишком большое число итераций и/или возвратов, которые надо оптимизировать.
