Сложно? Урегулируем!

1 март, 2006 - 00:00Андрей Зубинский

Когда интересное становится совсем очевидным – оно становится и совсем неинтересным. Какую замечательную авантюру можно было бы построить на скупой информации о том, что основатель и бывший главный архитектор проекта одного из популярных дистрибутивов ОС Linux Дэниэл Роббинс, не так давно принятый на работу в... Microsoft, ушел по собственному желанию...

К сожалению автора, никакой авантюры из истории с Дэниэлом Роббинсом не получается – просто хороший специалист решил заниматься более нравящимся ему и одновременно, по всей вероятности, более выгодным делом. А именно разработкой в независимой компании программного обеспечения... для платформы .NET. Вместе с Роббинсом (обвинить которого в предвзятом отношении очень трудно) подобным же делом «как-то вдруг» заинтересовалась сразу целая армия работодателей, в итоге профессия .NET-программиста мгновенно переместилась в первую пятерку списка самых востребованных IT-специальностей. «Неожиданность» роста популярности .NET усугубил шок, вызванный заявлением Borland об уходе с рынка интегрированных средств разработки (IDE). Ту самую знаменитую Borland, которая в многолетней игре «на чужом поле» успешно противостояла Microsoft, по-видимому, можно назвать «еще одной» жертвой рыночной дубины, вырезанной хитрыми маркетологами из того, что выросло на мощных академических корнях Оpen Source. Действительно, пока Borland играла там, где принято играть «по правилам» (соотношением качества к цене), все было вполне хорошо, несмотря на то что в той игре Microsoft имела вполне законные преимущества, которые имеет любой производитель системного и инструментального ПО для своей собственной платформы. Но как только в формуле качество/цена в знаменателе забрезжил вожделенный маркетологами и потребителями ноль, правила действовать перестали. А бесконечные обсуждения преимуществ «новых» моделей (типа «деньги за сервис») и success stories, увы, правил не заменяют.

Впрочем, довольно о грустном. Раз .NET-программисты нужны, и .NET-программистам нужны инструменты, значит, мы будем регулярно о таких инструментах рассказывать, придерживаясь прежних негласных правил – говорить только о бесплатном, полезном и достойном траты времени. Естественно, ни о какой объективности при оценках по столь неопределенным и зависящим от массы факторов критериям и речи быть не может, но все-таки...

Регулярная экспрессия

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

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

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

Вернемся к ранее использованному примеру двух строк, построенных из множества символов б,в,е,з,н,о,с,т,ь,я. Такое множество принято называть алфавитом. Для вольно используемого и интуитивно понятного термина «слово» также есть определение: слово – это рассматриваемая как единое целое последовательная запись нескольких символов алфавита. Количество символов в слове называется его длиной. Теперь мы знаем, что «обезьянство» и «светобоязнь», – это два разных слова одинаковой длины (11), построенные на алфавите б,в,е,з,н,о,с,т,ь,я. Слово, состоящее ни из одного символа, также возможно – его принято называть пустым словом. Примечательно, что теперь мы можем рекурсивно определить алфавит, для которого ранее существовало только построенное на основе сравнения с примером определение: алфавит – это множество, состоящее из слов с длиной 1.

Над алфавитами (как полноценными множествами) можно производить некоторые операции. Одна из них – соединение (по-умному – конкатенация). В результате конкатенации двух алфавитов получается множество всех возможных слов, каждое из которых имеет длину 2 и образовано символами этих алфавитов. Например, конкатенацией алфавитов а, б и в, г будет множество ав, аг, бв, бг, ва, га, вб, гб. Конкатенация трех алфавитов породит множество слов длины 3, четырех – длины 4, N – длины N. Операцию конкатенации алфавитов, обозначенных, например, A и B, принято записывать как AB, операцию конкатенации алфавита A с самим собой – AA или A2. Таким образом, слово «светобоязнь» принадлежит множеству слов, построенному одиннадцатикратной конкатенацией алфавита A=б,в,е,з,н,о,с,т,ь,я самого с собой, иначе – A11. Множество всех слов длины от 1 до N, образованное объединением множеств A1, A2, A3...AN, но не содержащее пустого слова, принято обозначать A+. Если же в перечень элементов A+ добавить пустое слово, получится именуемое итерацией языка множество A*, описывающее все возможные слова, которые можно построить на основании алфавита A.

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

• регулярными множествами являются: пустое множество (т. е. вообще не содержащее элементов), множество, содержащее один элемент – пустое слово и алфавиты (множества, состоящие из слов с длиной 1);
• если A и B – регулярные множества, то регулярными являются итерации языков A* и B*, а также множества, образованные операциями конкатенаций и объединения этих множеств, т. е. AA, BB, AB, AUB и т.д.

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

Рис. 1

А теперь, после знакомства с понятийным аппаратом, лежащим в основе регулярных выражений, пора сказать пару слов о простоте и сложности. В книгах и самоучителях словосочетание «регулярное выражение» в комбинации со словом «просто» встречается очень часто. Например Google находит 11 900 000 страниц, содержащих фразу (именно фразу!) "regular expression" и 3 350 000 – на которых встречаются одновременно "regular expression" и "simple" (строка поиска +"regular expression" + simple). Но обольщаться столь часто упоминаемой простотой не стоит. Чтобы в этом убедиться, достаточно взглянуть на регулярное выражение (рис. 1), описывающее язык всех возможных e-mail адресов, составленных в точном и полном соответствии с требованиями RFC 822. С другой стороны, что такое менее чем шесть с половиной тысяч символов в сравнении с множеством всех возможных e-mail-адресов (число элементов которого, очевидно, колоссально)? И кто (из находящихся в здравом уме и сознании) возьмется полностью перечислить элементы этого множества и реализовать процедуру определения правильности e-mail-адреса методом поиска в нем? Вы спросите, к чему были это предупреждение и «безумный» пример? А помните, в начале статьи речь шла о продуктах прекрасной эпохи алфавитно-цифровых терминалов – гуру, способных «в голове» составлять сложные регулярные выражения? Кроме собственно гуру, алгоритмики и великолепных реализаций библиотек регулярных выражений та эпоха оставила еще и некоторое «ковбойское» презрение к якобы излишним инструментальным средствам. Ну а теперь попробуйте не согласиться со следующими утверждениями: с одной стороны, регулярное выражение, позволяющее распознать формально правильный e-mail-адрес, весьма полезно, с другой, – оно настолько сложное (в первую очередь, из-за масштаба), что без привлечения инструментов создать что-либо подобное, да еще и определяющее правильный язык, невозможно.

Итак, мы добрались до начал собственно языка регулярных выражений (в англоязычной литературе часто встречается сокращенный термин regexp). Прежде всего отметим, что базовый язык regexp, несмотря на существование множества вариаций, стандартен и специфицирован в секции 2.8 документа IEEE POSIX 1003.2. Для его описания используются те же специфические термины, к которым прибегают при ознакомлении с любыми компьютерными языками.

Литеральные константы, или просто литералы (literal) языка regexp – это фактически элементы регулярных множеств, заданных в явном виде, перечислениями. Возвращаясь к использованному ранее в примерах алфавиту (множеству, заданному перечислением элементов) б,в,е,з,н,о,с,т,ь,я, мы можем сказать, что символы «б», «е» и, например, «я» – литералы. Более того, – любая заданная в явном виде строка символов, составленная из таких «литералов начального уровня», также будет литералом. К примеру, то же слово «светобоязнь» – это литерал. Главная особенность литералов состоит в том, что они не имеют никакого специального значения, они только то, что они есть – строки символов.

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

Специальные последовательности символов, или искейп-последовательности, применяются тогда, когда надо лишить метасимвол его специального значения и превратить в литерал. Поскольку множество односимвольных литералов более чем ограниченное, то метасимволы, естественно, его еще больше сокращают. Но это непозволительная роскошь – если нет возможности использовать символ «.» как литерал, невозможно и описать язык адресов e-mail. Кроме того, искейп-последовательности применяются для описания непечатаемых символов – таких как перевод строки.

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

The Regulator

Реализаций различных сопроводительных инструментов для regexp-разработчиков немало (и одну мы некогда уже упоминали). Среди них есть распространяющиеся на основании практически всех известных принципов – и коммерческие, и условно-бесплатные, и freeware, и, наконец, Оpen Source. Но все-таки из всего обширного перечня стоит выделить интегрированную среду Regulator, разработанную израильским программистом и блогером Роем Оширови (Roy Osherove). Хотя бы потому, что Regulator – разработка очень профессиональная, продуманная, мощная и GPL-лицензированная. Единственное «но», напрашивающееся само собой, – после того как вы загрузите в свой компьютер двухмегабайтовый дистрибутив Regulator, установите программу, вдоволь «наиграетесь» с ней – так, чтобы оценить ее возможности и качество реализации этих возможностей, – не забудьте о том, что говорилось в начале статьи. А именно, попробуйте сами подумать, насколько эффективно может быть использована такая высококлассная Оpen Source-разработка в качестве оружия против ведущих бизнес в той же нише традиционных производителей коммерческого ПО, особенно мелких (так и хочется добавить: особенно против тех мелких, в которых именно вы получаете зарплату). Автор просит вас об этом ни в коей мере не для того, чтобы подвести к мысли о необходимости запрета Оpen Source ПО (и хоть аналогии опасны и мы стараемся их избегать, в данном случае одна все-таки уместна – кухонными ножами совершается множество злодейств, но разве это повод запрещать кухонные ножи?). Просто целесообразно понимать, что Оpen Source ПО, – в первую очередь, высококлассное, пока еще беспрецедентное явление, но надо верить, что со временем «болячки» интеграции его массового производства в существующую систему рыночных отношений будут успешно излечены.

Итак, вы загрузили Regulator и не забыли, что это .NET-программа, требующая как минимум среды исполнения платформы .NET. Основные интерфейсные области Regulator – доступа к ресурсам сайта RegExpLib панель редактора регулярных выражений, расположенные под нею панель текста, в котором ищутся совпадения со словами языка, описанными регулярным выражением, и панель отображения найденных совпадений, и, наконец, правая панель персональной коллекции фрагментов (snippets) кода на языке regexp. В принципе, для начала освоения программы достаточно только центральных панелей, поэтому интерфейсы доступа к сетевой базе данных и персональной коллекции можно закрыть (при первой необходимости вы их вернете комбинациями клавиш Ctrl-Shift-F и Ctrl-Shift-S соответственно).

Рис. 2

Практическое знакомство с языком regexp мы начнем с решения простых традиционных задач. Создайте текстовый файл LST.txt со списком файлов в установочном каталоге Regulator (по умолчанию инсталляционный путь – C:Program FilesThe RegulatorThe Regulator 2.0, требуемая операция выполняется командой dir /w > LST.txt) и откройте его в правой нижней панели программы. Попробуем создать первое регулярное выражение, определяющее язык, возможных имен файлов, составленных только из латинских букв, т. е., позволяющее находить в образцовом тексте фрагменты, являющиеся именами файлов с учетом указанного ограничения. Мы знаем, что ввиду специфики файловой системы ОС Windows расширения имен файлов состоят из трех печатных символов и отделяются от собственно имени символом «.». Мы также требуем, чтобы имя содержало только латинские буквы верхнего или нижнего регистра. Начнем именно с этого требования. Очевидно, что перечислять все двадцать восемь латинских букв, да еще и дважды (для двух регистров), в регулярном выражении неудобно. Для того чтобы этого не делать, в языке regexp предусмотрена конструкция «класс символов». Ее основу образуют два метасимвола «[» и «]». Итак, начнем запись нового регулярного выражения в верхней панели Regulator'а именно с метасимвола «[». Система автоматического анализа программы сразу выдаст вам меню сокращенного ввода (фактически – выбора) возможных конструкций языка regexp (рис. 2). Так как мы определяем именно группу символов, а не ее инверсию, выбираем Group, и Regulator формирует «заготовку», указывая требования к содержанию поля ввода и автоматически закрывая конструкцию символом «]» (это не излишество, а крайне важная деталь, позволяющая избежать весьма неприятных ошибок при разработке сложных выражений). Теперь детально опишем группу – она состоит из всех символов от «A» до «Z» и от «a» до «z». На языке regexp это принято записывать так: A-Za-z. Эта форма пополняет уже известное нам множество метасимволов языка еще одним – «-». Итак, наше регулярное выражение выглядит следующим образом: [A-Za-z]. Оно описывает язык, слова которого имеют длину 1 и являются всеми символами латинского алфавита двух регистров (для такого простого языка даже нетрудно подсчитать количество слов – 56). Это, естественно, далеко от того, что нам необходимо. Нам ведь нужны слова не только единичной длины, но образованные именно на основе этого алфавита (а мы уже знаем, что выражение [A-Za-z] определяет именно алфавит). Вспомним, что говорилось о регулярных множествах, – для получения такого результата требуется выполнить конкатенацию, обозначаемую в понятийном аппарате теории регулярных множеств как A+, где A – обозначение алфавита. Именно такой синтаксис применяется и в языке регулярных выражений – [A-Za-z]+ обозначает все возможные слова всех возможных длин, которые можно создать из 56 букв (и теперь даже не пытайтесь их пересчитать). После того как вы введете за закрывающей скобкой символ «+», Regulator вам подскажет два возможных варианта его использования. Нас интересует самый простой – «один или более» («One or more»). Итак, мы уже создали язык, слова которого – все возможные имена файлов, составленные только из букв. Однако мы знаем, что в имени файла обязательно должен присутствовать символ «.», отделяющий собственно имя от расширения. Если вы попробуете просто ввести этот символ в Regulator сразу за «+», программа немедленно отреагирует диалоговым окном подсказки. Теперь уже можно понять – Regulator выдает окна-подсказки при вводе определенных символов, имеющих специальное значение. Иначе говоря, – метасимволов. И вы уже знаете, что раз нам необходимо трансформировать метасимвол в литерал (нам же нужен именно литерал «.»), надо использовать искейп-последовательность. Особенность ее синтаксиса такова, что все возможные искейп-последовательности всегда начинаются с метасимвола «». Введите его – и Regulator предложит вам различные варианты, из которых требуется выбрать последовательность « ASCII код символа». Так как ASCII-код символа «.» – 2E (в шестнадцатеричной системе счисления), ваше первое уточненное регулярное выражение будет выглядеть так: [A-Za-z]+x2E. Осталось совсем немногое – мы знаем, что расширение в имени файла состоит из трех символов. Так как мы говорим об именах, содержащих только буквы, алфавит для расширения будет тем же, что и для имени – [A-Za-z]. Но в этом случае нам нужно не бесконечное множество всех слов, а пусть очень большое, но конечное множество трехбуквенных слов. Иначе говоря, нам необходимо регулярное множество A3 (если A – алфавит). Для обозначения такой N-арной операции конкатенации в языке регулярных выражений существует своя конструкция – AN, т. е. множество всех трехбуквенных слов будет выглядеть так: [A-Za-z]3. Естественно, Regulator вам подскажет и все возможные варианты конструкции (из которых вам следует выбрать «exactly N», «в точности N»), и неявно пополнит список известных вам метасимволов языка regexp.

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

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