Минимальные квантификаторы

Четыре квантификатора, встречавшиеся нам ранее, являются максимальными (greedy). Это означает, что они находят совпадение максимально возможной длины и неохотно «уступают» символы только в том случае, если это необходимо для общего совпадения шаблона. Пример: допустим, шаблон /fred.+barney/ применяется к строке fred and barney went bowling last night. Понятно, что совпадение будет найдено, но давайте посмотрим, как это происходит. Сначала, конечно, элемент шаблона fred совпадает с идентичной литеральной строкой. Далее следует элемент .+, который совпадает с любым символом, кроме символа новой строки, не менее одного раза. Но квантификатор + «жаден»: он пытается захватить как можно больше символов. Поэтому он немедленно пытается найти совпадение для всей оставшейся строки, включая слово night. (Как ни странно, поиск совпадения на этом не закончен.)

Теперь ядру хотелось бы найти совпадение для элемента barney, но сделать это не удается – мы находимся в конце строки. Но т. к. совпадение .+ будет считаться успешным даже в случае, если оно станет на один символ короче, + неохотно уступает букву t в конце строки. (Несмотря на «жадность», квантификатор стремится к совпадению всего выражения даже больше, чем к захвату максимального числа символов.) Снова ищется совпадение для элемента barney, и снова поиск оказывается неудачным.


Элемент .+ уступает букву h и делает очередную попытку. Так, символ за символом .+ отдает весь захваченный фрагмент, пока в какой-то момент не уступит все буквы barney. Теперь для элемента barney находится совпадение и общий поиск завершается удачей. Ядро регулярных выражений постоянно «отступает» подобным образом, перебирая все возможные варианты размещения шаблона, пока один из них не завершится удачей или станет ясно, что совпадение невозможно. Но как видно из рассмотренного примера, поиск может потребовать большого количества «отступлений», потому что квантификатор захватывает слишком большую часть строки, а ядро регулярных выражений заставляет его вернуть часть символов.

Однако у каждого максимального («жадного») квантификатора существует парный минимальный квантификатор. Вместо плюса (+) мы можем использовать минимальный квантификатор +?. Как и +, он совпадает один или несколько раз, но при этом довольствуется минимальным количеством символов (вместо максимально возможного). Давайте посмотрим, как работает новый квантификатор в шаблоне /fred.+?barney/. Совпадение для fred снова находится в самом начале строки. Но на этот раз следующий элемент шаблона .+? старается совпасть с одним символом, поэтому на совпадение с ним проверяется только пробел после fred.


Следующий элемент шаблона barney в этой позиции совпасть не может (так как строка в текущей позиции начинается с and barney…). Элемент .+? неохотно добавляет к совпадению a и повторяет попытку.

И снова для barney не находится совпадения, поэтому .+? добавляет букву n и т. д. Когда .+? совпадет с пятью символами, для barney будет найдено совпадение, и применение шаблона завершится успешно. И в этом случае без неудачных попыток не обошлось, но ядру пришлось возвращаться всего несколько раз, что должно обеспечить значительный выигрыш по скорости. Вообще говоря, выигрыш присутствует только в том случае, если barney обычно находится вблизи от fred. Если в ваших данных fred чаще всего находится в начале строки, а barney – в конце, максимальный квантификатор будет работать быстрее. В конечном итоге скорость работы регулярных выражений зависит от данных. Но достоинства минимальных квантификаторов не ограничиваются эффективностью. Хотя они всегда совпадают (или не совпадают) в тех же строках, что и их максимальные версии, квантификаторы могут совпасть с разными частями строки. Допустим, у нас имеется HTMLQ подобный1 текст, из которого необходимо удалить все теги и , оставив их содержимое без изменений.


Текст выглядит так:

I’m talking about the cartoon with Fred and Wilma!

А вот оператор замены для удаления этих тегов. Почему он не подходит?

s#(.*)#$1#g;

Проблема в максимальности квантификатора *. А если бы текст выглядел так:

I thought you said Fred and Velma, not Wilma

Шаблон совпадет с текстом от первого тега до последнего тега , а все промежуточные теги останутся в строке. Какая неприятность! Вместо максимальных квантификаторов здесь необходимо использовать минимальные квантификаторы. Минимальная форма * имеет вид *?, так что замена принимает вид

s#(.*?)#$1#g;

И она работает правильно. Итак, в минимальной версии + превращается в +?, а * в *?. Вероятно, вы уже догадались, как будут выглядеть два других квантификатора. Минимальная форма квантификатора в фигурных скобках выглядит аналогично, но вопросительный знак ставится после закрывающей скобки, например {5,10}? или {8,}?.1 Даже квантификатор ? существует в минимальной форме: ??. Она совпадает только один раз или не совпадает вовсе, причем второй вариант является предпочтительным.

Оцените статью: (0 голосов)
0 5 0

Статьи из раздела Perl на эту тему:
m// в списочном контексте
Глобальная замена (/g)
Другие возможности регулярных выражений
Другие ограничители
Замена с использованием оператора s///