Регулярные выражения: диалекты и возможности

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

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

Для чего написана эта глава

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

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

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

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

История регулярных выражений

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

grep как мировоззрение

Наша история начинается с программы grep — предка egrep и, вероятно, самой распространенной программы с поддержкой регулярных выражений. Эта программа появилась в семействе Unix в середине 1970-х годов и с тех пор была перенесена практически на все современные системы. Существуют десятки разных (иногда очень разных) версий grep для DOS.

Возможно, вы полагаете, что такая распространенная программа-ветеран установила какие-то стандарты в области регулярных выражений? К сожалению, ничего подобного. Переключайтесь в режим «развлекательного чтения» — мы вернемся к истокам и проследим за развитием событий с самого начала.

Мир до появления grep

Семена регулярных выражений были посажены в начале 1940-х годов. Двое нейрофизиологов, Уоррен Мак-Каллох (Warren McCulloch) и Уолтер Питтс (Walter Pitts), занимались моделированием работы нервной системы на нейронном<$M[R3-9]> уровне[1]. Регулярные выражения воплотились в реальность через несколько лет, когда математик Стивен Клин (Stephen Kleene) формально описал эти модели при помощи алгебры, которую он назвал регулярными множествами (regular sets). Он разработал для регулярных множеств простую математическую запись, которую и назвал регулярными выражениями.

В 1950-х и 60-х годах регулярные выражения стали предметом серьезного изучения в кругах теоретической математики. Роберт Констейбл (Robert Constable) написал хорошую статью[2] для специалистов-математиков. Хотя существуют свидетельства о более ранних работах, первой публикацией, посвященной применению регулярных выражений в области компьютерных технологий, которую мне удалось обнаружить, была статья Кена Томпсона «Regular Expression Search Algorithm» от 1968 года[3]. В этой статье Томпсон описывает компилятор регулярных выражений, генерирующий объектный код IBM 7094. Это подтолкнуло его к работе над qed — редактором, который был положен в основу известного редактора Unix ed. Регулярные выражения ed уступали по своим возможностям выражениям qed, но именно они впервые получили широкое распространение за пределами теоретических кругов. Одна из команд ed выводила строки редактируемого файла, в которых находилось совпадение для заданного регулярного выражения. Эта команда, «g/регулярное выражение/p», читалась как «Global Regular Expression Print» («глобальный вывод по регулярному выражению»). Функция оказалась настолько полезной, что была преобразована в отдельную утилиту. Так появилась программа grep.

Метасимволы grep

Регулярные выражения, поддерживаемые ранними программами, заметно уступали по своим возможностям выражениям egrep. Метасимвол * поддерживался, но + и ? не поддерживались (причем отсутствие последнего было особенно сильным недостатком). Для группировки метасимволов в grep использовалась конструкция \(…\), а неэкранированные круглые скобки являлись литералами[4]. Программа grep поддерживала привязку к позициям строки, но в ограниченном варианте. Если символ ^ находился в начале регулярного выражения, он представлял собой метасимвол, совпадающий с началом строки (как в egrep и Perl). В противном случае он вообще не считался метасимволом и просто обозначал соответствующий литерал. Аналогично, символ $ считался метасимволом только в конце регулярного выражения. В результате терялась возможность использования выражений вида [end$|^start]. Впрочем, это несущественно, поскольку конструкция выбора все равно не поддерживалась.

Взаимодействие метасимволов также отличалось некоторыми особенностями. Например, один из главных недостатков grep заключался в том, что квантификатор * не мог применяться к выражениям в круглых скобках, а только к литералам, символьным классам или метасимволу «точка». Следовательно, в grep скобки предназначались только для сохранения совпавшего текста (как, например, при поиске повторяющихся слов в выражении [\([a-z]+\)spc\1]), но не для общей группировки. Более того, в некоторых ранних версиях grep не допускались вложенные круглые скобки.

Все течет, все изменяется

Эволюция grep

Хотя grep существует во многих системах и в наши дни, я в основном говорил об этой программе в прошедшем времени, поскольку речь шла о диалекте регулярных выражений в старых версиях 20-летней давности. Однако технология не стоит на месте, и со временем старые программы дополняются новыми возможностями. Программа grep не является исключением.

В AT&T Bell Labs grep дополнили новыми возможностями — например, интервальным квантификатором \{мин, макс\} (см. главу 1), позаимствованным из программы lex. Также была исправлена ошибка с ключом -y, который должен был обеспечивать поиск без учета регистра, но работал ненадежно. Одновременно в Беркли были добавлены метасимволы начала и конца слова, а ключ -y был переименован в -i. К сожалению, * и другие квантификаторы все еще не могли применяться к выражениям в круглых скобках.

Эволюция egrep

К этому времени Альфред Ахо (Alfred Aho) написал программу egrep, которая поддерживала большинство метасимволов, описанных в главе 1. Еще важнее то, что программа была реализованы совершенно иным (и обычно более эффективным) способом. Вариантам реализации и их значению для пользователя посвящены две следующие главы. В egrep не только появились новые квантификаторы + и ?, но и они наряду с другими квантификаторами стали применяться к выражениям в круглых скобках, что значительно расширило возможности регулярных выражений egrep.

Также была добавлена конструкция выбора, а метасимволы привязки получили «равноправие», то есть могли использоваться практически в любом месте регулярного выражения. Конечно, у egrep были свои проблемы — иногда программа находила совпадение, но не включала его в результат, а также не поддерживала некоторые распространенные возможности. И все же пользы она приносила на порядок больше.

Появление других видов

В это время появились и начали развиваться другие программы (такие, как awk, sed и lex). Разработчик, которому нравилась какая-то возможность одной программы, часто пытался реализовать ее в другой программе. Иногда это приводило к печальным последствиям. Например, если вам вдруг захотелось включить в grep поддержку квантификатора «плюс», для этой цели нельзя было использовать символ +, поскольку в grep он традиционно не являлся метасимволом, и неожиданное превращение удивило бы пользователей. Поскольку комбинация \+ в обычных условиях встречается редко, ее можно смело связать с метасимволом «один или больше».

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

Умножьте это обстоятельство на прошедшее время и количество программ, и в результате получится сущая неразбериха (особенно когда автор программы пытается заниматься несколькими делами сразу[5]). Ситуация немного прояснилась в 1986 году, когда Генри Спенсер (Henry Spencer) выпустил первый пакет для работы с регулярными выражениями на языке C. Любой желающий мог бесплатно включить этот пакет в свою программу. Все программы, использовавшие этот пакет (а такие программы были, и немало), поддерживали один и тот же согласованный диалект регулярных выражений — если только автор не вносил в него сознательные изменения.

С первого взгляда

Достаточно взглянуть лишь на некоторые аспекты распространенных программ, чтобы понять, как сильно они отличаются друг от друга. В табл. 3.1 приведена очень поверхностная сводка диалектов некоторых программ (это сокращенный вариант табл. 6.1 на с. <$R[P#,R6-1]>).<$M[R3-27]>

Таблица 3.1. Поверхностный обзор диалектов некоторых распространенных программ

Возможность

Современные версии grep

Современные версии egrep

awk

GNU Emacs версия 19

Perl

Tcl

vi

*, ^, $, […]

Ц

Ц

Ц

Ц

Ц

Ц

Ц

? + |

\? \+ \|

? + |

? + |

? + \|

? + |

? + |

\? \+ spc

группировка

\(…\)

(…)

(…)

\(…\)

(…)

(…)

\(…\)

границы слов

spc

\< \>

spc

\< \> \b \B

\b \B

spc

\< \>

\w, \W

spc

Ц

spc

Ц

Ц

spc

spc

обратные ссылки

Ц

spc

spc

Ц

Ц

spc

Ц

Такие таблицы часто приводятся в книгах для наглядной демонстрации различий между другими инструментами. Но здесь таблица в лучшем случае открывает верхушку айсберга — у перечисленных возможностей существуют десятки важных аспектов, в том числе следующие<$M[R3-17]>:

l      Может ли * и другие квантификаторы применяться к выражениям, заключенным в круглые скобки?

l      Может ли точка совпадать с символом новой строки? А инвертированные символьные классы? И как насчет нуль-символа?

l      К какой строке привязываются якорные метасимволы — целевой или логической? К обеим? Ни к одной? Являются ли они полноправными метасимволами или допускаются только в определенных частях регулярного выражения?

l      Распознаются ли экранированные символы в символьных классах? Какие еще символы разрешаются или запрещаются в символьных классах?

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

l      Допускается ли экранирование восьмеричных кодов символов? Если допускается, то как разрешаются конфликты с обратными ссылками? А как насчет экранирования шестнадцатеричных кодов? И кто в действительности поддерживает восьмеричные и шестнадцатеричные коды — механизм регулярных выражений или какая-то другая часть программы?

l      Совпадает ли [\w] только с алфавитно-цифровыми символами или допускаются еще какие-то другие символы? (Все три программы с поддержкой \w, перечисленные в табл. 3.1, интерпретируют этот символ по-разному!)

l      Если программа поддерживает метасимвол \n, то что именно это означает? Поддерживаются ли другие вспомогательные метасимволы?

Даже при таком поверхностном обзоре, как в табл. 3.1, приходится учитывать множество факторов. Если вы поймете, что под гладкой поверхностью кроется немало подводных камней, то сможете без особого труда обойти их. Также следует помнить, что многие программы отличаются от поставщика к поставщику и от версии к версии. Поскольку в табл. 3.1 приведен лишь очень краткий сравнительный обзор, я ограничился самыми распространенными возможностями последних версий. Например, GNU-версии многих распространенных программ почти всегда работают надежнее и обладают большими возможностями, чем другие версии.

Различия в семантике поиска совпадений (или по крайней мере в том, как она выглядит извне) являются очень важным фактором, который нередко упускается из виду в других обзорах. Если вы знаете, что выражение, которое на awk выглядит как [(Jul|July)], в GNU Emacs должно записываться в виде [\(Jul|July\)], можно подумать, что дальше все идет одинаково. Это не всегда так — в некоторых ситуациях для внешне похожих выражений используются разные механизмы поиска (как в приведенном примере). Этот важный вопрос рассматривается в следующей главе.

Конечно, то, что программа может сделать с регулярным выражением, нередко играет более важную роль, чем поддерживаемый ей диалект регулярных выражений. Даже если бы регулярные выражения Perl уступали egrep по своим возможностям, благодаря гибким средствам их использования Perl все равно приносил бы больше пользы. Поэтому, хотя табл. 3.1 дает представление о возможностях некоторых диалектов, по ней не стоит судить об общей полезности того или иного инструмента. Мы подробнее займемся темой изучения разных диалектов в главе 6.

POSIX

POSIX (сокращение от слов portable operating system interface, то есть «переносимый интерфейс операционной системы»), представляет собой стандарт, обеспечивающий переносимость программ между операционными системами. В этот грандиозный стандарт входят и спецификации регулярных выражений и многих традиционных средств, в которых они используются.

В попытке упорядочить хаос, о котором наглядно свидетельствует табл. 3.1, POSIX делит распространенные диалекты на две категории: BRE (basic regular expressions, то есть «базовые регулярные выражения») и ERE (extended regular expressions, то есть «расширенные регулярные выражения»). Полностью POSIX-совместимые инструменты используют один из диалектов, возможно с небольшими специфическими дополнениями. Метасимволы двух категорий перечислены в табл. 3.2.<$M[R3-25]>

Таблица 3.2. Категории диалектов регулярных выражений в стандарте POSIX

Метасимволы

BRE

ERE

точка, ^, $, […], [^…]

Ц

Ц

*, +, ?, {мин, макс}

*, spc, spc, \{мин, макс\}

*, +, ?, \{мин, макс\}

группировка

\(…\)

(…)

применение квантификаторов к скобкам

Ц

Ц

обратные ссылки

\1…\9

spc

конструкция выбора

spc

Ц

Табл. 3.2, как и табл. 3.1, весьма поверхностна. Например, $ в BRE является метасимволом лишь в конце регулярного выражения (и возможно, на усмотрение конкретной реализации — перед закрывающей круглой скобкой). Однако в ERE $ является метасимволом в любом месте, кроме символьного класса. В этой главе встречаются и другие примеры.

Должен признать свое невежество во многих аспектах POSIX, поскольку я еще никогда не встречал инструмента, в котором бы они полноценно поддерживались. Однако многие распространенные программы избирательно реализуют отдельные требования стандарта POSIX, поэтому даже на платформах, не отвечающих стандарту POSIX, о них все же следует знать. Начнем с рассмотрения локальных контекстов POSIX.

Локальный контекст POSIX

Одной из особенностей стандарта POSIX является понятие локального контекста<$M[R3-6]> (locale) — совокупности параметров, описывающих языковые и культурные правила: формат даты, времени и денежной величины, интерпретация символов активной кодировки и т. д. Локальные контексты упрощают адаптацию программ в других странах. Они не относятся к специфике регулярных выражений, однако могут влиять<$M[R3-3]> на их применение.

Например, при работе в локальном контексте с кодировкой Latin-1 (ISO-8859-1), а и А считаются «буквами» (хотя во многих программах символы за пределами кодировки ASCII интерпретируются как двоичные данные). При любом применении регулярных выражений, при котором игнорируется регистр символов, эти два символа будут считаться идентичными.

Другой пример — метасимвол [\w], обычно обозначающий «символ слова» (как правило, [[a-zA-Z0-9]]). POSIX не требует, но допускает поддержку этого метасимвола. При поддержке [\w] в поиск включаются все буквы и цифры, определенные в локальном контексте, а не только те, которые определены для английского алфавита.

Объединяющие последовательности POSIX

В локальном контексте можно определить именованные объединяющие последовательности<$M[R3-7]> (collating sequences), описывающие особенности обработки некоторых символов или комбинаций символов при сортировке и т. д. Например, в испанском языке комбинация ll (как в слове tortilla) традиционно сортируется как один логический символ, расположенный между l и m, а в немецком языке Я считается символом, расположенным между s и t, но сортируемым как два s, стоящих подряд. Эти правила могут быть реализованы в объединяющих последовательностях — например, с именами span-ll и eszet.

Объединяющая последовательность (как в случае с span-ll) может представлять собой набор<$M[R3-14]> из нескольких символов, интерпретируемых как один символ с позиций символьных классов (называемых в POSIX «групповыми выражениями»; см. с. <$R[P#,R3-5]>) Это означает, что класс [torti[a-z]a] совпадет с двухбуквенным «символом» в слове tortilla. А поскольку Я определяется как символ, находящийся между s и t, он входит в символьный класс [[a-z]].

Косвенная поддержка локальных контекстов

<$M[R3-29]>Локальные контексты могут влиять на работу многих программ, не претендующих на соответствие стандарту POSIX — причем иногда без их ведома! Многие утилиты пишутся на C или C++ и часто используют стандартные библиотечные функции C для определения того, какие байты являются буквами, цифрами и т. д. Если такая утилита компилируется в системе с библиотекой C, соответствующей стандарту POSIX, это может обеспечить определенный уровень соответствия, хотя ее точную степень предсказать трудно. Например, автор программы может использовать библиотечные функции C для решения проблем с регистром символов, но не для поддержки \w[6]<$M[R3-31]>.

Некоторые программы пытаются реализовать частичную поддержку локальных контекстов в своих регулярных выражениях. Примерами являются Perl, Tcl и GNU Emacs. При использовании метасимвола Perl \w и поиске с игнорированием регистра символов локальный контекст учитывается, как говорилось выше, а при использовании метасимвола «точка» и интервалов в символьных классах — нет. Другие примеры будут приведены при описании метасимволов в разделе «Стандартные метасимволы» (см. с. <$R[P#,R3-11]>).

Основные операции с регулярными выражениями

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

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

Идентификация регулярных выражений

В предыдущей главе мы познакомились с Perl — полноценным языком программирования, работающим с многими типами регулярных выражений. При любом типе выражения необходимо сообщить Perl, что именно вы хотите сделать с регулярным выражением. Конструкция m/…/, в которую заключается регулярное выражение, означает операцию поиска, а оператор =~ связывает выражение с текстом, в котором производится поиск (вообще говоря, при желании m можно опустить и даже использовать вместо / другие символы). Запомните: символы / не входят в само регулярное выражение. Это всего лишь ограничители, определяющие границы выражения в сценарии — та самая синтаксическая обертка, о которой я упоминал.

Операции с совпавшим текстом

Конечно, возможности регулярных выражений не ограничиваются простым поиском текста. Хорошим примером является команда подстановки $var =~ s/регулярное выражение/замена/, рассмотренная в главе 2. Она ищет в тексте, хранящемся в переменной, подстроку, совпадающую с заданным регулярным выражением, и заменяет ее строкой замены. Модификатор /g обеспечивает «глобальную» замену в строке. Это означает, что после первой замены поиск возможных совпадений продолжается в оставшейся части строки.

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

$var =~ s/[0-9]+/<CODE>$&<\/CODE>/g

Эта команда заключает каждое число, находящееся в тексте $var, в пару тегов <CODE>…</CODE>. Строка замены имеет вид <CODE>$&<\/CODE>. Символ \ экранирует символ косой черты, выполняющий функции ограничителя, чтобы этот символ мог присутствовать в строке замены. Переменная Perl $& содержит текст, совпавший при последнем применении регулярного выражения ([[0-9]+] в первой части команды).

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

$var =~ s![0-9]+!<CODE>$&</CODE>!g

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

Необходимо понимать, что в следующих командах:

$var =~ m/[0-9]+/;

$var =~ m/[0-9]+/a number/g;

$var =~ m![0-9]+!<CODE>$&</CODE>!g;

используется одно и то же регулярное выражение. Различаются только операции, выполняемые с этим выражением программой (в данном случае Perl).

Другие примеры

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

Awk

В языке awk конструкция /регулярное_выражение/ ищет совпадения в текущей входной строке, а конструкция var ~ … выполняет поиск в других данных. Именно awk повлиял на синтаксис операций с регулярными выражениями языка Perl (впрочем, при выборе оператора подстановки Perl за образец была взята программа sed).

В ранних версиях awk операция подстановки не поддерживалась, но в современных версиях появилась функция sub(…). Команда вида sub(/mizpel/, "misspell") применяет регулярное выражение [mizpel] к текущей строке, заменяя первый найденный экземпляр строкой «misspell». Сравните с командой Perl s/mizpel/misspell/.

Для замены всех экземпляров в строке вместо аналога модификатора /g в awk используется другая функция: gsub(/mizpel/, "misspell").

Tcl

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

regsub mizpel $var misspell newvar

Команда проверяет содержимое переменной var, заменяет первый экземпляр [mizpel] строкой «misspell» и присваивает полученный текст переменной newvar. Ни регулярное выражение, ни строка замены не требуют специальных ограничителей, кроме обычных пробелов. На первом месте передается регулярное выражение, на втором — целевая строка, на третьем — строка замены, и на четвертом — имя целевой переменной (если регулярное выражение или строка замены содержат пробелы или другие аналогичные символы, они, как и все остальные аргументы в Tcl, заключаются в апострофы). Tcl также позволяет передавать при вызове regsub дополнительные параметры. Например, ключ -all обеспечивает глобальную замену всех найденных экземпляров (не только первого):

regsub -all mizpel $var misspell newvar

Ключ -nocase заставляет механизм регулярных выражений игнорировать регистр символов (по аналогии с флагом egrep -i или модификатором Perl /i).

GNU Emacs

В невероятно мощном текстовом редакторе GNU Emacs (в дальнейшем просто «Emacs») поддерживается встроенный язык программирования elisp (Emacs lisp) и многочисленные функции для работы с регулярными выражениями. Одна из важнейших функций, re-search-forward, получает в качестве аргумента обычную строку и интерпретирует ее как регулярное выражение, после чего ищет текст от текущей позиции до первого совпадения или отменяет поиск, если совпадение отсутствует. Именно эта функция вызывается при выполнении команды поиска в редакторе. Например, команда (re-search-forward "main") ищет текст [main], начиная с текущей позиции редактируемого текста.

Как видно из табл. 3.1, для диалекта регулярных выражений Emacs характерно наличие многочисленных символов<$M[R3-2]> \. Например, регулярное выражение [\<([a-z]+\)\([\nspc\t]\|<[^>]+>\)+\1\>] находит в тексте повторяющиеся слова (см. главу 1). Непосредственно использовать это выражение нельзя, поскольку механизм регулярных выражений Emacs не понимает символов \n и \t. С другой стороны, эти символы поддерживаются для строк Emacs<$M[R3-1]>, заключенных в кавычки. В отличие от Perl и awk (но по аналогии с Tcl и Python), регулярные выражения в сценариях elisp обычно передаются механизму обработки в виде строковых литералов, поэтому мы можем свободно использовать \t и другие символы. С другой стороны, это вызывает некоторые проблемы, поскольку символ \ имеет особый смысл в строках elisp.

В egrep регулярные выражения обычно заключаются в апострофы, что позволяет использовать в них символы *, \ и т. д., являющиеся метасимволами командного интерпретатора. В командах Perl m/регулярное выражение/ и s/регулярное выражение/замена/ регулярное выражение передается непосредственно, что предотвращает возможные конфликты метасимволов (конечно, кроме символа-ограничителя — обычно /). В elisp такого простого решения не существует. Поскольку обратная косая черта является строковым метасимволом, ее приходится экранировать, то есть заменять каждый символ \, непосредственно включаемый в регулярное выражение, последовательностью \\. Добавьте к этому частое использование этого символа в elisp — и результат начинает выглядеть так, словно кто-то рассыпал упаковку зубочисток. Ниже приведена небольшая функция для поиска следующего повторения слова:

(defun FindNextDbl()

    "move to next doubled word, ignoring <...> tags" (interactive)

    (re-search-forward "\\<\\([a-z]+\\)\\([\n \t]\\|<[^>]+>\\)+\\1\\>

Если объединить эту функцию с командой (define-key global-map "\C-x\C-d" 'FindNextDbl), вы сможете использовать последовательность «Ctrl+x Ctrl+d» для быстрого поиска повторяющихся слов.

Python

Python — объектно-ориентированный сценарный язык, не похожий ни на один из традиционных языков. Его диалект регулярных выражений довольно близок к диалекту Emacs… во всяком случае, его стандартная разновидность — в Python некоторые особенности диалекта регулярных выражений могут изменяться во время работы программы! Вам надоело изобилие обратных косых черт, характерное для Emacs? Проблему можно легко решить:

regex.set_syntax( RE_NO_BK_PARENS | RE_NO_BK_VBAR )

Два флага указывают, что для группировки в выражениях должны использоваться неэкранированные скобки, а в конструкции выбора — неэкранированная вертикальная черта. Нетрудно догадаться, почему я выбираю именно этот вариант!

Python является объектно-ориентированным языком, причем это относится и к регулярным выражениям. Вы можете создать «объект регулярного выражения»<$M[R3-16]> и позднее применить его к строке для выполнения поиска или подстановки. В следующем фрагменте в именах переменных используются символы обоих регистров. Это сделано для того, чтобы переменные было проще отличать от библиотечных компонентов.

MyRegex = regex.compile("\([0-9]+\)");

.

.

.

MyChangedData = regsub.gsub(MyRegex, "<CODE>\\1<</CODE>", MyData)

Как нетрудно догадаться, строка с тегами <CODE> представляет собой текст замены. При обратных ссылках внутри регулярного выражения в Python, Perl, Tcl и Emacs используется обозначение [\1], но в отличие от Perl с его переменной $1, обозначение \1 здесь используется и в тексте замены.

Может возникнуть вопрос — как обратиться к тексту совпадения в другой точке программы, после завершения подстановки? (В Perl переменная $1 почти ничем не отличается от обычных переменных, и ее можно использовать там, где потребуется). В объектно-ориентированном Python информация о последнем совпадении хранится в объекте регулярного выражения (MyRegex в приведенном примере). Аналогом переменной Perl $1 является конструкция MyRegex.group(1) (кстати, в Tcl и Emacs эта проблема решается иначе; см. с. <$R[P#,R6-2]> и <$R[P#,R6-3]>).

С Python никогда не бывает скучно. В этом языке реализован интересный подход к поиску без учета регистра символов: вы можете предоставить собственное описание того, как каждый байт (то есть символ) должен интерпретироваться при сравнении. Если в описании указано, что версии некоторого символа в верхнем и нижнем регистре следует считать одинаковыми, это обеспечит традиционный поиск без учета регистра, но в действительности перед вами открываются более широкие возможности. Например, при работе в кодировке Latin-1, распространенной в Web (эта кодировка содержит массу символов с всевозможными диакритическими знаками), можно организовать поиск, при котором игнорируется наличие диакритических знаков. Кроме того, при желании можно сделать так, чтобы символ ї совпадал с вопросительным знаком, символ Ў — с восклицательным знаком, а обозначения валют ў, ¤, Ј и совпадали с $. В сущности, вы можете определять символьные классы, применяемые на разных уровнях совпадения. Фантастика!

Итоги

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

При выборе дальнейших примеров я столкнулся с одной трудностью. Регулярные выражения используются не на пустом месте, а в контексте конкретной программы, и поэтому часто связываются с функциональными возможностями программы-носителя, не относящимся к регулярным выражениям. Чтобы материал носил по возможности общий характер, мне пришлось выбрать один из стилей оформления регулярных выражений. Обычно я придерживаюсь стиля egrep/awk/Perl, не отягощенный лишними символами \ — при желании вы можете легко перейти на свой излюбленный стиль.

Механизмы и внешняя отделка

Внешний вид автомобиля (или в моем случае — мотоцикла) ничего не говорит о его внутреннем устройстве. Соседи хвалят блеск и внешнюю отделку, но механики и другие специалисты в первую очередь будут обсуждать двигатель. Что это — рядная четверка? V8? Дизель? Как насчет повышенной степени сжатия? А особой формы входного коллектора? А может, ваш автомобиль приводится в движение обычными педалями? На гоночном треке водитель учитывает все эти факторы в каждом решении, которое он принимает. Возможно, для коротких поездок в магазин это несущественно — но когда-нибудь вам все равно придется заправлять машину и выбирать сорт бензина. Спросите водителя, застрявшего в пустыне из-за того, что у него сломалась какая-нибудь штуковина — так ли важны глянец и хром? Ответ предположить нетрудно. И еще одно замечание: если вы называете сломанную деталь «какой-то штуковиной», вряд ли вам удастся самостоятельно починить ее.

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

Отделка и внешний вид

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

Двигатели и механика

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

l      какой именно текст считается совпадающим;

l      скорость поиска совпадений;

l      информация, которая становится доступной после успешного совпадения (например, переменная $1 и ее семейство в языке Perl).

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

Стандартные метасимволы

<$M[R3-11]>В настоящий обзор метасимволов современных регулярных выражений были включены наиболее распространенные понятия и концепции. Разумеется, здесь не анализируются все существующие метасимволы, и ни одна программа не поддерживает всего, что здесь перечислено. В определенном смысле это сводка того, что вы видели в двух начальных главах, но в свете более широкого, более сложного мировоззрения, представленного в начале этой главы. Если вы впервые беретесь за этот раздел, можете на скорую руку просмотреть его и перейти к следующим главам. Вы сможете вернуться к нему за подробностями, когда они вам понадобятся.

Одни программы (в первую очередь Perl) обогащаются новыми, полезными возможностями, другие по своей прихоти изменяют стандартные правила (практически любой продукт от Microsoft). Третьи пытаются соблюдать стандарты, но оставляют «черные ходы» для своих целей. Хотя я иногда буду упоминать конкретные утилиты, эта глава в основном посвящена общим аспектам работы с регулярными выражениями(awk, Emacs и Tcl подробно рассматриваются в главе 6, а Perl — в главе 7). В этом разделе я всего лишь пытаюсь описать некоторые распространенные метасимволы и область их применения, а также некоторые проблемы, которые при этом должны учитываться. Во время чтения рекомендую держать под рукой руководство по той программе, с которой вы часто работаете.

Сокращенные обозначения символов

Во многих программах существуют метасимволы для представления машинно-зависимых управляющих символов, которые трудно вводить с клавиатуры или выводить на экран:

\a

Сигнал (при «выводе» раздается звуковой сигнал). Обычно соответствует ASCII-символу <BEL>, код 007 (в восьмеричной системе).

\b

Забой. Обычно соответствует ASCII-символу <BS>, код 010 (в восьмеричной системе). Обратите внимание: \b часто интерпретируется как метасимвол границы слова (см. ниже).

\e

Символ Escape. Обычно соответствует ASCII-символу <ESC>, код 033 (в восьмеричной системе).

\f

Подача листа. Обычно соответствует ASCII-символу <FF>, код 014 (в восьмеричной системе).

\n

Новая строка. На большинстве платформ (включая Unix и DOS/Windows) обычно соответствует ASCII-символу <LF>, код 012 (в восьмеричной системе). В системе MacOS обычно соответствует ASCII-символу <CR>, код 015 (в восьмеричной системе).

\r

Возврат курсора. Обычно соответствует ASCII-символу <CR>. В системе MacOS обычно соответствует ASCII-символу <LF>.

\t

Обычная (горизонтальная) табуляция. Обычно соответствует ASCII-символу <HT>, код 011 (в восьмеричной системе).

\v

Вертикальная табуляция[7]. Обычно соответствует ASCII-символу <VT>, код 013 (в восьмеричной системе).

В табл. 3.3 перечислены некоторые стандартные программы и поддерживаемые ими сокращенные обозначения управляющих символов, а также ряд других конструкций, которые встретятся нам в этой главе.<$M[R3-22]>

Таблица 3.3. Сокращенные обозначения, поддерживаемые некоторыми программами

См. расшифровку в файле pict!

Зависимость от операционной системы

<$M[R3-28]>Во многих программах сокращенные обозначения управляющих символов являются платформенно-зависимыми, а точнее — зависящими от компилятора. Все программы, упоминаемые в этой книге (исходные тексты которых я видел), были написаны на C или C++.

Как правило, когда вы запрашиваете один из этих управляющих символов в регулярном выражении или в строке, вы получаете байт, который ассоциируется у компилятора C с заданной последовательностью, начинающейся с префикса \. Стандарты C оставляют выбор фактических значений на усмотрение разработчика компилятора[8].

На практике компиляторы для всех платформ в этом вопросе подчиняются определенным стандартам, поэтому эти значения можно рассматривать как<$M[R3-26]> зависимые от операционной системы. Кроме того, на практике все символы, кроме \n и \r, стандартизируются между платформами; вы можете рассчитывать на то, что обозначение \t соответствует ASCII-символу табуляции практически везде, где поддерживается кодировка ASCII или ее надмножество (исключений я еще не видел).

К сожалению, как видно из приведенного на предыдущей странице списка, символы \n и \r стандартизированы не полностью. На всех платформах стандартной поставки GNU C (к числу которых не принадлежит MacOS) символы \n и \r отображаются на ASCII-символы перевода строки и возврата курсора соответственно. Исключением является только система IBM 370, использующая EBCDIC.

Если вы хотите, например, чтобы символ обозначал «новую строку» во всех системах, где будет работать ваш сценарий, воспользуйтесь обозначением \n. Если вы хотите работать с конкретным значением байта (например, при программировании для стандартных протоколов типа HTTP[9]), воспользуйтесь записью \012 или другим значением, соответствующим вашему стандарту.

Восьмеричные коды — \число

В некоторых реализациях байт с конкретным значением может обозначаться восьмеричным кодом, состоящим из трех цифр. Например, [\015\012] соответствует последовательности ASCII-символов CR/LF. Восьмеричные коды позволяют легко вставлять в выражения символы, которые трудно вставить другим способом. Например, в Perl можно использовать для ASCII-символа Escape обозначение [\e], но в awk такая возможность отсутствует. Поскольку в awk поддерживаются восьмеричные коды, символ Escape можно вставить непосредственно в виде ASCII-кода: [\033].

Восьмеричная цифра 9 и другие странности

Неточности в реализациях порой приводят к замечательным последствиям. Везде, кроме очень старых версий lex, правильная интерпретация \0079 не вызывала проблем. Длина восьмеричного кода не может превышать три цифры, поэтому \0079 соответствует двум символам: байту с восьмеричным кодом 7, за которым следует литерал «9». А что вы скажете о \079? Многие реализации понимают, что 9 не является восьмеричной цифрой, и интерпретируют как восьмеричный код только \07; результат получается такой же, как и для \0079 и \79. Однако flex, AT&T-версии awk и Tcl<$M[R3-23]> интерпретируют 9 как восьмеричную цифру (значение которой совпадает с \11!) Для пущего разнообразия GNU awk иногда выдает фатальную ошибку[10].

Возникает вопрос: а как интерпретируются коды, выходящие за пределы допустимого интервала — скажем, \565 (8-разрядные восьмеричные величины принимают значения от \000 до \377)? Оказывается, половина реализаций оставляет их в виде величины, выходящей за границы байта (которая никогда ни с чем не совпадет), а другая половина усекает до байта (в приведенном примере значение обычно усекается до \165, ASCII-символа u).

Шестнадцатеричные коды — \x число

По аналогии с восьмеричными кодами, во многих утилитах существует возможность ввода кодов в шестнадцатеричной системе счисления (с основанием 16) при помощи префикса \x. Последовательность [\x0D\x0A] соответствует последовательности ASCII-символов CR/LF. Проблемы, описанные в предыдущем разделе, для шестнадцатеричных кодов еще более усложняются. Одни реализации разрешают использовать шестнадцатеричные коды, состоящие только из двух цифр, другие также разрешают шестнадцатеричные коды с одной цифрой. В третьих количество цифр может быть любым. Это приводит к всевозможным сюрпризам<$M[R3-19]> — например, если вы включаете в выражение [ora\x2Ecom] шестнадцатеричный код \x2E, а реализация воспринимает его как \x2EC.

Может показаться, что если вы привыкли к особенностям своей программы, такие ошибки не возникают. К сожалению, когда разные реализации одной программы начинают вести себя по-разному, возникают проблемы переносимости и обновления. Например, одни известные мне версии awk (GNU awk и MKS awk) читают любое количество шестнадцатеричных цифр, а другие (такие, как mawk) читают только две цифры. AT&T awk тоже ограничивается двумя цифрами.

Числовые коды и литералы

Если диалект вашей программы поддерживает вставку числовых кодов символов, можно предположить, что выражение [[+\055*/]] представляет собой символьный класс, совпадающий с плюсом, минусом (055 — ASCII-код символа «-»), звездочкой или косой чертой. В Perl и многих других программах это действительно так — предполагается, что если вы решились на хлопоты<$M[R3-18]> с вводом восьмеричного кода, то этот код не следует интерпретировать как обычный метасимвол. Однако некоторые реализации[11] преобразуют вставленные коды еще до просмотра выражения основным механизмом, поэтому с точки зрения последнего выражение содержит символ «-», который должен был замаскирован посредством вставки кода. В результате +-* рассматривается как интервал. Это приводит к неожиданным последствиям, поэтому в табл. 3.3 такие реализации помечены знаком ▲.

Из всех протестированных мной программ подобная «двухпроходная» обработка выполнялась только в GNU и MKS awk. Я говорю это, зная о том, что в аналогичной ситуации Tcl, Emacs и Python тоже рассматривают \055 как интервальный метасимвол, но эти программы не были помечены знаком ▲. В чем же дело?

Строки как регулярные выражения

<$M[R3-21]>Как видно из табл. 3.3, в регулярных выражениях Emacs, Tcl и Python[12] поддерживается большинство из перечисленных обозначений. Но почему они помечены знаком ###белая галочка### ? Потому что на самом деле эта запись, даже восьмеричные коды, не поддерживаются механизмом регулярных выражений. В этих программах операнды, которые представляют собой регулярные выражения, обычно передаются в строковом виде. Это означает, что до того, как выражение будет передано механизму регулярных выражений, оно проходит стандартную строковую обработку в соответствии с правилами языка. Именно строковые средства, а не механизм регулярных выражений, обеспечивают поддержку синтаксических элементов, помеченных знаком ###белая галочка### (подобный пример уже встречался при описании Emacs на с. <$R[P#,R3-1]>).

Это означает, что данные обозначения могут использоваться в регулярных выражениях<$M[R3-4]> в большинстве практических ситуаций, поэтому я включил их в табл. 3.3. Однако следует помнить, что строковая обработка, обеспечивающая эту возможность, выполняется лишь в том случае, когда операнды регулярных выражений действительно являются строками. Если выражение передается в командной строке или читается из файла в другой, не строковой форме, то данные передаются механизму регулярных выражений в «сыром», необработанном виде, и тогда эти обозначения становятся недоступными. Вот почему, например, они не могут использоваться в регулярных выражениях Emacs, вводимых пользователем непосредственно во время сеанса редактирования.

Что это означает лично для вас? Как минимум то, что эти обозначения могут превращаться в метасимволы (как помеченные знаком ▲ в табл. 3.3), и при возникновении конфликтов между метасимволами строк и регулярных выражений приоритет отдается метасимволам строк. Для предотвращения неверной интерпретации конфликтные метасимволы регулярных выражений необходимо экранировать.

[\b] как забой, [\b] как граница слова

Вероятно, вы заметили, что в Python и Emacs символ \b имеет двойную интерпретацию. Знак ###белая галочка### указывает на интерпретацию \b строковым механизмом, в результате которой он превращается в забой. Знак √ относится к интерпретации \b механизмом регулярных выражений, в результате чего он преобразуется в метасимвол границы слова[13]. Вторая интерпретация обеспечивается включением в строку последовательности \\b — в процессе обработки строки \\ преобразуется в один символ \, оставляя механизму регулярных выражений \b. Как ни смешно, но регулярное подвыражение, означающее один литерал «обратная косая черта», состоит из четырех символов \. Регулярное выражение должно содержать последовательность [\\], а каждый символ \, присутствующий в регулярном выражении, должен быть удвоен в исходной строке. В результате получается \\\\.

Хотя в рассматриваемых до настоящего момента ситуациях Python и Emacs вели себя похожим образом, они по-разному интерпретируют экранированные последовательности, не опознанные в процессе обработки строк.

Обработка в стиле Emacs: удаление символа \

<$M[R3-24]>В строках Emacs, как и в большинстве пакетов и языков с поддержкой регулярных выражений, неопознанные символы \ удаляются, а в строку включается следующий символ. Следовательно, каждый символ \, который должен войти в регулярное выражение, должен экранироваться дополнительным префиксом \. Пример был приведен на с. <$R[P#,R3-2]>; приведу другое выражение:

"\"[^\\\"]*\\(\\\\\\(.\\|\n\\)[^\\\"]*\\)*\""

Ну как? Удастся ли вам сходу разобраться в этом выражении? Пример взят из реальной программы[14], но у меня от него голова идет кругом. Поскольку выражение передается в виде строки, механизм регулярных выражений получает его лишь после того, как оно пройдет стандартную строковую обработку. Механизму регулярных выражений в действительности будет передано выражение:

["[^\"]*\(\\\(.\|new\)[^\"]*\)*"]

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

["[^\"]*(\\(.|new)[^\"]*\)*"]

Это регулярное выражение для поиска строки, заключенной в кавычки. Одно замечание: в символьных классах Emacs символ \ не является метасимволом. В этом отношении Emacs похож, например, на egrep, но отличается от Perl, lex и awk. В тех программах, где обратная косая черта имеет особую интерпретацию в символьных классах, [^\"] следует записывать в виде [^\\"]. Кажется, я забегаю вперед, потому что это регулярное выражение встретится нам в главах 4 и 5, но для сравнения замечу, что на Perl приведенный пример записывается в виде

[(?s)"[^\\"]*(\\.[^\\"]*)*"]

Обработка в стиле Python: передача символа \

В строках Python по отношению к неопознанным символам \ используется противоположный подход: они передаются без изменений. В регулярных выражениях Python первые девять обратных ссылок обозначаются метасимволами от [\1] до [\9], а для последующих образных ссылок используются обозначения от [\v10] до [\v99]. Однако в строках Python \v опознается как символ вертикальной табуляции, поэтому для того, чтобы сослаться на двенадцатую группу круглых скобок, необходимо включить в строку \\v12. Вроде бы пока все идет, как в Emacs.

В регулярных выражениях Python [\w] интерпретируется как символ слова (см. следующий раздел). Поскольку [\w] не имеет собственной интерпретации в строках Python, а неопознанные символы \ передаются без изменений, вы можете смело включить в строку неэкранированный метасимвол \w. Это уменьшает проявления «синдрома обратной косой», от которого страдает Emacs, но ограничивает потенциальные возможности расширения строк Python в будущем (впрочем, если вы цените логическую согласованность превыше всего прочего, это можно считать положительным свойством).

Сокращенные обозначения классов, символ «точка» и символьные классы

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

\d

Цифра. Обычно эквивалентно [[0-9]].

\D

Не-цифра. Обычно эквивалентно [[^0-9]].

\w

Символ, входящий в слово. Часто эквивалентно [[a-zA-Z0-9]]. В некоторых программах (особенно Perl, GNU awk и GNU sed) в эту категорию также включается символ подчеркивания. В GNU Emacs интерпретация \w может изменяться во время работы программы — см. раздел «Синтаксические классы».

\W

Символ, не входящий в слово. Обычно эквивалентно отрицанию \w (то есть [[^…]]).

\s

Пропуск. Часто эквивалентно [[spc\f\n\r\t\v]].

\S

Не-пропуск. Обычно эквивалентно отрицанию \s (то есть [[^…]]).

Эти обозначения также приведены в табл. 3.3. Как говорилось на с. <$R[P#,R3-3]>, локальный контекст POSIX может влиять на интерпретацию некоторых обозначений. Я твердо знаю, что это так в Tcl, Emacs и Perl, и уверен, что в остальных программах дело обстоит также. За точной информацией следует обратиться к документации (даже если вы не пользуетесь локальными контекстами, их необходимо учитывать хотя бы из соображений переносимости).

Синтаксические классы Emacs

Однако возможны совершенно иные интерпретации. В GNU Emacs и его семействе [\s] означает специальный «синтаксический класс». Ниже приведены два примера:

\sсимвол

совпадает с символами, принадлежащими синтаксическому классу Emacs, определяемому заданным символом.

\Sсимвол

совпадает с символами, не принадлежащими синтаксическому классу Emacs.

Например, [\sw] означает «символ, входящий в слово» (идентично [\w]), а [\s-] означает «символ-пропуск». Поскольку последняя конструкция очень похожа на метасимвол Perl [\s], в табл. 3.3 она помечена знаком ###плюс с дыркой###.

Особенность синтаксических классов заключается в том, что точный состав входящих в них символов может изменяться во время работы программы. Например, концепция символов, образующих слова<$M[R3-8]>, может изменяться в зависимости от типа редактируемого файла (за подробностями обращайтесь к главе 6, начиная со с. <$R[P#,R6-4]>)

Точка — (почти) любой символ

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

Исходные инструменты Unix работали в построчном режиме, поэтому до появления sed и lex сама проблема совпадения с символом новой строки была неактуальной. К моменту появления этих программ запись [.*] стала распространенной идиомой «совпадения до конца строки», поэтому запрет выхода за границу строки предотвратил «чрезмерное разрастание»[15] совпавшего текста.

Итак, было решено, что точка будет совпадать с любым символом, кроме символа новой строки. Большинство современных программ поддерживает работу с многострочным текстом, и эти два варианта реализации выбираются примерно с одинаковой частотой (привязка к границам логических и обычных строк анализируется в разделе «Якорные метасимволы» на с. <$R[P#,R3-12]>, а также в разделе «Точка и инвертированные символьные классы»). Существует и другое обстоятельство, не столь важное при работе с обычным текстом — стандарт POSIX требует, чтобы точка не совпадала с нуль-символом (байтом, значение которого равно 0).

Символьные классы — […] и [^…]

Базовая концепция символьного класса уже рассматривалась выше, но позвольте мне снова подчеркнуть, что правила интерпретации метасимволов изменяются в зависимости от того, принадлежат они символьному классу или нет. Например, в табл. 3.3 в классах могут использоваться только те метасимволы, которые помечены знаком ###галочка с буквой C### (в действительности могут использоваться и метасимволы со знаком ###белая галочка###; причины и ограничения описаны на с. <$R[P#,R3-4]>).

Во многих программах в символьных классах распознаются только следующие символы:

l      символ ^ в начале класса (признак инвертированного класса);

l      завершающая квадратная скобка (завершение класса);

l      дефис, выполняющий функции интервального оператора (позволяет использовать 0-9 как удобное сокращение для 0123456789).

В реализациях классов с ограниченным набором метасимволов другие метасимволы (включая даже \) не распознаются. Соответственно, вы не сможете использовать \- или \] для того, чтобы вставить в класс символ «дефис» или закрывающую квадратную скобку. Конкретные правила различаются, но обычно размещение символа в самом начале класса, где он не может интерпретироваться как метасимвол, обеспечивает его интерпретацию как литерала.

В общем случае порядок перечисления символов в классе несущественен, а использование интервалов вместо списка не влияет на скорость обработки (то есть [0-9] ничем не отличается от [9081726354]).

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

При использовании интервалов старайтесь оставаться в границах [0-9], [a-z] или [a-Z]. Даже если вы знаете кодировку символов и уверены в том, что ваша задача решается конструкцией вида [.-m], все же рекомендуется перечислить конкретные символы, чтобы выражение было проще понять. Конечно, при работе с двоичными данными использование интервалов вида [\x80-\xff] вполне оправдано.

Точка и инвертированные символьные классы

При работе с программами, допускающими поиск в многострочном тексте, следует помнить, что точка обычно не совпадает<$M[R3-10]> с символом новой строки, но инвертированные классы типа [[^"]] обычно с этим символом совпадают. Таким образом, переход от [".*] к [[^"]*] может преподнести сюрприз. Вопрос, совпадает ли инвертированный класс с символом новой строки, лучше всего выяснить для каждой конкретной программы — сведения о нескольких распространенных программах приведены в табл. 3.4 на с. <$R[P#,R3-13]>.

Групповые выражения в стандарте POSIX

<$M[R3-5]>То, что мы обычно называли символьным классом, в стандарте POSIX было решено назвать групповым выражением (bracket expression). В POSIX термин «символьный класс» относится к специальной конструкции, используемой внутри группового выражения[16].

«Символьные классы» в групповых выражениях POSIX

Символьный класс POSIX представляет собой одну из нескольких специальных метапоследовательностей, используемых внутри групповых выражений в стандарте POSIX. Примером является конструкция [:lower:], соответствующая любой букве нижнего регистра в текущем локальном контексте (см. с. <$R[P#,R3-6]>). Для нормального английского текста конструкция [:lower:] означает интервал a-z.

Поскольку вся метапоследовательность действительна только внутри группового выражения, класс, эквивалентный [[a-z]], имеет вид [[[:lower:]]]. Да, это выглядит уродливо, но предоставляет дополнительную возможность включения других символов — ц, с и т. д. (если в локальном контексте они действительно являются символами нижнего регистра).

Точный список символьных классов POSIX зависит от локального контекста, но по крайней мере следующие классы обычно поддерживаются (должны поддерживаться для полного соответствия стандарту POSIX):<$M[R3-30]>

[:alnum:]

алфавитные символы и цифровые символы

[:alpha:]

алфавитные символы

[:blank:]

пробел и табуляция

[:cntrl:]

управляющие символы

[:digit:]

цифры

[:graph:]

отображаемые символы (не пробелы, не управляющие символы и т. д.)

[:lower:]

алфавитные символы нижнего регистра

[:print:]

аналог [:graph:], но включает пробел

[:punct:]

знаки препинания

[:space:]

все пропуски ([:blank:], символ новой строки, возврат курсора и т. д.)

[:upper:]

алфавитные символы верхнего регистра

[:xdigit:]

цифры, допустимые в шестнадцатеричных числах (то есть 0-9a-fA-F).

Программы, не соответствующие стандарту POSIX, тоже часто пытаются поддерживать эти конструкции. Во всяком случае, это относится к flex и GNU awk, grep и sed (но, как ни странно, в GNU egrep они не поддерживаются).

«Символьные эквиваленты» в групповых выражениях POSIX

В некоторых локальных контекстах определяются символьные эквиваленты (character equivalents), указывающие, что какие-то из символов должны считаться идентичными при выполнении сортировки и других аналогичных операций. Например, локальный контекст может определить класс-эквивалент «, содержащий символы n и с, или класс «a», содержащий символы a, а и б. Используя запись, аналогичную приведенной выше конструкции [:…:], и заменив двоеточия знаками равенства, можно ссылаться на классы-эквиваленты в групповых выражениях; например, [[[=n=][=a=]]] совпадает с любым из перечисленных символов.

Если символьный эквивалент с однобуквенным именем используется, но не определяется в локальном контексте, он по умолчанию совпадает с объединяющей последовательностью с тем же именем. Локальные контексты обычно содержат объединяющие последовательности для всех обычных символов ([.a.], [.b.], [.c.] и т. д.), поэтому при отсутствии специальных эквивалентов конструкция [[[=n=][=a=]]] по умолчанию считается идентичной [[na]].

«Объединяющие последовательности» в групповых выражениях POSIX

Как упоминалось на с. <$R[P#,R3-7]>, в локальном контексте могут определяться объединяющие последовательности, описывающие интерпретацию некоторых символов или совокупностей символов при сортировке и других операциях. Объединяющая последовательность отображает несколько физических символов на один логический символ — например, span-ll рассматривается как «один символ» в механизме регулярных выражений, в полной мере соответствующем стандарту POSIX. Это означает, что выражение типа [[^123]] совпадет с последовательностью ll.

Для включения элементов объединяющих последовательностей в групповые выражения используется обозначение [.….]: выражение [torti[[.span-ll.]]a] совпадает с tortilla. Объединяющая последовательность позволяет осуществлять сравнение символов, которые представляют собой комбинации других символов. Кроме того, становятся возможными ситуации, при которых групповое выражение совпадает с последовательностью из нескольких физических символов!

Другой пример, eszet, всего лишь обеспечивает правильное упорядочение Я — новый логический символ при этом не создается, поэтому в групповом выражении [.eszet.] представляет собой просто экзотический способ записи символа Я (который выглядит и без того странно, если вы не владеете немецким языком).

Наличие объединяющих последовательностей также влияет на интервалы. Поскольку span-ll создает логический символ, расположенный между l и m, интервал a-z будет включать и последовательность «ll».

Якорные метасимволы

<$M[R3-12]>Якорные метасимволы совпадают не с реальными символами, а с позициями в тексте. Существует несколько распространенных разновидностей якорных метасимволов.

Начало строки и начало фрагмента — символ ^

Первоначально символ ^ использовался для привязки выражения к началу строки. В таких приложениях, как ed и grep, где проверяемый регулярным выражением текст всегда делился на строки, понятия «логическая строка» и «проверяемый текст» всегда совпадали. Однако другие программы позволяли выполнять поиск в произвольном тексте. Если текст содержит внутренние<$M[R3-15]> символы новой строки, можно считать, что он состоит из нескольких логических строк. Где в этом случае должен совпадать символ ^ — в начале каждой логической строки или только в начале всего целевого текста (в дальнейшем будет использоваться термин «фрагмент»)?

Правильный ответ — «зависит от программы». В текстовом редакторе начало текста фактически означает начало файла, и совпадение ^ только в начале файла выглядело бы довольно глупо. С другой стороны, в sed, awk и Tcl символ ^ совпадает только в начале всего фрагмента. Фрагмент может представлять собой отдельную  строку, весь файл или что-нибудь еще — способ получения проверяемых данных не имеет отношения к их обработке. В Perl можно организовать совпадение как в начале строки, так и в начале фрагмента, но по умолчанию ^ совпадает только в начале фрагмента. В табл. 3.4 приведена информация об использовании символов ^ и $ в нескольких распространенных программах.<$M[R3-13]>

Таблица 3.4. Привязка к строке/фрагменту и другие аспекты, связанные с символами новой строки

См. расшифровку в файле pict!

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

Где в регулярном выражении ^ интерпретируется как метасимвол?

В символьных классах действуют особые правила, и в большинстве программ они соблюдаются, но за пределами символьного класса ^ иногда интерпретируется как якорный метасимвол, а иногда — как литерал «крышка». Во многих программах он интерпретируется как метасимвол там, где это «имеет смысл» (например, после [(] или [|]), но в других программах он считается метасимволом лишь в начале регулярного выражения.

Конец строки и конец фрагмента — символ $

Символ $ образует пару с ^ — он совпадает в конце строки/фрагмента. Обычно проблема внутренних логических строк решается для него так же, как и для ^, но как показывает табл. 3.4, при этом возникают дополнительные проблемы. В одних реализациях $ совпадает перед любой новой строкой, в других — только в конце всего фрагмента. Кроме того, совпадение может происходить в конце фрагмента или перед символом новой строки, завершающим фрагмент (в Perl по умолчанию используется последний вариант, однако в программе можно переключиться в режим, при котором совпадение происходит перед любой новой строкой). В третьих программах (особенно lex) совпадение происходит только перед символом новой строки, но не в любой позиции — в частности, не в конце целевого текста.

Границы слов — \<…\>, \b и \B

Эти метасимволы, как и ^ с $, совпадают не с символом, а с определенной позицией строки. Существуют два разных подхода. В одном позиция начала и конца слова обозначается разными метасимволами [\<] и [\>]. В другом метасимвол [\b] совпадает с любой границей слова (началом или концом), а [\B] — с любой позицией, не являющейся границей слова. Кстати, последний метасимвол иногда оказывается на удивление полезным.

У каждой программы имеются свои представления о том, что следует считать «символом слова», а у программ с поддержкой локальных контекстов POSIX (см. с. <$R[P#,R3-6]>) эти представления зависят от локального контекста. Как было сказано на с. <$R[P#,R3-8]>, в Emacs они тоже могут изменяться, но по другим причинам. В любом случае проверка границы слова всегда сводится к простой проверке соседних символов. Ни один механизм регулярных выражений не принимает решений на основе лексического анализа — строка «NE14AD8» везде считается словом, а «M.I.T.» к словам не относится.

Группировка и сохранение текста

(…) или \(…\); \1, \2, \3 и т. д.

До настоящего момента я уделял относительно мало внимания обратным ссылкам. Если программа поддерживает обратные ссылки, то конструкция [\цифра] обозначает текст, совпавший с подвыражением в круглых скобках с заданным порядковым номером (группы нумеруются слева направо в соответствии с номером открывающей круглой скобки). Обычно разрешаются обратные ссылки с номерами до [\9], хотя в некоторых программах поддерживается произвольное количество обратных ссылок.

Как упоминалось выше, в некоторых программах конструкции [\1], [\2] и т. д. позволяют работать с совпавшим текстом за пределами регулярного выражения. В других программах доступ к совпавшему тексту предоставляется лишь в строке замены (обычно при помощи тех же конструкций [\1], [\2] и т. д., но в данном случае они являются метасимволами строки замены, а не метасимволами регулярного выражения). В некоторых программах совпавший текст доступен в любой точке программы — например, в Perl для этого используется переменная $1, а в Python — конструкция MyRegex.group(1). Некоторые программы не только предоставляют доступ к тексту совпавшего подвыражения, но и выдают информацию о точной позиции этого текста в строке. Эти сведения часто оказываются полезными при решении нетривиальных задач по обработке текста. В качестве примеров можно привести GNU Emacs, Tcl и Python (данная возможность почему-то отсутствует в Perl).

Квантификаторы

Квантификаторы (*, +, ? и интервальная конструкция — метасимволы, определяющие количество экземпляров повторяющегося элемента) рассматривались в одной из предшествующих глав. Однако обратите внимание, что в некоторых программах вместо [+] и [?] используются [\+] и [\?]. Кроме того, в отдельных программах квантификаторы не могут применяться к обратным ссылкам или выражениям, заключенным в скобки.

Пример совершенно иного подхода представлен в Perl. Нескладные конструкции *?, +?, ?? и {мин, макс}? в других диалектах обычно не поддерживаются. Они представляют собой минимальные[17] версии квантификаторов. Обычные квантификаторы руководствуются критерием максимального совпадения и пытаются найти совпадение как можно большей длины. Стандартные квантификаторы Perl являются максимальными, но существуют и другие, минимальные версии, которые ищут совпадение наименьшей длины. Подробности приведены в следующей главе.

Интервалы — {мин, макс} и \{мин, макс\}

Интервальный квантификатор «ведет счет» найденных экземпляров совпадения. Он определяет наименьшее количество обязательных и наибольшее количество допустимых экземпляров. Если указывается только одно число ([[a-z]{3}] или [[a-z]\{3\}] в зависимости от диалекта) и этот синтаксис поддерживается программой, совпадает в точности заданное количество экземпляров. Приведенный пример эквивалентен [[a-z][a-z][a-z]], хотя в некоторых типах механизмов последний вариант более эффективен (см. с. <$R[P#,R5-2]>).

Предупреждаю: не стоит полагать, что конструкция вида [X{0,0}] означает «здесь не должно быть X». Выражение [X{0,0}] бессмысленно, поскольку оно означает «ни один экземпляр X не обязателен, так что можно даже не пытаться их искать». Это равносильно тому, что конструкция [X{0,0}] вообще отсутствует — если даже элемент X и есть, он может совпасть с одной из следующих частей выражения, поэтому исходный смысл этой конструкции полностью утрачивается[18].

Поскольку нежелательным элементом в данном примере является один символ X, вы можете воспользоваться конструкцией [[^X]], означающей, что в этой позиции находится любой символ, кроме X. Иногда такое решение подходит, но эта формулировка все же не эквивалентна формулировке «убедиться в том, что в этой позиции нет X», поскольку для совпадения [[^X]] необходимо присутствие символа, а концепция «отсутствия X» никаких символов не требует. Из всех распространенных диалектов регулярных выражений эта возможность реализована только в Perl (см. с. <$R[P#,R7-1]>).

Конструкция выбора

Конструкция выбора допускает совпадение одного из нескольких подвыражений. Каждое подвыражение называется альтернативой (alternative). Вместо символа [|] в некоторых диалектах используется [\|].

Конструкция выбора всегда является высокоуровневой (то есть обладающей очень низким приоритетом). Это означает, что выражение [this and|or that] эквивалентно [(this and)|(or that)], а не потенциально более полезному [this (and|or) that]. Одно из исключений состоит в том, что якоря строк в lex не являются равноправными метасимволами — они действительны только на концах регулярного выражения и обладают еще меньшим приоритетом, чем конструкция выбора. Это означает, что в lex выражение [^this|that$] эквивалентно [^(this|that)$], а не [(^this)|(that$)], как в большинстве других случаев.

Хотя стандарт POSIX, lex и большинство версий awk запрещают выбор с пустой<$M[R3-20]> альтернативой ([(this|that|)], я полагаю, что такая конструкция выглядит вполне естественно. Пустое подвыражение означает, что совпадение происходит всегда, поэтому данный пример логически эквивалентен [(this|that)?]. Впрочем, это только теория; на практике во многих программах это далеко не так. В числе немногих программ, в которых эти два выражения действительно эквивалентны — awk, lex и egrep (см. главу 4). Но даже если эти выражения полностью идентичны, такая запись полезна хотя бы из соображений удобства и наглядности. Как мне однажды объяснил Ларри Уолл, она «выполняет те же функции, как ноль в системе счисления».

Путеводитель по серьезным главам

После знакомства с метасимволами, диалектами, синтаксической оберткой и т. д. настало время перейти к техническим подробностям, действительно серьезному материалу, подлинной сути  — называйте, как хотите. Рассмотрение этой темы начинается с главы 4, «Механика обработки выражений». Существуют разные варианты реализации механизма, обеспечивающего поиск совпадений, и от выбора того или иного варианта зависит, будет найдено совпадение или нет, какой текст в строке совпадет и сколько времени займет поиск. Мы рассмотрим все подробности. Заодно этот материал поможет вам более уверенно строить сложные выражения.

Мы естественно переходим к теме главы 5, «Построение сложных выражений». Разобравшись в основах работы механизма, мы рассмотрим приемы, позволяющие извлечь максимум пользы из этих знаний — и этого механизма. В главе 5 описаны недочеты некоторых распространенных диалектов регулярных выражений (нередко приводящие к неприятным сюрпризам) и рассказано, как обратить их себе на пользу.

Главы 4 и 5 являются центральным стержнем этой книги, ее истинной квинтэссенцией. Первые три главы всего лишь подводили нас к этой теме, а последующее описание конкретных программ основано на этих главах. Изложенный материал никак не назовешь «легким чтивом», но я постарался держаться подальше от алгебры, математики и всего того, что для большинства из нас выглядит китайской грамотой. Вероятно, как обычно бывает при получении большого объема информации, новые знания будут усвоены не сразу.

Информация о конкретных программах

Концепции и принципы, рассмотренные в главах 4 и 5, выходят за рамки конкретных программ. Возможно, некоторые примеры придется слегка подправить, чтобы они соответствовали конкретному диалекту, но важны не конкретные примеры, а вынесенные из них уроки.

Такие языки, как awk, Tcl, Python, sed и Emacs обладают последовательным интерфейсом для работы с регулярными выражениями. Если вы разобрались в работе их механизма регулярных выражений (главы 4 и 5), остается не так уж много информации, относящейся к конкретной программе — разве что несколько замечаний, касающихся «хрома и внешней отделки». Мы рассмотрим эту тему в главе 6.

С другой стороны, Perl и «Путь Perl» связаны с регулярными выражениями на многих уровнях. Богатые и выразительные средства Perl для работы с регулярными выражениями содержат немало неясностей и темных мест, на которые следует обратить особое внимание. Одни рассматривают Perl как всепобеждающую силу в мире сценарных языков, другие считают его забавным уродцем. Те возможности, которые позволяют мастеру решить теорему Ферма[19] в однострочной программе, в руках непосвященного превращаются в адскую машину. По этой причине в главе 7 мы до мельчайших подробностей рассмотрим регулярные выражения и операторы Perl. Попутно приводится немало общих сведений о программировании на Perl, но основной темой этой главы является понимание и использование средств Perl, связанных с регулярными выражениями.



[1] Статья «A logical calculus of the ideas immanent in nervous activity» была впервые опубликована в бюллетене «Bulletin of Math.Biophysics» (номер 5, 1943 г.) и позднее перепечатана в «Embodiments of Mind» (MIT Press, 1965 г.) Статья начинается с интересного обзора поведения нейронов (оказывается, скорость внутринейронных импульсов меняется от 1 до 150 метров в секунду!), после чего погружается в бездну формул, в которых я так и не разобрался.

[2] Rebert L.Constable, «The Role of Finite Automata in the Development of Modern Computing Theory», материалы «The Kleene Symposium», редакторы Barwise, Keisler и Kunen (North-Holland Publishing Company, 1980), с. 61–83.

[3] «Communications of the ACM», Vol. 11, No. 6, June 1968.

[4] Историческая информация: edgrep) использовали в качестве ограничителей экранированные скобки вместо простых, потому что Кен Томпсон решил, что регулярное выражения будут в основном использоваться для работы с программным кодом C, и поиск скобок-литералов будет происходить чаще, чем применение обратных ссылок.

[5] Как при написании книги по регулярным выражениям — поверьте, я знаю, о чем говорю!

[6] Например, в кодировщике URL на с. <$R[P#,R7-103]> вместо [[^a-zA-Z0-9]] в предыдущих изданиях этой книги использовался метасимвол [\W]. Но один мой друг столкнулся с проблемами при интерпретации некоторых байтов, не входящих в набор ASCII-символов (???, ??? и т. д.) Он ожидал, что эти байты будут отнесены к [\W], но его версия Perl отнесла их к [\w], что приводило к неожиданным результатам.

[7] Насколько мне известно, ASCII-символ вертикальной табуляции перестал использоваться вместе с телетайпами.

[8] Спасибо Хэлу Вайну (Hal Wine) за разъяснения по этому вопросу.

[9] Я написал на Perl программу выборки URL webget (имеется на моей домашней странице, см. приложение А). Я получал множество сообщений о том, что программа не работает с некоторыми хостами. Пришлось сделать ее более «тупой» и не настаивать на правильном форматировании ответов HTTP. Оказалось, при построении ответов некоторые Web-серверы ошибочно использовали \n вместо \015\012.

[10] Фатальная ошибка выдавалась в GNU awk 3.0.0, последней версии на момент подготовки книги. Мне сообщили, что эта ошибка (как и многие другие, упоминаемые в книге) будет исправлена в следующей версии.

[11] Для тех, кто хочет соблюдать стандарт POSIX, разобраться в происходящем будет нелегко. Пол Стейнбах (Paul Steinbach), ведущий инженер из Mortice Kern Systems, убедил меня в том, что именно вторая интерпретация при всей своей нелепости соответствует стандарту POSIX.

[12] К Perl данный раздел не относится. Уникальные свойства Perl в этом отношении подробно рассматривается в главе 7 (с. ???)

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

[14] Стандартная библиотека Emacs elisp битком набита регулярными выражениями. Приведенный пример взят из файла hilit19.el.

[15] По словам Кена Томпсона, автора ed.

[16] Обычно в этой книге термины «символьный класс» и «выражение POSIX в квадратных скобках» используются как синонимы, описывающую конструкцию в целом, а термин «символьный класс POSIX» относится к особой псевдо-интервальной конструкции, описанной в этом разделе.

[17] Также называемые «ленивыми» (lazy) или «щедрыми» (non-greedy) — см. с. ???.

[18] Теоретически все сказанное о {0,0} верно. На практике дело обстоит еще хуже — последствия почти непредсказуемы! В некоторых программах (включая GNU awk, GNU grep и старые версии Perl) конструкция {0,0} эквивалентна *, а во многих других (включая большинство виденных мной версий sed и некоторые версии grep) она эквивалентна ?. Безумие!

[19] Конечно, я преувеличиваю, но если хотите попробовать — поищите слово Fermat на Yahoo (http://www.yahoo.com).