Механика обработки регулярных выражений
От необходимых теоретических сведений мы переходим к описанию механики обработки регулярных выражений. Глянец и внешняя отделка остались в предыдущей главе, а эта глава полностью посвящена двигателям[1] и всему тому, о чем автомеханики болтают в барах. Мы проведем немало времени под капотом машины, поэтому не бойтесь запачкать руки прикосновениями к реальным примерам.
Давайте посмотрим, сколько я еще смогу выжать из своей аналогии с двигателями. Как известно, двигатель нужен для того, чтобы вы могли без особых хлопот попасть из точки А в точку Б. Двигатель работает, а вы расслабляетесь и наслаждаетесь новеньким кожаным сиденьем. Главная задача двигателя — вертеть колеса, а как он это делает, вас не волнует. Но так ли это?
Электромобили появились относительно давно, но еще не получили такого распространения, как автомобили с бензиновым двигателем. Но если вы все же пользуетесь электромобилем, по крайней мере нужно помнить, что в него не стоит заливать бензин. С бензиновым двигателем дело обстоит сложнее. Электрический двигатель более или менее работает сам по себе, а бензиновому двигателю может потребоваться уход. Небольшая регулировка зазора между электродами свечи, воздушного фильтра или переход на другой сорт бензина — каждый из этих факторов способен существенно улучшить работу двигателя. Но стоит вам ошибиться, и двигатель начнет работать хуже или попросту заглохнет.
Каждый двигатель работает по-своему, но конечный результат один и тот же: колеса крутятся. Если вы захотите куда-нибудь добраться, вам придется еще и крутить руль, но это уже совсем другая история.
Теперь давайте усложним ситуацию и добавим в нее новую переменную: калифорнийский стандарт, определяющий допустимый состав выхлопных газов[2]. Одни двигатели соответствуют жестким стандартам, принятым в Калифорнии, другие не соответствуют им, причем это не разные двигатели, а всего лишь разновидности уже существующих моделей. Стандарт регулирует результат работы двигателя — состав выхлопных газов, но ничего не говорит о том, как заставить двигатель работать чище. Итак, два класса двигателей делятся на четыре типа: электрические (соответствующие и несоответствующие) и бензиновые (соответствующие и несоответствующие).
Готов поспорить, что электрический двигатель пройдет проверку без всяких изменений, поэтому на него этот стандарт особенно не влияет — он всего лишь «одобряет» уже готовый результат. С другой стороны, бензиновый двигатель может потребовать значительной доработки и настройки. Владельцы таких двигателей должны обратить особое внимание на топливо — стоит воспользоваться неправильным сортом бензина, и у вас начнутся большие неприятности.
Экологические стандарты — дело хорошее, но они требуют от водителя большой внимательности и предусмотрительности (по крайней мере для бензиновых двигателей, как упоминалось в предыдущем абзаце). Впрочем, этот стандарт не влияет на большинство автомобилистов, поскольку в других штатах действуют собственные законы, и калифорнийские стандарты в них не соблюдаются… пока. Вероятно, это вопрос времени.
Итак, четыре типа двигателей можно разделить на три группы (две группы для бензиновых двигателей, одна для электрических). Вы знаете, чем они отличаются, и что в конечном счете все двигатели должны крутить колеса. Правда, совершенно непонятно, какое отношение все сказанное имеет к регулярным выражениям.
Гораздо большее, чем вы можете себе представить.
Существует два принципиально разных типа механизмов регулярных выражений: ДКА и НКА. Смысл этих сокращений будет объяснен ниже (см. с. <$R[P#,R4-14]>), а пока просто считайте их техническими терминами (как «электрический» и «бензиновый»).
Оба типа механизмов существуют довольно давно, но тип НКА, как и его бензиновый аналог, встречается чаще. К числу программ, использующих механизм НКА, принадлежат Tcl, Python, Perl, GNU Emacs, ed, sed, vi, большинство версий grep и даже некоторые версии egrep и awk. С другой стороны, механизм ДКА реализован практически во всех версиях egrep и awk, а также в lex и flex. В табл. 4.1 перечислены некоторые распространенные программы, существующие на многих разных платформах, и указан механизм регулярных выражений, используемый большинством версией. Версия «общая» означает, что это старая программа с большим количеством клонов — информация о заметно отличающихся клонах приведена отдельно.
Как было показано в главе 3, 20 лет эволюции регулярных выражений привели к ненужному разнообразию, постепенно перераставшему в хаос. Появился стандарт POSIX<$M[R4-15]>, который должен был прояснить ситуацию и четко определить, какие метасимволы должны поддерживаться механизмом регулярных выражений и каких результатов следовало ожидать. Если опустить второстепенные подробности, тип ДКА (наши электрические двигатели) достаточно хорошо соответствовали стандарту, но результаты, традиционно обеспечиваемые НКА, несколько отличались от требований нового стандарта, поэтому потребовалось внести некоторые изменения. В результате механизмы регулярных выражений стали делиться на три типа:
l ДКА (соответствующие стандарту POSIX или нет — практически одно и то же);
l традиционные НКА;
l НКА стандарта POSIX.
POSIX стандартизировал работу более 70 программ, включая традиционные инструменты для работы с регулярными выражениями — awk, ed, egrep, expr, grep, lex и sed. Большинство диалектов этих программ были (и до сих пор остаются) маломощными, сравнимыми разве что с движком мопеда — настолько маломощными, что на мой взгляд, они не заслуживают упоминания при обсуждении регулярных выражений. Хотя в некоторых ситуациях они приносят несомненную пользу, в этой книге expr, ed и sed почти не упоминаются. Впрочем, для справедливости стоит упомянуть о том, что в некоторых современных версиях этих программ реализуется новый, более мощный диалект. Особенно часто это происходит с программой grep, которая по своим регулярным выражениям является прямым родственником sed, ed и expr.
С другой стороны, egrep, awk и lex обычно реализуются на базе «электрического» механизма ДКА, поэтому новый стандарт фактически лишь утвердил status quo без каких-либо принципиальных изменений. Тем не менее, существовали «бензиновые» версии этих программ, и чтобы обеспечить соответствие стандарту POSIX, в них приходилось вносить некоторые изменения. Механизмы, удовлетворяющие «калифорнийскому стандарту» (POSIX НКА) были хороши тем, что выдаваемые ими результаты были стандартными, однако от внесенных изменений они стали более капризными. Если раньше можно было жить с небольшими отклонениями в зазоре электродов, сейчас это было абсолютно нетерпимо. От бензина, который раньше был «достаточно хорош», мотор теперь чихал и останавливался. Но если вы умели ухаживать за своей крошкой, двигатель работал гладко. И притом чисто.
<$M[R4-16]>
Таблица 4.1. Некоторые программы и их механизмы регулярных выражений
|
Программа |
Автор |
Версия |
Механизм |
|
awk Новый awk GNU awk MKS awk mawk |
Ахо, Вайнбергер, Керниган Брайан Керниган Арнольд Роббинс Mortice Kern Systems Майк Бреннан |
общая общая последние
все |
ДКА ДКА в основном ДКА POSIX НКА POSIX НКА |
|
egrep MKS egrep |
Альфред Ахо Mortice Kern Systems |
общая |
ДКА POSIX НКА |
|
GNU Emacs |
Ричард Столлмен |
все |
Традиционный. НКА (существует версия с POSIX НКА) |
|
Expect |
Дон Либс |
все |
Традиционный НКА |
|
expr |
Дик Хейт |
общая |
Традиционный НКА |
|
grep |
Кен Томпсон |
общая |
Традиционный НКА |
|
GNU grep |
Майк Хартел |
версия 2.0 |
В основном ДКА, но иногда используется НКА |
|
GNU find |
GNU |
|
Традиционный НКА |
|
lex flex lex |
Майк Леск Верн Паксон Mortice Kern Systems |
общая все |
ДКА ДКА POSIX НКА |
|
more less |
Эрик Шинбруд Марк Нудельман |
общая |
Традиционный НКА Меняется (обычно традиционный НКА) |
|
Perl |
Ларри Уолл |
все |
Традиционный НКА |
|
Python |
Гвидо ван Россум |
все |
Традиционный НКА |
|
sed |
Ли МакМагон |
общая |
Традиционный НКА |
|
Tcl |
Джон Устерхаут |
все |
Традиционный НКА |
|
vi |
Билл Джой |
общая |
Традиционный НКА |
А сейчас я попрошу вас вернуться на пару страниц назад и перечитать историю о двигателях. Каждое из приведенных там высказываний относится и к регулярным выражениям. При втором прочтении возникают некоторые вопросы. В частности, что означает «электрический двигатель более или менее работает сам по себе»? Какие характеристики влияют на работу «бензиновых» механизмов НКА? Как настроить НКА? Какие особенности присущи POSIX НКА? Что означает «заглохший двигатель» в мире регулярных выражений? И наконец, что имеется в виду под «новенькими кожаными сиденьями»? (см. с. <$R[P#,R4-25]>)
Прежде чем выяснять, чем различаются разные типы двигателей, мы сначала рассмотрим их общие свойства. У всех двигателей имеется нечто общее (хотя бы с чисто практической точки зрения), поэтому эти примеры относятся к двигателям любого типа.
В этой главе рассматривается обобщенный полнофункциональный механизм регулярных выражений, поэтому какие-то из описанных возможностей могут не поддерживаться некоторыми программами. Скажем, в моем примере указатель уровня находится слева от масляного фильтра, а у вас он может быть расположен за крышкой распределителя. Вы должны понять основные концепции, чтобы успешно управлять работой своей любимой программы с поддержкой регулярных выражений (а также тех, которые заинтересуют вас в будущем).
В большинстве примеров я буду придерживаться синтаксиса Perl, хотя иногда буду переходить на другой синтаксис, чтобы вы не забывали — запись второстепенна, а рассматриваемые вопросы выходят за границы одной программы или диалекта. Если вы встретите незнакомую конструкцию, обращайтесь к главе 3.
В этой главе подробно описаны практические алгоритмы выполнения поиска. Конечно, было бы удобно свести все к нескольким простым правилам, которые можно просто запомнить, не затрудняя себя доскональным пониманием происходящего. К сожалению, в данном случае это не так. Во всей главе я могу выделить лишь два универсальных правила:
1. Предпочтение отдается более раннему совпадению.
2. Квантификаторы работают максимально.
Мы рассмотрим эти правила, некоторые следствия из них и многое другое.
Начнем с Первого правила регулярных выражений:
Предпочтение отдается тому совпадению, которое начинается раньше.
Правило гласит, что более раннему совпадению предпочтение отдается всегда, даже в том случае, если позднее в строке будет обнаружено другое возможное совпадение. Правило ничего не говорит о длине совпадения (вскоре мы обсудим этот вопрос подробнее). Речь идет лишь о том, что из всех возможных совпадений в строке выбирается то, начало которого располагается ближе к началу строки.
Это правило работает следующим образом: сначала механизм пытается найти совпадение от самого начала строки, в которой осуществляется поиск (в позиции до первого символа). Выражение «пытается» означает, что с указанной позиции ищутся все возможные комбинации всего (иногда довольно сложного) регулярного выражения. Если после перебора всех возможностей совпадение так и не будет найдено, вторая попытка делается с позиции, предшествующей второму символу. Эта процедура повторяется для каждой позиции в строке. Результат «совпадение не найдено» возвращается лишь в том случае, если совпадение не находится после перебора всех позиций до конца строки (после завершающего символа).
Следовательно, при поиске совпадения [ORA] в строке FLORAL первая попытка завершается неудачей (поскольку [ORA] не совпадает с FLO). Совпадение, начинающееся со второго символа (LOR), тоже не подходит. Но сопоставление, начинающееся с третьего символа, оказывается удачным, поэтому механизм поиска прекращает перебор и сообщает о найденном совпадении: FLORAL.
Если вы не знаете этого правила, результат иногда оказывается неожиданным. Например, при поиске [cat] в строке
The dragging belly indicates your cat is too fat
совпадение находится в слове indicates, а не в слове cat, расположенном правее. Слово cat могло бы совпасть, но cat в слове indicates начинается раньше, и поэтому совпадает именно оно. В таких приложениях, как egrep, учитывается лишь наличие совпадения, а не его точная позиция, поэтому в них это различие несущественно, но в других операциях (например, при поиске с заменой) оно имеет первостепенное значение.
Помните: при каждой попытке осуществляется полный поиск регулярного выражения, поэтому [fat|cat|belly|your] совпадет с belly, а не с fat, хотя fat в списке альтернатив находится в более ранней позиции:
The dragging belly indicates your cat is too fat
Конечно, регулярное выражение позволяет найти совпадения и для fat с остальными альтернативами, но поскольку они не являются самым ранним (то есть начинающимся в ближайшей к левому краю позиции) совпадением, выбор делается не в их пользу. Как я уже говорил, механизм пытается применить все выражение в текущей позиции, прежде чем переходить к следующей позиции для повторения попытки. В данном примере это означает, что в текущей позиции будут рассмотрены все альтернативы — [fat], [cat], [belly] и [your], и только после этого произойдет переход к следующей позиции.
Следующий принцип работы механизма регулярных выражений можно рассматривать как аналог автомобильной трансмиссии, соединяющей двигатель с мостом. Вся настоящая работа (поворот коленчатого вала) осуществляется двигателем, а трансмиссия передает эту работу на колеса.
<$M[R4-17]>
Если механизм не находит совпадение в начале строки, то «трансмиссия» смещает текущую позицию поиска, и новая попытка осуществляется в следующей позиции строки — потом в следующей, и так далее. Во всяком случае, обычно. Например, если регулярное выражение начинается с якорного метасимвола начала строки, то «трансмиссия» может догадаться, что дальнейшие сдвиги ни к чему не приведут, поскольку успешное совпадение может начинаться только от начала строки. Это пример оптимизации привязки к границам логических строк/фрагментов, рассмотренной в следующей главе (см. с. <$R[P#,R5-3]>).
<$M[R4-7]>
Двигатель состоит из множества деталей разных типов и размеров. Чтобы понять, как он работает, необходимо разобраться с тем, как работают его составные части. В регулярных выражениях этим частям соответствуют синтаксические единицы — литералы, квантификаторы (* и т. п.), символьные классы, выражения в круглых скобках и т. д. Комбинация этих частей (и их интерпретация механизмом) и делает регулярное выражение тем, чем оно является, поэтому способы объединения и взаимодействие этих частей представляют для нас первоочередной интерес. Начнем с рассмотрения некоторых из этих частей.
l Литералы. Для литеральных, не-метасимвольных конструкций типа [z] или [!] поиск совпадения сводится к простому выяснению вопроса — совпадает ли символ-литерал с текущим символом текста? Если регулярное выражение содержит только литеральный текст — например, [usa] — оно интерпретируется как последовательность «[u], затем [s], после чего [a]». Ситуация немного усложняется при поиске без учета регистра, где [b] может совпадать с b и B, но и в этом случае все относительно просто.
l Символьные классы, точка и т. д. Поиск совпадений для символьного класса тоже несложен. Независимо от размера символьный класс все равно совпадает только с одним символом[3]. Символьный класс определяет набор символов, которые могут совпадать с символом текста. Символы перечисляются либо явно, либо косвенно (в инвертированных классах). Точка представляет собой сокращенную запись для большого символьного класса, состоящего из всех символов (кроме новой строки и/или нуль-символа в некоторых диалектах), поэтому и здесь поиск обходится без проблем. Так же обстоит дело и с другими сокращенными обозначениями — [\w], [\W], [\d], [\D], [\s], [\S] и т. д.
l Якорные метасимволы. Не вызывает особых трудностей и поиск некоторых метасимволов, совпадающих не с символами целевого текста, а с определенной позицией в нем. К числу таких символов относятся границы строк/фрагментов (^ и $), границы слов ([\<], [\b] и т. п.). Проверка проста, поскольку в большинстве случае она сводится к простому сравнению типов двух соседних символов целевого текста.
l Круглые скобки (при сохранении текста). Использование круглых скобок только для сохранения совпавшего текста (в отличие от группировки) иногда снижает быстроту поиска (см. главу 5), но в общем случае скобки не влияют на сам процесс поиска.
На первых порах основное внимание будет уделяться сходным чертам двух механизмов, но для начала я опишу одно интересное отличие. Сохраняющие круглые скобки (и связанные с ними обратные ссылки) напоминают бензиновую присадку. Они влияют на работу бензинового двигателя, но несущественны для электрических двигателей — прежде всего потому, что бензин в нем вообще не используется. Принцип работы механизма ДКА полностью исключает саму концепцию обратных ссылок и сохраняющих круглых скобок. Эти конструкции в ДКА попросту невозможны[4]. Становится понятно, почему программы с механизмом ДКА не обладают этими возможностями. В частности, awk, lex и egrep не поддерживают обратных ссылок или каких-либо аналогов $1.
Однако следует заметить, что GNU-версия egrep поддерживает обратные ссылки. Для этого под одним капотом устанавливаются два разных двигателя! Сначала механизм ДКА находит возможное совпадение, после чего механизм НКА (реализующий полноценный диалект с обратными ссылками) подтверждает совпадение. Позднее в этой главе будет показано, почему ДКА не позволяет применять обратные ссылки и сохранять текст, и зачем вообще нужен такой механизм (у него есть свои большие преимущества — например, очень быстрый поиск совпадений).
До настоящего момента процесс поиска совпадений выглядел очень просто. К тому же он кажется неинтересным — трудно сделать что-нибудь серьезное без применения более мощных метасимволов (*, +), конструкции выбора и т. д. Но чтобы понять новые возможности, необходимо больше знать о них.
Во-первых, вы должны запомнить, что квантификаторы (?, *, + и {мин, макс}) работают максимально<$M[R4-22]>. Когда квантификатор применяется к подвыражению (например, a в [a?], [(выражение)] в [(выражение)*] или [[0-9]] в [[0-9]+]), существует некоторое минимальное количество повторений, необходимых для успешного совпадения, и максимальное количество повторений, больше которого механизм искать даже не пытается. Об этом говорилось в одной из предыдущих глав — но здесь вступает в силу Второе правило регулярных выражений:
Если некоторый элемент может совпадать переменное количество раз, механизм всегда пытается найти максимальное количество повторений. Квантификаторы работают максимально.
Другими словами, при необходимости механизм может «согласиться» и на минимальное количество обязательных совпадений, но он всегда пытается обнаружить как можно больше совпадений вплоть до разрешенного максимума.
Механизм регулярных выражений соглашается на значения меньше максимума только в одном случае — если слишком большое количество повторений не позволяет найти совпадение для какой-либо последующей части регулярные выражения. Рассмотрим простой пример: выражение [\<\w+s\>], предназначенное для поиска слов, заканчивающихся на s (скажем, regexes). Конструкция [\w+] была бы рада совпасть с целым словом, но в этом случае литералу s совпадать будет уже не с чем. Чтобы добиться общего совпадения, [\w+] соглашается на совпадение с подстрокой regexes; и это позволяет совпасть [s\>] и всему выражению.
Если выясняется, что оставшаяся часть регулярного выражения совпадает лишь в том случае, если максимальная конструкция не совпадает ни с чем (если нулевое количество повторений разрешено, как для *, ? и интервального квантификатора {мин, макс})… что ж, это вполне нормально. Но такая ситуация возможна лишь в том случае, когда этого требует одно из дальнейших подвыражений. Квантификаторы всегда захватывают (или по крайней мере стремятся захватить) больше повторений, чем им требуется по минимуму, поэтому их иногда называют «жадными».
Из этого правила вытекает много полезных следствий (впрочем, проблем тоже хватает). В частности, оно объясняет, почему [[0-9]+] совпадает со всем числом в строке Marchspc1998. Найденное совпадение 1 выполняет минимальное требование для квантификатора +. Но из-за того, что квантификатор всегда старается обеспечить максимальное количество повторений, поиск продолжается и в совпадение включаются символы 998. Поиск прерывается при обнаружении конца строки — [[0-9]] не может совпасть с «пустым местом», и обработка + на этом завершается.
Конечно, описанный метод используется не только при поиске чисел. Допустим, у нас имеется строка из заголовка сообщения электронной почты, и мы хотим проверить, является ли она строкой темы. Как было показано в одной из предшествующих глав, задача решается при помощи выражения [^Subject:spc]. Но если воспользоваться выражением [^Subject:spc(.*)], то программа сохранит тему сообщения в служебной переменной ($1 в Perl)[5].
Прежде чем выяснять, почему [.*] совпадает с текстом темы, необходимо твердо уяснить одно обстоятельство: если часть [^Subject:spc] совпадает, то и все регулярное выражение заведомо совпадет. Это объясняется тем, что после [^Subject:spc] нет ни одного элемента, который бы мог отменить потенциальное совпадение — [*] совпадает всегда, поскольку даже худший случай «0 повторений» для квантификатора * все равно считается успешным.
Тогда зачем включать [.*] в регулярное выражение? Квантификатор * постарается найти как можно больше повторений метасимвола «точка», и поэтому используем его для «заполнения» переменной $1. Круглые скобки никак не влияют на логику поиска совпадения — в данном случае они используются только для сохранения текста, совпавшего с [.*].
После того, как [.*] доберется до конца строки, следующего совпадения для точки не находится, поэтому работа * завершается, и начинается поиск совпадения для следующего элемента регулярного выражения (хотя для [.*] совпадений больше нет, возможно, найдется совпадение для следующего элемента). Однако в нашем случае следующего элемента нет, мы достигаем конца регулярного выражения и знаем, что совпадение было найдено успешно.
Допустим, переменная $line содержит строку
Subject: Re: happy birthday
Следующий фрагмент на языке Perl:
if ($line =~ m/^Subject: (.*)/ ) {
print "The subject is: $1\n";
}
выводит результат: «The subject is: Re: happy birthday».
Для расширения кругозора приведу аналогичные фрагменты для Tcl:
if [regexp "^Subject: (.*)" $line all exp1] {
puts "The subject is: $exp1"
}
и Python:
reg = regex.compile("Subject: \(.*\)")
if reg.match(line) > 0:
print "The subject is:", reg.group(1)
Как видите, в каждом языке используется свой синтаксис работы с регулярными выражениями, но принцип максимализма (и результат его применения) остаются одинаковыми.
Давайте усовершенствуем рассмотренный пример и удалим надоедливые префиксы Re:spc, который вставляется многими почтовыми программами как признак ответа на другое, исходное сообщение. Наша цель — проигнорировать все «Re:spc», с которых начинается тема сообщения, и оставить только «настоящую» тему.
В решении этой задачи нам поможет принцип максимализма. Рассмотрим выражение [^Subject:spc(Re:spc)?(.*)] — от приведенного выше оно отличается добавлением [(Re:spc)?] перед [(.*)]. Оба подвыражения стремятся захватить как можно больше повторений, но [(Re:spc)?] начинает «жадничать» первым. Оно захватывает возможную последовательность Re:spc, оставляя на долю [(.*)] весь оставшийся текст. С таким же успехом можно воспользоваться и конструкцией [(Re:spc)*], которая «заберет» все префиксы, вставленные в ответ на все предыдущие ответы в цепочке.
Круглые скобки в [(Re:spc)?] предназначены только для группировки, но они все равно учитываются при подсчете. Это означает, что исходная пара круглых скобок, захватывающая результат совпадения [.*], становится второй по счету. В свою очередь, это означает, что тема сообщения сохраняется в переменной $2, а не $1. Следовательно, программа
if ($line =~ m/^Subject: (Re: )?(.*)/ ) {
print "The subject is: $2\n";
}
выводит строку «The subject is: happy birthday».
Можно даже представить себе фрагмент вида:
if ($line =~ m/^Subject: (Re: )?(.*)/ ) {
# Совпадение - выбрать тип сообщения в зависимости от $1
if ($1 eq "Re: ") {
print "The reply is: $2\n";
} else {
print "The subject is: $2\n";
}
}
Даже если для пары скобок, заполняющая $1, не найдется совпадения в строке, вторая пара все равно сохранит совпавший текст в $2.
Напоследок рассмотрим то же выражение с перемещением одной из скобок:
вставить рисунок<f97-1>
Поскольку пары скобок всегда нумеруются слева направо в соответствии с порядковым номером открывающей скобки, скобки [Re:spc] соответствуют переменной $2, а вся тема соответствует $1. Однако в этом случае префикс «Re:spc», который может попасть в $2, также находится и внутри первой пары скобок, поэтому $1 будет содержать этот префикс (вместе с оставшейся частью темы). В нашем примере это не нужно, однако такая возможность пригодится, если вы хотите оставить текст темы без изменений, но при этом знать, является ли сообщение ответом.
Вернемся к принципу максимализма, согласно которому квантификатор забирает все, что только может забрать. Подумайте, как изменится совпадение и результаты поиска, если добавить второе подвыражение [.*] — [^Subject:spc(.*).*]. Ответ: ничего не изменится. Первое подвыражение [.*] (в круглых скобках) оказывается настолько жадным, что совпадает со всей темой сообщения, а на долю второго подвыражения [.*] ничего не остается. Отсутствие совпадающего текста в этом случае не вызывает проблем, поскольку ни одно повторение не является обязательным для *. Если бы второе подвыражение [.*] было также заключено в скобки, то переменная $2 всегда была бы пустой.
Означает ли это, что после [.*] в регулярном выражении не может быть ни одного элемента, для которого требуется реальное совпадение? Конечно, нет. Там могут находиться любые элементы, которые заставят предыдущий «жадный» квантификатор вернуть часть захваченного, необходимую для совпадения всего выражения.
Рассмотрим вполне реальное выражение<$M[R4-1]> [^.*([0-9][0-9])]. Оно находит две последних цифры в строке, где бы они ни располагались, и сохраняет их в переменной $1. Это происходит следующим образом: сначала [.*] сопоставляется со всей строкой. Следующее подвыражение [([0-9][0-9])] является обязательным, и отсутствие совпадения для него фактически означает: «Эй, ты взял лишнее! Верни мне что-нибудь, чтобы и для меня нашлось совпадение». «Жадные» компоненты всегда сначала стараются захватить побольше, но потом всегда отдают излишки, если при этом достигается общее совпадение. Впрочем, как истинные жадины, они упрямы и добровольно ничего не отдают. Конечно, никогда не уступаются обязательные части — например, первое совпадение квантификатора +.
Учитывая сказанное, применим [^.*([0-9][0-9])] к строке aboutspc24spccharactersspclong. После того, как [.*] совпадет со всей строкой, необходимость совпадения для первого класса [[0-9]] заставит [.*] уступить символ g (последний из совпавших). Однако при этом совпадение для [[0-9]] по-прежнему не находится, поэтому [.*] приходится идти на новые уступки — на этот раз это n в слове long. Цикл повторяется еще 15 раз, пока [.*] не доберется до цифры 4.
К сожалению, совпадение появляется лишь для первого класса [[0-9]]. Второму классу, как и прежде, совпадать не с чем. Поэтому [.*] приходится уступать дальше, чтобы обеспечить общее совпадение всего выражения. На этот раз [.*] уступает цифру 2, с которой может совпасть первый класс [[0-9]]. Цифра 4 освобождается и совпадает со вторым классом, а все выражение — с aboutspc24spcchar…. Переменной $1 присваивается строка «24».
Попробуем привести это регулярное выражение к виду [^.*([0-9]+)]. Идея состоит в том, чтобы найти не только две последние цифры, а все число независимо от длины. Однако такое решение не работает<$M[R4-2]>. Подвыражению [.*] снова приходится идти на частичные уступки, поскольку для совпадения всего выражения необходимо хотя бы одно совпадение для [[0-9]+]. Для строки aboutspc24spcchar…это означает возврат до цифры 4. Как и прежде, появляется совпадение для класса [[0-9]]. Но на этот раз никаких обязательных элементов дальше нет, поэтому [.*] не приходится уступать цифру 2. В принципе подвыражение [[0-9]+] с радостью согласилось бы на такой подарок, но нет — кто первым приходит, тот первым обслуживается. Жадные квантификаторы по-настоящему скупы — если что-то попало им в лапы, они отдадут это «что-то» только по принуждению, а не по доброте душевной.
Если такой подход кажется вам противоестественным, подумайте: [[0-9]+] всего на одно совпадение отличается от [[0-9]*], а это выражение из одной категории с [.*]. После подстановки выражение [^.*([0-9]+)] превращается в [^.*(.*)], которое подозрительно напоминает [^Subject:spc(.*).*] с предыдущей страницы.
Пожалуй, я должен кое-что пояснить. Фразы типа «[.*] уступает…» или [[0-9]] заставляет…» на самом деле неточны. Я воспользовался этими оборотами, потому что они достаточно наглядны и при этом приводят к правильному результату. Однако события, которые в действительности происходят за кулисами, зависят от базового типа механизма, ДКА или НКА. Пришло время узнать, что же означают эти термины.
В двух базовых типах механизмов регулярных выражений отражаются два принципиально разных подхода к сравнению регулярного выражения со строкой. Говорят, что механизм НКА «управляется регулярным выражением», а механизм ДКА «управляется текстом».
Рассмотрим один из алгоритмов<$M[R4-12]>, который может использоваться механизмом для поиска выражения [to(nite|knight|night)] в тексте «…tonight». Механизм просматривает регулярное выражение по одному компоненту, начиная с [t], и проверяет, совпадает ли компонент с «текущим текстом». В случае совпадения проверяется следующий компонент. Процедура повторяется до тех пор, пока не будет найдено совпадение для всех компонентов регулярного выражения; в этом случае мы считаем, что найдено общее совпадение.
В примере [to(nite|knight|night)] первым компонентом является литерал [t]. Проверка завершается неудачей до тех пор, пока в целевом тексте не будет обнаружен символ t. Когда это произойдет, [o] сравнивается со следующим символом, и в случае совпадения управление будет передано следующему компоненту. В данном случае следующим компонентом является конструкция выбора [(nite|knight|night)], которая означает «либо [nite], либо [knight], либо [night]». Столкнувшись с тремя альтернативами, механизм просто по очереди перебирает их. Мы, существа с хитроумными нейронными сетями в голове, сразу видим, что для строки tonight к совпадению приводит третья альтернатива. Но несмотря на свое интеллектуальное происхождение (см. с. <$R[P#,R3-9]>), механизм, управляемый регулярным выражением, придет к этому выводу лишь после перебора всех возможных вариантов.
Проверка первой альтернативы, [nite], подчиняется тому же принципу последовательного сравнения компонентов: «Сначала проверить [n], потом [i], затем [t], и наконец [e]». Если проверка завершается неудачей (как в нашем примере), механизм переходит к другой альтернативе и т. д. до тех пор, пока не будет найдено совпадение или не будут исчерпаны все варианты (тогда механизм сообщает о неудаче). Управление передается внутри регулярного выражения от компонента к компоненту, поэтому я говорю, что такой механизм «управляется регулярным выражением».
В механизме, управляемом регулярными выражениями, каждый компонент фактически проверяется независимо от других. В сущности, компоненты объединяет лишь то, что все они входят в одно регулярное выражение. Порядок компонентов управляет действиями механизма в процессе поиска совпадений.
Поскольку механизм НКА управляется регулярными выражениями, перед автором регулярного выражения открываются широкие возможности для регулировки процесса поиска (этой теме посвящена глава 5). Пока эта фраза выглядит довольно туманно, но ее смысл будет разъяснен после того, как перед вами откроется Великая Тайна (всего через пару страниц).
Механизму НКА противопоставляется механизм ДКА<$M[R4-13]>, который сканирует строку и следит за всеми «потенциальными совпадениями» В описанном выше примере с tonight механизм узнает о начале потенциального совпадения, как только в строке встречается символ t:
|
в строке |
в регулярном выражении |
|
after…tlwronight… |
потенциальные совпадения: [tlwro(nite|knight|night)] |
Каждый следующий сканируемый символ обновляет список потенциальных совпадений. Через несколько символов мы приходим к следующей ситуации:
|
в строке |
в регулярном выражении |
|
after…tonilwrght… |
потенциальные совпадения: [to(nilwrte|knight|nilwrght)] |
с двумя потенциальными совпадениями (одна альтернатива, knight, к этому моменту уже отвергается). Проверка следующего символа, g, исключает и первую альтернативу. После сканирования h и t механизм понимает, что он нашел полное совпадение и успешно завершает свою работу.
Механизм ДКА «управляется текстом», поскольку его работа зависит от каждого просканированного символа строки. В приведенном выше примере частичное совпадение быть началом любого количества разных (но потенциально возможных) совпадений. Отвергаемые совпадения исключаются из дальнейшего рассмотрения по мере сканирования последующих символов. Возможны даже ситуации, при которых «частичное потенциальное совпадение» является полным совпадением. Например, при обработке круглых скобок в выражении [to(…)?] полное совпадение (to) уже считается подтвержденным и держится в резерве на тот случай, если не удастся найти более длинное совпадение.
Если очередной символ текста аннулирует все потенциальные совпадения, приходится либо вернуться к полному совпадению, находящемуся в резерве, либо (при его отсутствии) — объявить, что для текущей начальной позиции совпадений нет.
<$M[R4-24]>Если сравнивать эти два механизма на основании только того, о чем я упоминал, нетрудно придти к выводу, что управляемый текстом механизм ДКА обычно работает быстрее. Механизм НКА, управляемый регулярным выражением, может тратить время на поиск разных подвыражений в одном тексте (см. пример с тремя альтернативами).
И это будет верно. При работе механизма НКА один символ целевого текста может сравниваться во многих разных компонентах регулярного выражения (или даже многократно в одном компоненте). Даже если подвыражение совпадает, возможно, его придется применять снова (а потом еще и еще), поскольку общее совпадение определяется в совокупности с остальными компонентами регулярного выражения. Локальное подвыражение может совпадать или не совпадать, но судить о наличии общего совпадения можно, лишь добравшись до конца регулярного выражения. С другой стороны, механизм ДКА является детерминированным — каждый символ в строке проверяется не более одного раза. Если символ совпал, вы еще не знаете, войдет ли он в итоговое совпадение (символ может быть частью потенциального совпадения, которое позднее будет отвергнуто), но поскольку механизм отслеживает все потенциальные совпадения одновременно, символ достаточно проверить только один раз. Точка.
Две базовые технологии, на основе которых строятся механизмы регулярных выражений, носят устрашающие названия<$M[R4-14]>: недетерминированный конечный автомат (НКА) и детерминированный конечный автомат (ДКА). Надеюсь, вы поняли, почему я предпочитаю использовать простые сокращения «НКА» и «ДКА». На страницах этой книги полные названия больше не встречаются[6].
Поскольку механизм НКА управляется регулярным выражением, при его использовании необходимо очень хорошо разбираться в том, как происходит поиск совпадений. Как я уже говорил, автор может в значительной степени управлять процессом поиска просто за счет правильного написания выражения. Вероятно, в примере c tonight для повышения эффективности поиска можно было бы записать регулярное выражение в виде [to(ni(ght|te)|knight)], [tonite|toknight|tonight] или даже [to(k?night|nite)]. Эти регулярные выражения эквивалентны с точки зрения совпадающего текста, но при этом они по-разному управляют работой механизма. Пока вы еще недостаточно хорошо разбираетесь в регулярных выражениях и не можете судить, какие варианты работают эффективнее других, но вскоре мы займемся этой темой.
В ДКА все наоборот — поскольку механизм отслеживает все совпадения одновременно, любые различия в представлении несущественны, если они в конечном счете определяют один и тот же совпадающий текст. Можно придумать сотню эквивалентных выражений, но поскольку ДКА следит за всеми потенциальными совпадениями (почти волшебным образом — но об этом позднее), конкретный вид представления несущественен. Для «чистого» ДКА даже такие разные выражения, как [abc] и [[aa-a](b|b{1}|b)c], попросту неразличимы.
При описании механизма ДКА я бы выделил три обстоятельства<$M[R4-19]>:
l Совпадения в ДКА ищутся очень быстро.
l Процесс поиска совпадений в ДКА предсказуем и логичен.
l Описывать поиск в ДКА скучно.
Вскоре мы вернемся к этой теме и рассмотрим ее подробнее.
Механизм НКА управляется регулярным выражением, поэтому писать о нем интересно — НКА открывает настоящую свободу для творчества. Правильное построение выражений приносит большую пользу, хотя ошибка может принести еще больший вред. Механизм, как и бензиновый двигатель, тоже может расчихаться и полностью заглохнуть. Но чтобы досконально разобраться во всех тонкостях НКА, необходимо рассмотреть одну из важнейших концепций этого механизма — возврат (backtracking).
<$M[R4-20]>Основной принцип работы механизма НКА заключается в следующем: он последовательно рассматривает все подвыражения или компоненты, и когда приходится выбирать между двумя равноправными вариантами — выбирает один вариант и запоминает другой, чтобы позднее вернуться к нему в случае необходимости. Если выбранный вариант и все выражение успешно совпадают, процесс поиска завершается. Если какая-либо из оставшихся частей регулярного выражения приводит к неудаче, механизм регулярных выражений возвращается к развилке, где было принято решение, и продолжает поиск с другим вариантом. В конечном счете механизм перепробует все возможные сочетания компонентов (или по крайней мере столько сочетаний, сколько потребуется для успешного совпадения).
Представьте себе, что вы ищете выход из лабиринта. На каждой развилке вы оставляете горку хлебных крошек. Если выбранный путь приводит к тупику, вы поворачиваете назад и на ближайшей развилке сворачиваете на дорогу, по которой еще не ходили. Если и эта дорога закончится тупиком, вы возвращаетесь к следующей горке хлебных крошек. В конце концов вы либо найдете дорогу, которая приведет вас к цели, либо переберете все возможные пути.
Существуют разные ситуации, при которых механизму регулярных выражений приходится выбирать один из двух (или более) вариантов. Конструкция выбора является лишь одним из примеров. Другой пример — встретив конструкцию […x?…], механизм решает, искать [x] в тексте или нет. Для […x+…] такого вопроса не возникает — квантификатор + требует хотя бы одного обязательного совпадения, и это требование обсуждению не подлежит. Но если первое совпадение для [x] будет найдено, обязательное требование снимается, и механизм должен решить, следует ли ему искать другие повторения [x]. Если будет найдено второе совпадение, механизм решает, нужно ли искать дальше… и дальше… и т. д. Каждый раз, когда механизм принимает решение, он оставляет воображаемую «кучку крошек», которая напоминает о том, что в этой точке остается другой возможный вариант (совпадение или его отсутствие — тот вариант, который не был выбран ранее).
Рассмотрим поиск знакомого выражения [to(nite|knight|night)] в строке «hotspctonicspctonight!» (фраза, конечно, глупая, но зато хороший пример). Первый компонент [t] сравнивается с началом строки. Он не совпадает с h, поэтому в этой позиции все регулярное выражение заведомо не совпадет. Механизм перемещается ко второму символу регулярного выражения, где совпадение тоже не обнаруживается. Затем наступает очередь третьего символа. На этот раз [t] совпадает, но следующий символ [o] отличается от «spc» в тексте, поэтому эта попытка тоже завершается неудачей.
Попытка, начинающаяся с …lwrtonic…, представляет больший интерес. После совпадения to появляются три возможных варианта, соответствующие трем разным альтернативам. Механизм регулярных выражений выбирает одну альтернативу и запоминает остальные («оставляет хлебные крошки») на случай, если первая попытка окажется неудачной. Предположим, механизм начал с альтернативы [nite]. Это выражение делится на «[n] + [i] + [t] …», и процесс поиска и добирается до символа …tonilwrc…, где происходит расхождение. В отличие от предыдущих неудач, эта не означает перехода к следующей позиции, поскольку остались другие возможные варианты. Механизм выбирает один из них (скажем, [knight]), но и здесь происходит немедленная неудача. Остается последний вариант, [night]. Совпадение не происходит и на этот раз. Поскольку это был последний неопробованный вариант, неудача означает неудачу всей попытки, начинающейся с …lwrtonic…, поэтому механизм переходит к следующей позиции.
Ситуация снова становится интересной, когда механизм начинает поиск совпадения с позиции …lwrtonight!… На этот раз альтернатива [night] совпадает до самого конца. Наличие совпадения до конца регулярного выражения означает общее совпадение, поэтому механизм прекращает дальнейшие поиски.
Концепция возврата выглядит довольно просто, но для ее применения на практике необходимо учитывать некоторые технические детали. Во-первых, какой вариант из нескольких возможных должен проверяться в первую очередь? Во-вторых, какой из сохраненных вариантов должен использоваться механизмом при возврате?
l В тех ситуациях, где механизм выбирает между попытками найти совпадение или отказаться от его поиска (например, при использовании квантификаторов ?, * и т. д.), механизм всегда сначала пытается найти совпадение. Позднее он может вернуться, чтобы попытаться пропустить необязательный элемент, но лишь в том случае, если это необходимо для общего совпадения на уровне выражения.
Это простое правило имеет далеко идущие последствия. Во-первых, оно частично объясняет принцип максимализма в регулярных выражениях. Для полноты картины необходимо знать, какой из сохраненных вариантов должен выбираться при возврате. Простой ответ выглядит так:
l При локальной неудаче происходит возврат к последнему из сохраненных вариантов. Перебор вариантов осуществляется по правилу LIFO (последним пришел — первым обслужен).
Это правило легко понять по нашей аналогии с крошками — оказавшись в тупике, вы просто идете в обратную сторону до тех пор, пока не наткнетесь на горку хлебных крошек. На вашем пути первой встретится та горка, которая была оставлена последней. При описании LIFO также часто используется классическая аналогия со стопкой тарелок: первой со стопки снимается та тарелка, которая была поставлена в нее последней.
НКА: теория и практика
<$M[R4-35]>Настоящий математический смысл «НКА» отличается от того, что обычно называется «механизмом НКА» применительно к регулярным выражениям. Теоретически механизмы НКА и ДКА должны обеспечивать совпадение с одним и тем же текстом и обладать абсолютно одинаковыми возможностями. На практике необходимость в богатом, более выразительном синтаксисе привела к расхождению их семантик<$M[R4-8]>. Некоторые примеры будут приведены ниже, но один пример лежит прямо на поверхности — я говорю о поддержке обратных ссылок.
Если вы действительно хорошо (с математических позиций) разбираетесь в механизме НКА, то с позиций программирования организовать поддержку обратных ссылок не так уж сложно. Принцип работы механизма ДКА не позволяет реализовать эту возможность, но в стандартной реализации НКА она реализуется элементарно. В этом случае программа обогащается новыми возможностями, но в математическом смысле она становится нерегулярной. Что это означает? Вероятно, то, что вы должны перейти к термину «нерегулярные выражения», поскольку с математической точки зрения он точнее описывает новую ситуацию. Использовать термин НКА по отношению к этому механизму тоже не совсем корректно. Но в действительности подобные формальности не соблюдаются, а термин «НКА» продолжает существовать, хотя с математических позиций реализация уже не отвечает принципам НКА.
Что все сказанное означает для пользователя? Абсолютно ничего. Пользователя не интересует, является ли выражение регулярным, нерегулярным или каким-нибудь еще. Если вы понимаете, к какому результату оно приводит, то будете знать, за чем следует особо проследить.
В терминологии регулярных выражений РКА «хлебные крошки» на развилках называются сохраненными состояниями (saved states). Сохраненное состояние определяет точку, с которой при необходимости можно начать очередную проверку. В нем сохраняется как текущая позиция в регулярном выражении, так и позиция в строке, с которой начинается проверка. Поскольку сохраненные состояния образуют основу для работы механизма НКА, позвольте мне пояснить сказанное на простых, но поучительных примерах. Если вы и так понимаете, как работают сохраненные состояния, то следующий раздел можно пропустить.
Рассмотрим простой пример — поиск выражения [ab?c] в строке abc. После совпадения a текущее состояние выглядит следующим образом:
|
в строке: «alwrbc» |
в выражении: [alwrb?c] |
Но теперь, перед поиском [b?], механизм должен принять решение — пытаться найти [b] или нет? Из-за своей жадности квантификатор ? начинает искать совпадение. Но для того, чтобы в случае неудачи он мог вернуться к этой точке, в пустой список сохраненных состояний добавляется следующая запись:
|
в строке: «alwrbc» |
в выражении: [ab?lwrc] |
Это означает, что механизм позднее продолжит поиск с компонента, следующего в регулярном выражении после [b?], и сопоставит его с текстом, находящимся до b (то есть в текущей позиции). В сущности, это означает, что литерал [b] пропускается, как допускает квантификатор ?.
Успешно разместив «горку хлебных крошек», механизм переходит к проверке [b]. В нашем примере для него находится совпадение, поэтому новое текущее состояние выглядит так:
|
в строке: «ablwrc» |
в выражении: [ab?lwrc] |
Последний компонент, [c], тоже совпадает. Следовательно, механизм нашел общее совпадение для всего регулярного выражения. Единственное сохраненное состояние становится ненужным, и механизм попросту забывает о нем.
Если бы поиск производился в строке «ac», все происходило бы точно так же до попытки найти совпадение для [b]. Конечно, на этот раз совпадение не обнаруживается. Попытка найти подвыражение, которое может отсутствовать в строке, завершилась неудачей. Поскольку у нас имеется сохраненное состояние, к которому можно вернуться, «локальная неудача» вовсе не означает общей неудачи. Механизм возвращается к последнему сохраненному состоянию и превращает его в новое текущее состояние. В нашем примере восстанавливается состояние
|
в строке: «alwrc» |
в выражении: [ab?lwrc] |
сохраненное перед поиском [b]. На этот раз [c] и c совпадают, что обеспечивает общее совпадение.
Рассмотрим поиск того же регулярного выражения в строке «abX». Перед попыткой поиска [b] квантификатор ? сохраняет состояние
|
в строке: «alwrbX» |
в выражении: [ab?lwrc] |
Совпадение для [b] находится, однако этот путь позднее оказывается тупиковым, поскольку [c] не совпадает с X. Неудача приводит к восстановлению сохраненного состояния. Механизм сравнивает [c] с символом b, «выпавшим» из совпадения в результате возврата. Разумеется, и эта проверка завершается неудачей. При наличии других сохраненных состояний произошел бы следующий возврат, но таких состояний нет, поэтому попытка найти совпадение в текущей начальной позиции завершается неудачей.
Работа закончена? Нет. Механизм перемещается к следующей позиции в строке и снова пытается применить регулярное выражение. Происходит своего рода «псевдо-возврат». Исходное состояние для повторного поиска выглядит так:
|
в строке: «alwrbX» |
в выражении: [lwrab?c] |
Весь поиск повторяется с новой позиции, но, как и прежде, все пути ведут к неудаче. После провала еще двух попыток (с позиций ablwrX и abXlwr) механизм сообщает о том, что совпадение для всего выражения найти не удалось.
При работе с программами, использующими средства возврата механизма НКА, необходимо хорошо понимать, как происходит возврат<$M[R4-21]>. Это позволяет создавать выражения, которые решают нужную задачу и притом с максимальной эффективностью. Вы уже видели, как действует принцип максимализма для квантификатора [?]. Давайте посмотрим, как этот принцип проявляется для квантификаторов * и +.
Если рассматривать выражение [x*] как более или менее эквивалентное [x?x?x?x?x?x?…] (а точнее, [x(x(x(x…?)?)?)?)?])[7], этот квантификатор не так уж сильно отличается от того, что вы уже видели. Прежде чем проверять очередной символ, механизм сохраняет состояние на случай неудачи при проверке (или последующих проверках), чтобы поиск совпадений можно было продолжить после *. Это происходит снова и снова, пока попытка сопоставления * не завершится неудачей.
Например, при поиске [[0-9]+] в строке «aspc1234spcnum» класс [[0-9]] не совпадает с пробелом после 4. К этому моменту появляется четыре сохраненных состояния, показывающих, что поиск совпадения может быть продолжен в позиции регулярного выражения [[0-9]+lwr] для каждой из следующих позиций в строке:
a 1lwr234 num
a 12lwr34 num
a 123lwr4 num
a 1234lwr num
В сохраненных состояниях отражается тот факт, что наличие совпадения для [[0-9]] в каждой из перечисленных позиций было необязательным. Когда [[0-9]] не совпадает с пробелом, механизм возвращается к самому новому из сохраненных состояний (последнему из перечисленных) и продолжает работу с позиции «a 1234lwr num» в тексте и [[0-9]+lwr] в регулярном выражении. Однако текущая позиция уже находится в конце регулярного механизма. Заметив это, механизм понимает, что он нашел общее совпадение.
Обратите внимание: строка «a lwr1234 num» отсутствует среди перечисленных, поскольку первое совпадение для квантификатора + является обязательным. Как вы думаете, будет ли она присутствовать она в списке для регулярного выражения [[0-9]*]? (Внимание — каверзный вопрос!)ref<$M[R4-3]>Переверните страницу, чтобы проверить ответ.
После всего сказанного давайте вернемся к примеру [^.*([0-9][0-9])] со с. <$R[P#,R4-1]>. На этот раз для объяснения того, почему поиск производится именно так, а не иначе, мы не будем ссылаться на «жадность». Знание механики поиска позволяет точно описать все происходящее (если от подробностей у вас голова идет кругом, попробуйте уловить общий смысл этой главы — позднее вы всегда сможете вернуться к примерам и разобрать их более подробно).
В качестве примера будет использована строка «CAspc95472,spcUSA». После успешного совпадения [.*] до конца строки в списке сохраненных состояний оказывается 12 записей. Сохраненные состояния накапливаются из-за того, что точка с квантификатором * совпала с 12 элементами, которые (при необходимости) могут оказаться необязательными. Это позволяет продолжить подбор вариантов совпадения с позиции выражения [^.*lwr([0-9][0-9])] и каждой позиции в строке, для которой сохранялось состояние.
Механизм достигает конца строки и передает управление первому классу [[0-9]]. Конечно, попытка найти совпадение проваливается. Нет проблем: у нас в запасе есть сохраненное состояние (даже целая дюжина состояний). Происходит возврат, и механизм восстанавливает то состояние, которое был сохранено последним — то есть перед тем, как подвыражение [.*] совпало с последним A. Отказ от этого совпадения позволит нам сравнить A с первым классом [[0-9]]. Попытка оказывается неудачной.
Возвраты и проверки в цикле продолжаются до тех пор, пока механизм не отменит совпадение для цифры 2. В этот момент для первого класса [[0-9]] находится совпадение. Однако второму классу совпадать не с чем, поэтому возврат продолжается. При этом механизм забывает, что первый класс [[0-9]] совпал при предыдущей попытке — в восстановленном состоянии поиск продолжается с позиции перед первым классом [[0-9]]. В результате возврата текущая позиция в строке перемещается перед цифрой 7, поэтому для первого класса [[0-9]] снова находится совпадение. Но на этот раз оно находится и для второго класса (цифра 2). Таким образом, в строке обнаруживается совпадение: «CAspc95472,spcUSA», а переменной $1 присваивается 72.
Несколько замечаний: во первых, в процессе возврата также обновляется информация о тексте, совпавшем с подвыражениями в круглых скобках. В приведенном примере возврат всегда приводил к возобновлению поиска с позиции [^.*lwr([0-9][0-9])]. В том, что касается простого поиска совпадений, это выражение эквивалентно [^.*lwr[0-9][0-9]], поэтому я использовал такие обороты, как «…продолжается с позиции перед первым классом [[0-9]]». Однако при перемещении текущей позиции в круглые скобки и за их пределеы обновляется информация о том, какой текст попадает в $1, а это влияет на эффективность. Этот вопрос подробно рассматривается в следующей главе (с. <$R[P#,R5-4]>).
Необходимо понимать, что для конструкции, к которой применяется * (или любой другой квантификатор), сначала находится как можно больше совпадений независимо от того, что следует за ней в регулярном выражении. В нашем примере [.*] не остановится у первой цифры, у предпоследней цифры или в любом другом месте до тех пор, пока поиск совпадения не завершится неудачей. Об этом уже говорилось ранее, когда мы говорили о том, что выражение [^.*([0-9]+)] в части [[0-9]+] никогда не совпадет более чем с одной цифрой (с. <$R[P#,R4-2]>).
С чем совпадает [[0-9]*]
bref Ответ на вопрос со с. <$R[P#,R4-3]>
Нет, «a lwr1234 num» не будет включена в сохраненные состояния при поиске совпадения для [[0-9]*]. Я задал этот вопрос, поскольку многие новички допускают эту ошибку.
Вспомните: компонент, содержащий *, совпадает всегда. Если регулярное выражение не содержит других компонентов, то и для него всегда найдется совпадение. Конечно, этому правилу подчиняется и самая первая попытка, когда регулярное выражение применяется от начала строки. В этом случае механизм находит совпадение в позиции «lwra 1234 num», и на этом все кончается — до цифр он даже не доходит.
Многие хорошие (и плохие) стороны принципа максимального захвата присущи как НКА, так и ДКА. Я хочу рассмотреть некоторые аспекты максимализма для обоих механизмов, но на примерах, относящихся к НКА. Все сказанное также относится и к ДКА, но по другим причинам. ДКА стремится к максимальному захвату, и точка — говорить здесь больше не о чем. Его работа отличается редкостным постоянством, но писать об этом скучно. С другой стороны, механизм НКА интересен именно творческими возможностями, которые обусловлены самой природой механизма, управляемого регулярным выражением. НКА позволяет автору регулярного выражения непосредственно управлять процессом поиска совпадений. При этом открывается немало полезных возможностей, но не обходится и без подвохов, связанных с эффективностью (проблемы эффективности обсуждаются в следующей главе).
Несмотря на все отличия, поиск часто приносит одинаковые результаты. На нескольких ближайших страницах я буду говорить о механизмах обоих типов, но в примерах буду использовать более понятную терминологию поиска НКА, управляемого регулярными выражениями. К концу главы вы будете четко представлять себе, в каких случаях результаты могут различаться, а также почему это происходит.
Как было показано в последнем примере, [.*] всегда распространяет совпадение до конца строки[8]. Это связано с тем, что [.*] думает только о себе и стремится захватить все, что может. Впрочем, позднее часть захваченного может быть возвращена, если это необходимо для общего совпадения.
Иногда это поведение вызывает немало проблем. Рассмотрим регулярное выражение для поиска текста, заключенного в кавычки. На первый взгляд напрашивается простое [".*"], но попробуйте на основании того, что нам известно о [.*], предположить, какое совпадение будет найдено в строке:
The name "McDonald's" is said "makudonarudo" in Japanese
Вообще говоря, поскольку вы понимаете механику поиска совпадений, предполагать не нужно — вы просто знаете правильный ответ. После совпадения первого символа " управление передается конструкции [.*], которая немедленно захватывает все символы до конца строки. Она начинает нехотя отступать (под нажимом механизма регулярных выражений), но только до тех пор, пока не будет найдено совпадение для последней кавычки. Если прокрутить происходящее в голове, вы поймете, что найденное совпадение будет выглядеть так:
The name "McDonald's" is said "makudonarudo" in Japanese
Найден совсем не тот текст, который мы искали. Это одна из причин, по которым я не рекомендую злоупотреблять [.*] — если не учитывать проблем максимального совпадения, эта конструкция часто приводит к неожиданным результатам.
Как же ограничить совпадение строкой «McDonald's»? Главное — понять, что между кавычками должно находиться не «все, что угодно», а «все, что угодно, кроме кавычек». Если вместо [.*] воспользоваться выражением [[^"]*], совпадение не пройдет дальше закрывающей кавычки.
При поиске совпадения для [[^"]*] механизм ведет себя практически так же. После совпадения первой кавычки [[^"]*] стремится захватить как можно большее потенциальное совпадение. В данном случае это совпадение распространяется до кавычки, следующей после «McDonald's». На этом месте поиск прекращается, поскольку [[^"]] не совпадает с кавычкой, после чего управление передается закрывающей кавычке в регулярном выражении. Она благополучно совпадает, обеспечивая общее совпадение:
The name "McDonald's" is said "makudonarudo" in Japanese
В первой главе я упоминал о задаче поиска тегов HTML. Скажем, в последовательности<$M[R4-11]> …<B>very</B>… слово «very» выводится жирным шрифтом, если браузер на это способен. Задача поиска последовательности <B>…</B> на первый взгляд похожа на поиск строк, заключенных в кавычки. Правда, в роли «кавычек» на этот раз выступают многосимвольные последовательности <B> и </B>. Как и в предыдущем примере, повторяющиеся «кавычки» порождают проблемы при поиске:
…<B>Billions</B> and <B>Zillions</B> of suns…
Если воспользоваться выражением [<B>.*</B>], жадное подвыражение [.*] распространяет текущее совпадение до конца строки и отступает лишь до тех пор, пока не найдется совпадение для </B>. В результате вместо тега, парного открывающему <B>,совпадает последний тег </B>.
К сожалению, завершающий ограничитель состоит из нескольких символов, поэтому решение, использованное для поиска строк в кавычках, здесь не подходит. Конечно, смехотворные попытки типа [<B>[^</B>]*</B>] не годятся. Символьный класс представляет только один символ, а нам нужна последовательность </B>[9].
Эта проблема возникает лишь в том случае, если * и другие квантификаторы работают по максимальному принципу. На секунду давайте представим, что они ведут себя «минимально» («нежадно», «щедро», «лениво» и т. д. — называйте, как хотите). Вернемся к описанному выше примеру с выражением [<B>.*</B>] и текстом
…<B>Billions</B> and <B>Zillions</B> of suns…
Если квантификатор работает по минимальному принципу, после совпадения начального [<B>] он немедленно решает, что обязательные совпадения не требуются, а раз так — не стоит и возиться с дальнейшими поисками. Поэтому управление немедленно передается [<].
На этой стадии [<] не совпадает, поэтому управление возвращается «ленивой» конструкции [.*], у которой остались непроверенные варианты поиска совпадения (точнее говоря, многих совпадений). Квантификатор неохотно берется за дело, и точке предлагается совпадение …<B>Billions… И снова * может либо продолжить захват, либо остановиться. В нашем примере квантификатор стремится к минимальному захвату, поэтому сначала он останавливается. Сравнение следующего элемента [<] завершается неудачей, поэтому [.*] снова переходит к непроверенному варианту совпадения. После восьми итераций [.*] распространится на Billions, и в этот момент появится возможность совпадения последующего [<] (и всего подвыражения [</B>]):
…<B>Billions</B> and <B>Zillions</B> of suns…
Как вы убедились, максимализм * и других квантификаторов в одних случаях приносит пользу, а в других — одни хлопоты. Минимальные, «ленивые» версии квантификаторов очень удобны, поскольку с их помощью можно решать задачи, которые другими средствами решаются с большим трудом (или вообще не решаются). Оказывается, помимо обычных максимальных квантификаторов в Perl существуют и минимальные квантификаторы. Как и все великие изобретения, они основаны на простой идее; просто нужно дождаться, пока эта идея придет кому-нибудь в голову (в данном случае это создатель Perl, Ларри Уолл).
К сожалению, если вы не работаете на Perl и минимальная версия квантификатора * вам недоступна, проблема с поиском многосимвольных ограничителей <B>…</B> остается открытой. Честно говоря, при помощи простых, стандартных регулярных выражений ее решить очень трудно. Я рекомендую разделить ее на две части: сначала найти начальный ограничитель, а затем от найденной позиции переходить к поиску конечного ограничителя.
Вспомните проблему с округлением денежных величин из главы 2 (с. <$R[P#,R2-6]>). Из-за специфики представления вещественных чисел величины «1.625» или «3.00» иногда превращались в «1.625000000002828» или «3.00000000028822». Решение задачи выглядело так:
$price =~ s/(\.\d\d[1-9]?)\d*/$1/
Команда удаляет все цифры, кроме первых двух или трех, из дробной части числа, хранящегося в переменной $price. Подвыражение [\.\d\d] всегда совпадает с первыми двумя цифрами, а [[1-9]?] совпадает с третьей цифрой лишь в том случае, если она отлична от нуля.
Затем я написал следующее:
l …Все совпавшие до настоящего момента символы образуют часть, которую мы хотим оставить, поэтому они заключаются в круглые скобки для сохранения в переменной $1. Затем значение $1 используется в строке замены. Если ничего больше не совпало, строка заменяется сама собой — не слишком интересно. Однако вне круглых скобок $1 продолжается поиск других символов. Эти символы не включаются в строку замены и поэтому они фактически удаляются из числа. В данном случае «удаляемый» текст состоит из всех дальнейших цифр, то есть [\d*] в конце регулярного выражения.
Все это, конечно, хорошо. Но давайте посмотрим, что произойдет, если содержимое переменной $price уже имеет правильный формат. Для числа 27.625 подвыражение<$M[R4-5]> [(\.\d\d[1-9]?)] совпадает со всей дробной частью. Поскольку завершающая конструкция [\d*] не совпадает ни с чем, подстановка заменяет «.625» строкой «.625» — в сущности, не происходит ровным счетом ничего.
Конечно, мы добиваемся нужного результата, но не лучше ли выполнять замену лишь в том случае, если она обеспечивает какой-то реальный эффект? В таких случаях [\d*] совпадает хотя бы с одной цифрой, которая будет удалена из результата.
Но мы же знаем, как записать «хотя бы одну цифру»! Достаточно заменить [\d*] на [\d+]:
$price =~ s/(\.\d\d[1-9]?)\d+/$1/
Для ненормальных чисел типа «1.625000000002828» все работает так же, как раньше, но для числа «9.43» завершающее подвыражение [\d+] совпасть не может, и подстановка в этом случае не выполняется. Отличная замена, да? Нет! Что происходит с числами, у которых дробная часть состоит из трех цифр (например, 27.625)?
Ненадолго задержитесь и попробуйте самостоятельно вычислить результат для числа 27.625.
На самом деле задача очень проста. Продолжив поиск с того момента, когда выражение [(\.\d\d[1-9]?)\d+] совпало с 27.625, мы выясняем, что для [\d+] совпадение не находится. Механизм регулярных выражений это вполне устраивает, поскольку совпадение [[1-9]] с 5 было необязательным, и у него в запасе имеется сохраненное состояние, которое еще не было проверено. В этом варианте [[1-9]?] не совпадает ни с чем, а цифра 5 используется для обязательного совпадения [\d+]. Таким образом, мы получаем совпадение, но только неправильное: .625 заменяется на .62, и значение становится неверным.
Мораль: совпадению всегда отдается предпочтение перед несовпадением. В частности, это относится и к отдаче максимальным квантификатором того, что необходимо для достижения общего совпадения<$M[R4-41]>[10].
<$M[R4-23]>Единственным важным элементом, который мы еще не рассматривали, является конструкция выбора, [|]. Принцип обработки конструкции выбора играет важную роль, поскольку в разных механизмах она может обрабатываться совершенно различными способами. При передаче управления конструкции выбора в строке может совпасть любое количество из перечисленных альтернатив, но какой из них будет отдано предпочтение? Второе правило регулярных выражений относится к квантификаторам (* и т. д.), но не к конструкции выбора. Итак, максимальна ли конструкция выбора?
Рассмотрим механизм НКА. Столкнувшись с конструкцией выбора, он последовательно проверяет все альтернативы. Вы можете быть уверены в том, что альтернативы проверяются в порядке их перечисления в выражении. Рассмотрим выражение [^(Subject|Date):spc]. Когда механизм достигает конструкции выбора, он пытается найти совпадение для первой альтернативы, [Subject]. Если совпадение будет найдено, проверяется оставшаяся часть регулярного выражения, [:spc]. Если выяснится, что общее совпадение невозможно, и при этом остаются другие непроверенные альтернативы (в данном случае [Date]), механизм регулярных выражений возвращается и проверяет их. Это еще один случай, когда механизм возвращается к точке с непроверенными вариантами. Перебор продолжается до тех пор, пока не будет найдено общее совпадение, или пока не закончатся все варианты (в данном случае — альтернативы).
Какой текст совпадет с выражением [tour|to|tournament], примененным к строке «threespctournamentsspcwon»? Механизм пробует применить все альтернативы (неудачно) во всех позициях выражения — в первой, второй, третьей и т. д., до тех пор, пока не будет достигнута позиция «threespclwrtournamentsspcwon». На этот раз совпадает первая альтернатива, [tour]. Поскольку конструкция выбора завершает регулярное выражение, в момент совпадения [tour] совпадает все регулярное выражение. Другие альтернативы даже не рассматриваются.
Итак, мы видим, что конструкция выбора не максимальна — по крайней мере, в НКА… точнее говоря, не в традиционном НКА. Максимальная конструкция выбора совпала бы с самой длинной возможной альтернативой ([tournament]) независимо от ее положения в списке. В механизме POSIX НКА или ДКА именно это бы и произошло, но я опережаю события.
Чтобы убедиться в том, что вы поняли сказанное, позвольте спросить: как должна выглядеть конструкция выбора, совпадающая с тем же текстом, что и [to(ur(nament)?)?]? Прежде чем отвечать на этот вопрос, убедитесь в том, что вы понимаете логическую эквивалентность этих конструкций: каждая из них совпадает с tour, to или tournament, и ни с чем более. Фактически вопрос заключается в следующем: какой текст совпадет с [to(ur(nament)?)?] — tour (минимальная[11] конструкция выбора), tournament (максимальная конструкция выбора) или что-нибудь еще? ref<$M[R4-6]>Переверните страницу, чтобы проверить ответ.
Вернемся к примеру [(\.\d\d[1-9]?)\d*] со с. <$R[P#,R4-5]>. Если вы поймете, что [\.\d\d[1-9]?] фактически означает «либо [\.\d\d], либо [\.\d\d[1-9]]», все выражение можно записать в виде [(\.\d\d|\.\d\d[1-9])\d*] (для подобных изменений особых причин нет — это всего лишь удобный пример). Но действительно ли оно эквивалентно [(\.\d\d[1-9]?)\d*]? Для максимальной конструкции выбора это действительно так, но для минимального выбора результат будет разным.
Начнем с минимальной конструкции. Если первая альтернатива, [\.\d\d], совпадает, то и следующее подвыражение [\d*] заведомо совпадет. Может быть, в совпадение будет включена и отличная от нуля цифра (если вспомнить исходную задачу, это та самая цифра, которая должна совпадать только внутри круглых скобок). Также необходимо понять, что вторая альтернатива начинается с копии первой альтернативы — если первая альтернатива не совпадает, то и вторая не совпадет. Впрочем, механизм регулярных выражений все же попытается найти для нее совпадение, но вопросы эффективности мы оставим до следующей главы.
Один интересный момент: если использовать выражение [(\.\d\d[1-9]|\.\d\d)\d*], полностью идентичное предыдущему, но с переставленными альтернативами, мы фактически получим копию исходного выражения [(\.\d\d[1-9]?)\d*]. В этом случае перестановка осмыслена — если первая альтернатива завершится неудачей из-за [[1-9]], у второй альтернативы еще остаются шансы.
Распределив [[1-9]?] по двум альтернативам и поставив более короткую альтернативу в начало, мы в каком-то отношении смоделировали минимальный квантификатор [?]. В данном примере это все равно бессмысленно — если первая альтернатива не совпадает, то и вторая совпасть никак не сможет. Подобный «ложный выбор» мне встречается довольно часто, и неизменно он является ошибкой. В одной из книг, которые я читал, выражение [a*((ab)*|b*)] использовалось в качестве примера при описании чего-то, относящегося к регулярным выражениям. Глупый пример, не правда ли? Поскольку первая альтернатива, [(ab)*], никогда не может завершиться неудачей, все остальные альтернативы (в нашем случае только [b*]) абсолютно бессмысленны. С таким же успехом можно добавить:
[a*((ab)*|b*|.*|partridgespcinspcaspcpearspctree|[a-z])]
От этого смысл выражения нисколько не изменится.
Минимальную конструкцию выбора часто можно использовать с выгодой для себя и построить в точности такое выражение, которое вам нужно, однако для непосвященных минимальный выбор оборачивается неожиданными затруднениями. Допустим, вы ищете в строке январскую дату в формате «Jan 31». Для этого потребуется что-нибудь более изощренное, чем [Janspc[0123][0-9]], поскольку при этом будут найдены «даты» «Jan 00» и «Jan 39», но потеряются вполне нормальные даты типа «Jan 7».
Максимально ли работает [to(ur(nament)?)?]
bref Ответ на вопрос со с. <$R[P#,R4-6]>
После совпадения исходного [to] общее совпадение гарантировано, поскольку ни один из следующих элементов регулярного выражения не является обязательным. Хотя в итоге эта часть может быть принята за окончательное совпадение, механизм еще не может принять решение, поскольку существует непроверенная возможность найти больше — квантификаторы ? максимальны, поэтому они всегда пытаются найти совпадение для квантифицируемого элемента.
Подвыражение [(ur(nament)?)], квантифицируемое внешним вопросительным знаком, всегда совпадает, если это возможно; находящееся внутри него подвыражение [nament] тоже по возможности совпадает. Следовательно, по возможности находится совпадение для всей конструкции [to] + [ur] + [nament]. На практике она совпадает с тем же текстом, что и [tour|to|tournament] при максимальном выборе — то есть с самым длинным из всех возможных.
Один из простых способов поиска даты заключается в том, чтобы разделить ее на секции. От 1 до 9 января используется подвыражение [0?[1-9]], допускающая начальный ноль. Подвыражение [[12][0-9]] обеспечивает поиск чисел с 10-го по 29-е, а [3[01]] находит оставшиеся числа месяца. Объединив эти подвыражения в конструкцию выбора, мы получаем [Janspc(0?[1-9]|[12][0-9]|3[01])]<$M[R4-10]>.
Как вы думаете, с чем это выражение совпадет в строке «Jan 31 is my dad's birthday»? Конечно, мы хотим, чтобы оно совпало с «Jan 31», но минимальный выбор обеспечивает совпадение только с «Jan 3». Удивлены? Во время проверки первой альтернативы, [0?[1-9]], начальное подвыражение [0?] не совпадает, но альтернатива в целом подходит, поскольку следующий элемент [[1-9]] совпадает с 3. Выражение на этом заканчивается, и общее совпадение считается найденным.
Если бы порядок альтернатив был другим, или конструкция выбора была максимальной, эта проблема не возникла бы. Другое решение задачи с поиском даты выглядит так: [Janspc(31|[123]0|[012]?[1-9])]. Как и в первом решении, проблемы обходятся продуманным порядком альтернатив. Впрочем, существует и третье решение, [Janspc(0[1-9]|[12][0-9]?|3[01]?|[4-9])], которое работает правильно при любом порядке. Сравнительный анализ этих трех выражений — довольно интересное занятие (это упражнение остается читателю для самостоятельной работы, хотя приведенная ниже врезка «Разные способы поиска даты» поможет вам в этом).
Как вы убедились, минимальная конструкция выбора по своим возможностям превосходит максимальную, поскольку она позволяет лучше контролировать процесс поиска совпадений — она означает не «Попробуй один из этих вариантов», а «Попробуй этот вариант, затем этот, и наконец этот».
В НКА конструкция выбора порождает большое количество возвратов, и поиск возможностей для уменьшения их числа обычно делает выражение более эффективным, что означает более высокую скорость выполнения. Вскоре мы рассмотрим некоторые примеры, и еще несколько примеров будет приведено в следующей главе.
Разные способы поиска даты
На этом рисунке продемонстрированы разные решения задачи с поиском даты, описанной выше. Разными цветами на календаре обозначены числа, соответствующие каждой альтернативе.
вставить рисунок<f115-01>
Из-за поверхностного сходства между [[abc]] и [a|b|c] может возникнуть впечатление, что символьные классы реализуются похожим образом, но в НКА ничего не может быть дальше от истины. В ДКА способ записи не важен, но в НКА<$M[R4-40]> символьный класс представляет собой атомарную единицу, которая действует как «решето» и пропускает символ лишь в том случае, если он совпадает с одним из указанных символов. Фактически все проверки при этом происходят параллельно. Этот процесс гораздо эффективнее аналогичной конструкции выбора НКА, при которой последовательно проверяется каждая альтернатива (что связано с большим количеством возвратов).
Позвольте мне повторить: когда механизм ДКА ищет регулярное выражение с какой-либо позиции строки и совпадение вообще существует, то ДКА найдет самое длинное совпадение из всех возможных. Точка<$M[R4-18]>. Поскольку это самое длинное из всех возможных совпадений среди позиций, равноудаленных от левого края строки, это «самое длинное совпадение, ближнее к левому краю».
Проблема поиска самого длинного совпадения не ограничивается конструкцией выбора. Давайте посмотрим, как НКА ищет изощренное выражение [one(self)?(selfsufficient)?] в строке oneselfsufficient. Сначала НКА находит совпадение для [one], а потом — для максимального [self], после чего [(selfsufficient)?] сравнивается с оставшимися символами sufficient. Совпадения нет, но это не страшно, поскольку этот элемент является необязательным. Итак, традиционный механизм НКА возвращает oneselfsufficient и отбрасывает непроверенные состояния (в POSIX НКА дело обстоит иначе, но до этого мы вскоре доберемся).
С другой стороны, ДКА находит самое длинное совпадение oneselfsufficient. Если элемент [(self)?] остается без совпадения, то совпадет [(selfsufficient)?], и в результате будет достигнуто самое длинное общее совпадение. Именно оно будет возвращено механизмом ДКА.
Я выбрал этот глупый пример по соображениям наглядности, но вы должны понимать: эта проблема актуальна и в реальной жизни. Например, рассмотрим задачу поиска<$M[R4-9]> строк продолжения. В спецификациях данных одна логическая строка часто может распространяться на несколько «физических» строк. Признаком продолжения предыдущей строки является символ \, стоящий перед символом новой строки. Рассмотрим следующий пример[12]:
SRC=array.c builtin.c eval.c field.c gawkmisc.c io.c main.c \
missing.c msg.c node.c re.c version.c
Для поиска строк в формате «переменная=значение» обычно используется выражение [^\w+=.*], но в нем не учитываются возможные строки продолжения. Предполагается, что в используемой программе точка не совпадает с символом новой строки — при необходимости ее можно заменить чем-нибудь вроде [[^\n]].
Чтобы выражение находило строки продолжения, можно попытаться присоединить к нему [(\\\n.*)*]. Предполагается, что это выражение означает «любое количество дополнительных логических строк, следующих за комбинацией \+символ новой строки». Такое решение выглядит разумно, однако в традиционном НКА оно не работает. К тому моменту, когда [.*] достигает символа новой строки, символ \ уже остается позади, и никакие компоненты выражения не заставляют механизм произвести возврат. Однако ДКА найдет самое длинное многострочное совпадение, если оно существует — просто потому, что оно является самым длинным.
Стандарт POSIX требует, чтобы при наличии нескольких возможных совпадений, начинающихся в одной и той же позиции, возвращалось совпадение, содержащее наибольшее количество символов. Точка.
В стандарте использовано выражение «самое длинное совпадение, ближнее к левому краю». В нем не сказано, что вы обязаны использовать ДКА. Что делать, если вы хотите реализовать в программе поддержку НКА? Если реализуется POSIX-совместимая версия НКА, вам придется организовать поиск всего текста oneselfsufficient и всех строк продолжения, хотя для традиционного НКА эти результаты выглядят «неестественно».
Традиционный механизм НКА останавливается с первым найденным совпадением. А что, если заставить его перебрать все непроверенные варианты? Каждый раз, когда механизм достигает конца регулярного выражения, он получает еще одно возможное совпадение. Когда будут перебраны все возможные варианты, механизм просто возвращает самое длинное из всех найденных совпадений. Так работает POSIX НКА
В рассмотренном выше примере механизм НКА после найденного совпадения [(self)?] сохраняет состояние с информацией о том, что поиск совпадения для [one(self)?lwr(selfsufficient)?] может быть продолжен с позиции onelwrselfsufficient. Даже после нахождения oneselfsufficient, возвращаемого традиционным механизмом НКА, POSIX НКА продолжает исчерпывающий перебор остальных вариантов и со временем находит более длинное совпадение oneselfsufficient.
В стандарте POSIX нахождение самого длинного совпадения, ближнего к левому краю — не единственное требование. Если механизм поддерживает сохранение совпадающего текста (в круглых скобках), то<$M[R4-39]> каждое сохраняемое подвыражение также должно содержать максимальный объем текста, удовлетворяющий общему принципу самого длинного совпадения (и соответствующий совпадению текста в предыдущих выражениях). Это означает, что общее совпадение выбирается исключительно по правилу самого длинного совпадения, ближнего к левому краю — но после того, как оно будет выбрано, для первой пары круглых скобок также выбирается совпадение максимальной длины. После этого вторая половина получает максимум от того, что осталось, и т. д.
Выражение [(to|top)(o|polo)?(gical|o?logical)] может совпасть со строкой topological разными способами, однако в механизме POSIX совпадение должно выглядеть top o logical (подчеркнутый текст соответствует каждой паре круглых скобок). Сравните это, скажем, с совпадением to polo gical, найденным традиционным механизмом НКА. В первом случае альтернатива top из первой пары скобок длиннее, чем альтернатива to, поэтому в POSIX будет выбрано именно это совпадение. Аналогично, хотя вторая пара круглых скобок может не совпасть ни с чем (при последующем совпадении ological в третьей паре скобок), ей назначается совпадение максимальной длины (o), соответствующее самому длинному общему совпадению и совпадению текста в предыдущих скобках.
Впрочем, многие POSIX-совместимые механизмы не поддерживают сохранения частичных совпадений, поэтому эта проблема возникает редко.
Если в традиционном НКА эффективность является одной из важнейших аспектов (из-за большого количества возвратов), то в POSIX НКА она играет еще более важную роль, поскольку возвратов становится еще больше. Механизм POSIX НКА должен каждый раз перебирать все возможные комбинации всех компонентов регулярного выражения. Примеры следующей главы наглядно показывают, что плохо написанное регулярное выражение заметно снижает скорость его обработки.
Управляемый текстом механизм ДКА прекрасно справляется с проблемой неэффективности возвратов. Высокая скорость поиска достигается за счет отслеживания всех текущих потенциальных совпадений. Как же это происходит?
Перед тем, как производить попытки поиска, механизм ДКА расходует дополнительное время и память на анализ регулярного выражения (более тщательный и проводимый по другому принципу, чем в НКА). Когда механизм переходит к фактическому поиску в строке, у него уже есть внутренняя карта с описанием типа «если сейчас я прочитают такой-то символ, то он будет относиться к такому-то потенциальному совпадению». При проверке каждого символа строки механизм просто следует этой карте.
Процесс построения карты, называемый компиляцией регулярного выражения (выполняемый и в НКА, но в более простом виде), иногда требует довольно значительных расходов времени и памяти. Но после того, как регулярное выражение будет один раз откомпилировано<$M[R4-37]>, результат компиляции можно применять к тексту неограниченного объема. В нашей аналогии это напоминает зарядку аккумуляторов электромобиля. Сначала автомобиль некоторое время стоит в гараже, подзаряжаясь от сети, но потом он работает четко и безотказно.
Механизмы ДКА и НКА обладают как сильными, так и слабыми сторонами.
Перед тем, как применять регулярное выражение в процессе поиска, оба типа механизмов компилируют его в соответствии со своими алгоритмами поиска. В НКА компиляция обычно происходит быстрее и требует меньших затрат памяти. Не существует принципиальных различий между компиляцией в традиционном и POSIX-совместимом механизмах НКА.
Простой литеральный поиск в «обычных» ситуациях выполняется механизмами обоих типов с одинаковой скоростью. Скорость поиска в ДКА не связана с конкретным регулярным выражением, тогда как в НКА она напрямую зависит от него. Чтобы традиционный механизм НКА сделал вывод об отсутствии совпадения, он должен перепробовать все возможные комбинации элементов регулярного выражения, поэтому в следующей главе рассматриваются приемы написания регулярных выражений НКА, обеспечивающих быстрый поиск. Как будет показано, поиск в НКА иногда занимает целую вечность (или чуть меньше). Традиционный механизм НКА хотя бы может остановиться в тот момент, когда он найдет совпадение. С другой стороны, POSIX НКА всегда проверяет все возможные комбинации и убеждается в том, что он нашел самое длинное возможное совпадение, поэтому успешный поиск обычно занимает столько же времени, как и неудачная попытка. В POSIX НКА эффективность регулярных выражений приобретает еще большее значение.
Возможно, в предыдущем абзаце я сгустил краски — оптимизация часто сокращает объем работы, необходимой для получения ответа. Один из примеров оптимизации уже встречался нам, когда мы говорили о том, что поиск совпадений для регулярных выражений с якорным метасимволом ^ должен осуществляться только с начала строки (с. <$R[P#,R4-7]>). Множество других примеров будет рассмотрено в следующей главе. Вообще говоря, в механизме ДКА необходимость оптимизации не так уж велика (вследствие того, что он так быстро работает), но обычно дополнительная работа, выполняемая на стадии предварительной компиляции в ДКА, обеспечивает лучшую оптимизацию, чем в большинстве существующих механизмов НКА.
Современные механизмы ДКА часто пытаются сократить затраты времени и памяти на стадии компиляции за счет того, что часть работы откладывается до момента непосредственного поиска. Большая часть затрат на стадии компиляции часто остается невостребованной из-за специфики проверяемого текста. Откладывая эту работу до того момента, когда в ней возникнет прямая необходимость, можно добиться заметной экономии времени и памяти. С другой стороны, при этом возникают ситуации, при которых скорость поиска в ДКА начинает зависеть от регулярного выражения.
ДКА (а также любой механизм, соответствующий стандарту POSIX) всегда находит самое длинное совпадение, ближнее к левому краю. Традиционный механизм НКА может вернуть тот же текст, но может найти и что-нибудь другое. Любой конкретный механизм всегда одинаково интерпретирует заданную комбинацию регулярного выражения с текстом, поэтому в этом смысле его поведение нельзя назвать «случайным», однако другие механизмы НКА могут работать несколько иначе. Практически все известные мне механизмы НКА работают именно так, как я описываю[13], однако это не гарантируется ни технологией, ни стандартами.
Механизм НКА может обладать многими возможностями, недоступными для ДКА, в том числе:
l Сохранение текста, совпадающего с подвыражениями в круглых скобках. К этой же категории относятся обратные ссылки и полученная после поиска информация о том, где именно в целевом тексте были найдены частичные совпадения.
l Опережающая проверка (lookahead). В этой главе данная возможность еще не рассматривалась, потому что она поддерживается только в Perl[14] — см. с. <$R[P#,R7-1]>. Позитивная опережающая проверка фактически означает: «Все выражение должно совпадать лишь в том случае, если где-то совпадает указанное подвыражение — но только проверь условие, не “поглощая” текста». Негативная опережающая проверка работает аналогично, но условием является отсутствие совпадения для заданного выражения.
l [Традиционный НКА]. Минимальные квантификаторы и конструкция выбора. Механизм ДКА может легко обеспечить поиск общего совпадения минимальной длины (хотя почему-то такая возможность не поддерживалась ни в одной программе), но он не позволяет реализовать локальное принятие решений без проверки всех вариантов, о которой говорилось выше.
Несмотря на некоторые ограничения, простейшие версии механизмов ДКА и НКА понятны и легко реализуемы. Стремление к сокращению затрат (как времени, так и памяти) и расширению возможностей все более и более усложняет реализацию. Если взять за основу оценки объем программного кода, поддержка регулярных выражений НКА в ed версии 7 (январь 1979 г.) занимала менее 350 строк программного кода C (кстати, весь исходный текст grep состоял всего из 478 строк). Бесплатно распространяемый пакет для работы с регулярными выражениями (версия 8, 1986 г.), написанный Генри Спенсером, занимал почти 1900 строк на языке C. Пакет rx с поддержкой POSIX НКА[15] (в частности, используемый в GNU sed) занимает уже 9700 строк. Что касается реализаций ДКА, то механизм регулярных выражений в egrep версии 7 занимал чуть более 400 строк программного кода, а полноценный пакет POSIX ДКА Генри Спенсера (1992 г.) содержит свыше 4500 строк. Чтобы объединить все лучшие стороны обоих механизмов, в GNU egrep версии 2.0 используются два полноценных механизма (около 8300 строк программного кода).
Впрочем, простота не всегда означает неполноценность. Недавно я захотел воспользоваться регулярными выражениями для обработки текста в Delphi — среде программирования на Pascal, созданной компанией Borland. Я не программировал на Pascal со времен учебы в колледже, однако мне удалось довольно быстро написать несложный механизм НКА. Пусть он не обладает всевозможными «рюшечками и бантиками» и не оптимизирован для максимальной скорости работы, но даже этот простой пакет обладает относительно полными возможностями и приносит немалую пользу.
Скорость ДКА с возможностями НКА: нирвана в сфере регулярных выражений?
<$M[R4-34]>Я несколько раз упоминал о том, что механизм ДКА не поддерживает сохраняющих круглых скобок или обратных ссылок. Это действительно так, однако существуют комбинированные решения, в которых разные технологии объединяются для достижения нирваны. Во врезке на с. <$R[P#,R4-8]>говорится о том, что в стремлении к богатству возможностей механизмы НКА отклоняются от прямого и узкого пути, начертанного теорией. Вполне естественно, что то же самое происходит и с ДКА. Принцип работы ДКА усложняет задачу, но не делает ее невозможной.
В GNU grep было выбрано простое, но эффективное решение. Там, где это возможно, программа использует ДКА, и переходит на НКА лишь при использовании обратных ссылок. Нечто похожее происходит и в GNU awk — для простых проверок принадлежности используется быстрый механизм поиска кратчайшего совпадения из GNU grep, а в тех ситуациях, когда необходимо знать действительные границы совпадения, задействуется другой механизм. Поскольку этот механизм построен по технологии НКА, GNU awk поддерживает сохранение текста совпадений в круглых скобках при помощи специальной функции gensub.
До недавнего времени никто особенно не занимался расширением ДКА, но сейчас в этой области идет активная работа. На момент завершения моей работы над книгой Генри Спенсер пишет, что последняя версия его пакета, ориентированная на технологию ДКА, поддерживает сохраняющие круглые скобки, и что время поиска «в худшем случае связано с объемом текста квадратичной зависимостью, тогда как в НКА она является экспоненциальной». Прежде чем получить широкое распространение, новая технология должна «созреть», но выглядит она перспективно.
Рассмотрев теоретические принципы построения регулярных выражений, мы применим этот материал на практике и займемся нетривиальными аспектами построения регулярных выражений. Темп наращивается постепенно, но учтите, что некоторые проблемы будут довольно сложными.
В хорошо написанном регулярном выражении должны быть сбалансированы несколько факторов:
l Регулярное выражение должно совпадать там, где нужно, и нигде больше.
l Регулярное выражение должно быть понятным и управляемым.
l При использовании механизма НКА выражение должно быть эффективным<$M[R4-29]> (то есть быстро приводить к совпадению или несовпадению в зависимости от результата поиска).
Эти факторы часто зависят от контекста. Если вы работаете в режиме командной строки и хотите побыстрее найти нужные строки при помощи grep, вероятно, вас не слишком огорчит пара лишних совпадений, и вы вряд ли станете долго корпеть над построением нужного выражения. Для экономии времени можно немного поступиться качеством, поскольку полученные результаты можно будет быстро проверить. Но при работе над важным сценарием стоит затратить побольше времени и усилий и сделать все на совесть: сложное регулярное выражение приносит пользу лишь в том случае, если оно работает, как было задумано. Между всеми перечисленными факторами приходится выдерживать баланс.
Впрочем, даже в сценариях эффективность зависит от контекста. Например, в НКА выражение [^-(display|geometry|cemap|…|quick24|random|raw)$], предназначенное для проверки аргументов командной строки, из-за большой конструкции выбора работает неэффективно. Но из-за специфики проверки (обычно выполняемой всего несколько раз в самом начале работы программы) неважно, даже если выражение работает в 100 раз медленнее положенного. Просто это не тот случай, когда следует беспокоиться об эффективности. Однако если бы мы проверяли каждую строку большого файла, то неэффективность привела бы к более тяжелым последствиям.
<$M[R4-27]>Вернемся к примеру со строками продолжения (с. <$R[P#,R4-9]>). Как говорилось выше, выражение [^\w+=.*(\\\n.*)*] в традиционном НКА не обнаружит вторую строку фрагмента:
SRC=array.c builtin.c eval.c field.c gawkmisc.c io.c main.c \
missing.c msg.c node.c re.c version.c
Дело в том, что первое подвыражение [.*] захватывает символ \ и «отнимает» его у подвыражения [(\\\n.*)*], в котором оно должно совпасть. Если мы не хотим, чтобы совпадение распространялось за \, необходимо сообщить об этом в регулярном выражении[16]:
[^\w+=[^\n\\]*(\\\n[^\n\\]*)*]
Впрочем, такая формулировка оказывается слишком жесткой, поскольку она не допускает в строке символов \ кроме тех, которые завершают строку. Можно воспользоваться преимуществами минимальной конструкции выбора механизма НКА, вернуться к исходному выражению и заменить [[^\n\\]*] на [(\\\n|.)*]:
[^\w+=(\\\n|.)*]
Подвыражение, присоединенное ранее для совпадения с комбинацией «\ + новая строка» и последующими строками продолжения, становится лишним — основное подвыражение [(\\\n|.)*] совпадает с символами новой строки, но лишь в том случае, если они экранированы префиксом \.
Впрочем, это не совсем точно. В строке, завершающейся последовательностью \\ (ситуация нестандартная, но возможная), символ \ стоит перед символом новой строки, однако символ новой строки при этом не экранируется, и строка продолжения отсутствует. Проблема заключается в том, что точка совпадает с первым символом \, что позволит второму символу совпасть с [\\\n] в следующем цикле и приведет к появлению ложной строки продолжения. Мы были недостаточно точны — если вторая альтернатива не должна совпадать с \, об этом нужно специально сообщить при помощи описанной выше конструкции [[^\n\\]].
Недостаток выражения [(\\\n|[^\n\\])*] заключается в том, что оно запрещает экранировать что-либо, кроме символов новой строки. В действительности первая альтернатива должна означать «любой экранированный байт». Если точка не совпадает с символом новой строки, не допускайте глупых ошибок вроде [[\n.]]. Если поддерживаются восьмеричные коды, задача решается выражением [(\\[\000-\377]|[^\n\\])*].
Остается сделать небольшое замечание, относящееся к теме следующей главы: поскольку альтернативы четко разделяются, их можно переставить так, чтобы на первом месте стояла более вероятная. Это несколько ускорит поиск совпадения в НКА.
Следующий пример будет рассмотрен значительно подробнее. Наша задача — поиск адресов IP (Internet protocol), то есть четырех чисел, разделенных точками (например, 1.2.3.4). Числа нередко дополняются нулями до трех цифр — 001.002.003.004. Если вы хотите проверить строку на присутствие IP-адреса, можно воспользоваться выражением [[0-9]*\.[0-9]*\.[0-9]*\.[0-9]*], но это решение настолько неопределенное, что оно совпадает даже в строке «and then.....?». Взгляните на регулярное выражение: оно даже не требует существования чисел — единственным требованием является наличие трех точек (между которыми нет ничего, кроме цифр).
Сначала мы заменяем звездочки плюсами, поскольку нам известно, что каждое число должно содержать хотя бы одну цифру. Чтобы гарантировать, что вся строка состоит только из IP-адреса, мы заключаем регулярное выражение в [^…$]. Полученное выражение выглядит так:
[^[0-9]+\.[0-9]+\.[0-9]+\.[0-9]+$]
Если заменить [[0-9]] метасимволом Perl [\d], выражение становится более наглядным[17] — [^\d+\.\d+\.\d+\.\d+$], но оно по-прежнему совпадает с конструкциями, которые не являются IP-адресами — например, [1234.5678.9101112.131415] (каждое число в IP-адресе принадлежит интервалу 0–255). Если потребовать, чтобы каждое число состояло ровно из трех цифр, можно воспользоваться выражением
[^\d\d\d\.\d\d\d\.\d\d\d\.\d\d\d\$]
Однако это требование слишком жесткое. Необходимо поддерживать числа, состоящие из одной и двух цифр (например, 1.2.3.4). Если в диалекте регулярных выражений поддерживается интервальный квантификатор [{мин,макс}], можно воспользоваться выражением [^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$], а если нет — каждая часть легко заменяется на [\d\d?\d?] или [\d(\d\d?)?]. Все эти выражения поддерживают от одной до трех цифр в каждом числе, но каждое делает это по-своему.
Возможно, в зависимости от ситуации вас устроят определенные нечеткости в построенном выражении (например, моего редактора вполне устроило простое выражение, приведенное на с. <$R[P#,R1-5]>). Если вы хотите абсолютной четкости, придется учесть, что [\d\d\d] может совпасть с числом 999, которое превышает 255 и поэтому не является допустимым компонентом IP-адреса.
Чтобы в IP-адресе содержались только числа от 0 до 255, возможны несколько решений. Самое тупое выглядит так: [0|1|2|3|…253|254|255]. На самом деле это решение не поддерживает дополнение чисел нулями, поэтому в действительности вам понадобится [0|00|00|1|01|001|…], что еще смешнее. Впрочем, для механизма ДКА вызывает смех только длина и неуклюжесть выражения — оно совпадает точно так же, как и любое регулярное выражение, описывающее этот текст. Для механизма НКА конструкция выбора делает выражение крайне неэффективным.
В более реалистичном решении нужно проследить за тем, какие цифры допускаются в числе и в каких позициях они находятся. Если число состоит всего из одной или двух цифр, принадлежность числа нужному интервалу проверять не нужно, поэтому для этих случаев вполне достаточно [\d|\d\d]. Проверка не нужна и в том случае, если число из трех цифр начинается с 0 или 1, поскольку оно заведомо принадлежит интервалу 000–199. Следовательно, в конструкцию выбора можно добавить [[01]\d\d]; получается [\d|\d\d|[01]\d\d]. Полученное выражение похоже на те, которые использовались для поиска даты (с. <$R[P#,R4-10]> и времени в главе 1 (с. <$R[P#,R1-6]>).
Число из трех цифр, начинающееся с 2, допустимо лишь в том случае, если оно равно 255 и меньше. Следовательно, если вторая цифра меньше 5, значит, число правильное. Если вторая цифра равна пяти, третья цифра должна быть меньше 6. Все сказанное выражается в форме [2[0-4]\d|25[0-5]].
На первый взгляд кажется, что наш анализ окончательно запутал задачу, но если поразмыслить, все становится на свои места. В результате получается выражение [\d|\d\d|[01]\d\d|2[0-4]\d|25[0-5]]. Вообще говоря, первые три альтернативы можно объединить, и выражение придет к виду [[01]?\d\d?|2[0-4]\d|25[0-5]]. В НКА такое решение работает более эффективно, поскольку любая неудачная альтернатива приводит к возврату. Обратите внимание: использование [\d\d?] в первой альтернативе вместо [\d?\d] немного ускоряет выявление неудачи в НКА при полном отсутствии цифр. Подробный анализ оставляю вам для самостоятельной работы — применение двух вариантов к простому примеру наглядно продемонстрирует отличия. Возможны и другие шаги к тому, чтобы эта часть выражения работала более эффективно, но я оставлю этот аспект до следующей главы.
Итак, мы построили подвыражение, совпадающее с отдельным числом в интервале от 0 до 255. Его можно заключить его в круглые скобки и подставить вместо подвыражений [\d{1,3}] в предыдущем примере. Окончательный результат выглядит так (выражение разбито на строки по ширине печатной страницы):
[^([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])\.
([01]?\d\d?|2[0-4]\d|25[0-5])\.([01]?\d\d?|2[0-4]\d|25[0-5])$]
Ничего себе! А стоит ли игра свеч? Решайте сами в зависимости от своих потребностей. Это выражение все равно допускает строку 0.0.0.0, которая неверна, поскольку в ней все цифры равны нулю, но написать выражение для исключения этой возможности будет намного труднее. Нельзя просто запретить ноль в каждом числе, поскольку адрес типа 123.202.0.188 вполне допустим. В какой-то момент в зависимости от конкретной ситуации вы должны решить, стоит ли стремиться к дальнейшей точности — хлопоты начинают приносить все меньше пользы. Например, можно вернуться к выражению [^\d{1,3}\.\d{1,3}\.\d{1,3}\.\d{1,3}$], заключить каждый компонент в круглые скобки, чтобы числа сохранились в переменных $1, $2, $3 и $4, и проверить их при помощи других программных конструкций.
Кстати, стоит подумать и о негативной опережающей проверке, реализованной в Perl. Она позволяет исключить<$M[R4-33]> некоторые случаи еще до того, как механизм начнет применять «главное» выражение. В приведенном примере начальное подвыражение [(?!0+\.0+\.0+\.0+$] обеспечивает немедленную неудачу при поиске в том случае, если все компоненты адреса равны нулю. Мы вернемся к этой теме в главе 7 (с. <$R[P#,R7-2]>).
Обратите внимание на два якорных метасимвола. Их присутствие необходимо для правильной работы регулярного выражения. Без них оно запросто совпадет с «ip=72123.3.21.993» или (для традиционного НКА) даже «ip=123.3.21.223».
Во втором случае выражение даже не полностью совпадает с завершающим 223, как могло бы. На самом деле оно действительно могло, но в выражении нет ничего (разделительной точки или завершающего якоря), что бы форсировало это совпадение. Первая альтернатива последней группы, [[01]?\d\d?], совпадает с первыми двумя цифрами, и на этом регулярное выражение завершается. Как и в задаче с поиском даты на с. <$R[P#,R4-10]>, для достижения нужного эффекта можно изменить порядок альтернатив. На первое место ставится альтернатива с тремя цифрами, поэтому любое допустимое число из трех цифр будет полностью обнаружено до того, как проверка перейдет к двухцифровой альтернативе.
Но с перестановкой или без нее, первое ошибочное совпадение все равно остается. «Ага!» — подумаете вы. — «Проблема решается при помощи метасимволов границ слов». К сожалению, нет. Такое выражение будет находить совпадения типа 1.2.3.4.5.6. Чтобы исключить подобные внутренние совпадения, необходимо проверить окружающий контекст, и метасимволов границ слов для этого недостаточно. В одном из возможных решений все регулярное выражение заключается в конструкцию [(^|spc)…(spc|$)], но ответ на вопрос о том, что считать «хорошим решением», зависит от ситуации.
Если в выражении нужно указать «почти все», иногда бывает трудно разобраться, что же конкретно указывать. В этом вы убедились выше, при описании примера [".*"]. В этом примере речь шла не о «всем, что угодно», а о «всем, кроме кавычек», поэтому выражение следовало записать в виде ["[^"]*"].
К сожалению, не всегда удается так четко разобраться во всем. Например, если вы хотите, чтобы в тексте могли встречаться экранированные кавычки (например, "hespcisspc6'4\"spctall"), подвыражение [[^"]*] остановится на экранированной (или любой другой) кавычке, и будет найдена лишь малая часть правильного совпадения (в приведенном примере — "hespcisspc6'4\"spctall"). Более серьезная проблема возникает в случае, если ненужный текст состоит из нескольких символов, как, например, в примере <B>…</B> на с. <$R[P#,R4-11]>. Подобные проблемы и способы их решения рассматриваются в следующем разделе.
Другая трудность связана с поиском парных наборов круглых скобок, фигурных скобок и т. д. Задача поиска парных скобок часто встречается при лексическом анализе конфигурационных файлов, программ и т. д. Допустим, вы хотите каким-то образом обработать все аргументы функции в процессе анализа программы, написанной на C. Аргументы функции перечисляются в круглых скобках после ее имени. Они и сами могут содержать круглые скобки, обусловленные вложенными вызовами функций или группировкой операндов при выполнении математических операций. Если забыть о возможном присутствии вложенных скобок, возникает искушение воспользоваться следующей командой:
[\bfoo\([^)]*\)]
По священной традиции программирования на C я присвоил функции-примеру имя foo. Предполагается, что подчеркнутая часть выражения совпадет с аргументами функции. В таких примерах, как foo(2,spc4.0) и foo(somevar,spc3.7) все работает именно так, как ожидалось. К сожалению, в foo(bar(somevar),spc3.7) возникают проблемы. Необходимо придумать что-нибудь поумнее [[^)]*].
Для поиска текста, заключенного в круглые скобки, можно предложить следующие регулярные выражения:
|
\(.*\) |
Скобки-литералы, между которыми находится произвольный текст |
|
\([^)]*\) |
От открывающей круглой скобки до следующей закрывающей круглой скобки |
|
\([^()]*\) |
От открывающей круглой скобки до следующей закрывающей круглой скобки, но с запретом других открывающих скобок между ними |
На рис. 4.1 показано, как эти выражения совпадают в примерном тексте.
Рис. 4.1. Совпадения для приведенных вариантов регулярных выражений
Мы видим, что регулярное выражение 1 забирает слишком много[18], а выражение 2 довольствуется слишком малым. Выражение 3 вообще не совпадает — само по себе оно бы совпало с (this), но поскольку оно должно следовать сразу же после foo, поиск оказывается неудачным. Итак, ни один из предложенных вариантов не работает. В сущности, проблема в том, что находить конструкции произвольной вложенности при помощи регулярных выражений не удается. Это попросту невозможно.
Можно сконструировать регулярное выражение, которое будет находить вложенные конструкции до определенного уровня вложенности, но не до произвольного уровня. Всего один уровень вложенности требует чудовищного выражения [\([^()]*(\([^()]*\[^()]*)*\)]. Если вы не беспокоитесь об эффективности или работаете с механизмом ДКА, для которого это несущественно, можно с таким же успехом воспользоваться выражением [\(([^()]|\([^()]*\))*\)]. Одна мысль о том, чтобы взяться за следующие уровни вложенности, наводит на меня ужас. Иногда приходится прибегать к другим способам, не связанным с регулярными выражениями[19].
<$M[R4-28]>Новички часто забывают о том, что происходит, если структура текста отличается от предполагаемой. Предположим, вы пишете фильтр для преобразования текстового файла в формат HTML и хотите, чтобы строка дефисов преобразовывалась в тег <HR> (этот тег рисует на странице горизонтальную линию). Если воспользоваться командой поиска и замены s/-*/<HR>, она заменит все нужные последовательности, но лишь в том случае, если они находятся в начале строки. Удивлены<$M[R4-31]>? Это еще не все: команда s/-*/<HR> добавит <HR> в начало каждой строки, независимо от того, начинается ли она с серии дефисов или нет!
Вспомните: все элементы, которые не являются обязательными, совпадают всегда. При попытке применить [-*] в начале строки это выражение совпадает со всеми найденными дефисами. Но если ни одного дефиса не найдено, выражение успешно совпадет с «ничем». Уж так устроен квантификатор *.
Рассмотрим похожий пример. Я недавно читал новую книгу одного почтенного автора, в которой он описывает регулярное выражение для поиска чисел, целых и вещественных. В соответствии с условиями задачи число состоит из необязательного знака «минус», произвольного количества цифр в целой части, необязательной десятичной точки и произвольного количества цифр в дробной части. Приведенное решение выглядело так<$M[R4-32]>: [-?[0-9]*\.?[0-9]*].
В самом деле, это выражение успешно совпадает с такими примерами, как 1, -272.37, 129238843., .191919 и даже -.0. Вроде бы все хорошо.
А теперь подумайте, что произойдет, если применить это выражение к строкам «thisspctextspchasspcnospcnumber», «nothingspchere» и даже к пустой строке? Внимательно взгляните на регулярное выражение — все его элементы являются необязательными. Если там присутствует число и если оно находится в начале строки, то это число будет успешно найдено, однако ни один элемент не является обязательным. Выражение совпадает во всех трех случаях, причем каждый раз оно совпадает с «ничем» в начале строки. Более того, оно совпадет с «ничем» даже в начале такой строки, как «numspc123», поскольку это «ничто» совпадает раньше, чем число!
Поэтому необходимо точно сформулировать, что же вы имеете в виду. Вещественное число должно содержать как минимум одну цифру, или это вообще не число. В процессе конструирования регулярного выражения мы сначала предположим, что хотя бы одна цифра находится перед десятичной точкой. В этом случае для цифр целой части используется квантификатор +: [-?[0-9]+].
При написании подвыражения для поиска необязательной десятичной точки и последующих цифр необходимо понять, что наличие дробной части полностью зависит от наличия десятичной самой точки. Если воспользоваться наивным выражением типа [\.?[0-9]*], то [[0-9]*] сможет совпасть независимо от наличия десятичной точки. Как и прежде, необходимо точно сформулировать, что же мы хотим. Десятичная точка необязательна (и цифры в дробной части, если она есть): [(\.[0-9]*)?]. Здесь вопросительный знак квантифицирует не одну десятичную точку, а комбинацию десятичной точки с последующими цифрами. Внутри этой комбинации десятичная точка должна присутствовать обязательно: если ее нет, [[0-9]*] вообще не получит шанса на совпадение.
Объединяя все сказанное, мы получаем [-?[0-9]+(\.[0-9]*)?]. Это выражение все еще не находит числа вида .007, поскольку оно требует наличия хотя бы одной цифры перед десятичной точкой. Если изменить левую часть и разрешить нулевое количество цифр, придется изменять и правую часть, потому что нельзя допустить, чтобы все цифры выражения были необязательными (собственно, именно эту проблему мы и пытались решить).
Одно из возможных решений — добавить для таких ситуаций специальную альтернативу: [-?[0-9]+(\.[0-9]*)?|-?\.[0-9]+]. Теперь выражение также находит числа, состоящие из десятичной точки, за которой следуют одна или несколько цифр. Подробности, подробности… Вы обратили внимание на то, что во второй альтернативе также предусмотрено наличие необязательного минуса? Об этом легко забыть. Конечно, [-?] можно вынести за пределы конструкции выбора, и тогда получится выражение [-?([0-9]+(\.[0-9]*)?|\.[0-9]+)].
Хотя такое решение работает лучше оригинала, оно все равно обладает некоторыми недостатками. Все зависит от того, как вы будете его использовать. Часто при написании регулярного выражения автор ориентируется на определенный контекст и делает некоторые допущения относительно его применения — скажем, когда искомый текст является частью некоторой конструкции и окружается специальными ограничителями, предотвращающими лишние совпадения. Например, наше простое выражение с превеликим удовольствием найдет совпадение в строке «1997.04.12».
Но если регулярное выражение используется в конкретной ситуации, проблемы внутренних совпадений можно решить. Например, при анализе строк данных, разделенных запятыми, можно воспользоваться конструкцией [,…,] или, что еще лучше, [(^|,)…(,|$)].
Рассмотренные выше выражения для поиска IP-адресов и строк, заключенных в кавычки, демонстрируют лишь два примера из целой категории распространенных задач. Речь идет о поиске совпадения для текста, ограниченного (или, возможно, разделяемого) другими текстовыми элементами. В числе других примеров<$M[R4-26]>:
l Поиск комментариев в программах на языке C, расположенных между ограничителями /* и */.
l Поиск тегов HTML, заключенных в угловые скобки <…> — например, <CODE>.
l Выборка текста, находящегося между тегами HTML — например, «anchor text» в ссылке <AspcHREF="…">anchorspctext</A>.
l Поиск строк в файле .mailrc. В этом файле определяются псевдонимы электронной почты, а каждая строка имеет формат
alias псевдоним полный_адрес
Пример — alias jeff jfriedl@ora.com. В данном случае ограничителями являются пропуски между символами, а также конец строки.
l Поиск строк, заключенных в кавычки, которые могут содержать внутренние экранированные кавычки<$M[R4-30]> — например, «for your passport, you need a "2\"x3" likeness" of yourself».
Обобщенное решение всех этих задач выглядит так<$M[R4-38]>:
1. Найти открывающий ограничитель.
2. Найти основной текст (фактически это означает «все, что не является закрывающим ограничителем»).
3. Найти закрывающий ограничитель.
Как упоминалось выше, «поиск всего, что не является закрывающим ограничителем» значительно усложняется в том случае, если закрывающий ограничитель состоит из нескольких символов или может встречаться в основном тексте.
Вернемся к примеру 2\"x3\". Искомая строка заключена в кавычки, однако экранированные кавычки могут встречаться и в тексте.
Хотя функции ограничителей в данном примере выполняют простые кавычки, сейчас речь идет о поиске основного текста. Давайте разберемся, что же может входить в основной текст. Мы знаем, что если символ не является кавычкой (то есть совпадает с выражением [[^"]]), его следует принять. Но даже если символ является кавычкой, он тоже подойдет, если перед ним находится экранирующий символ \.
К сожалению, в регулярном выражении нельзя выразить понятие «если перед ним находится». Если бы наряду с опережающей проверкой существовала и ретроспективная проверка (lookbehind), то она идеально подходило бы для подобных ситуаций. Впрочем, ретроспективная проверка не поддерживается ни одной программой. Сказать «если за ним следует» нетрудно — для этого нужно просто присоединить символы продолжения или воспользоваться опережающей проверкой, если она поддерживается вашей программой (например, Perl). Никакого волшебства здесь нет, это всего лишь вопрос трактовки. С тех же позиций [abc] в действительности означает «символ a допустим в том случае, если за ним следует b, а затем c». Может показаться, что я цепляюсь к словам, но на самом деле это довольно важный момент — отсюда следует, что нельзя сказать «кавычка допустима, если перед ней стоит символ \», а лишь «допустим символ \, после которого стоит кавычка». Это записывается в виде [\\"] (не забывайте — обратная косая черта является метасимволом, поэтому если мы хотим, чтобы наше выражение совпадало с литералом \, его необходимо экранировать еще одним символом \).
Итак, выражение для основного текста формулируется так: «разрешить либо [[^"]], либо [\\"]», или на языке регулярных выражений — [[^"]|\\"]. Поскольку до завершающей кавычки оно может совпасть любое количество раз, следует заключить его в круглые скобки и использовать квантификатор *. После добавления начальной и завершающей кавычки получается ["([^"]|\\")*"].
Логично? По-моему, да. К сожалению, это решение не работает по двум причинам. Первая связана со спецификой традиционного механизма НКА. Когда выражение применяется к строке 2\"x3\" likeness", мы видим, что после совпадения начальной скобки проверяется первая альтернатива, которая совпадает с 2. Обнаружив совпадение, механизм оставляет конструкцию выбора, но немедленно возвращается к ней из-за *. Снова проверка начинается с первой альтернативы, и она снова совпадает (с обратной косой чертой). К сожалению, этот символ должен опознаваться как экранирующий префикс для следующей кавычки, а не как произвольная «не-кавычка», относящаяся к подвыражению [[^"]].
Затем проверяется следующий символ, но на этот раз первая альтернатива завершается неудачей, поскольку текущим символом является кавычка. Вторая альтернатива, экранированная кавычка, тоже не подходит, поскольку символ \ остался позади. Квантификатор * завершает поиск, и следующая кавычка воспринимается как завершающая. Таким образом, в строке обнаруживается совсем не то совпадение:
… you need a "2\"x3" likeness" of yourself.
В механизмах ДКА и POSIX такой проблемы не возникает, поскольку эти механизмы всегда находят самое длинное совпадение от любой начальной позиции (как я уже неоднократно говорил). Эти механизмы «понимают», что если обратная косая черта совпадает с [\\] (а не [[^"]]), то станет возможным более длинное совпадение (которое нам и нужно).
Итак, как же справиться с этой проблемой в традиционном НКА? Если поменять эти две альтернативы местами, то альтернатива [\\] будет применена до того, как [[^"]] «поглотит» обратную косую черту, и механизм пройдет мимо экранированной кавычки. Выражение ["(\\"|[^"])*"] найдет следующее совпадение:
… you need a "2\"x3" likeness" of yourself.
Что нам и требовалось. Проверка первой альтернативы обычно завершается неудачей, вследствие чего механизму приходится проверить вторую альтернативу. Поэтому данное выражение приводит к лишним возвратам, но, по крайней мере, оно работает.
К сожалению, существует и другая проблема. Она проявляется в механизмах любого типа, когда в тексте допущена малозаметная ошибка. Рассмотрим следующий пример:
"someone has \"forgotten\" the closing quote
«Обычная» закрывающая кавычка отсутствует, поэтому эта строка вообще не должна совпадать. Но как было показано выше, экранированная кавычка может совпасть. В приведенных выше примерах с использованием механизмов ДКА и POSIX НКА экранированная кавычка не была последней, поэтому поиск совпадения на ней не заканчивался. Однако на этот раз экранированная кавычка является последней, поэтому поиск завершается. Даже в традиционном НКА, где механизм проходит мимо экранированных кавычек, поиск общего совпадения приведет к возврату и нахождению кавычки.
Отсюда следует очень важная мораль: всегда учитывайте, что может произойти в «неожиданных» ситуациях, когда ваше регулярное выражение не должно совпадать. В таких случаях нет ничего лучше досконального понимания того, что происходит при поиске совпадения, и обширного набора тестов.
Другая мораль: следите за тем, чтобы нежелательные совпадения не прошмыгнули с черного хода. При решении описанной выше проблемы нам следовало понять, что кавычка и обратная косая черта в данном контексте имеют особое значение и должны обрабатываться отдельно от других символов. Исходная точка сначала превратилась в [[^"]], а потом претерпела новое изменение: ["(\\"|[^"\\])*"].
Поскольку [[^"\\]] предотвращает первую проблему, мы можем снова поменять альтернативы местами и поставить более вероятный случай в начало: ["([^"\\]|\\")*"]. При этом ничего не изменится в ДКА (из-за отсутствия возврата) и POSIX НКА (где всегда перебираются все комбинации независимо от порядка альтернатив), но в традиционном НКА выражение будет работать эффективнее.
У полученного выражения есть один недостаток: оно не совпадает с "hello, world\n", поскольку позволяет экранировать только кавычки. Проблема решается простой заменой [\\"] на [\\.], что дает нам ["([^"\\]|\\.)*"].
Если в используемом диалекте регулярных выражений точка не совпадает с символом новой строки, то возникает очередная проблема — как использовать это выражение для комбинации «\ + символ новой строки»? Если в диалекте поддерживается метасимвол [\n], вместо точки можно воспользоваться [(.|\n)]. Более эффективное решение (для тех программ, в которых оно поддерживается) — использование символьного класса, совпадающего со всеми байтами (например, [[\000-\377]].Учтите, что символьный класс [[.\n]] совпадает с двумя символами, точкой и символом новой строки. Впрочем, в некоторых программах этот символьный класс совпадает с двумя символами, точкой и n, а есть и такие программы, где он совпадает с тремя символами (точкой, обратной косой чертой и n).
Я хочу еще раз особо выделить один общий принцип, относящийся к конструированию и использованию регулярных выражений, о котором я уже несколько раз кратко упоминал. Необходимо учитывать все предположения, относящиеся к типу используемых данных и тем условиям, для которых предназначено ваше регулярное выражение. Даже такое простое выражение, как [a], предполагает, что целевые данные относятся к той же кодировке (см. с. <$R[P#,R1-11]>), которую использует автор. Это понятно на уровне здравого смысла, поэтому я не надоедал вам напоминаниями.
Однако многие предположения, которые выглядят очевидными для одних, вовсе не кажутся очевидными другим. Скажем, наше регулярное выражение для поиска строк в кавычках предполагает, что посторонние кавычки в строке отсутствуют. Если попытаться применить его к исходным текстам, написанным практически на любом языке программирования, может оказаться, что выражение не работает из-за кавычек внутри комментариев.
Нет ничего плохого в том, чтобы делать предположения о структуре данных или тех условиях, в которых будет использоваться ваше выражение. Все возникающие проблемы обычно связаны с чрезмерно оптимистичными предположениями, а также расхождениями между намерениями автора и реальным использованием регулярного выражения.
Конечно, во многих ситуациях принцип максимализма работает вам на пользу. Рассмотрим несколько простых примеров. Общая методика конструирования регулярных выражений будет продемонстрирована в конкретных (и, надеюсь, полезных) приложениях.
По своему опыту знаю, что работать обычно интереснее, чем читать. Ниже приводятся примеры программного кода на языках Perl, Tcl и Python. Если эти конкретные языки вас не интересуют, их можно спокойно пропустить. Я буду использовать специфические возможности этих языков, но в целом постараюсь сделать так, чтобы примеры были простыми, а уроки носили по возможности общий характер.
Возможность обработки имен файлов используется довольно часто. Например, нередко требуется удалить<$M[R4-36]> путь из полного имени файла — скажем, преобразовать /usr/local/bin/gcc в gcc.
Толковая постановка задачи — половина решения. В нашем случае из полного имени файла удаляются все символы до последнего символа / (включительно). Если символ / отсутствует, имя файла уже преобразовано в нужную форму, и делать ничего не нужно.
В этом примере использование [.*] действительно оправдано. В выражении [^.*/] подвыражение [.*] поглощает всю строку, но затем отступает (то есть происходит возврат) к последнему символу / для получения общего совпадения. Поскольку / выполняет функции ограничителя в команде подстановки, необходимо либо экранировать его в регулярном выражении, как в s/.*///(регулярное выражение подчеркнуто), либо (если это возможно) использовать другой ограничитель — скажем, s!^.*/!!.
Если полное имя файла хранится в переменной $filename, следующие команды удаляют из него путь к файлу:
|
Язык |
Команда |
|
Perl |
$filename =~ s!^.*/!!; |
|
Tcl |
regsub "^.*/" $filename "" filename |
|
Python |
filename = regsub.sub("^.*/", "", filename) |
Кстати, при работе с именами файлов DOS вместо / используется символ \. Поскольку в регулярных выражениях он интерпретируется как метасимвол, его необходимо экранировать другим символом \. Получится что-нибудь вроде s/^.*\\//. Но в Tcl, Python и других языках, где регулярные выражения передаются функциям в виде обычных строк, символ \ часто является не только метасимволом регулярного выражения, но и строковым метасимволом. Это означает, что для передачи одного символа \ в регулярное выражение необходима комбинация \\. Поскольку в регулярном выражении должны присутствовать два символа \, один литерал \ приходится обозначать последовательностью \\\\.
Запомните главное правило: всегда думайте о том, что произойдет при отсутствии совпадения. В нашем примере, если в строке нет символов /, подстановка не производится, и строка остается без изменений. Прекрасно, именно это и требовалось… /bin/sh превращается в sh, //../ernst превращается в ernst, а vi просто остается без изменений.
По соображениям эффективности следует вспомнить, как механизм регулярных выражений выполняет свою работу (конечно, речь идет о механизме НКА). Давайте посмотрим, что произойдет, если вы забыли о начальном якоре ^ и применили выражение к строке, не содержащей символа /. Как обычно, механизм регулярных выражений начинает поиск с начала строки. Подвыражение [.*] распространяется до начала строки, после чего начинает отступать в поисках совпадения для /. Постепенно оно возвращает все символы, поглощенные [.*], но совпадение так и не находится. Итак, механизм регулярных выражений решает, что при поиске от начала строки совпадения нет — но его работа еще не закончена!
Механизм перемещается ко второму символу строки и заново ищет все регулярное выражение. Теоретически процедура сканирования с возвратом повторяется для всех возможных начальных позицией в строке. Имена файлов обычно имеют небольшую длину, но этот принцип применяется во многих ситуациях, и при большой длине строки возникает большое количество лишних возвратов. Как говорилось выше, в ДКА такой проблемы нет.
На практике «разумный» механизм понимает, что любое регулярное выражение, начинающееся с [.*] и не совпадающее в начале строки, не совпадет и в любой другой позиции, поэтому выражение проверяется только один раз. И все же будет правильнее сразу записать выражение именно так, как мы это сделали — с якорем ^.
Возможно и другое решение — обойти путь, просто выделить имя файла из полного имени и присвоить найденный текст другой переменной. Имя файла определяется как все завершающие символы, отличные от косой черты: [[^/]*$]. На этот раз функции $ не ограничиваются оптимизацией, якорь в конце выражения действительно необходим. Теперь в программе можно действовать так:
$WholePath =~ m!([^/]*)$!; # Применить выражение к переменной $WholePath
$FileName = $1; # Присвоить найденный текст
Обратите внимание — мы не проверяем, совпало регулярное выражение или нет, поскольку совпадение заведомо существует. Единственное обязательное требование заключается в том, чтобы у строки был конец, совпадающий с символом $, а конец есть даже у пустой строки.
Следовательно, когда я использую $1 для ссылки на текст, совпавший с подвыражением в круглых скобках, я уверен, что этой переменной было присвоено некоторое значение (возможно, пустая строка)[20].
Тем не менее, поскольку в Tcl, Python и Perl используются механизмы НКА (вернее, традиционные механизмы НКА), конструкция [[^\/]*$] работает очень неэффективно. Внимательно проанализируйте, как в НКА будет происходить поиск, и вы увидите, что он сопряжен с большим количеством возвратов. Даже в коротком примере usr/local/bin/perl окончательное совпадение будет найдено лишь после примерно 40 возвратов.
Рассмотрим попытку, начинающуюся с позиции …lwrlocal…. После того, как [[^\/]*$] доберется до второй буквы l и не совпадет с косой чертой, совпадение с $ проверяется (неудачно) для каждого из сохраненных состояний l, a, c, o, l. Если этого недостаточно, большая часть этой работы повторится при новой попытке для начальных позиций …llwrocal/…, …lolwrcal/… и т. д.
В данном примере это не так уж важно, поскольку имена файлов обычно имеют небольшую длину, а 40 возвратов — сущие пустяки (вот если бы 40 миллионов, тогда другое дело!) Но если вы будете знать о подобных проблемах, то всегда сможете применить общие уроки к конкретным ситуациям.
Хочу обратить ваше внимание на одно обстоятельство. Хотя эта книга посвящена регулярным выражениям, они не являются панацеей. Например, в Tcl для анализа имен файлов существуют специальные команды, входящие в набор команд file. В Perl задача гораздо эффективнее решается командой
$name = substr($WholePath, rindex($WholePath, "/")+1);
Впрочем, я не буду подробно останавливаться на этой теме.
Следующим логичным шагом станет разделение полного имени на два компонента: путь и имя файла. Существует много возможных решений; все зависит от того, чего вы добиваетесь. Прежде всего, можно воспользоваться выражением [^(.*)/(.*)$] для того, чтобы присвоить соответствующие компоненты переменным $1 и $2. Зная, как работает максимальный поиск, можно быть уверенным в том, что первое подвыражение [.*] никогда не оставит для $2 текст, в котором присутствует /. Первоначально [.*] захватывает все символы, после чего происходит возврат для нахождения следующего в регулярном выражении символа /. Для второй конструкции [.*] не остается только «возвращенная» часть. Таким образом, $1 будет содержать путь к файлу, а $2 — завершающее имя файла.
Обратите внимание: мы полагаемся на то, что первое подвыражение [(.*)/] не оставит второму [(.*)] текста, содержащего косую черту. Принцип максимализма вам понятен, поэтому дополнительные разъяснения не понадобятся. И все же я стараюсь как можно точнее формулировать свои выражения, поэтому для имени файла предпочитаю использовать [[^/]*]. Получается [^(.*)/([^/]*)$]. Поскольку это выражение наглядно показывает, что мы ищем, оно выполняет и документирующие функции.
Наше выражение обладает одним большим недостатком — оно требует, чтобы в строке присутствовала хотя бы одна косая черта. Если попытаться применить его к строке file.txt, совпадения не будет, а значит, не будет и информации. При правильном подходе это можно обратить себе на пользу:
if ( $WholePath =~ m!^(.*)/(.*)$! ) {
$LeadingPath = $1;
$FileName = $2;
} else {
$LeadingPath = "."; # Чтобы имя "file.txt" воспринималось
# как "./file.txt"
$FileName = $WholePath;
}
Существует и другой вариант получения обоих компонентов — тем или иным способом получить путь или имя файла, а затем воспользоваться побочными эффектами совпадения для конструирования другой части. Следующий фрагмент Tcl находит позицию последнего символа / и выделяет подстроки, находящиеся по обе стороны от него:
if [regexp -indices .*/ $WholePath Match] {
# Совпадение есть. Позиция символа / определяется концом совпадения.
set LeadingPath [string range $WholePath 0 [expr [lindex $Match 1] -1]]
set FileName [string range $WholePath [expr [lindex $Match 1] +1] end]
} {
# Совпадения нет - полное имя является именем файла.
set LeadingPath .
set FileName $WholePath
}
Конструкция Tcl regexp -indices используется для получения индексов совпадения: скажем, для строки /tmp/file.txt переменной Match будет присвоено значение 0spc4, показывающее, что совпадение распространяется от символа 0 до символа 4. Мы знаем, что второй индекс указывает на косую черту, поэтому выражение [expr [lindex $Match 1] – 1] ссылается на позицию, предшествующую ей, а версия с +1 — на позицию после нее. Затем две подстроки извлекаются при помощи string range.
И снова в этом конкретном примере использовать регулярное выражение для поиска последней косой черты неразумно — функция rindex или ее аналог будет работать быстрее (в Tcl это string last / $WholePath). И все же идея с извлечением частей строки выглядит заманчиво, хотя в этом простом примере задачу можно было решить и иначе.
Если вы с первого раза поняли все, о чем говорится в этой главе, вероятно, вам вообще незачем было ее читать. Речь идет о вещах, мягко говоря, нетривиальных. Мне понадобилось немало времени, чтобы понять этот материал, и еще больше — чтобы осознать его. Надеюсь, четкое, последовательное изложение поможет вам в этом. Я старался объяснять просто, но не увлекаться чрезмерным упрощением (к сожалению, это весьма распространенное явление, которое лишь мешает подлинному пониманию).
Глава разделена на две части — описания общей механики поиска и некоторых практических применений.
При реализации механизмов регулярных выражений обычно используются две базовые технологии. Механизм НКА управляется регулярным выражением (см. с. <$R[P#,R4-12]>), а механизм ДКА управляется текстом (см. с. <$R[P#,R4-13]>). Расшифровки сокращений приведены на с. <$R[P#,R4-14]>.
В сочетании со стандартом POSIX (см. с. <$R[P#,R4-15]>) и для практических целей механизмы делятся на три типа:
l Традиционный механизм НКА (аналог — бензиновый двигатель с широкими возможностями регулировки).
l Механизм POSIX НКА (аналог — бензиновый двигатель со стандартным поведением).
l Механизм ДКА, POSIX-совместимый или нет (аналог — электрический, стабильно работающий двигатель).
Чтобы программа приносила максимальную пользу, необходимо знать, какой тип механизма в ней используется, и соответствующим образом строить регулярные выражения. Самым распространенным типом является традиционный механизм НКА, за ним по популярности следует ДКА. В табл. 4.1 (см. с. <$R[P#,R4-16]>) перечислены некоторые распространенные программы и типы их механизмов. В главе 5 (см. с. <$R[P#,R5-5]>) я покажу, как опытным путем определить тип механизма в незнакомой программе.
Существует универсальное правило, не зависящее от типа механизма: предпочтение отдается совпадениям, начинающимся с более ранней позиции. Это связано с последовательной проверкой регулярного выражения в каждой позиции строки (см. с. <$R[P#,R4-17]>).
Для попытки найти совпадение с произвольной позиции строки:
Механизм ДКА, управляемый текстом — находит самое длинное совпадение. Точка. Говорить больше не о чем (с. <$R[P#,R4-18]>). Все очень предсказуемо, очень быстро и очень скучно (с. <$R[P#,R4-19]>).
Механизм НКА, управляемый регулярным выражением — «прорабатывает» совпадение. Сердцем механизма НКА является принцип возврата (с. <$R[P#,R4-20]>, <$R[P#,R4-21]>). Совпадение определяется метасимволами; квантификаторы (* и др.) максимальны (с. <$R[P#,R4-22]>). Конструкция выбора обычно не максимальна (с. <$R[P#,R4-23]>), исключением является POSIX НКА.
l POSIX НКА — всегда находит самое длинное совпадение. Однако вам не придется скучать, поскольку возникает проблема эффективности (тема следующей главы).
l Традиционный НКА — самый выразительный механизм регулярных выражений. Используя природу механизма, управляемого регулярным выражением, можно сделать так, чтобы найденное совпадение было именно тем, что вам нужно.
В разделе «Сравнение двух механизмов» (см. с. <$R[P#,R4-24]>) перечислены основные различия механизмов ДКА и НКА.
Найти аналог для «новеньких кожаных сидений» (см. с. <$R[P#,R4-25]>) нам так и не удалось.
Одной из самых распространенных задач является поиск текста, заключенного в ограничители (например, строк в кавычках или комментариев в языке C) — см. с. <$R[P#,R4-26]>. Общее решение заключается в том, чтобы найти открывающий ограничитель, затем весь текст до закрывающего ограничителя, и, наконец, сам закрывающий ограничитель. Как правило, сложности связаны с тем, чтобы закрывающий ограничитель не проник в среднюю фазу поиска.
При умелом использовании максимализм может быть вашим другом, но при отсутствии должной осторожности он натворит немало бед. Старайтесь как можно точнее формулировать задачу (<$R[P#,R4-27]>) и внимательно следите за тем, как могут появиться нежелательные совпадения (<$R[P#,R4-28]>).
При конструировании регулярного выражения для конкретной задачи часто приходится соблюдать баланс между поиском нужных совпадений, исключением ненужных совпадений и (для НКА) эффективностью поиска (см. с. <$R[P#,R4-29]>). Для механизма НКА эффективность настолько важна, что вся следующая глава посвящается одной теме — построению эффективных регулярных выражений в НКА.
[1] В английском языке слово «engine» обозначает и двигатель машины, и механизм обработки регулярных выражений. К сожалению, сохранить игру слов в русском переводе не удалось — Примеч. перев.
[2] В Калифорнии установлены довольно жесткие стандарты, регулирующие допустимую степень загрязнения окружающей среды автомобилем. Из-за этого многие автомобили продаются в Америке в двух моделях: «для Калифорнии» и «не для Калифорнии».
[3] В действительности, как было показано в предыдущей главе (с. <$R[P#,R3-14]>), объединяющие последовательности POSIX могут совпадать с несколькими символами, но это особый случай.
[4] Конечно, это вовсе не означает, что нельзя изобрести какое-нибудь комбинированное решение, использующее средства обоих механизмов. Этот вопрос рассматривается во врезке на с. <$R[P#,R4-34]>.
[5] Этот пример демонстрирует принцип максимализма с использованием круглых скобок и поэтому подходит только для механизма НКА (поскольку в ДКА такая возможность отсутствует). Тем не менее, принцип максимализма действует во всех механизма, в том числе и в ДКА.
[6] Вероятно, мне бы следовало объяснить азы теории конечных автоматов… если бы я ее знал! Впрочем, теоретические обоснования не столь важны, если понимать их практические последствия. К концу этой главы вы будете в них разбираться. Впрочем, любознательным стоит обратиться к врезке на с. <$R[P#,R4-35]>.
[7] Просто для сравнения вспомните о том, что ДКА не зависит от того, в какой форме представляется выражение; в ДКА все три примера действительно идентичны.
[8] В тех программах, где точка может совпадать с символом новой строки, а текстовый фрагмент может состоять из нескольких логических строк, совпадение всегда распространяется по всем логическим строкам до конца фрагмента.
[9] Заманчивая простота [[^</B>]] не должна сбить вас с толку. Это всего лишь класс, совпадающий с одним символом — любым символом, кроме <, >, / и B. С таким же успехом его можно было записать в виде [[^/<>B]]. Конечно, для поиска «всего, кроме </B>» он не годится.
[10] Одна из возможностей, которая на мой взгляд является полезной, но не поддерживается ни в одном из известных диалектов — так называемые неуступчивые квантификаторы. Они работают так же, как и обычные квантификаторы, но после принятия решения, обеспечивающего локальное успешное совпадение, неуступчивый квантификатор не позволяет вернуться и опробовать другой вариант. Захваченный ими текст может быть возвращен при отмене совпадения для подвыражения, внутри которых они содержатся, но по собственной воле неуступчивый квантификатор не отступает никогда, даже если это необходимо для общего совпадения. С неуступчивым квантификатором ? выражение [(\.\d\d[1-9]?)\d+] решило бы поставленную задачу.
[11] Термин «минимальный» в терминологии регулярных выражений не следует понимать как «обеспечивающий совпадение наименьшей длины». Традиционно он означает «не обеспечивающий совпадения наибольшей длины», то есть «не-максимальный» — Примеч. перев.
[12] В данном случае конкретный текст значения не имеет, но на всякий случай замечу, что этот фрагмент взят из make-файла GNU awk.
[13] Я видел всего две программы, которые вели себя иначе. В старой версии GNU awk (gawk) — в частности, версии 2.15.6 — конструкция выбора не была ни максимальной, ни минимальной. В неоднозначных ситуациях совпадающая альтернатива выбиралась произвольно. Другая программа — MIFES, популярный японский редактор. Некоторые версии иногда преобразуют [.*X] в [[^X]*X]. Вероятно, это делается для того, чтобы регулярные выражения выглядели более «естественно» для тех, кто в них слабо разбирается.
[14] В lex существует понятие завершающего контекста (trailing context), в точности эквивалентное позитивному опережению нулевой длины в конце регулярного выражения, однако оно не обобщается для использования внутри выражения.
[15] Автор — Том Лорд (Tom Lord).
[16] Обратите внимание — символ \n исключен из класса. Как было сказано на с. <$R[P#,R4-9]>, предполагается, что точка не совпадает с символом новой строки, поэтому ее замена тоже не должна с ним совпадать (см. с.<$R[P#,R3-10]>).
[17] А может, и наоборот — все зависит от того, к чему вы привыкли. Новичку все регулярные выражения на первых порах кажутся странными. Вероятно, в Perl реализован самый богатый из всех существующих диалектов регулярных выражений, и из-за нехватки условных обозначений метасимволы часто представляются комбинацией «\ +буква» (например, [\d]). Кому-то эти дополнительные возможности кажутся излишними «фишками», которые лишь увеличивают количество символов \ в строке. Лично я тоже не люблю лишние символы \, но мне нравится обилие возможностей (пусть можно обойтись и без них) и нравится пользоваться ими.
[18] [.*] говорит о том, что вы должны быть особенно внимательны и лишний раз проверить, действительно ли квантификатор * должен применяться к точке. В некоторых ситуациях именно это и требуется, но конструкция [.*] часто используется неправильно.
[19] Следующий фрагмент на Perl по заданному уровню вложенности $depth генерирует регулярное выражение, совпадающее вплоть до заданного уровня:
'\(' . '([^()]|\(' x $depth . '[^()]*' . '\))*' x $depth . '\)'
Читатель может проанализировать его самостоятельно.
[20] Если вы разбираетесь в Perl, возможно, вас удивляет, почему я использую круглые скобки и $1 вместо переменной $&, обозначающей весь совпавший текст. Дело в том, что использование $& в программе может заметно снизить скорость ее работы — см. раздел «Переменная $& и ее родственники» на с. <$R[P#,R7-3]>.