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";
 $phrase =~ s/i*/I/;
 print "$phrase"; 

Результат — IHostinfo несколько неожиданный, не правда ли? Но это только на первый взгляд. На самом деле все сработало верно. Ведь шаблон i* призывает найти ноль и более букв i в слове. Perl начинает работу и тут же убеждается, что ноль букв i встречается в самом начале слова. Ничтоже сумняшеся, Perl, следуя принципу торопливости, производит замену.

Возврат

Как мы уже неоднократно убеждались в предыдущих публикациях на эту тему, шаблоны могут быть достаточно сложными, состоять из нескольких частей. Для того чтобы фрагмент текста совпал с шаблоном, необходимо полное совпадение этого фрагмента со всеми частями регулярного выражения. Нужно понимать, как Perl работает с этими «многокомпонентными» выражениями. Проверив первую часть и обнаружив совпадение, Perl переходит ко второй части. Если здесь совпадения не обнаружено, он возвращается к первой части выражения и ищет в тексте следующий фрагмент, совпадающий с ней. Эта история повторяется до тех пор, пока не будет найдено полное совпадение фрагмента текста и всех частей регулярного выражения. Такой принцип работы и получил название возврат. Проиллюстрируем его на простом примере.

В статье «Perl: найти и не сдаваться» мы реализовали простую функцию для смены формата записи даты. Для этого использовалось следующая подстановка: s/(\d{4})-(\d{2})-(\d{2})/$3\.$2\.$1/. Посмотрим, как она сработает, будучи «натравлена» на текст 2004-й год начался на следующий день после 2003-12-31. Произойдет следующее:

1. Будет найдено соответствие первой части шаблона \d{4}. Таким соответствием окажется 2004 в начале предложения.
2. Поскольку эта часть выражения заключена в круглые скобки, значение 2004 будет присвоено переменной $1.
3. Далее Perl «смотрит», следует ли за найденным соответствием следующая часть шаблона, то есть дефис. Да, следует. Отлично, продолжаем работу.
4. После 2004-, согласно шаблону, должны следовать две цифры (\d{2}). Ничего подобного, вместо этого Perl видит букву й.
5. «Соответствие нарушено!» — понимает Perl, возвращается в начало регулярного выражения, то есть к \d{4}, и идет далее по тексту в поисках соответствия этой части шаблона.
6. 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), где:

• [А-Я]*[а-я]+ — обозначает необязательную заглавную и обязательные (одну или более) прописные кириллические буквы в русскоязычном слове,
• [A-Z]*[a-z]+ — то же самое для слов, написанных латиницей,
• \s|[.,!?]\s — пробельный символ или один из перечисленных знаков препинания и следующий за ним пробел.

Таким образом, мы научились выделять в тексте отдельные слова. Но как найти следующие друг за другом повторяющиеся слова? Для этого воспользуемся новым для нас элементом синтаксиса регулярных выражений, обратной ссылкой \1. Что она означает? Чтобы разобраться, запишем выражение шаблона целиком: ([А-Я]*[а-я]+|[A-Z]*[a-z]+)(\s|[.,!?]\s)\1. Каким образом Perl будет его обрабатывать?

1. В тексте выделяется первое слово и, благодаря круглым скобкам, записывается в переменную $1.
2. Выясняется, что следует после слова — пробел или знак препинания с пробелом. Ответ на этот вопрос записывается в переменную $2.
3. А теперь — внимание! Обратная ссылка \1 заставляет Perl проверить, не следует ли за пробелом значение переменной $1, то есть обнаруженное ранее, на первом шаге, слово. Обратная ссылка \1 ссылается на первый совпавший фрагмент шаблона, \2 — на второй, и так далее.

Чтобы лучше понять принцип применения обратных ссылок в шаблонах, попробуйте выполнить следующую функцию:

 $text = "Два одинаковых слова, следующих в тексте тексте подряд,
 как правило, являются опечаткой.";
 if ($text =~ /([А-Я]*[а-я]+|[A-Z]*[a-z]+)(\s|[.,!?]\s)\1/) {
  print "В предложении дублируется слово <b>$1</b><br>";
 } 

Поэкспериментируйте с предложением, замените его своим примером, поиграйте с порядком следования слов и знаков препинания. В результате принцип работы функции, а значит, и языка Perl в целом, станет для вас более понятен.

Ссылки по теме Спецификация регулярных выражений Perl Perl: бороться и искать Perl: найти и не сдаваться