Секреты регулярных выражений (regular expressions): Часть 1. Диалекты и возможности. Составление регулярных выражений

Описание:  Словосочетание "регулярные выражения" слышал (или видел) каждый, чья деятельность так или иначе связана с использованием компьютеров. Многие применяют простейшие варианты регулярных выражений чуть ли не ежедневно, даже не подозревая об этом. Обычно им уделяется не слишком много внимания и, как правило, в контексте конкретной утилиты (grep, sed, less) или языка программирования (Perl, Python и т.д). В данном цикле статей я попытаюсь обобщить информацию о регулярных выражениях, сосредоточившись при этом не на элементарных "обучающих" примерах, которые всем известны, а на более тонких аспектах практического использования.

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

1. Введение. Используем ли мы регулярные выражения в полной мере?

Если задуматься над вопросом: "А что такое "регулярное выражение" вообще?", то ответ найдётся не сразу. Можно сказать, что это специализированный язык описания символьного шаблона (последовательности символов) поиска в строках текста. Здесь важно то, что при поиске совпадений выполняется именно посимвольное сравнение. Автор энциклопедии по регулярным выражениям (Mastering Regular Expressions) Джеффри Фридл (J.E.F. Friedl) советует развивать привычку буквально интерпретировать регулярные выражения. Например, глядя на шаблон "^cat", обозначающий "строка должна начинаться со слова cat", следует рассуждать так: "совпадение будет найдено, если мы находимся в начале строки и обнаруживаем символ c, непосредственно за которым располагается символ a, сразу после которого находится символ t". Это позволяет максимально точно оценить смысл и сущность регулярного выражения.

Большинство пользователей знают, что для поиска достаточно задать слово-образец. Например, в Web-браузере в поле "Поиск" после ввода "Linux" вы получите длинный список ссылок на страницы, в тексте которых найдено совпадение с заданным шаблоном "Linux". В локальной файловой системе используется команда grep "Linux" или графические средства поиска.

Не все, но многие пользователи умеют применять метасимволы (* . ?) в шаблонах поиска. Ещё меньшее количество людей знает о возможности применения модификаторов и других изощрённых средств для конструирования регулярных выражений, т.е. во многих случаях мощность механизма регулярных выражений используется едва ли на треть. Отчего бы не попытаться увеличить к.п.д.?

2. Различные диалекты регулярных выражений. Соответствие стандарту POSIX

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

Программы vi(m), sed, grep, less, ed, expr, lex понимают только простые регулярные выражения, а утилиты (g)awk, egrep, а также интерпретаторы языков Perl, Tcl, Python – расширенные регулярные выражения. В то же время в каждой из программ существуют собственные усовершенствования, т.е. создаются поддиалекты регулярных выражений. Рассмотрим сходства и различия этих диалектов.

2.1. Общая схема регулярного выражения

Как правило, регулярное выражение состоит из трёх основных частей:

  1. Якорь – определяет позицию шаблона в строке текста:
    • ^ – якорь, определяющий начало строки;
    • $ – якорь, определяющий конец строки.
  2. Набор (последовательность) символов – для поиска соответствий в заданных позициях строки текста:
    • символ "точка" (.) соответствует любому произвольному символу;
    • алфавитно-цифровые символы и пробел представляют сами себя;
    • прочие символы – интерпретация зависит от диалекта.
  3. Модификатор – задаёт количество повторов предыдущего символа или набора символов (в зависимости от диалекта):
    • * – любое количество повторов символа/набора, в том числе и нулевое;
    • ? – соответствует нулю или одному экземпляру символа/набора;
    • + – соответствует одному или большему количеству экземпляров символа/набора.

Пример: необходимо найти все директивы определения макроконстант в исходном коде на языке С.

grep '^ *#define.*' *.c *.h

Здесь учтено, что в начале строки макроопределения может быть вставлено любое количество пробелов или же пробелы отсутствуют. Часть шаблона #define является литеральной, т.е. каждый символ интерпретируется "как есть". Заключительная часть шаблона означает "любые символы в любых количествах".

Отметим, что символ ^ интерпретируется как якорь, обозначающий начало строки, только в том случае, если он является самым первым символом шаблона. Точно так же символ $ обозначает конец строки при условии, что является самым последним символом шаблона. Во всех прочих случаях эти символы становятся литералами, т.е. представляют сами себя.

2.2. Определение диапазонов символов в регулярных выражениях

Если возникает необходимость задать символ из определённой группы, например, только цифровой символ, или только гласную букву нижнего регистра, или только символы пунктуации, то используются квадратные скобки, внутри которых определяются требуемые символы. Таким образом:

Обратите внимание на то, что в последнем случае точка в квадратных скобках утрачивает свой особый статус и обозначает не "любой символ", а собственно символ "точка".

Непрерывные диапазоны символов можно записывать в сокращённой форме с использованием дефиса: первый пример удобнее записать в виде [0–9]. Кроме того, допускаются любые сочетания диапазонов и конкретных символов.

Имеется также возможность исключать заданные наборы символов из поиска, которая осуществляется следующим образом:

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

2.3. Модификаторы количества повторений символов

Здесь сложность состоит в том, что модификатор * для поиска IP-адреса не годится – попытка использовать шаблон [0-9]*\.[0-9]*\.[0-9]*\.[0-9] приведёт к выводу строк, содержащих элементы типа 2344.5657.11.00000, не являющихся IP-адресами. Для уточнения количества повторений наборов символов применяется модификатор \{min,max\}. Зная, что в каждой части IP-адреса может содержаться от одной до трёх цифр, запишем модификатор в виде \{1,3\}. Символы "обратный слэш" перед точками необходимы для того, чтобы отменить их специальный статус универсального метасимвола. Также следует учесть, что значение 0 не используется в качестве первого байта обычных IP-адресов. В итоге получим следующий шаблон поиска:

grep '[1-9][0-9]\{0,2\}\.[0-9]\{1,3\}\.[0-9]\{1,3\}\.[0-9]\{1,3\}' *.txt

Модификатор \{min,max\} работает только в простых регулярных выражениях. В расширенных регулярных выражениях нельзя использовать конструкции \{ \}, но можно применять модификатор ? в качестве эквивалента выражения \{0,1\}, а модификатор + как эквивалент выражения \{1,\}. Во втором случае после запятой не указано числовое значение – это означает, что максимальное количество совпадений не ограничено.

2.4. Запоминание и повторное использование элемента шаблона

Этот механизм также работает только в простых регулярных выражениях. (Впрочем, в языках программирования Perl, Python и т.п. данный механизм поддерживается – граница между диалектами становится всё менее различимой, помните?)

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

2.5. Соответствие стандарту POSIX

Стандарт POSIX также делит регулярные выражения на две категории: BRE (Basic Regular Expressions) и ERE (Extended Regular Expressions). В обеих категориях поддерживаются метасимволы . и *, якоря ^ и $, группирование символов в скобках (для BRE скобки экранируются обратным слэшем), применение квантификаторов \{min,max\} к группам в скобках. Запоминание и повторное использование \1...\9 поддерживает только категория BRE, а квантификаторы + и ? и конструкцию выбора – только категория ERE.

В стандарте POSIX используется понятие локального контекста (locale) – совокупности параметров, описывающих языковые и культурные правила: формат даты и времени, интерпретация символов активной кодировки и т.д. Это не относится напрямую к регулярным выражениям, но влияет на их функционирование. При работе в локальном контексте с кодировкой UTF-8, принятой почти во всех современных дистрибутивах, корректно обрабатываются символы русского алфавита и их диапазоны, т.е. можно указывать диапазоны [а-я] и [А-Я] в шаблонах поиска.

3. Примеры составления полезных регулярных выражений

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

3.1. Пример шаблона для поиска денежной суммы, записываемой в формате "10000 руб. 00 коп."

[0-9]\{1,\} руб\. [0-9]\{2\} коп\.

Необходимое пояснение: если в модификаторе типа \{min,max\} отсутствует и запятая, и максимальное значение, то такая конструкция задаёт точное количество ожидаемых повторов элемента шаблона. В нашем примере определяются ровно два цифровых символа для обозначения копеек.

3.2. Пример шаблона для поиска URL-строки, соответствующей Web-ресурсу в Интернете:

http://[a-zA-Z0-9]\{1,\}\.[-a-zA-Z0-9_]\{1,\}/*

Необходимое пояснение: дефис теряет своё специальное значение, если он указан в самой первой позиции сразу после открывающей квадратной скобки в диапазоне. По данному шаблону могут быть найдены и такие "экзотические" URL-строки, как, например, http://my.home-server/

В формате расширенных регулярных выражений этот шаблон можно было бы записать более компактно:

http://[a-zA-Z0-9]+\.[-a-zA-Z0-9_]+/*

Такую запись понимают, например, утилиты egrep и awk.

3.3. Шаблон для поиска любого HTML-тэга выглядит на удивление просто:

<[^>]+>

Совпадает с любой последовательностью символов за исключением > в количестве от одного и более, заключённой в угловые скобки. Иными словами, будет найден и односимвольный тэг <p>, и более "многословные" тэги, подобные <hr size=50>.

3.4. Вариант шаблона для поиска дат

Расширенные регулярные выражения позволяют написать несколько громоздкий, но тем не менее корректно работающий шаблон для поиска дат, имеющих вид "13 ноября 2009 г.":

[12]?[0-9] (янв|фев|мар|апр|мая|июн|июл|авг|сен|окт|ноя|дек).* [0-9][0-9][0-9][0-9] г\.

Недостаток этого шаблона заключается в том, что с его помощью невозможно найти даты из древней истории, например, "13 ноября 245 г." или 1 января 88 г.", но для работы с современными документами он вполне годится (учитываем контекст поиска!).

3.5. Практическое применение нумерованных частей шаблона

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

\(.\)\(.\)\(.\)\3\2\1

С помощью такого шаблона можно находить шестисимвольные палиндромы не только на английском, но и на русском и на любых других языках, а также последовательности символов, не относящихся к алфавитным, например /*!!*/

Более практичным способом использования запомненных и пронумерованных частей шаблона является поиск стоящих рядом повторяющихся слов, что позволяет обнаружить такие часто встречающиеся в текстах ошибки (опечатки), как "для для". Шаблон можно записать так:

\<\(..*\)\> \<\1\>

Здесь применяются ещё два элемента регулярных выражений: \< для обозначения начальной границы слова и \> для обозначения конечной границы слова. Таким образом, мы запоминаем только отдельные слова, а не любые последовательности символов. Выражение ..* соответствует любому слову, состоящему по крайней мере из одного символа. В результате мы сможем найти такие опечатки-повторения, как "и и", "не не", "для для" и т.п.

3.6. Ограничение размера совпадающей части шаблона

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

".*"

Строки, в которых производится поиск, имеют следующий вид:

"Петров" "охранник"
"Иванов" "отдел снабжения" "экспедитор"
"Сидоров" "администрация" "директор"

Если была поставлена задача извлечения из данных строк только первого аргумента (фамилия сотрудника), то предложенный выше шаблон выполнит её некорректно, поскольку вторая кавычка шаблона соответствует последней кавычке строки (из-за стремления получить максимальное совпадение). Изменение шаблона:

".*" ".*"

решает проблему только для первой строки, а во второй и третьей к фамилии подцепляется ещё и место работы – опять не то, что нам нужно!

Данная задача корректно решается с помощью регулярного выражения, соответствующего самому короткому из всех возможных фрагментов строки, расположенному между двумя кавычками:

"[^"]*"

Здесь после открывающей кавычки должно следовать любое количество символов, не являющихся кавычками, до тех пор, пока не встретится завершающая эту последовательность кавычка.

4. Заключение

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

В первой статье было дано общее представление о регулярных выражениях и области их применения, а также краткий обзор особенностей их диалектов. Рассматривались примеры составления регулярных выражений для решения различных задач.

Продолжение цикла будет посвящено практической работе с регулярными выражениями в конкретных программах и языковых средах.


Источник статьи