Регулярные выражения Unix/Linux

Регулярные выражения поддерживаются большинством современных языков, хотя одни языки "принимают их ближе к сердцу", чем другие. Они также используются в таких UNIX-командах, как grep и vi. Регулярные выражения настолько распространены, что их название в оригинальной литературе часто сокращали до слова "regex" (regular expressions). О том, как использовать их немалые возможности, написаны уже целые книги, и неудивительно, что они стали объектом исследования многочисленных докторских диссертаций.

Сопоставление имен файлов и их раскрытие, выполненное оболочкой в процессе интерпретации таких командных строк, как wc -1 * .pi9 не является формой сопоставления с регулярным выражением. Это совсем другая система, именуемая "универсализацией файловых имен с помощью оболочки" (shell globbing), в которой используется другой, причем более простой, синтаксис.

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

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

Язык сопоставления Perl-шаблонов остается промышленным мерилом качества, и он принят на вооружение во многих других языках и инструментах. Библиотека Филиппа Гейзела (Philip Hazel) PCRE (Perl-compatible regular expression) несколько упрощает для разработчиков включение этого языка в проекты.

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

 

Процесс сопоставления

 

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

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

 

Литеральные символы

 

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

I am the walrus

совпадает со строкой "I am the walrus" и только с этой строкой. Поскольку совпадение может быть обнаружено в любом месте исследуемого текста, этот шаблон может Да успешный результат совпадения со строкой "I am the egg man. I am the walrus. Koo koo ka-choo!" При этом реальное совпадение ограничено фрагментом "I am the walrus". Процесс сопоставления чувствителен к регистру букв.

 

Специальные символы

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

 

Распространенные специальные символы регулярных выражений:

 

.               Совпадает с любым символом

[ chars ] Совпадает с любым символом из заданного набора

[^chars] Совпадает с любым символом не из заданного набора

^              Совпадает с началом строки

$              Совпадает с концом строки

\w           Совпадает с любым алфавитно-цифровым символом (аналогично набору [A-Za-z0-9_])

\s            Совпадает с любым пробельным символом (аналогично набору [  \f\t\n\r])a

\ d           Совпадает с любой цифрой (аналогично набору [ 0 — 9 ])

|               Совпадает с элементом либо слева, либо справа

(ехрг)     Ограничивает область действия, группирует элементы, позволяя формировать группы совпадений с "захватом" и без "захвата"

?              Позволяет одно повторение (или ни одного) предшествующего элемента

*             Позволяет множество повторений (или ни одного) предшествующего элемента

+             Позволяет одно или больше повторений предшествующего элемента

{n}         Ровно n повторений предшествующего элемента

{min,   } не менее min повторений (обратите внимание на запятую)

{min, max}            Любое число (от min до max) повторений а пробел, символ прогона страницы, табуляции, новой строки или возврата каретки.

 

Многие такие специальные конструкции, как + и |, оказывают влияние на сопоставление подстрок слева или справа. В общем случае подстроку может составлять один символ, или "подшаблон", заключенный в круглые скобки, или класс символов, заключенный в квадратные скобки. Однако для символа " | " подстрока распространяется неограниченно как влево, так и вправо. Если вы хотите ограничить область действия вертикальной черты, заключите ее и обе подстроки в их собственный набор круглых скобок. Например, шаблон

I am the  (walrus | egg man)\.

даст совпадение либо со строкой "I am the walrus.", либо со строкой "I am the egg man.". Этот пример демонстрирует также способ "экранирования" специальных символов (в данном случае точки) с помощью обратной косой черты (\). Шаблон

(I am the  (walrus | egg man)\.  ?){1,2} совпадет с любой из следующих строк.

  • I   am  the   walrus.
  • I   am  the   egg  man.
  • I   am  the   walrus.   I   am  the   egg  man.
  • I   am  the   egg  man.   I   am  the  walrus.

К сожалению, он также даст совпадение со строкой "I am the egg man. I am the egg man.". (И какой в этом смысл?) Важнее то, что приведенный выше шаблон также совпадет со строкой "I am the walrus. I am the egg man. I am the walrus.", хотя количество повторений явно ограничено числом два. Дело в том, что шаблон не обязательно должен совпадать полностью с исследуемым текстом. В данном случае после обнаружения совпадений этого регулярного выражения с двумя предложениями дальнейшее его сопоставление прекратилось с объявлением об успешном завершении. После выполнения условия, заданного в регулярном выражении, уже не важно, что в данном тексте есть еще одно совпадение с шаблоном.

Часто метасимвол регулярного выражения "*" (квантификатор, равный нулю или больше нуля) путают с символом "*", используемым командной оболочкой для универсализации файловых имен. В системе регулярных выражений используйте метасимвол "*" в случае, если для совпадения приемлема любая последовательность символов (включая их отсутствие).

 

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

 

В Соединенных Штатах почтовые индексы (zip-коды) имеют либо пять цифр, либо пять цифр с последующим тире и еще четырьмя цифрами. При создании регулярного выражения для zip-кода необходимо обеспечить сопоставление пятизначного номера. Следующее регулярное выражение отвечает всем этим требованиям.

^\d{5}$

Символы "А" и "$" сопоставляются с началом и концом обрабатываемого текста, не соответствуя при этом реальным символам в тексте; они представляют собой "утверждения нулевой длины" (т.е. это не символы, а лишь "позиции" в тексте). Эти символы гарантируют, что только те текстовые строки, которые состоят ровно из пяти цифр, должны совпадать с регулярным выражением (строки большей длины не должны давать совпадения). Сочетание символов \d обеспечивает совпадение с цифрой, а квантификатор {5} выражает требование совпадения ровно пяти цифр.

Для того чтобы можно было выявить либо пятизначный почтовый индекс, либо расширенный zip-код (zip+4), добавим в качестве необязательной части тире и четыре дополнительные цифры.

^\d{5)(-\d{4})?$

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

Классический пример использования регулярного выражения демонстрирует следующее выражение.

 

M[ou]*? ат+[ае]г ([АЕае]1[- 3)?[GKQ]h?[aeu]+([dtz][dhz]?)+af[iy]

 

Оно дает совпадения со многими вариантами произношения имени ныне покойного лидера Ливии Муаммара Каддафи (Moammar Gadhafl), например, с такими, как:

  • Muammar al-Kaddafi          (ВВС);
  • Moammar Gadhafi              (Associated Press);
  • Muammar al-Qadhafi          (Al-Jazeera);
  • Mu'ammar Al-Qadhafi        (U.S. Department of State).

Вы понимаете, почему каждый из приведенных вариантов успешно совпал с шаблоном?

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

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

 

Захваты

 

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

Поскольку круглые скобки могут быть вложенными, как узнать, чему соответствует каждое совпадение? Ответ простой: совпадения выстраиваются в результате в том же порядке, в котором располагаются открывающие скобки. Количество "захватов" равно количеству открывающих скобок, независимо от роли (или ее отсутствия), которую играла каждая взятая в скобки группа в реальном совпадении. Если взятая в скобки группа не используется (например, при сопоставлении регулярного выражения Mu (*) ?ammar со строкой "Muammar"), соответствующий "захват" будет пустым.

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

(I am the  (walrus|egg man)\.  ?){1,2} и таком варианте обрабатываемого текста

I am the egg man.  I am the walrus, существует два результата (по одному для каждого набора круглых скобок).

I am the walrus. Walrus

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

 

Жадность, леность и катастрофический поиск с возвратом

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

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

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

Теперь анализатор может сопоставлять компонент а*а, но он по-прежнему не может это сделать для последней буквы "а" в шаблоне. Поэтому он снова откатывается и "отнимает" вторую букву "а" из "добычи" компонента а*. На этот раз вторая и третья буквы "а" в шаблоне имеют буквы "а" для фиксации совпадения, и на этом обработка текста завершена. Этот простой пример иллюстрирует некоторые важные общие моменты. Прежде всего, "жадное" сопоставление с "откатами" делает использование таких простых шаблонов, как <img. *></tr>, дорогим удовольствием при обработке целых файлов. Действие порции. * начинается с сопоставления всего содержимого от первой найденной подстроки <img до конца входного текста, и только благодаря повторным откатам область поиска сузится, чтобы "подобраться" к локальным тегам.

Более того, порция ></tr>, с которой связан этот шаблон, — это последнее возможное допустимое вхождение искомого элемента во входном тексте, что, наверняка, совсем не отвечает вашим намерениям. Вероятно, вы хотели отыскать совпадение с подстрокой <img>, за которой следует тег </tr>. Тогда лучше переписать этот шаблон в виде <img [ A>] *></tr>, что позволит распространить совпадение с начальными групповыми символами только до конца текущего тега благодаря явно заданной невозможности пересечь границу, обозначенную правой угловой скобкой.

Можно также использовать "ленивые" (в противоположность "жадным") операторные выражения: *? вместо * и +? вместо +. Эти варианты квантификаторов ограничивают количество вхождений искомых символов во входном тексте до минимально возможного. Во многих ситуациях эти операторы работают эффективнее и дают результаты, более близкие к желаемым, чем "жадные" варианты.

Однако обратите внимание на то, что "ленивые" квантификаторы (в отличие от "жадных") могут давать различные совпадения; разница состоит не просто в используемой реализации. В нашем HTML-примере "ленивый" шаблон выглядел бы так: <img. * ?></tr>. Но даже в этом случае элемент. *? мог бы стать причиной внесения в результат ненужных нам символов ">", поскольку следующим после тега <img> может быть не тег </tr>. А такой результат вас, скорее всего, не устроит.

Шаблоны с несколькими секциями групповых символов могут "спровоцировать" анализатор регулярных выражений на экспоненциальное поведение, особенно в случае, если порции текста могут совпадать с несколькими шаблонными выражениями, и тем более в случае, если искомый текст в действительности не соответствует шаблону. Эта ситуация не является такой уж необычной, как может показаться, главным образом тогда, когда шаблон сопоставляется с HTML-кодом. Очень часто вам придется искать конкретные теги, за которыми следуют другие теги, возможно, разделенные третьими тегами, и так далее, одним словом, вам придется создавать задание, которое потребует, чтобы анализатор проверил массу возможных комбинаций.

Большой специалист в области регулярных выражений Ян Гойвертс (Jan Goyvaerts) называет этот эффект катастрофическим откатом (catastrophic backtracking) и описывает его в своем блоге (за подробностями и некоторыми удачными решениями обращайтесь по адресу: regular-expressions.info/catastrophic.html).

Из всего сказанного выше можно сделать такие выводы.

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

 

Все экземпляры специальных символов ". * " по своему существу подозрительны и должны быть тщательно исследованы.

 

 

Комментарии (0)

Только зарегистрированные и авторизованные пользователи могут оставлять комментарии.