Поиск по шаблону

[Искусство - это] шаблон, наполняемый разумом.

Сэр Герберт Рид, «Значение Искусства!

Введение

в большинстве современных языков программирования существуют примитивные средства поиска по шаблону (обычно вынесенные в дополнительные библиотеки), но шаблоны Perl интегрируются на уровне самого языка. Они обладают возможностями, которыми не могут похвастаться другие языки; возможностями, которые позволяют взглянуть на данные с принципиально новой точки зрения. Подобно тому, как шахматист воспринимает расположение фигур иа доске как некий образ, адепты Perl рассматривают данные с позицгпг шаблонов. Шаблоны записываются на языке регулярных выражений, богатом знаками препинания, и позволяют работать с замечательными алгоритмами, обычно доступными лишь экспертам в области компьютерных технологий.

«Если поиск по шаблону - такая потрясающая и мощная штука, - спросите вы, - то почему же эта глава не содержит сотни рецептов по применению регулярных выражений?» Да, регулярные выражения обеспечивают естественное решение многих проблем, связанных с числами, строками, датами, Web-документами, почтовыми адресами и буквально всем, что встречается в этой книге. В других главах поиск по шаблону применяется свыше 100 раз. А в этой главе в основном представлены те рецепты, в которых шаблоны являются частью вопроса, а не ответа.

Обширная и тщательно проработанная поддержка регулярных выражений в Perl означает, что в вашем распоряжении оказываются не только те средства, которые не встречаются ни в одном другом языке, но и принципиально новые возможности их использования. Программисты, недавно познакомившиеся с Perl, часто ищут в нем функции поиска и подстановки:

Точнее, регулярные выражения в классическом смысле не содержат обратных ссылок, присутствующих в шаблонах Perl.

match( $строка $шаблон)

subst( $строка $шаблон, $замена)

Однако поиск и подстановка - настолько распространенные задачи, что они заслуживают собственного синтаксиса

Smeadow =" m/sheep/, # Истинно если $meadow содержит sheep Smeadow ~ m/sheep/ # Истинно если Smeadow не содержит sheep Smeadow = s/old/new # Заменить в Smeadow old на new

Поиск по шаблону даже в упрощенном виде не похож на обычные строковые сравнения. Он больше похож на поиск строк с применением универсальных символов-мутантов, к тому же накачанных допингом. Без специального «якоря» позиция, в которой ищется совпадение, свободно перемещается по всей строке. Допустим, если вы захотите найти слово ovine или ovines и воспользуетесь выражением Smeadow =" /ovine/, то в каждой из следующих строк произойдет ложное совпадение-Fine bovines demand fine toreadors Muskoxen are a polar ovibovine species Grooviness went out of fashion decades ago

Иногда нужная строка находится прямо у вас перед глазами, а совпадение все равно не происходит

Ovines are found typically in oviaries

Проблема в том, что вы мыслите категориями человеческого языка, а механизм поиска по шаблону - нет. Когда этот механизм получает шаблон /ovine/ и другую строку, в которой происходит поиск, он ищет в строке символ о , за которым сразу же следует v , затем i , п и е Все, что находится до этой последовательности символов или после нее, не имеет значения.

Итак, выясняется, что шаблон находит совпадения там, где они не нужны, и не узнает то, что действительно нужно. Придется усовершенствовать его. Например, для поиска последовательности ovine или ovmes шаблон должен выглядеть примерно так:

if (Smeadow =~ /\bovines\b/i) { print Here be sheepi }

Шаблон начинается со метасимвола \b, который совпадает только с границей слова, s"? обозначает необязательный символ s - он позволяет находить как ovrae, так и ovines. Модификатор /i в конце шаблона означает, что поиск осуществляется без учета регистра.

Как видите, некоторые символы и последовательности символов имеют особый смысл для механизма поиска по шаблону. Метасимволы фиксируют шаблон в начале или конце строки, описывают альтернативные значения для частей шаблона, организуют повторы и позволяют запомнить часть найденной подстроки, чтобы в дальнейшем использовать ее в шаблоне или программном коде.

Освоить синтаксис поиска по шаблону не так уж сложно. Конечно, служебных символов много, но существование каждого из них объясняется вескими причинами. Регулярное выражение - это не просто беспорядочная груда знаков... это тщательно продуманная груда знаков! Если вы что-нибудь забыли, всегда можно

заглянуть в документацию. Сводка по синтаксису регулярных выражений имеется в страницах руководстварег/ге(1) ирег1ор(1), входящих в любую поставку Perl.

Три затруднения

Но синтаксис регулярных выражений - это еще цветочки по сравнению с их хитроумной семантикой. Похоже, большинство трудностей вызывают три особенности поиска по шаблону: жадность, торопливость (а так же то, как эти три аспекта взаимодействуют между собой) и возврат.

Принцип жадности: если квантификатор (например, *) может совпасть в нескольких вариантах, он всегда совпадает со строкой наибольшей длины. Объяснения приведены в рецепте 6.15.

Принцип торопливости: механизм поиска старается обнаружить совпадение как можно скорее, иногда даже раньше, чем вы ожидаете. Рассмотрим конструкцию Fred =~ /х*/. Если попросить вас объяснить ее смысл, вы, вероятно, скажете. «Содержит ли строка Fred символы х?» Вероятно, результат поиска окажется неожиданным - компьютер убежден, что символы присутствуют. Дело в том, что /х*/ означает не просто «символы х», а «любое количество символов х». Или более формально - ноль и более символов. В данном случае нетерпеливый механизм поиска удовлетворяется нулем.

Приведем более содержательный пример:

Sstring = good food Sstring =~ s/o«/e/

Как вы думаете, какое из следующих значений примет $string после подстановки?

goof food geod food geed food geed feed ged food ged fed egood food

Правильный ответ - последний, поскольку первая точка, в которой встречается ноль и более экземпляров о , находится прямо в начале строки. Удивлены? С регулярными выражениями это бывает довольно часто.

А теперь попробуйте угадать, как будет выглядеть результат при добавлении модификатора /д, который делает подстановку глобальной? Строка содержит много мест, в которых встречается ноль и более экземпляров о , - точнее, восемь. Итак, правильный ответ - egeede ef eede .

Приведем другой пример, в котором жадность уступает место торопливости:

% echo ababacaca perl -ne print $&\n if /(abab)+(aac)+/ ababa

Это объясняется тем, что при поиске в Perl используются так называемые традиционные неопределенные конечные автоматы (в отличие от неопределенных конечных автоматов POSIX). Подобные механизмы поиска гарантируют возврат не самого длинного общего совпадения, а лишь самого длинного левого совпаде-