Регулярные выражения Perl и их применение


Возвраты и сохраненные состояния


Линейный алгоритм поиска не всегда обеспечивает нахождение совпадения. Рассмотрим такой пример: пусть мы имеем шаблон

\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




Начало  Назад  Вперед



Книжный магазин