Принципы жадности, торопливости и возврата при поиске по шаблону (в регулярных выражениях языка Perl)
В двух недавних публикациях мы кратко рассмотрели богатые возможности, которые предоставляет Perl для и по шаблону. Однако осталась незатронутой очень важная сторона вопроса: каким образом происходит поиск, какими принципами руководствуется Perl в этом процессе? Без понимания этих нюансов невозможно воспользоваться всей мощью регулярных выражений. Более того, очень часто результат поиска может оказаться абсолютно неожиданным для пользователя, не знакомого с принципами жадности , торопливости и возврата . Проиллюстрируем это несколькими примерами.
Составляя регулярные выражения для поиска по шаблону, всегда нужно учитывать: Perl по умолчанию очень жаден. Это означает, что, получив шаблон для обработки, он будет искать в тексте максимально длинное соответствие заданным условиям. Возьмем для примера фразу Perl for girls . Как "найти" в ней слово Perl, какой шаблон применить? На первый взгляд, вполне подходит P.+l . То есть мы пытаемся отыскать фрагмент текста, начинающийся с заглавной буквы P , после которой следует один или более других символов, а заканчивается фрагмент буквой l . Вроде бы, все верно. Однако если мы попытаемся применить этот шаблон на практике, жадный Perl выдаст нам несколько неожиданный результат, а именно: Perl for girl . Убедитесь сами:
if ("Perl for girls" =~ /(P.+l)/) {
print "$1";
}
Здесь жадность Perl проявляется во всей красе. Результат
Perl for girl
шаблону соответствует? Соответствует, ведь он начинается с заглавной
P
, а заканчивается строчной
l
. Значит именно он и будет выбран, а менее "объемный" результат - слово
Perl
- результатом не признается.
Как усмирять жадность Perl? Для этого жадные или максимальные метасимволы-повторители *, +, ? и {} заменяют на их минимальные аналоги: *?, +?, ?? и {}?. ( Примечание: Метасимволы-повторители часто называют квантификаторами. Как видим, для того чтобы квантификатор перестал проявлять чрезмерную жадность, к нему достаточно приписать знак вопроса: P.+?l . Попробуйте сделать это в предыдущем примере, результатом выполнения функции станет слово Perl .
При всей своей жадности Perl еще и на удивление тороплив при поиске. Он пытается максимально быстро найти соответствие шаблону, что также может привести к определенным казусам. Например, что получится, если к слову Hostinfo применить простейшую подстановку s/i*/I/ ? Казалось бы, результат очевиден: сначала в слове будет найдена буква i , после чего она превратится в заглавную. Попробуем:
$phrase = "Hostinfo";Результат - IHostinfo несколько неожиданный, не правда ли? Но это только на первый взгляд. На самом деле все сработало верно. Ведь шаблон i* призывает найти ноль и более букв i в слове. Perl начинает работу и тут же убеждается, что ноль букв i встречается в самом начале слова. Ничтоже сумняшеся, Perl, следуя принципу торопливости, производит замену.
$phrase =~ s/i*/I/;
print "$phrase";
Как мы уже неоднократно убеждались в предыдущих публикациях на эту тему, шаблоны могут быть достаточно сложными, состоять из нескольких частей. Для того чтобы фрагмент текста совпал с шаблоном, необходимо полное совпадение этого фрагмента со всеми частями регулярного выражения. Нужно понимать, как Perl работает с этими "многокомпонентными" выражениями. Проверив первую часть и обнаружив совпадение, Perl переходит ко второй части. Если здесь совпадения не обнаружено, он возвращается к первой части выражения и ищет в тексте следующий фрагмент, совпадающий с ней. Эта история повторяется до тех пор, пока не будет найдено полное совпадение фрагмента текста и всех частей регулярного выражения. Такой принцип работы и получил название возврат . Проиллюстрируем его на простом примере.
В статье мы реализовали простую функцию для смены формата записи даты. Для этого использовалось следующая подстановка: s/(\d{4})-(\d{2})-(\d{2})/$3\.$2\.$1/ . Посмотрим, как она сработает, будучи "натравлена" на текст 2004-й год начался на следующий день после 2003-12-31 . Произойдет следующее:
- Будет найдено соответствие первой части шаблона \d{4} . Таким соответствием окажется 2004 в начале предложения.
- Поскольку эта часть выражения заключена в круглые скобки, значение 2004 будет присвоено переменной $1 .
- Далее Perl "смотрит", следует ли за найденным соответствием следующая часть шаблона, то есть дефис. Да, следует. Отлично, продолжаем работу.
- После 2004- , согласно шаблону, должны следовать две цифры ( \d{2} ). Ничего подобного, вместо этого Perl видит букву й .
- "Соответствие нарушено!" - понимает Perl, возвращается в начало регулярного выражения, то есть к \d{4} , и идет далее по тексту в поисках соответствия этой части шаблона.
- Perl натыкается на 2003 , перезаписывает содержимое переменной $1 (теперь оно равно 2003), продолжает проверку остальных частей шаблона, удостоверяется, что найденный фрагмент текста целиком шаблону соответствует и производит замену.
$text = "2004-й год начался на следующий день после 2003-12-31.";
$text =~ s/(\d{4})-(\d{2})-(\d{2})/$3\.$2\.$1/;
print "$text";
В этой статье мы затронули сугубо теоретические проблемы. Но в заключение хотелось бы привести некую вполне практическую задачу, которая дополнительно проиллюстрировала бы описанный выше принцип возврата, которым руководствуется Perl при поиске. Задача будет заключаться в следующем: обнаружить в предложении одинаковые слова, следующие друг за другом. Для примера возьмем фразу Два одинаковых слова, следующих в тексте тексте подряд, как правило, являются опечаткой. Налицо - хорошо заметная человеческому глазу ошибка. Как заставить Perl обратить на нее внимание?
Прежде чем искать дублирующиеся слова, давайте определимся, что такое слово, с точки зрения синтаксиса регулярных выражений? Существует много вариантов такого определения. Возьмем одно из них: слово - это некий набор кириллических или латинских букв, после которых следует пробел или знак препинания и пробел. Причем, слово может начинаться с заглавной буквы. На языке регулярных выражений это утверждение записывается следующим образом:
- [А-Я]*[а-я]+ - обозначает необязательную заглавную и обязательные (одну или более) прописные кириллические буквы в русскоязычном слове,
- [A-Z]*[a-z]+ - то же самое для слов, написанных латиницей,
- \s|[.,!?]\s - пробельный символ или один из перечисленных знаков препинания и следующий за ним пробел.
Примечание: Как вы вероятно помните, вертикальная черта | в регулярных выражениях обозначает выбор между двумя вариантами, соответствует логическому оператору ИЛИ
Таким образом, мы научились выделять в тексте отдельные слова. Но как найти следующие друг за другом повторяющиеся слова? Для этого воспользуемся новым для нас элементом синтаксиса регулярных выражений, обратной ссылкой
\1
. Что она означает? Чтобы разобраться, запишем выражение шаблона целиком:
- В тексте выделяется первое слово и, благодаря круглым скобкам, записывается в переменную $1.
- Выясняется, что следует после слова - пробел или знак препинания с пробелом. Ответ на этот вопрос записывается в переменную $2.
- А теперь - внимание! Обратная ссылка \1 заставляет Perl проверить, не следует ли за пробелом значение переменной $1, то есть обнаруженное ранее, на первом шаге, слово. Обратная ссылка \1 ссылается на первый совпавший фрагмент шаблона, \2 - на второй, и так далее.
Чтобы лучше понять принцип применения обратных ссылок в шаблонах, попробуйте выполнить следующую функцию:
$text = "Два одинаковых слова, следующих в тексте тексте подряд,Поэкспериментируйте с предложением, замените его своим примером, поиграйте с порядком следования слов и знаков препинания. В результате принцип работы функции, а значит, и языка Perl в целом, станет для вас более понятен.
как правило, являются опечаткой.";
if ($text =~ /([А-Я]*[а-я]+|[A-Z]*[a-z]+)(\s|[.,!?]\s)\1/) {
print "В предложении дублируется слово <b>$1</b><br>";
}
Ссылки по теме