Рубрики
 
 

Perl-3: жадный и торопливый возвращенец

Впервые опубликовано:
21.09.2004
HostInfo.ru

Принципы жадности, торопливости и возврата при поиске по шаблону (в регулярных выражениях языка 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: найти и не сдаваться



  • Поиск по сайту
    SoftRing     Web

     
    белорусский вокзал
     
     
     
     
    Карта сайта | Обратная связь

    © 2004-2012 Soft Ring: интернет-энциклопедия полезных программ