Знакомство с регулярными выражениями
Представьте ситуацию: вашему начальнику из отдела документации понадобилось средство для поиска повторяющихся слов в тексте (например, «this this»). Эта проблема довольно часто возникает в документах, подвергающихся постоянному редактированию. Ваше решение должно:
l Обеспечивать проверку произвольного количества файлов; сообщать о каждой строке каждого файла, содержащей повторяющиеся слова; выделять (при помощи стандартных Escape-последовательностей ANSI) каждое повторяющееся слово и выводить имя исходного файла в каждой строке отчета.
l Учитывать возможные разрывы строк и даже обнаруживать ситуации, когда слово, находящееся в конце одной строки, повторяется в начале следующей.
l Находить повторяющиеся слова, несмотря на различия в регистре символов (например, The the…) и в количестве пропусков (пробелов, табуляций, переводов строки и т. п.) между словами.
l Находить повторяющиеся слова, разделенные тегами HTML (и, разумеется, любым количеством пропусков). Теги HTML применяются при разметке текста в страницах World Wide Web — например, для выделения слов жирным шрифтом: «it is <B>very</B> very important…».
Ничего себе! Однако для реальных задач нужны реальные решения, а описанная задача вполне реальна. Я воспользовался подобным инструментом при подготовке текста этой книги и был просто поражен количеством обнаруженных повторений. Существует немало языков программирования, позволяющих решить эту задачу, но поддержка регулярных выражений в любом языке существенно упростит вашу работу.
Регулярные выражения — мощное, гибкое и эффективное средство обработки текстов. Универсальные шаблоны регулярных выражений сами по себе напоминают миниатюрный язык программирования, предназначенный для описания и анализа текста. При дополнительной поддержке со стороны конкретной утилиты или языка программирования регулярные выражения способны вставлять, удалять, выделять и выполнять самые невероятные операции с текстовыми данными любого вида. Они бывают очень простыми, вроде команды поиска в текстовом редакторе, или очень сложными, как специализированные языки обработки текстов. Из этой книги вы узнаете, как повысить эффективность своей работы при помощи регулярных выражений. Вы научитесь мыслить регулярными выражениями, и это позволит вам в полной мере использовать их выдающиеся возможности.
Как вы убедитесь в следующей главе, программа поиска повторяющихся слов занимает всего несколько строк на Perl или Python — сценарных языках с поддержкой регулярных выражений. Всего одна команда поиска/замены находит и выделяет повторяющиеся слова во всем документе. Другая команда удаляет все строки, не содержащие повторяющихся слов (и оставляет только те строки, которые включаются в отчет). Наконец, третья команда выводит в начале каждой строки имя файла, к которому относится эта строка.
Язык (Perl, Python и т. д.) обеспечивает периферийную поддержку, но подлинная сила исходит от регулярных выражений. Укротив эту силу для своих целей, вы научитесь писать регулярные выражения, которые отыскивают нужный текст и обходят то, что вас не интересует. После этого остается объединить готовые выражения с вспомогательными конструкциями языка, чтобы выполнить с текстом нужную операцию (добавить коды выделения, удалить текст, изменить его и т. д.)
Регулярные выражения откроют перед вами возможности, о которых вы, возможно, даже не подозревали. Ежедневно я неоднократно использую их для решения всевозможных задач — и простых, и сложных (и если бы не регулярные выражения, многие простые задачи оказались бы довольно сложными). Конечно, эффектные примеры, открывающие путь к решению серьезных проблем, наглядно демонстрируют достоинства регулярных выражений. Менее очевиден тот факт, что регулярные выражения используются в повседневной работе для решения «неинтересных» задач — «неинтересных» в том смысле, что программисты вряд ли станут обсуждать их с коллегами в курилке, но без решения которых вы не сможете нормально работать. Лично мне возможность избавиться от часа-другого нудной и утомительной работы кажется весьма привлекательной.
Приведу простой пример<$M[R1-4]>. Однажды мне потребовалось проверить множество файлов (точнее, 70 с лишним файлов с текстом этой книги) и убедиться в том, что в каждом файле строка SetSize встречается ровно столько же раз, как и строка ResetSize. Задача усложнялась тем, что регистр символов при подсчете не учитывался (то есть строки setSIZE и SetSize считаются эквивалентными). От одной мысли о ручном просмотре 32 000 строк текста я нервно вздрагиваю. Даже использование стандартных команд поиска в редакторе потребует воистину титанических усилий, учитывая количество файлов и возможные различия в регистре символов.
На помощь приходят регулярные выражения! Я ввожу всего одну короткую команду, которая проверяет все файлы и выдает всю необходимую информацию. Общие затраты времени — секунд 15 на ввод команды и еще 2 секунды на проверку данных. Потрясающе! (Если вам интересно, как выглядит эта команда, загляните на с. <$R[P#,2-7]>).
Другой пример: однажды я помогал своему другу Джеку решить проблемы с электронной почтой на удаленном компьютере, и он захотел, чтобы я отправил ему список всех сообщений в файле почтового ящика. В принципе можно было загрузить копию всего файла в текстовый редактор и вручную удалить в каждом сообщении все строки, кроме заголовка. Но даже если бы файл не был таким большим и если бы я не использовал медленное подключение по телефонной линии, эта работа была бы долгой и монотонной. Наконец, читать чужую почту попросту неэтично.
И снова меня выручили регулярные выражения! Я ввел простую команду (используя стандартную утилиту поиска egrep, описанную ниже в этой главе) для вывода строк From: и Subject: каждого сообщения. Чтобы точно указать egrep, какие строки должны (или не должны) присутствовать в выходных данных, я воспользовался регулярным выражением [^(From|Subject):spc]. Получив список, Джек попросил меня отправить одно конкретное сообщение — состоящее из 5 000 строк! И снова на извлечение одного сообщения в текстовом редакторе потребовалось бы слишком много времени. Вместо этого я воспользовался другой утилитой (sed) и при помощи регулярных выражений точно описал, какая часть текста в файле меня интересует. Это позволило легко и быстро извлечь и отправить нужное сообщение.
Применение регулярных выражений сэкономило нам обоим много времени и сил. Пусть оно не было особенно «интересным» — в любом случае это интереснее, чем часами просиживать за текстовым редактором. Если бы я не знал о существовании регулярных выражений, мне бы и в голову не пришло, что существует другой выход. Эта характерная история показывает, что при помощи регулярных выражений и тех утилит, в которых они поддерживаются, можно делать совершенно неожиданные вещи. Научившись пользоваться регулярными выражениями, вы будете удивляться, как же вы раньше обходились без них.
Умение работать с регулярными выражениями — воистину бесценный навык. Информация, приведенная в этой книге, поможет вам овладеть этим навыком. Надеюсь, мне также удастся убедить вас в том, что потраченные усилия не пропадут зря.
Тем, кому еще не приходилось работать с регулярными выражениями, строка [^(From|Subject):spc] из предыдущего примера покажется непонятной. На самом деле никакого волшебства здесь нет — как нет его и в выступлениях циркового фокусника. Просто фокусник знает что-то простое, что не кажется простым или естественным его неискушенным зрителям. Стоит научиться держать карту так, чтобы рука казалась пустой, и немного потренироваться — и вы тоже сможете «показывать фокусы». Регулярные выражения также можно сравнить с иностранным языком — когда вы начинаете изучать язык, он перестает казаться белибердой.
Поскольку вы взялись за эту книгу, вероятно, вы хотя бы отчасти представляете себе, что такое «регулярное выражение». Но даже если и не представляете, общий принцип их работы вам наверняка знаком.
Как известно, каждому файлу присваивается конкретное имя (например, report.txt). Однако любому пользователю Unix или DOS/Windows известно, что для выборки нескольких файлов можно воспользоваться шаблоном вида «*.txt». В подобных шаблонах (называемых файловыми глобами) используются символы[1], имеющие особый смысл. Звездочка (*) означает «любая последовательность символов», а вопросительный знак (?) — «один произвольный символ». Итак, шаблон «*.txt» начинается с [*] и заканчивается строковым литералом [.txt]. Полученный в результате шаблон означает «Выбрать все файлы, имена которых начинаются с любой последовательности символов и заканчиваются символами .txt».
Во многих системах существуют дополнительные специальные символы, но в общем случае выразительные возможности файловых шаблонов ограничены. Впрочем, это вряд ли можно считать недостатком, поскольку файловые шаблоны применяются в относительно узкой сфере — только при работе с именами файлов.
С другой стороны, при работе с текстом вообще возникает гораздо больше проблем. Проза и поэзия, листинги программ, отчеты, тексты песен, HTML, статьи, таблицы, книги (вроде этой), списки слов… при желании продолжайте сами. Конечно, для узкоспециализированной задачи (например, «выбор файлов») можно разработать специализированную схему или инструмент. Но за долгие годы был выработан обобщенный язык текстовых шаблонов, обладающий достаточной мощью и выразительностью для применения в разных областях. Каждая программа по-своему реализует и использует эти шаблоны, но обычно этот мощный язык и сами шаблоны называются «регулярными выражениями».
Регулярное выражение состоит из двух типов символов. Специальные символы (вроде * в файловых шаблонах) называются метасимволами. Все остальные символы, то есть обычный текст, называются литералами. Регулярные выражения отличаются от файловых шаблонов в первую очередь по возможностям своих метасимволов. В файловых шаблонах используется малое количество метасимволов, предназначенных для ограниченных целей, но «язык» регулярных выражений содержит богатый и впечатляющий набор метасимволов для опытных пользователей.
Регулярные выражения можно рассматривать как самостоятельный язык, в котором литералы выполняют функции слов, а метасимволы — функции грамматических элементов. Слова по определенным правилам объединяются с грамматическими элементами и создают конструкции, выражающие некоторую мысль. Скажем, в примере с электронной почтой я воспользовался регулярным выражением [^(From|Subject):spc] для поиска строк, начинающихся с «From:spc» или «Subject:spc». Метасимволы в этом выражении подчеркнуты, а их смысл будет рассмотрен ниже.
На первый взгляд регулярные выражения (как и любой другой незнакомый язык) производят устрашающее впечатление. Они выглядят как магические заклинания, понятные лишь для немногих избранных и абсолютно недоступные для простых смертных. Но подобно тому, как строка ###5-1###[2]<$M[R1-2]> вскоре становится понятной для изучающего японский язык, регулярное выражение в команде
s!<emphasis>([0-9]+(\.[0-9])+){3})</emphasis>!<inet>$1</inet>!
вскоре станет абсолютно понятной и для вас.
Приведенный пример взят из сценария Perl, использованного моим редактором при правке авторского варианта рукописи. Автор ошибочно использовал теги <emphasis> для пометки IP-адресов (которые выглядят как набор чисел, разделенных точками — например, 198.112.208.25). В этой команде Perl, предназначенной для поиска/замены текста, регулярное выражение<$M[R1-5]>
[<emphasis>([0-9]+(\.[0-9])+){3})</emphasis>]
заменяет их тегами <inet>, оставляя прочие теги <emphasis> без изменения. В следующих главах вы узнаете, как конструируются подобные выражения, и сможете использовать их в своих целях.
Вряд ли лично вам когда-нибудь придется заменять теги <emphasis> тегами <inet>, но похожие задачи типа «найти то-то и заменить тем-то» возникают довольно часто. Эта книга написана не для того, чтобы снабдить вас готовыми решениями конкретных проблем. Она научит вас мыслить категориями регулярных выражений, чтобы вы могли успешно справиться с любой задачей такого типа.
Как вы вскоре узнаете, большие регулярные выражения строятся из маленьких «кирпичей». Сами по себе эти «кирпичи» просты, но в сочетании друг с другом они образуют бесконечное множество комбинаций. Чтобы научиться правильно объединять их для достижения желаемой цели, вам потребуется некоторый опыт.
Поймите меня правильно — изучить регулярные выражения и научиться пользоваться ими не уж сложно. Более того, к концу этой главы вы освоите некоторые возможности регулярных выражений, даже если вы столкнулись с ними впервые.
Но здесь, как и в любом деле, ничто не заменит практического опыта. Опыт формирует особый склад ума и упорядочивает направление мыслей. Это трудно описать словами, но легко продемонстрировать на примерах, поэтому в этой главе я хочу в общих чертах представить вам некоторые концепции регулярных выражений. Не углубляясь в подробности, этот обзор закладывает основу для всего материала книги и готовит почву для важных вопросов, которые лучше обсудить до того, как мы займемся самими регулярными выражениями.
Хотя некоторые примеры выглядят глупыми (потому что они действительно глупые), они хорошо соответствуют тем задачам, которые вам предстоит решать — пусть вы даже этого еще не понимаете. Если что-то из сказанного покажется непонятным, не огорчайтесь. Постарайтесь уловить общий смысл. Именно с этой целью написана данная глава.
Читатели, знакомые с регулярными выражениями, вряд ли узнают из этого обзора что-нибудь принципиально новое — но, пожалуйста, хотя бы просмотрите его. Даже если вы знаете смысл некоторых метасимволов, может быть, какие-то особенности или аспекты применения регулярных выражений окажутся новыми для вас.
Подобно различиям между хорошим исполнением музыкального произведения и сотворением музыки, существуют различия между пониманием регулярных выражений и их настоящим пониманием. Возможно, информация, представленная в некоторых уроках, окажется знакомой, но будет представлена под новым углом зрения, и это окажется первым шагом на пути к настоящему пониманию.
Одним из простейших применений регулярных выражений является поиск текста — во многих текстовых редакторах существует возможность поиска по шаблонам регулярных выражений. Еще более простым примером является утилита egrep[3]. При запуске программе egrep передается регулярное выражение и список просматриваемых файлов. Она сопоставляет регулярное выражение с каждой строкой файла и выводит только те строки, в которых было найдено совпадение.
Вернемся к примеру с электронной почтой. Использованная мной команда показана на рис. 1.1. egrep интерпретирует первый аргумент командной строки как регулярное выражение, а остальные аргументы — как имена просматриваемых файлов. Обратите внимание: апострофы, присутствующие на рис. 1.1, не входят в регулярное выражение, но их присутствия требует мой командный интерпретатор[4]. При использовании egrep я почти всегда заключаю регулярные выражения в апострофы.
Рис. 1.1. Запуск egrep из командной строки
Если в вашем регулярном выражении не используется ни один из десятка с лишним метасимволов, поддерживаемых egrep, оно фактически превращается в средство «простого поиска текста». Например, при поиске выражения [cat] будут найдены и выведены все строки файла, содержащие три стоящих подряд буквы cdotadott. Среди них будут выведены строки, в которых встречается слово vacation.
Даже если в строке нет отдельного слова cat, последовательность cdotadott в слове vacation все равно считается успешно найденной. Необходимо только наличие указанных символов, и поскольку символы присутствуют — egrep выводит всю строку. Ключевым моментом здесь является то, что поиск осуществляется не на уровне «слов» — egrep различает байты и строки файла, но обычно не имеет ни малейшего представления о языках, предложениях, абзацах или других концепциях высокого уровня[5].
Начнем с рассмотрения некоторых метасимволов, используемых egrep при работе с регулярными выражениями. Существует несколько типов метасимволов, выполняющих разные функции. Мы в общих чертах познакомимся с ними в нескольких примерах, а подробные описания и многочисленные примеры будут приведены в последующих главах.
Прежде чем читать дальше, пожалуйста, просмотрите список условных обозначений в предисловии (с. <$R[P#,R0-1]>). В книге используются некоторые нестандартные обозначения, и смысл каких-либо из них может оказаться неочевидным.
Вероятно, простейшими метасимволами являются [^] (крышка, циркумфлекс) и [$] (доллар), представляющие соответственно начало и конец проверяемой строки. Как говорилось выше, регулярное выражение [cat] находит последовательность символов cdotadott в любом месте строки, но для выражения [^cat] совпадение происходит лишь в том случае, если символы cdotadott находятся в начале строки — [^] фактически привязывает совпадение (остальной части регулярного выражения) к началу строки. Аналогично, выражение [cat$] находит символы cdotadott только в том случае, если они находятся в конце строки — например, если строка завершается словом scat.
Развивайте в себе привычку буквально интерпретировать регулярные выражения. Например, не думайте:
«[^cat] совпадает, если строка начинается с cat»
Думать нужно так:
«[^cat] совпадает, если мы находимся в начале строки, после которого сразу же следует символ c, потом немедленно следует символ a, и потом немедленно следует символ c».
Фактически это обозначает одно и то же, но буквальная интерпретация позволит вам лучше понять суть нового выражения, когда оно вам встретится. <$M[R1-7]>Как бы вы прочитали выражение [^cat$] или даже простейшее [^]? refПереверните страницу, чтобы проверить свою интерпретацию.
Специфика символов ^ и $ заключается в том, что они совпадают с определенной позицией строки, а не с символами текста. Конечно, большая часть метасимволов предназначена для поиска именно текста. Помимо символов-литералов, в регулярных выражениях также можно использовать метасимволы, описанные в нескольких следующих разделах.
Допустим, вы хотите найти строку «grey», которая также может быть записана и в виде «gray». При помощи конструкции [[…]], называемой символьным классом (character class), можно перечислить символы, которые могут находиться в данной позиции текста: [gr[ea]y]. Это выражение означает: «Найти символ g, за которым следует r, за которым следует e или a, и все это завершается символом y». В орфографии я не силен и поэтому всегда использую такие регулярные выражения для поиска правильных вариантов написания в списках слов. В частности, я нередко использую выражение [sep[ea]r[ea]te], потому что никак не могу запомнить, как же правильно пишется это слово — «seperate», «separate», «separete» или как-нибудь еще.
Еще один пример — возможная смена регистра в первой букве слова: [[Ss]mith]. Помните: это выражение по-прежнему совпадает со строками, у которых последовательность smith (или Smith) находится внутри другого слова — например, blacksmith. Я не хочу снова и снова напоминать об этом, но у новичков нередко возникают проблемы. Некоторые решения проблемы «встроенных» слов будут рассмотрены ниже, после того, как мы рассмотрим еще несколько метасимволов.
Количество символов в классе может быть любым. Например, класс [[123456]] совпадает с любой из перечисленных цифр. Этот класс может использоваться как часть выражения [<H[123456]>], совпадающего с тегами заголовков HTML <H1>, <H2>, <H3> и т. д.
В контексте символьного класса метасимвол символьного класса - (дефис) обозначает интервал символов; так, выражение [<H[1-6]>] эквивалентно предыдущему примеру. Классы [[0-9]] и [[a-z]] обычно используются соответственно для поиска цифр и символов нижнего регистра. Символьный класс может содержать несколько интервалов, поэтому класс [[0123456789abcdefABCDEF]] записывается в виде [[0-9a-fA-F]]. Такое выражение пригодится при обработке шестнадцатеричных чисел. Интервалы даже можно объединять с литералами: выражение [[0-9A-Z_!.?]] совпадает с цифрой, символом верхнего регистра, символом подчеркивания, восклицательным знаком, точкой или вопросительным знаком.
Обратите внимание: дефис выполняет функции метасимвола только внутри символьного класса — в остальных случаях он совпадает с обычным дефисом. Более того, даже в символьных классах дефис не всегда интерпретируется как метасимвол. Если дефис является первым символом, указанным в классе, он заведомо не может определять интервал и поэтому интерпретируется как литерал.
l Символьные классы можно рассматривать как своеобразный мини-язык. Правила, определяющие состав поддерживаемых метасимволов (и их функции) внутри класса и за его пределами, полностью отличаются.
Вскоре мы рассмотрим и другие примеры.
Интерпретация [^cat$], [^$] и [^]
bref Ответ на вопрос со с. <$R[P#,R1-7]>
[^cat$]
Буквально: совпадает, если у строки есть начало (конечно, оно есть у любой строки), за которым сразу же следуют символы cdotadott, после чего немедленно следует конец строки.
Фактически: строка состоит только из слова cat — никаких дополнительных слов, пробелов, знаков препинания… короче, ничего лишнего.
[^$]
Буквально: совпадает, если у строки есть начало, после которого немедленно следует конец строки.
Фактически: пустая строка (не содержащая никаких символов, даже пробелов).
[^]
Буквально: совпадает, если у строки есть начало.
Фактически: бессмысленно! Начало есть у любой строки, поэтому совпадают все строки — даже пустые!
Если вместо [[…]] используется запись [[^…]], класс совпадает с любыми символами, не входящими в приведенный список. Например, [[^1-6]] совпадает с символом, не принадлежащим интервалу от 1 до 6. Префикс ^ в каком-то смысле «инвертирует» список — вместо того, чтобы перечислять символы, принадлежащие классу, вы перечисляете символы, не входящие в него.
Возможно, вы заметили, что для инвертирования классов используется тот же символ ^, который отмечает начало строки. Символ действительно тот же, но смысл у него совсем другой. Например, слово «крыша» в зависимости от контекста может иметь совершенно разный смысл; то же самое можно сказать и о метасимволах. Мы уже встречались с одним примером множественной интерпретации — дефисом. Дефис интерпретируется как определитель интервалов только в символьном классе (и то если он не находится в первой позиции). За пределами символьного класса дефис выполняет привязку к началу строки, внутри класса он является метасимволом класса — но лишь в том случае, если не следует сразу же после открывающей скобки (в противном случае он интерпретируется как обычный символ).
Как известно, в английском языке за буквой q практически всегда следует u. Давайте поищем экзотические слова, в которых за буквой q следует какой-нибудь другой символ — в переводе на язык регулярных выражений это выглядит как [q[^u]]. Я применил это выражение к своему списку слов. Как и следовало ожидать, таких слов оказалось немного! Более того, о существовании некоторых из найденных слов я вообще не подозревал.
Вот как это выглядело:
% egrep 'q[^u]' word.list
Iraqi
Iraqian
miqra
qasida
qintar
qoph
zaqqum
%
В списке нет слов Qantas (австралийская авиакомпания) и Iraq. Хотя оба слова присутствуют в моем списке слов, ни одно из них не попало в результаты поиска. Почему<$M[R1-8]>? refПодумайте, а затем переверните страницу и проверьте свои предположения.
Помните: инвертированный символьный класс означает «совпадение с символами, не входящими в список», а не «несовпадение с символами, входящими в список». На первый взгляд кажется, что это одно и то же, однако пример со словом Iraq демонстрирует отличия между этими двумя трактовками. Инвертированный класс удобно рассматривать как сокращенную форму записи для обычного класса, включающего все возможные символы, кроме перечисленных.
Метасимвол [.] (точка) представляет собой сокращенную форму записи для символьного класса, содержащего все символы. Применяется в тех случаях, когда в некоторых позициях регулярного выражения могут находиться произвольные символы. Допустим, вы хотите найти дату, которая может быть записываться в формате 07/04/76, 07-04-76 и даже 07.04.76. Конечно, можно сконструировать регулярное выражение, в котором между числами указываются все допустимые символы-разделители («/», «-» и «.») — например, [07[-./]04[-./]76]. Возможен и другой вариант — просто ввести выражение [07.04.76].
В этом примере имеется ряд неочевидных аспектов. В выражении [07[-./]04[-./]76] точки не являются метасимволами, поскольку они находятся внутри символьного класса (не забывайте: состав и интерпретация метасимволов внутри класса и за его пределами различны). Дефисы в данном случае тоже интерпретируются как литералы, хотя в границах символьного класса они обычно являются метасимволами. Как упоминалось выше, дефис не интерпретируется как метасимвол, если он находится на первой позиции класса.
В выражении [07.04.76] точки являются метасимволами, совпадающими с любым символом, в том числе и с ожидаемыми нами «/», «-» и «.». Тем не менее, необходимо учитывать, что каждая точка может совпадать с абсолютно любым символом, поэтому совпадение обнаруживается, например, в строке «lottery numbers: 19 207304 7639».
Выражение [07[-./]04[-./]76] обеспечивает более точное совпадение, однако его труднее читать и записывать. Выражение [07.04.76] легко понять, но оно дает неоднозначный результат. Какой вариант использовать? Все зависит от того, что вам известно об искомых данных и насколько точным должен быть поиск. При построении регулярных выражений часто приходится идти на компромисс с точностью за счет знания текста. Например, если вы уверены, что в вашем тексте выражение [07.04.76] наверняка не вызовет нежелательных совпадений, будет вполне логично воспользоваться именно этим вариантом. Знание целевого текста — важный фактор, обеспечивающий эффективное использование регулярных выражений.
Почему [q[^u]] не совпадает со словами «Qantas» или «Iraq»?
bref Ответ на вопрос со с. <$R[P#,R1-8]>
Qantas не совпадает, поскольку в регулярном выражении указан символ q в нижнем регистре, а в слове «Qantas» он относится к верхнему регистру. Если использовать выражение [Q[^u]], было бы найдено это слово, но зато пропущены все остальные. Выражение [[Qq][^u]] обнаружило бы все слова.
В примере со словом Iraq кроется подвох. В регулярном выражении указан символ q, за которым следует символ, отличный от u. Но поскольку перед проверкой регулярного выражения egrep отделяет от него символ(ы) перевода строки (ах простите, я совсем забыл упомянуть об этом!), после q нет вообще никаких данных. Да, символа u там нет — но какого-нибудь другого символа нет тоже!
Не огорчайтесь, если вопрос оказался сложным. Уверяю вас: если бы программа egrep не удаляла символы перевода строк (как это делают некоторые другие программы) или если бы за словом Iraq следовали пробелы, другие слова или еще что-нибудь, строка была бы успешно обнаружена. Необходимо хорошо разбираться в тонкостях работы каждой программы, но пока из этого примера необходимо вынести одно: символьному классу, даже инвертированному, в тексте обязательно должен соответствовать какой-нибудь символ.
Очень удобный метасимвол [|] означает «или». Он позволяет объединить несколько регулярных выражений в одно, совпадающее с любым из выражений-компонентов. Например, [Bob] и [Robert] — два разных выражения, а [Bob|Robert] — одно выражение, совпадающее с любой из этих строк. Подвыражения, объединенные этим способом, называются альтернативами (alternatives).
Вернемся к примеру [gr[ea]y]. Обратите внимание: выражение также можно записать в виде [grey|gray] и даже [gr(a|e)y]. В последнем варианте круглые скобки отделяют конструкцию выбора от остального выражения (и, кстати говоря, тоже являются метасимволами). Без скобок [gra|ey] будет означать «[gra] или [ey]» — совсем не то, что нам нужно. Конструкция выбора действует только внутри круглых скобок.
Рассмотрим другой пример: [(First|1st)spc[Ss]treet]. Вообще говоря, поскольку [First] и [1st] заканчиваются на [st], выражение можно сократить до [(Fir|1)stspc[Ss]treet], но читать его будет сложнее. Обязательно проанализируйте оба выражения и убедитесь в их эквивалентности.
Впрочем, сравнение [gr[ea]y] c [gr(a|e)y] слегка отвлекло нас от основной темы. Будьте внимательны и не путайте концепции выбора и символьного класса. Символьный класс представляет один символ целевого текста. В конструкциях выбора каждая альтернатива может являться полноценным регулярным выражением. Символьные классы почти что обладают собственным мини-языком (и в частности, собственными представлениями о метасимволах), тогда как конструкция выбора является частью «основного» языка регулярных выражений. Обе конструкции в высшей степени полезны.
Кроме того, будьте внимательны при использовании знаков ^ и $ в выражениях с конструкциями выбора. Сравните два выражения: [^From|Subject|Date:spc] и [^(From|Subject|Date):spc]. Они напоминают рассмотренный выше пример с электронной почтой, но имеют разный смысл (а значит, и разную степень полезности). Первое выражение состоит из трех простых альтернатив; оно означает «[^From] или [Subject] или [Date:spc]» и потому особой пользы не приносит. Нам нужно, чтобы префикс ^ и суффикс [:spc] относились к каждой из альтернатив. Для этого конструкция выбора «ограничивается» круглыми скобками:
[^(From|Subject|Date):spc]
Это выражение совпадает в следующих трех случаях:
1. Начало строки, символы Fdotrdotodotm, а затем «:spc»
2. Начало строки, символы Sdotudotbdotjdotedotcdott, а затем «:spc»
3. Начало строки, символы Ddotadottdote, а затем «:spc»
Как видите, выбор происходит внутри круглых скобок, вследствие чего «внешняя оболочка» [^…:spc] применяется к каждой альтернативе. Поэтому выражение со скобками означает «[^From:spc] или [^Subject:spc] или [^Date:spc]».
Проще говоря, совпадение происходит в каждой строке, которая начинается либо с [^From:spc], либо с [^Subject:spc], либо с [^Date:spc] — именно то, что нам нужно для получения списка сообщений из файла электронной почты.
Пример:
%egrep '^(From|Subject|Date): ' mailbox
From: elvis@tabloid.org (The King)
Subject: be seein' ya around
Date: Thu, 31 Oct 96 11:04:13
From: The Prez <president@whitehouse.gov>
Date: Tue, 5 Nov 1996 8:36:24
Subject: now, about your vote...
.
.
.
Одна из распространенных проблем заключается в том, что искомое слово встречается внутри других слов. Я уже упоминал об этом в примерах с cat, gray и smith. Хотя я также говорил о том, что egrep обычно не воспринимает концепции слов, в некоторых версиях egrep реализована их ограниченная поддержка — а именно, возможность привязки к границе слова (началу или концу).
Вы можете использовать странноватые метапоследовательности [\<] и [\<], если они поддерживаются вашей версией egrep. Они представляют собой эквиваленты [^] и [$] на уровне слов и обозначают соответственно начало и конец слова. Как и якоря ^ и $, эти метапоследовательности не соответствуют конкретным символам текста. Регулярное выражение [\<cat\>] буквально означает «начало слова, за которым немедленно следуют символы cdotadott, а затем идет конец слова». Проще говоря, это означает «найти отдельное слово cat». При желании можно воспользоваться выражениями [\<cat] или [cat\>] для поиска слов, начинающихся и заканчивающихся символами cat.
Обратите внимание: сами по себе [<] и [>] метасимволами не являются — только в сочетании с обратной косой чертой они приобретают особый смысл. Именно поэтому я и назвал их «метапоследовательностями». Причем здесь важна их особая интерпретация, а не количество символов, поэтому в большей части книги я буду считать эти два «мета»-термина синонимами.
Помните о том, что не все версии egrep поддерживают метасимволы границ слов, но даже в случае поддержки они не начинают волшебным образом понимать английский язык. «Началом слова» просто называется та позиция, с которой начинается последовательность алфавитно-цифровых символов; «концом слова» называется позиция, в которой эта последовательность завершается. На рис. 1.2 приведен пример строки с разметкой этих позиций.
Рис. 1.2. Позиции начала и конца слов
Начала слов (как их опознает egrep) отмечены стрелками, направленными вверх; концы слов отмечены стрелками, направленными вниз. Как видите, «начало и конец слова» правильнее было бы называть «началом и концом алфавитно-цифровой последовательности», но это получается слишком длинно.
Таблица 1.1. Сводка упоминавшихся метасимволов
|
Метасимвол |
Название |
Смысл |
|
. […] [^…] |
точка символьный класс инвертированный символьный класс |
Один любой символ Любой из символов в списке Любой из символов, не входящих в список |
|
^ $ \< \> |
циркумфлекс доллар |
Позиция в начале строки Позиция в конце строки Позиция в начале слова[6] Позиция в конце слова[7] |
|
| (…) |
вертикальная черта круглые скобки |
Любое из разделяемых выражений Ограничивает действие [|], а также используется в других случаях. |
В табл. 1.1 перечислены метасимволы, упоминавшиеся до настоящего момента. Также следует запомнить несколько важных фактов:
l В символьных классах существуют особые правила, определяющие, какие символы являются или не являются метасимволами (а также их точную интерпретацию). Например, точка считается метасимволом за пределами класса, но не внутри него. И наоборот — дефис является метасимволом внутри класса, но не за его пределами. А символ ^ имеет один смысл за пределами класса, другой смысл — внутри класса сразу же после открывающей скобки [, и третий — в любой другой позиции класса.
l Не путайте конструкцию выбора с символьным классом. Класс [[abc]] и конструкция выбора [(a|b|c)] фактически означают одно и то же, но этот пример не распространяется на общий случай. Символьный класс совпадает ровно с одним символом, каким бы длинным или коротким не был список допустимых символов. С другой стороны, конструкция выбора может содержать альтернативы произвольной длины, совершенно не связанные друг с другом длиной текста: [\<(1,000,000|million|thousandspcthousand)\>]. В отличие от символьных классов, конструкции выбора не могут инвертироваться.
l Инвертированный символьный класс представляет собой сокращенное обозначение обычного символьного класса, обозначающего все символы, кроме перечисленных. Следовательно, выражение [[^x]] означает не «все что угодно, кроме x», а «любой символ, отличный от x». Различие тонкое, но важное. Например, в первой интерпретации совпадение будет найдено в пустой строке, чего быть не должно.
Даже те метасимволы, которые мы рассмотрели, способны принести несомненную пользу, но настоящие возможности регулярных выражений начинаются с применения квантификаторов.
Допустим, вам понадобилось найти слово color или colour. Эти два слова почти одинаковы, только в одном есть буква u, а в другом ее нет. Регулярное выражение [colou?r] позволяет найти любой из этих вариантов. Метасимвол [?] (вопросительный знак) означает «необязательный символ». Он ставится после символа, который может находиться в данной позиции текста, но наличие которого не требуется для успешного совпадения.
В отличие от других упоминавшихся метасимволов, вопросительный знак относится только к символу, расположенному непосредственно перед ним. Выражение [colou?r] интерпретируется как «[c], затем [o], затем [l], затем [o], затем [u?], затем[r]».
Сопоставление [u?] с текстом всегда оказывается успешным: иногда ему соответствует символ u в тексте, иногда не соответствует. Собственно, главная особенность необязательного элемента ? состоит в том, что совпадение для него находится всегда. Это вовсе не означает, что совпадение будет найдено для любого регулярного выражения, содержащего метасимвол ?. Например, при поиске в строке semicolon будут найдены совпадения для [colo] и [u?] (соответственно colo и ничего). Тем не менее, завершающее [r] не находится, из-за чего [colou?r] в конечном счете и не совпадает в строке semicolon.
Рассмотрим другой пример. Представьте, что вам требуется найти дату — четвертое июля, в которой месяц обозначается July или Jul, а число — fourth, 4th или просто цифра 4. Конечно, можно просто воспользоваться выражением [(July|Jul)spc(fourth|4th|4)], но давайте рассмотрим другие варианты выражения той же идеи.
Во-первых, [(July|Jul)] сокращается до [(July?)]. Вы видите, что это одно и то же? При удалении [|] круглые скобки перестают быть нужными. Вреда от скобок не будет, но без них выражение [July?] становится чуть более понятным. Получается [July?spc(fourth|4th|4)].
Переходим ко второй половине выражение. [4th|4] можно сократить до [4(th)?]. Как видите, [?] может присоединяться и к выражениям в круглых скобках. Выражение внутри скобок может быть сколь угодно сложным, но «снаружи» оно воспринимается как единое целое. Группировка для [?] (и других аналогичных метасимволов, рассматриваемых ниже) является одним из главных применений круглых скобок.
Итак, наше выражение принимает вид [July?spc(fourth|4(th)?)]. Хотя оно содержит довольно много метасимволов и даже вложенные скобки, расшифровать и понять его не так уж трудно. Мы довольно долго обсуждали два простых примера, но при этом затронули многие побочные вопросы, связанные с пониманием регулярных выражений. Проще сразу приобрести хорошие привычки, чем потом избавляться от плохих.
У вопросительного знака имеются родственники — [+] (плюс) и [*] (звездочка). Метасимвол [+] обозначает «один или несколько экземпляров непосредственно предшествующего элемента», а [*] — «любое количество экземпляров элемента (в том числе и нулевое)». Иначе говоря, […*] означает «найти столько экземпляров, сколько это возможно, но при необходимости обойтись и без них». Конструкция […+] имеет похожий смысл (она также пытается найти как можно большее число экземпляров указанного элемента), но при отсутствии хотя бы одного экземпляра сопоставление завершается неудачей. Эти три метасимвола, [?], [+] и [*], называются квантификаторами (поскольку количество экземпляров совпадения может быть переменным).
Как и […?], поиск части […*] в регулярных выражениях всегда оказывается успешным. Вопрос лишь в том, какой текст будет (и будет ли вообще) содержаться в совпадении. Сравните с конструкцией […+], требующей наличия хотя бы одного экземпляра искомого текста.
Простым примером является выражение [spc*], обозначающее произвольное число необязательных пробелов ([spc?] допускает не более одного необязательного пробела, тогда как [spc*] допускает любое их количество). С его помощью можно сделать наш пример <H[1-6]> более гибким. В спецификации HTML[8] говорится, что непосредственно перед закрывающей угловой скобкой > допускаются пробелы — например, <H3spc> или <H4spcspcspc>. Вставляя […+] в ту позицию регулярного выражения, где могут находиться (а могут и отсутствовать) пробелы, мы получаем [<H[1-6]spc*]. Выражение по-прежнему совпадает с <H1>, поскольку наличие пробелов необязательно, но при этом также подходит и для других вариантов.
Сделаем шаг вперед и попробуем организовать поиск конкретного тега HTML, поддерживаемого Web-броузером Netscape Navigator. Тег <HRspcSIZE=14> означает, что на экране рисуется горизонтальная линия толщиной 14 пикселов. Как и в примере <H3>, перед закрывающей угловой скобкой могут стоять необязательные пробелы. Кроме того, пробелы могут находиться и по обе стороны знака =. Наконец, минимум один пробел должен разделять HR и SIZE, хотя их может быть и больше. В последнем случае можно применить выражение [spcspc*], но мы воспользуемся [spc+]. Плюс разрешает дополнительные пробелы, но требует обязательного присутствия хотя бы одного пробела. Вы понимаете, почему это выражение эквивалентно [spcspc*]? Получается [<HRspc+SIZEspc*=spc*14spc*>].
При всей гибкости по отношению к пробелам наше выражение по-прежнему жестко фиксирует размер, указанный в теге. Вместо поиска тегов с конкретным размером (например, 14) мы хотим найти все варианты. Для этого [14] заменяется выражением для поиска обобщенного числа из одной или нескольких цифр. Цифра определяется выражением [[0-9]], а «одной или нескольких» преобразуется в +, поэтому в результате [14] заменяется [[0-9]+]. Как видите, символьный класс является отдельным элементом, применение к которому метасимволов +, ? и т. д. не требует круглых скобок.
Полученное выражение [<HRspc+SIZEspc*=spc*[0-9]+spc*>] выглядит весьма странно, поскольку большинство звездочек и плюсов относится к пробелам, а наш глаз привык особо выделять в строке пробелы. При чтении регулярных выражений вам придется бороться с этой привычкой, поскольку пробел является таким же обычным символом, как, например, j или 4.
Давайте продолжим совершенствование хорошего примера и внесем в него еще одно изменение. В Navigator можно использовать не только теги HR с явно заданным размером, но и стандартную «безразмерную» версию <HR> (как и прежде, перед > могут находиться дополнительные пробелы). Как<$M[R1-9]> модифицировать наше регулярное выражение так, чтобы оно совпадало с любым из этих типов? Главное — понять, что его часть с размером является необязательной (это подсказка).refПереверните страницу, чтобы проверить свой ответ.
Внимательно проанализируйте окончательное выражение (на врезке с ответом), чтобы понять, чем различаются метасимволы ?, * и +, и что они означают на практике. Смысл этих метасимволов перечисляется в табл. 1.2. Обратите внимание: у каждого квантификатора существует минимальное количество экземпляров текста, которые он обязательно должен найти. В некоторых случаях минимальное количество равно нулю.
Таблица 1.2. Сводка квантификаторов
|
Квантификатор |
Необходимый минимум |
Максимальное количество |
Смысл |
|
? |
нет |
1 |
допускается один экземпляр; не требуется ни один («один необязательно») |
|
* |
нет |
не ограничено |
допускается неограниченное количество; не требуется ни один («любое количество необязательно») |
|
+ |
1 |
не ограничено |
требуется один экземпляр; допускается неограниченное количество («хотя бы один и более») |
В некоторых версиях egrep поддерживается метапоследовательность для определения минимального и максимального количества совпадений: […{мин, макс}]. Эта конструкция называется интервальным<$M[R1-1]> квантификатором. Например, выражение […{3,12}] совпадает до 12 раз, если это возможно, но может ограничиться и всего 3 совпадениями. Запись {0,1} эквивалентна метасимволу ?.
Интервальный квантификатор поддерживается еще не всеми версиями egrep. Зато он поддерживается множеством других инструментов, о которых речь пойдет в главе 3 при рассмотрении широкого спектра метасимволов, используемых в наше время.
В тегах HTML могут использоваться символы обоих регистров, поэтому теги <h3> и <HrspcSize=26> вполне допустимы. Модификация выражения [H<[1-6]spc*] сводится к простой замене [H] выражением [[Hh]], но в более длинных словах [HR] и [SIZE] из другого примера возникают затруднения. Конечно, можно использовать громоздкие конструкции [[Hh][Rr]] и [[Ss][Ii][Zz][Ee]], но проще приказать egrep игнорировать регистр символов при сравнении.
Речь идет не о части языка регулярных выражений, а о полезной возможности, предоставляемой многими программными средствами. Чтобы при сравнениях не учитывался регистр символов, в командной строке egrep перед регулярным выражением передается ключ -i:
% egrep -i '<HR( +SIZE *= *[0-9]+)? *>' имя_файла
В следующих главах мы рассмотрим и другие вспомогательные возможности такого рода.
До настоящего момента мы встречались с двумя применениями круглых скобок: ограничение области действия | и группировка символов для применения квантификаторов (например, ? и *). Я бы хотел упомянуть еще одно специализированное применение круглых скобок, которое поддерживается лишь некоторыми версиями egrep (в том числе и популярной GNU-версией), но встречается во многих других программных средствах.
Круглые скобки могут «запоминать» текст, который совпал с находящимся в них подвыражением. Эта возможность будет использована в частичном решении проблемы повторяющихся слов, описанной в начале главы. Если вам известно конкретное повторяющееся слово, его можно включить в регулярное выражение — например, [thespcthe]. Правда, в этом случае также будут найдены строки типа thespctheory, но проблема легко решается, если ваша версия egrep поддерживает метапоследовательности для обозначения границ слов: [\<thespcthe\>]. Вместо одного пробела даже можно использовать [spc+], чтобы выражение стало более гибким.
Тем не менее, проверить все возможные пары слов попросту невозможно. Хотелось бы найти одно «обобщенное» слово, а потом сказать «а теперь поищи то же самое». Если ваша версия egrep поддерживает механизм обратных ссылок (backreferencing), такая возможность существует. Обратные ссылки позволяют искать новый текст, который совпадает с другим текстом, совпавшим с предшествующей частью выражения, причем на момент написания выражения этот текст неизвестен.
Начнем с выражения [\<thespc+the\>] и заменим [the] регулярным выражением для обозначения обобщенного слова — [[A-Za-z]+]. Затем по соображениям, которые станут ясны из следующего абзаца, это выражение заключается в круглые скобки. Наконец, второе «the» заменяется специальным метасимволом [\1]. Получается [\<([A-Za-z]+)spc+\1\>].
В программах с поддержкой обратных ссылок круглые скобки «запоминают» текст, совпавший с находящимся в них подвыражением, а специальный метасимвол [\1] представляет этот текст (каким бы он ни был) в оставшейся части регулярного выражения.
Конечно, в выражение можно включить несколько пар круглых скобок и ссылаться на совпавший текст при помощи символов [\1], [\2], [\3] и т. д. Пары скобок нумеруются в соответствии с порядковым номером открывающей скобки слева направо.
необязательное подвыражение
bref Ответ на вопрос со с. <$R[P#,R1-9]>
В данном случае «необязательный» означает, что часть тега может встречаться один раз, но ее присутствие не требуется. Следовательно, мы можем воспользоваться метасимволом [?]. Поскольку размер необязательного элемента превышает один символ, необходимо использовать круглые скобки: [(…)?] . После вставки этой конструкции наше выражение принимает вид:
[<HR(spc+SIZEspc*=spc*[0-9]+)?spc*>]
Обратите внимание: элемент [spc*] вынесен за круглые скобки. Это сделано для того, чтобы выражение успешно находило теги вида <HRspc>. Если бы этот элемент находился в скобках, то завершающие пробелы допускались бы только при указании в теге атрибута SIZE.
В нашем примере «thespcthe» подвыражение [[A-Za-z]+] совпадает с первым the. Оно находится в первой паре круглых скобок, поэтому на совпавшее «the» можно ссылаться при помощи метасимвола [\1] — если [spc+] совпадает, то на месте [\1] должно находиться слово «the». Если и это условие выполняется, [\>] проверяет, что мы находимся на границе слова (тем самым исключаются случайные совпадения в строках типа thespctheft). Успешное совпадение всего выражения означает, что мы нашли повторяющееся слово. Впрочем, это не всегда является ошибкой (например, в английском языке допускаются два слова «that» подряд), но найденные подозрительные строки можно просмотреть и самостоятельно принять решение.
Решив включить в книгу этот пример, я опробовал его на подготовленном тексте (моя версия egrep поддерживает [\<…\>] и обратные ссылки). Чтобы команда приносила больше пользы и находила повторения вида «Thespcthe», я включил в командную строку ключ -i, упоминавшийся выше:
% egrep -i '\<([a-z]+) +\1\>' файлы…
Как ни стыдно признаваться, я обнаружил четырнадцать пар ошибочно повторяющихся слов!
При всей полезности этого регулярного выражения необходимо хорошо понимать его принципиальные ограничения. Поскольку egrep просматривает каждую строку по отдельности, вы не сможете обнаружить те ситуации, когда слово в конце строки повторяется в начале следующей строки. Для этого нужны более совершенные инструменты, и некоторые примеры будут рассмотрены в следующей главе.
Я еще не упоминал об одном важном обстоятельстве — как включить в регулярное выражение символ, который обычно интерпретируется как метасимвол. Например, при попытке использовать регулярное выражение [ega.att.com] для поиска имени компьютера в Интернете ega.att.com в результат включаются строки типа megawattspccomputing. Как я уже говорил, метасимвол [.] совпадает с любым символом.
Метпоследовательность, совпадающая с литеральной точкой, состоит из обычной точки и экранирующего префикса \ — [ega\.att\.com]. Последовательность [\.] называется «экранированной» (escaped) точкой. Экранирование может выполняться со всеми стандартными метасимволами, кроме метасимволов символьных классов. Экранированный метасимвол теряет свой особый смысл и становится обычным литералом. При желании последовательность «экранирующий префикс+символ» можно интерпретировать как специальную метапоследовательность, совпадающую с указанным литералом.
Другой пример: для поиска слов в круглых скобках (например, «(very)») можно воспользоваться регулярным выражением [\([a-zA-Z]+\)]. Символ \ в последовательностях [\(] и [\)] отменяет особую интерпретацию символов ( ) и превращает их в литералы, предназначенные для поиска круглых скобок в тексте.
Если символ \ находится перед другим символом, не являющимся метасимволом, он может иметь различный смысл в зависимости от версии программы. Например, мы уже видели, что в некоторых версиях egrep [\<], [\>], [\1] и т. д. интерпретируются как метапоследовательности. В этой главе будут приведены и другие примеры.
Надеюсь, все эти примеры и объяснения заложили основу для глубокого понимания регулярных выражений. Но пожалуйста, учтите, что материал был подан весьма поверхностно, и вам предстоит еще многое узнать.
Я упоминал о некоторых возможностях регулярных выражений, поддерживаемых многими версиями egrep. Существуют и другие возможности, которые присутствуют лишь в небольшом числе версий. Они будут рассмотрены в последующих главах.
К сожалению, у языка регулярных выражений, как и у естественных языков, существуют различные диалекты и ответвления. Почти каждая новая программа с поддержкой регулярных выражений изобретает какое-нибудь новое «улучшение». В результате регулярные выражения постоянно развиваются, и в результате за многие годы появились многочисленные диалекты (flavors) регулярных выражений. Примеры будут рассмотрены в следующих главах.
В самом общем смысле регулярное выражение либо совпадает внутри некоторого фрагмента текста (при использовании egrep — в строке), либо не совпадает. При построении регулярного выражения приходится постоянно следить за тем, чтобы регулярное выражение:
1. Совпадало там, где нужно.
2. Не совпадало там, где не нужно.
Кроме того, egrep не следит за тем, где именно в строке произошло совпадение, однако в некоторых случаях этот вопрос может оказаться важным. Предположим, вы работаете с текстом, в котором встречается строка:
…zip is 44272. If you write, send $4.95 to cover postage and…
Если вы просто ищете строку по шаблону [[0-9]+], вас не интересует, в каком из чисел произошло совпадение. Но если вы собираетесь что-то сделать с найденным числом (сохранить в файле, увеличить, заменить и т. д. — примеры подобных операций приводятся в следующей главе), вопрос о том, какое именно число было найдено, становится очень существенным.
При работе с регулярными выражениями, как и с любым языком, чрезвычайно полезен практический опыт, поэтому я привожу еще несколько распространенных примеров регулярных выражений.
Половина хлопот при написании регулярного выражения связана с тем, чтобы оно совпадало в нужных местах. Другая половина — с тем, чтобы регулярное выражение не совпадало в ненужных местах. На практике важны оба аспекта, но пока основное внимание будет уделяться первому, то есть получению успешного совпадения. Хотя примеры анализируются не во всей полноте, так более наглядно прослеживаются основные принципы работы с регулярными выражениями.
В многих языках программирования существуют идентификаторы (имена переменных и т. п.), которые содержат только алфавитно-цифровые символы и знаки подчеркивания, но не могут начинаться с цифры — то есть [[a-zA-Z_][a-zA-Z_0-9*]. Первый класс определяет возможные значения первого символа идентификатора, второй (вместе с суффиксом *) определяет оставшуюся часть идентификатора. Если длина идентификатора ограничивается, допустим, 32 символами, звездочку можно заменить выражением [{0,31}], если эта конструкция поддерживается вашим программным средством (интервальный квантификатор кратко упоминается на с. <$R[P#,R1-1]>).
Простейшее решение выглядит так: ["[^"]*"].
Кавычки, ограничивающие регулярное выражение, совпадают с открывающими и закрывающими кавычками строки. Между ними может находиться все, что угодно… кроме других кавычек! Выражение [[^"]] совпадает с любым символом, кроме ", а звездочка говорит о том, что количество таких символов может быть любым.
Более полезное (хотя и более сложное) определение строки в кавычках позволяет включать в строку внутренние символы ", если перед ними стоит экранирующий префикс \ — например, "nailspcthespc2\"x4\"spcplank". Мы вернемся к этому примеру в главах 4 и 5, когда будем подробно рассматривать, как же на самом деле происходит поиск совпадений.
Одно из возможных решений: [\$[0-9]+(\.[0-9][0-9])?]
На верхнем уровне это простое регулярное выражение разбивается на три части: [\$], […+] и [(…)?]. Его можно вольно сформулировать как «литерал-знак доллара, за которым следует последовательность чего-то такого, а в конце еще может находиться что-то этакое». В данном случае «что-то такое» — это цифра (последовательность цифр образует число), а «что-то этакое» — это десятичная точка, за которой следуют две цифры.
Этот пример наивен по нескольким причинам. Например, в egrep важно лишь то, есть совпадение или нет, а длина совпадения несущественна, поэтому возиться с необязательными центами неразумно (состав совпадающих и несовпадающих строк от этого все равно не изменится). С другой стороны, если вам потребуется отыскать строки, содержащие только денежную сумму и ничего другого, выражение можно «завернуть» в конструкцию [^…$]. В этом случае необязательная дробная часть важна, поскольку она может находиться (или не находиться) между основной суммой и концом строки.
Кроме того, приведенное выражение не находит суммы вида $.49. Возникает искушение заменить + на *, но такое решение не годится. Почему? Этот вопрос останется открытым до возвращения к этому примеру в главе 4 (см. с. <$M[R4-31]>).
Поиск времени тоже может осуществляться с разной степенью точности. Например, выражение
[[0-9]?[0-9]:[0-9][0-9]spc(am|pm)]
успешно находит 9:17spcam и 12:30spcpm, но с такой же легкостью обнаруживает время 99:99spcpm.
Нетрудно понять, что если час состоит из двух цифр, то первая цифра может быть только единицей[9]. Но конструкция [1?[0-9]] также допускает 19 часов (и 0 часов), поэтому можно рассмотреть два отдельных случая: [1[012]] для часов из двух цифр и [[1-9]] для часов из одной цифры. В результате получается [(1[012]|[1-9])].
С минутами дело обстоит проще. Первая цифра определяется выражением [[0-5]], а для второй цифры можно оставить [[0-9]]. Объединяя все компоненты, мы получаем [(1[012]|[1-9]):[0-5][0-9]spc(am|pm)].
Попробуйте воспользоваться аналогичными рассуждениями и построить регулярное выражение для поиска времени в 24-часовом формате, с нумерацией часов от 0 до 23. Чтобы задание было посложнее, разрешите использование начального нуля — по крайней мере до 09:59. ref<$M[R1-10]>Попробуйте построить собственное решение, затем переверните страницу и сверьтесь с моим вариантом.
Поиск времени в 24-часовом формате
bref Ответ на вопрос со с. <$R[P#,R1-10]>
Существуют разные решения, но мы воспользуемся уже описанной логикой. Я разбил задачу на три группы: утро (c 00 до 09 часов, возможен начальный ноль), день (c 10 до 19 часов) и вечер (c 20 до 23 часов). Самое прямолинейное решение выглядит так: [0?[0-9]|1[0-9]|2[0-3]]<$M[R1-6]>.
Вообще говоря, первые два варианта можно объединить, и тогда запись получится более короткой: [[01]?[0-9]|2[0-3]]. На первый взгляд эквивалентность этих двух записей не очевидна, но на самом деле это так. Возможно, вам поможет приведенный ниже рисунок, на котором затененные группы обозначают числа, соответствующие разным альтернативам.
Концепция метасимвола (или «метапоследовательности» — я использую эти слова как синонимы) зависит от того, где именно в регулярном выражении он используется. Например, [*] является метасимволом, но только не внутри символьного класса и только если он не интерпретируется как литерал, то есть когда перед ним не стоит экранирующий префикс \… Впрочем, и это не всегда так. Например, звездочка интерпретируется как литерал в выражении [\*], но не в [\\*] (когда первый символ \ обеспечивает особую интерпретацию второго символа), хотя в обоих случаях «перед звездочкой стоит символ \».
В разных диалектах регулярных выражений также поддерживаются разные метасимволы. В главе 3 эта тема рассматривается более подробно.
Как я уже говорил, в разных программах регулярные выражения выполняют разные функции, поэтому наборы метасимволов и другие возможности, поддерживаемые программами, также различаются. В одних программах не поддерживаются какие-либо метасимволы, в других добавляются те или иные дополнительные возможности. Вернемся к примеру с границами слов. Некоторые версии egrep поддерживают обозначения \<…\>. В других версиях нет отдельных метасимволов для начала и конца слова, а есть один универсальный метасимвол<$M[R1-3]> [\b]. В третьих версиях поддерживаются все перечисленные метасимволы. Наконец, существуют версии, которые не поддерживают ни один из этих метасимволов.
Совокупность этих второстепенных различий в реализации я обозначаю термином «диалект». Однако диалект не сводится к набору поддерживаемых и неподдерживаемых метасимволов — за этим понятием кроется нечто большее. Даже если две программы поддерживают [\<…\>], они могут расходиться во мнениях относительно того, что именно следует считать словом. Если вы хотите на самом деле извлекать пользу из программы, это действительно важно. Подобным «закулисным» различиям посвящена глава 4.
Не путайте «диалект» с конкретной программой. Подобно тому, как двое людей могут говорить на одном и том же диалекте, две абсолютно разные программы могут поддерживать одинаковые диалекты регулярных выражений. Кроме того, две одноименные программы (и предназначенные для решения общей задачи) нередко обладают сильно различающимися диалектами.
Термин «подвыражение» (subexpression) на самом деле означает любую часть большего выражения, но обычно он относится к части, заключенной в круглые скобки, или к одной из альтернатив конструкции выбора. Например, в выражении [^(Subject|Date):spc] часть [Subject|Date] обычно именуется подвыражением. Внутри нее альтернативы [Subject] и [Date] тоже называются подвыражениями.
Конструкция типа [1-6] не считается подвыражением [H[1-6]spc*], поскольку она является частью неразрывного «элемента» — символьного класса. С другой стороны, [H], [1-6] и [spc*] являются подвыражениями исходного выражения.
В отличие от конструкции выбора, квантификаторы (*, + и ?) всегда применяются к наименьшему непосредственно предшествующему подвыражению. Вот почему в выражении [mis+pell] плюс относится только к [s], а не к [mis] или [is]. Конечно, когда квантификатору непосредственно предшествует подвыражение в круглых скобках, все подвыражение (сколь бы сложным оно ни было) воспринимается как единое целое.
<$M[R1-12]>Как упоминалось в одной из предыдущих сносок, термин «символ» в информатике имеет много значений. Символ, представленный некоторым байтом — всего лишь вопрос интерпретации. Значение байта остается неизменным в любом контексте, однако соответствующий ему символ зависит от кодировки<$M[R1-11]>. Например, два байта с десятичными значениями 64 и 53 представляют символы «@» и «5» в кодировке ASCII, но с другой стороны, в кодировке EBCDIC они соответствуют совершенно другим символам (пробел и символ <TRN>, что бы это ни означало).
В кодировке JIS (ISO-2022-JP) эти два байта совместно представляют иероглиф ###26-1### (возможно, вы узнали его по началу фразы, приведенной в разделе «Аналогия с языками» на с. <$R[P#,R1-2]>). Но в кодировке EUC-JP этот же иероглиф представляется двумя совершенно другими байтами. Кстати говоря, в кодировке Latin-1 (ISO-8859-1) эти два байта представляют два символа «Аµ», а в кодировке Unicode (но только начиная с версии 2.0[10]) — один корейский иероглиф ###26-2###.
Вы понимаете, что я имею в виду. Программы, работающие с регулярными выражениями, обычно интерпретируют свои данные как совокупность байтов, не учитывая предполагаемой кодировки. При поиске [Аµ] многие программы найдут ###26-1### в данных EUC-JP или ###26-2### в данных Unicode.
С этими (и еще более сложными) проблемами постоянно сталкиваются те, кто работает с данными Unicode или других многобайтовых кодировок. Впрочем, для большинства читателей они несущественны, поэтому я буду считать термины «байт» и «символ» синонимами.
Честно говоря, изучить регулярные выражения не так уж сложно. Но если поговорить со средним пользователем программы или языка с поддержкой регулярных выражений, скорее всего выяснится, что ваш собеседник «немножко разбирается» в них, но не чувствует достаточной уверенности для решения действительно нетривиальных задач или ограничивается только теми программами, которыми он часто пользуется.
Обычно документация по регулярным выражениям ограничивается коротким и неполным описанием одного-двух метасимволов, за которым следует таблица с перечислением всего остального. В примерах часто используются бессмысленные регулярные выражения типа [a*((ab)*|b*] и потрясающие тексты вроде «aspcxxxspccespcxxxxxxspccispcxxxspcd». Кроме того, в документации полностью игнорируются неочевидные, но важные моменты, и часто утверждается, что поддерживаемый диалект полностью совместим с диалектом другой, хорошо известной программы. При этом авторы всегда забывают упомянуть о неизбежных исключениях. В общем, состояние дел с документацией по регулярным выражениям явно нуждается в улучшении.
Я вовсе не утверждаю, что эта глава решит все проблемы. Скорее она заложит фундамент, на котором будет построена вся оставшаяся часть книги. Звучит амбициозно, но я надеюсь, что эта книга действительно решит многие проблемы. Может быть, из-за традиционных недостатков документации я постарался приложить дополнительные усилия и изложить материал действительно понятно. Для полноценного использования регулярных выражений вы должны действительно понять их.
Это и хорошо, и плохо.
Хорошо — потому что вы научитесь мыслить регулярными выражениями. Вы узнаете, на какие различия и особенности следует в первую очередь обращать внимание при знакомстве с новой программой, обладающей собственным диалектом. Вы научитесь выражать свои мысли даже на слабом, усеченном диалекте регулярных выражений. Столкнувшись с особенно сложным выражением, вы будете точно знать, как оно будет обработано программой. Короче говоря, потенциал регулярных выражений в полной мере раскроется перед вами.
Но при этом вам придется основательно потрудиться:
l Общие принципы использования регулярных выражений — в большинстве программ существуют более совершенные средства работы с регулярными выражениями, чем в утилите egrep. Прежде чем подробно рассматривать процесс написания действительно полезных регулярных выражений, необходимо разобраться с общими принципами их использования. Мы займемся этой темой со следующей главы.
l Возможности регулярных выражений — правильный выбор инструмента для решения конкретной проблемы наполовину решает задачу, поэтому я не хочу ограничиваться одной утилитой во всей книге. Разные программы (а иногда даже разные версии одной программы) обладают разными возможностями и поддерживают разные метасимволы. Прежде чем переходить к подробностям использования, мы подробно изучим обстановку. Этой теме посвящена глава 3.
l Механизм обработки регулярных выражений — чтобы мы могли изучать полезные (но нередко сложные) примеры, необходимо выяснить, как же происходит поиск регулярных выражений. Как вы убедитесь, порядок проверки некоторых метасимволов может играть очень важную роль. Более того, обработка регулярных выражений может быть реализована различными способами, поэтому разные программы часто выполняют с одним выражением разные действия. Эта обширная тема рассматривается в главах 4 и 5.
Последний пункт — самый важный и одновременно самый сложный в изложении. Теоретические рассуждения покажутся скучноватыми нетерпеливому читателю, стремящемуся поскорее добраться до самого интересного — до реальных задач. Тем не менее, механизм обработки регулярных выражений является ключом к их подлинному пониманию.
Возможно, кто-то возразит — чтобы научиться водить машину, необязательно знать, как она устроена. Но аналогия с вождением машины в данном случае неуместна. Я хочу, чтобы вы научились решать задачи с использованием регулярных выражений, а для этого вам придется самостоятельно строить регулярные выражения. Так что лучше провести аналогию не с вождением автомобиля, а с его самостоятельной сборкой. Чтобы построить свой автомобиль, необходимо знать, как он устроен.
В главе 2 вы получите дополнительный опыт практического вождения. В главе 3 рассматривается строение кузова (диалектов регулярных выражений), а в главе 4 вы познакомитесь со строением двигателя. Глава 3 также содержит краткий обзор автомобилестроения и проливает свет на сегодняшнюю ситуацию. Глава 5 показывает, как настраивать различные двигатели, а в последующих главах рассматриваются конкретные модели. Нам предстоит провести много времени, копаясь под капотом (особенно в главах 4 и 5), поэтому не забудьте надеть рабочий комбинезон и запаситесь тряпками.
В табл. 1.3 приведена сводка метасимволов egrep, рассмотренных в этой главе. Вы должны четко понимать следующие положения:
l Не все программы egrep одинаковы. Они часто различаются по набору поддерживаемых метасимволов и их интерпретации — за подробностями обращайтесь к документации.
l Круглые скобки применяются для группировки, сохранения совпавшего текста и ограничения конструкций выбора.
l Символьные классы занимают особое место — в них действуют совершенно иные правила использования метасимволов.
l Конструкции выбора и символьные классы принципиально отличаются друг от друга. Они решают разные задачи, которые лишь в одной специализированной ситуации выглядят похожими.
l Инвертированный символьный класс «позитивен» — он предполагает наличие символа, а не его отсутствие. Поскольку список символов инвертируется, совпадающий символ должен быть одним из тех, которые не перечислены в классе.
l Полезный ключ -i отменяет учет регистра символов при сравнении.
Таблица 1.3. Сводка метасимволов egrep
Элементы, обозначающие отдельный символ
|
Метасимвол |
Название |
Интерпретация |
|
. |
точка |
Один любой символ |
|
[…] |
символьный класс |
Любой из перечисленных символов |
|
[^…] |
инвертированный символьный класс |
Любой символ, не перечисленный в классе |
|
\символ |
экранирование |
Если перед метасимволом ставится экранирующий префикс \, то последний интерпретируется как соответствующий литерал. |
Квантификаторы
|
? |
вопросительный знак |
Допускается один экземпляр (ни один не требуется). |
|
* |
звездочка |
Допускается любое количество экземпляров (ни один не требуется). |
|
+ |
плюс |
Требуется один экземпляр, допускается любое количество экземпляров. |
|
{мин, макс} |
интервальный квантификатор[11] |
Требуется «мин» экземпляров, допускается «макс» экземпляров. |
Позиционные метасимволы
|
^ |
крышка, циркумфлекс |
Позиция в начале строки |
|
$ |
доллар |
Позиция в конце строки |
|
\< |
граница слова[12] |
Позиция в начале слова |
|
\> |
граница слова[13] |
Позиция в конце слова |
Прочие метасимволы
|
| |
конструкция выбора |
любое из перечисленных выражений |
|
(…) |
круглые скобки |
ограничение конструкции выбора, группировка для применения квантификаторов и «сохранение» текста для обратных ссылок. |
|
\1, \2, … |
обратная ссылка[14] |
Текст, ранее совпавший с первой, второй и т. д. парами круглых скобок |
l Существует три различных варианта экранирования:
1. [\] + метасимвол — метапоследовательность, обозначающая соответствующий литерал (например, [\*] обозначает литерал-звездочку).
2. [\] + некоторые метасимволы — метапоследовательность, смысл которой зависит от конкретной реализации (например, [\<] часто означает «начало слова»).
3. [\] + любой другой символ — просто указанный символ (иначе говоря, символ \ игнорируется).
Помните о том, что в символьных классах символ \ не имеет особой интерпретации.
l Элементы, к которым применяются метасимволы ? и *, не обязаны действительно совпадать с какой-то частью строки для получения «успешного совпадения». Они совпадают всегда, даже если они совпадают с «ничем».
Задача с повторяющимися словами, описанная в начале главы, выглядит довольно сложной, однако выдающиеся возможности регулярных выражений позволили нам практически полностью решить ее при помощи такого ограниченного инструмента, как egrep, и притом в первой главе книги. Я хотел привести и более эффектные примеры, но потом решил, что будет лучше направить свои усилия на укрепление надежного фундамента для последующих глав. Я испугался, что какой-нибудь новичок прочитает эту главу, заполненную всевозможными правилами, исключениями из правил, предупреждениями и т. д., и подумает: «А стоит ли с этим связываться?»
Недавно мои братья обучали своих друзей играть в «шафкопф» — карточную игру, в которую играет уже несколько поколений моей семьи. Она значительно интереснее, чем кажется на первый взгляд, но начинающим приходится нелегко. После получасовых мучений моя двоюродная сестра Лиз, образец терпения, окончательно запуталась в сложных правилах и сказала: «Может, лучше сыграем в рамми?» Но в конце концов они засиделись за игрой до поздней ночи. Стоило преодолеть первую «гору» на пути обучения, как простой азарт уже не отпустил их. Мои братья знали, что так и произойдет, но им пришлось затратить время и усилия на то, чтобы Лиз и другие новички оценили новую игру.
Возможно, кому-то из читателей понадобится некоторое время на то, чтобы привыкнуть к регулярным выражениям. До тех пор, пока вы не почувствуете настоящего удовольствия от решения ваших собственных задач, регулярные выражения могут показаться несколько абстрактной теорией. Надеюсь, вы удержитесь от желания «сыграть в рамми». Когда вы поймете, какие возможности открывают перед вами регулярные выражения, небольшие усилия по их изучению покажутся вам сущим пустяком.
[1] В информатике термин «символ» имеет много значений, но я использую его лишь как более удобный эквивалент для термина «байт». За дополнительными сведениями обращайтесь к разделу «Терминология регулярных выражений» этой главы.
[2] «Регулярные выражения — это просто!» Несерьезный комментарий: как вы узнаете из главы 3, термин «регулярные выражения» позаимствован из формальной алгебры. Когда меня спрашивают, о чем эта книга, ответ обычно вызывает недоуменное выражение, если мой собеседник никогда не слышал об использовании регулярных выражений в компьютерных технологиях. Японское обозначение регулярных выражений, ###5-2###, также незнакомо среднему японцу, однако ответ на японском языке вызовет нечто большее, чем простое недоумение. Дело в том, что в переводе на японский термин «регулярный» очень напоминает другое, более распространенное слово — медицинское обозначение гениталий. Только представьте себе, о чем думает мой собеседник, пока я не объясню подробнее!
[3] Утилита egrep существует во многих системах, включая DOS, MacOS, Windows, Unix и т. д. (за информацией о том, где найти версию egrep для вашей системы, обращайтесь к приложению A). Возможно, некоторым пользователям знакома программа grep, во многих отношениях аналогичная egrep. Из общего обзора, приведенного в главе 3, станет ясно, почему я начал именно с egrep.
[4] Командным интерпретатором называется часть операционной системы, которая обрабатывает введенные команды и запускает указанные в них программы. В том интерпретаторе, которым я пользуюсь, апострофы предназначаются для группировки аргументов. Они говорят о том, что командный интерпретатор не должен обращать внимания на заключенные в них символы (например, он не должен интерпретировать *.txt как файловый шаблон — утилита egrep сама интерпретирует эту строку так, как сочтет нужным, в контексте регулярного выражения). Пользователи интерпретатора COMMAND.COM системы DOS вместо апострофов используют кавычки.
[5] egrep просто разбивает входной файл на отдельные строки и затем проверяет их по шаблону регулярного выражения. Ни на одной из этих стадии утилита не пытается распознавать такие «человеческие» конструкции, как предложения и слова. Я мучительно искал правильное выражение, но потом встретил выражение «концепции высокого уровня» в книге Дейла Догерти (Dale Dougherty) «sed & awk» и почувствовал, что оно идеально подходит.
[6] Не поддерживается некоторыми версиями egrep.
[7] Не поддерживается некоторыми версиями egrep.
[8] Если вы не знаете языка HTML, не огорчайтесь. Я использую его, чтобы примеры выглядели более реально, но при этом привожу всю необходимую информацию. Читатели, знакомые с задачей анализа тегов HTML, наверняка увидят некоторые важные обстоятельства, которые пока не упоминаются в книге.
[9] Разумеется, речь идет о времени в формате AM/PM — Примеч. перев.
[10] Наиболее авторитетным руководством по многобайтовым кодировкам является книга Кена Лунде (Ken Lunde) «Understanding Japanese Information Processing». Когда я отдавал книгу в печать, Кен работал над вторым изданием своей книги с завлекательным названием «Understanding CJKV Information Processing». Сокращение CJKV означает «китайский, японский, корейский и вьетнамский» — все языки, в которых используется многобайтовая кодировка.
[11] Не поддерживается некоторыми версиями egrep.
[12] Не поддерживается некоторыми версиями egrep.
[13] Не поддерживается некоторыми версиями egrep.
[14] Не поддерживается некоторыми версиями egrep.