Построение регулярных выражений
Управляемый регулярным выражением механизм НКА встречается в Perl, Tcl, Expect, Python и некоторых версиях grep, awk, egrep и sed (список далеко не полон). Вследствие природы этого механизма незначительные изменения в регулярном выражении могут иметь глобальные последствия для того, какое совпадение будет найдено и как будет происходить процесс поиска. Проблемы, которые в механизме ДКА попросту несущественны, в НКА выходят на первый план. Возможности точной регулировки механизма НКА позволяют творить выражения, хотя для непосвященных это порой вызывает немало проблем. Настоящая глава поможет вам овладеть этим искусством.
Наша цель — правильность и эффективность. Это означает, что выражение должно находить именно то, что нужно, и притом быстро. Правильность рассматривалась в предыдущей главе. В этой главе будут рассмотрены вопросы эффективности механизма НКА и то, как обратить их в свою пользу (там, где это уместно, будет приведена и информация о ДКА, но эта глава в первую очередь посвящена механизмам НКА и вопросам их эффективности). Главное, что для этого нужно — доскональное понимание возврата и умение избегать его там, где это возможно. Мы рассмотрим некоторые практические приемы написания эффективных выражений, которые не только ускоряют их работу, но при хорошем понимании механики их обработки помогут вам создавать более сложные выражения.
Глава начинается с подробного примера, который демонстрирует, насколько важными могут быть эти проблемы. Затем, чтобы подготовиться к восприятию более сложных приемов, описанных далее, мы снова рассмотрим базовую процедуру возврата, описанную в предыдущей главе, с упором на эффективность и глобальные последствия возврата. Далее рассматриваются некоторые стандартные приемы внутренней оптимизации, способные довольно заметно влиять на эффективность, и особенности построения выражений для тех реализаций, в которых эти приемы используются. Наконец, все сказанное объединяется в нескольких убойных приемах, которые помогут вам конструировать чрезвычайно эффективные регулярные выражения НКА.
Как и во многих главах этой книги, приведенные примеры всего лишь демонстрируют общие ситуации, возникающие при использовании регулярных выражений. Анализируя эффективность конкретного примера, я часто привожу число отдельных проверок, используемых механизмом регулярных выражений при поиске совпадения. Например, при поиске [marty] в строке smarty происходит шесть отдельных проверок — сначала [m] сравнивается с s (неудача), затем [m] сравнивается с m, [a] с a и т. д. (все эти проверки проходят успешно). Я также часто сообщаю количество возвратов (в данном примере один — неявный возврат для повторного применения регулярного выражения со второго символа).
Я привожу эти конкретные величины не потому, что здесь так важна точность, а скорее для того, чтобы избежать использования туманных слов «много», «мало», «лучше», «терпимо» и т. д. Не подумайте, что использование регулярных выражений в НКА сводится к подсчету проверок или возвратов; я просто хочу, чтобы вы представляли себе порядок этих величин.
Еще одно важное замечание — вы должны понимать, что эти «точные» числа, вероятно, в разных программах будут разными. Я привожу лишь базовые показатели для тех примеров, которые, как я надеюсь, вам еще пригодятся. Однако приходится учитывать и другой важный фактор — оптимизацию, выполняемую конкретной программой. Достаточно «умная» реализация может полностью устранить поиск конкретного регулярного выражения, если она заранее решит, что оно в любом случае не совпадет с имеющейся строкой (например, из-за отсутствия в строке некоторого символа, который обязательно должен присутствовать в возможном совпадении). Мы рассмотрим некоторые приемы оптимизации в этой главе, но общие принципы важнее частных случаев.
Анализируя эффективность выражения, следует учитывать тип механизма используемой программы (традиционный НКА или POSIX НКА). Как будет показано в следующем разделе, некоторые проблемы относятся лишь к одному из этих типов. Иногда изменение, не влияющее на один механизм, сильно отразится на работе другого. Еще раз подчеркну, что понимание базовых принципов поможет вам правильно оценивать все ситуации по мере их возникновения.
Начнем с примера, который наглядно продемонстрирует, какими важными могут быть проблемы возврата и эффективности. В конце главы 4 мы построили выражение ["(\\.|[^"\\])*"] для поиска строк, заключенных в кавычки. В строке могут присутствовать внутренние кавычки, экранированные символом \ (см. с. <$R[P#,R4-30]>). Это регулярное выражение работает, но в механизме НКА конструкция выбора, применяемая к каждому символу, работает крайне неэффективно. Для каждого «обычного» символа в строке (не кавычки и не экранированного символа) механизм должен проверить [\\.], обнаружить неудачу и вернуться, чтобы в результате найти совпадение для [[^"\\]]. Если выражение используется в ситуации, когда важна эффективность, конечно, хотелось бы немного ускорить обработку этого выражения.
Поскольку в средней строке, заключенной в кавычки, обычных символов больше, чем экранированных, напрашивается простое изменение — изменить порядок альтернатив и поставить [[^"\\]] на первое место, а [\\.] — на второе. Если [[^"\\]] стоит на первом месте, то возврат происходит лишь при обнаружении экранированного символа в строке (и, конечно, при несовпадении *, поскольку конструкция выбора не совпадает лишь в том случае, если не совпадают все альтернативы). Рис. 5.1 наглядно демонстрирует отличия между этими двумя выражениями. Уменьшение количества стрелок в нижней половине означает, что для первой альтернативы совпадения находятся чаще. Это приводит к уменьшению количества возвратов.
Рис. 5.1. Изменение порядка альтернатив (для традиционного НКА)
Оценивая последствия такого изменения для эффективности, необходимо задать себе несколько ключевых вопросов:
l Какой механизм выиграет от этих изменений — традиционный НКА, POSIX НКА или оба?
l Когда изменение приносит наибольшую пользу — когда текст совпадает, когда текст не совпадает или в любом случае?
ref<$M[R5-1]>Подумайте над этими вопросами, затем переверните страницу и проверьте свои ответы. Прежде чем переходить к следующему разделу, убедитесь в том, что вы хорошо понимаете смысл ответов и их обоснование.
Из рис. 5.1 ясно видно, что в обоих случаях квантификатор * должен последовательно перебрать все нормальные символы, при этом он снова и снова входит в конструкцию выбора (и круглые скобки) и выходит из нее. Все эти действия сопряжены с лишней работой, от которой хотелось бы по возможности избавиться.
Однажды, работая над аналогичным выражением, я вдруг понял, что выражение можно оптимизировать, если учесть, что [[^"\\]] относится к нормальным случаям. Если использовать [[^"\\]+], одна итерация (…)* прочитает все последовательно стоящие обычные символы (не кавычки и не экранированные символы). При отсутствии экранированных символов будет прочитана вся строка. Это позволяет найти совпадение практически без возвратов и сокращает многократное повторение * до абсолютного минимума. Я был очень доволен своим открытием.
Последствия простых изменений
bref Ответ на вопрос со с. <$R[P#,R5-1]>
Для какого типа механизма? Изменение практически никак не повлияет на работу механизма POSIX НКА. Поскольку этот механизм в любом случае должен опробовать все комбинации элементов регулярного выражения, порядок проверки альтернатив не важен. Однако в традиционном НКА порядок альтернатив, ускоряющий поиск совпадения, является преимуществом, поскольку механизм может остановиться сразу же после того, как будет найдено первое совпадение.
Для какого результата? Изменение приводит к ускорению поиска лишь при наличии совпадения. НКА может сделать вывод о неудаче только после того, как будут проверены все возможные комбинации (повторяю — POSIX НКА проверяет их в любом случае). Следовательно, если попытка окажется неудачной, значит, были опробованы все комбинации, поэтому порядок не важен.
В следующей таблице перечислено количество проверок и возвратов для некоторых случаев (чем меньше число, тем лучше):
|
Текст примера |
Традиционный НКА ["(\\.|[^"\\])*"] пров. возвр. |
Традиционный НКА ["([^"\\]|\\.)*"] пров. возвр. |
POSIX НКА оба выражения пров. возвр. |
|
"2\"x3\" likeness" |
32 14 |
22 4 |
48 30 |
|
"makudonarudo" |
28 14 |
16 2 |
40 26 |
|
"very…(99 символов)…long" |
218 109 |
111 2 |
325 216 |
|
"No \"match\" here |
124 86 |
124 86 |
124 86 |
Как видите, в POSIX НКА оба выражения дают одинаковые результаты, а в традиционном НКА для нового выражения быстродействие возрастает (уменьшается количество возвратов). В ситуации без совпадения (последний пример в таблице) оба механизма проверяют все возможные комбинации, поэтому и результаты оказываются одинаковыми.
Этот пример будет подробно рассмотрен ниже, но даже беглый взгляд на статистику наглядно демонстрирует преимущества нового выражения. На рис. 5.2 показано, как происходит поиск в традиционном НКА. Модификация исходного выражения ["(\\.|[^"\\])*"] (верхняя пара на рис. 5.2) уменьшает количество возвратов, связанных с конструкцией выбора, а также число итераций квантификатора *. Нижняя пара на рис. 5.2 показывает, что объединение этой модификации с изменением порядка альтернатив приводит к еще большему повышению эффективности.
Рис. 5.2. Последствия добавления плюса (традиционный механизм НКА)
Добавление + уменьшает количество возвратов, обусловленных конструкцией выбора, что в свою очередь, приводит к уменьшению количества итераций *. Квантификатор * относится к подвыражению в круглых скобках, а каждая итерация сопряжена с немалыми затратами при входе и выходе из круглых скобок, поскольку механизм должен хранить информацию о том, какой текст совпадает с подвыражением в скобках (эта тема подробно рассматривается ниже).
Таблица 5.1 аналогична таблице, приведенной во врезке, но в ней рассматривается меньшее количеству примеров и имеются дополнительные столбцы для количества итераций *. При модификации выражения количество проверок и возвратов увеличивается незначительно, но количество итераций уменьшается очень заметно. Налицо заметное повышение эффективности.
|
Текст примера |
["([^"\\]|\\.)*"] пров. возвр. итер. |
["([^"\\]+|\\.)*"] пров. возвр. итер. |
|
"makudonarudo" |
16 2 13 |
17 3 2 |
|
"2\"x3\" likeness" |
22 4 15 |
25 7 6 |
|
"very…(99 символов)…long" |
111 2 108 |
112 3 2 |
<$M[R5-27]>Да, я был очень доволен своим открытием. Но как бы замечательно ни выглядело мое «усовершенствование», на самом деле я сотворил замаскированного монстра. Обратите внимание: расписывая его достоинства, я не привел статистику для механизма POSIX НКА. Вероятно, вы бы сильно удивились, узнав, что пример "veryspc…spc…long" требует выполнения свыше трехсот тысяч миллионов миллиардов триллионов возвратов (324 518 553 658 426 726 783 156 020 576 256, или около 325 нониллионов — если бы мне дали монетку за каждый возврат, то я стал бы богаче самого Билла Гейтса). Мягко говоря, это ОЧЕНЬ много работы. На моем компьютере это заняло бы свыше 50 квинтиллионов лет… плюс-минус несколько сотен триллионов тысячелетий[1].
Ничего себе сюрприз! Почему же это происходит? В двух словах — потому, что к некоторой части нашего выражения применяется как непосредственный квантификатор +, так и внешний квантификатор *, и механизм никак не может определить, какой из этих квантификаторов относится к конкретному символу текста. Подобная неопределенность оборачивается катастрофой. Позвольте пояснить чуть подробнее.
Прежде чем в выражении появился +, [[^"\\]] относилось только к *, и количество вариантов совпадения в тексте выражения [[^"\\]*] было ограниченным. Выражение могло совпасть с одним символом, двумя символами и т. д., но количество возможностей было прямо пропорционально длине целевого текста.
У «эффективного» выражения [([^"\\]+)*] количество вариантов, которыми + и * могут поделить между собой строку, растет с экспоненциальной скоростью. Возьмем строку<$M[R5-11]> makudonarudo. Следует ли рассматривать ее как 12 итераций *, когда каждое внутреннее выражение [[^"\\]+] совпадает лишь с одним символом (m a k u d o n a r u d o)? А может, одну итерацию *, при которой внутреннее выражение [[^"\\]+] совпадает со всей строкой (makudonarudo)? А может, три итерации *, при которых внутреннее выражение [[^"\\]+] совпадает соответственно с 5, 3 и 4 символами (makud ona rudo)? Или 2, 7 и 3 символами (ma kudonar udo)? Или…
В общем, вы поняли — возможностей очень много (4096 в 12-символьной строке). Для каждого нового символа в строке количество возможных комбинаций удваивается, и механизм POSIX НКА должен перепробовать все варианты, прежде чем вернуть ответ. А значит — происходят возвраты, и очень много[2]! 4096 комбинаций для 12 символов обрабатываются быстро, но обработка миллиона с лишним комбинаций для 20 символов занимает уже несколько секунд. Для 30 символов триллион с лишним комбинаций обрабатывается несколько часов, а для 40 символов обработка занимает уже больше года. Конечно, это неприемлемо.
«Ага!» — скажете вы. — «Но механизм POSIX НКА встречается не так уж часто. Я знаю, что в моей программе используется традиционный НКА, поэтому все нормально». Главное отличие между POSIX и традиционным НКА заключается в том, что последний останавливается при первом найденном совпадении. Если полное совпадение отсутствует, то даже традиционный НКА должен перебрать все возможные комбинации, чтобы узнать об этом. Даже в коротком примере "Nospc\"match\"spchere из приведенной выше врезки сообщение о неудаче поступает лишь после проверки 8192 комбинаций.
Да, я был очень доволен своим изобретением. Заодно я решил, что в программе обнаружилась какая-то ошибка — она стала слишком часто «виснуть». Оказывается, программа всего лишь занималась бесконечным перебором комбинаций. Теперь, когда я это понял, подобные выражения вошли в набор тестов для проверки типа механизма:
l Если выражение обрабатывается быстро даже в случае несовпадения — ДКА.
l Если выражение обрабатывается быстро только при наличии совпадения — традиционный НКА.
l Если выражение всегда обрабатывается медленно — POSIX НКА.
Мы вернемся к этой теме в разделе «Определение типа механизма» на с. <$R[P#,R5-5]>.
Конечно, не каждое мелкое изменение приводит к таким катастрофическим последствиям. Но если вы не разбираетесь в механике обработки выражений, то просто не будете знать о проблеме до тех пор, пока не столкнетесь с ней. В этой главе проблемы эффективности и ее последствия рассматриваются на многочисленных примерах. Как обычно, твердое понимание базовых принципов абсолютно необходимо для восприятия более сложных концепций, поэтому прежде чем искать решение проблемы бесконечного перебора, я хочу более подробно описать процесс возврата.
<$M[R5-22]>На локальном уровне возврат — это обратный переход к непроверенному варианту. На глобальном уровне дело обстоит сложнее. В этом разделе мы подробно проанализируем ход возврата при найденном и ненайденном совпадении, а также попытаемся найти общие закономерности в возникающих ситуациях. Если пример из предыдущего абзаца вас не удивил, и вы уверенно разбираетесь во всех деталях, переходите к разделу «Раскрутка цикла», где описаны некоторые нетривиальные приемы повышения эффективности.
Начнем с более подробного рассмотрения некоторых приемов из предыдущей главы. Процесс поиска совпадения [".*"] в строке
The name "McDonald's" is said "makudonarudo" in Japanese
наглядно продемонстрирован на рис. 5.3.
Рис. 5.3. Успешный поиск [".*"]
Поиск регулярного выражения осуществляется в каждой позиции строки, начиная с первой. Поскольку несовпадение обнаруживается при проверке первого элемента (кавычка), ничего интересного не происходит до того, когда поиск начнется с позиции A. В этот момент проверяется оставшаяся часть выражения, однако подсистема смещения текущей позиции (с. <$R[P#,R4-17]>) знает, что если попытка приведет к тупику, все регулярное выражение будет проверено заново со следующей позиции.
[.*] распространяется до самого конца строки, когда для точки не находится совпадения и квантификатор * завершает свою работу. Ни один из 46 символов, совпавших с [.*"], не является обязательным, поэтому в процессе поиска механизм накапливает 46 сохраненных состояний, к которым он может вернуться в случае необходимости. После остановки [.*] механизм возвращается к последнему сохраненному состоянию — «поиск [".*lwr"] в позиции …aneselwr».
Это означает, что механизм пытается найти совпадение для завершающей кавычки в конце текста. Разумеется, кавычка с «ничем» не совпадает (как и точка), поэтому проверка завершается неудачей. Механизм отступает и пытается найти совпадение для завершающей кавычки в позиции …aneslwre. Попытка снова оказывается неудачной.
Сохраненные состояния, накопленные при поиске совпадения от A до B, последовательно проверяются в обратном порядке. После 12 возвратов проверяется состояние «поиск [".*lwr"] в позиции …arudolwr"spcinspcJapa…» (состояние C). На этот раз совпадение может быть найдено, в результате чего мы переходим в состояние D и получаем общее совпадение:
The name "McDonald's" is said "makudonarudo" in Japanese
Так работает традиционный механизм НКА. Остальные непроверенные состояния попросту игнорируются, и механизм возвращает найденное совпадение.
В POSIX НКА найденное выше совпадение запоминается как «самое длинное совпадение, найденное до настоящего момента», однако механизм должен исследовать остальные состояния и убедиться в том, что он не сможет найти более длинное совпадение. Мы знаем, что в данном примере это невозможно, но механизм регулярных выражений должен убедиться в этом. Механизм перебирает и немедленное отвергает все сохраненные состояния за исключением двух ситуаций — когда в строке находится кавычка, которая может совпасть с завершающей кавычкой. Таким образом, последовательности D–E–F и F–G–H аналогичны B–C–D за исключением того, что совпадения F и H отвергаются, как уступающие по длине ранее найденному совпадению.
При возврате к состоянию I остается всего одна возможность — перейти к следующей позиции в строке и попробовать заново. Но поскольку в результате попытки, начинающейся с позиции A, было найдено совпадение (даже целых три совпадения), механизм POSIX НКА завершает свою работу.
Остается выяснить, что происходит при отсутствии совпадений. Рассмотрим выражение [".*"!], для которого в нашем примере не существует совпадения. Однако в процессе поиска оно довольно близко подходит к совпадению, что, как вы сейчас увидите, приводит к существенному возрастанию объема работы.
Происходящее показано на рис. 5.4. Последовательность A–I похожа на рис. 5.3. Первое отличие состоит в том, что на этот раз она не совпадает в точке D (из-за отсутствия совпадения для завершающего восклицательного знака). Второе отличие — то, что вся последовательность операций на рис. 5.4 относится как к традиционному НКА, так и POSIХ НКА: при отсутствии совпадения традиционный НКА должен перепробовать те же варианты, что и POSIX НКА — то есть все возможные варианты.
Поскольку при общей попытке, начинающейся с точки A и заканчивающейся в точке I, совпадение не найдено, механизм переходит к следующей позиции в строке. Попытки, начинающиеся в позициях J, Q и V, выглядят перспективными, но все они завершаются неудачей в точке A. Наконец, в точке Y завершается перебор всех начальных позиций в строке, поэтому вся попытка завершается неудачей. Как видно из рис. 5.4, для получения этого результата пришлось выполнить довольно большую работу.
Для сравнения давайте заменим точку выражением [[^"]]. Как было показано в предыдущей главе, это улучшает общую картину, поскольку выражение становится более точным и работает эффективнее. В выражении ["[^"]*"!] конструкция ["[^"]*] не проходит мимо завершающей кавычки, что устраняет многие попытки и последующие возвраты.
На рис. 5.5 показано, что происходит при неудачной попытке (сравните с рис. 5.4.). Как видите, количество возвратов значительно уменьшилось. Если новый результат вам подходит, то сокращение возвратов можно считать положительным побочным эффектом.
Конструкция выбора является одной из главных причин, порождающих возвраты. В качестве простого примера мы воспользуемся знакомым текстом makudonarudo и сравним, как организуется поиск совпадений для выражений [u|v|w|x|y|z] и [[uvwxyz]]. Символьный класс проверяется простым сравнением, поэтому [[uvwxyz]] страдает только от возвратов перехода к следующей позиции в строке (всего 34), пока не будет найдено следующее совпадение:
The name "McDonald's" is said "makudonarudo" in Japanese
Однако выражение [u|v|w|x|y|z] требует шести возвратов для каждой начальной позиции, поэтому то же совпадение будет найдено только после 204 возвратов.
Конечно, далеко не каждую конструкцию выбора удается заменить каким-нибудь эквивалентом, но даже в этом случае замена не всегда происходит так просто, как в этом примере. Впрочем, мы рассмотрим некоторые приемы, которые в некоторых ситуациях кардинально сокращают количество возвратов, необходимых для поиска совпадения.
Рис. 5.4. Неудачный поиск совпадения для [".*"!]
Рис. 5.5. Неудачный поиск совпадения для ["[^"]*"!]
С точки зрения эффективности одно из положительных свойств предыдущих примеров заключается в том, что они начинаются с одного простого элемента (кавычки). Если этот элемент не совпадает, вся попытка поиска (с текущей начальной позиции) немедленно отменяется. В свою очередь, это позволяет механизму быстро перейти к следующей позиции для повторной проверки.
Как будет показано ниже, по отношению к конструкции выбора (и в других ситуациях) не все выражения одинаково эффективны. Например, черновой вариант выражения для поиска простых строк в апострофах или кавычках может выглядеть так: ['[^']*'|"[^"]*"]. Каждая попытка поиска начинается не с простой кавычки, а фактически с ['|"], поскольку приходится проверять обе возможности. Как следствие, происходит возврат. Было бы хорошо, если бы механизм регулярных выражений понимал, что любое совпадение может начинаться только с кавычки или апострофа и даже не пытался искать совпадение в позициях, не начинающихся с одного из этих символов. Некоторые механизмы выполняют эту оптимизацию автоматически, если они могут определить первый символ. Благодаря специальной возможности Perl, которая называется опережающей проверкой[3]<$M[R5-8]> (lookahead), можно «вручную» проверить [['"]] и немедленно прервать попытку, если оставшаяся часть выражения заведомо не совпадает. Кстати говоря, вместо регулярного выражения ['.*'|".*"] можно было бы использовать [(['"]).*\1], но как будет показано позже, этот способ в данном случае не подходит, поскольку \1 не может использоваться внутри инвертированного (или обычного) символьного класса.
На первый взгляд кажется, что мы поднимаем много шуму из ничего, поскольку простая проверка двух альтернатив в каждой позиции строки не так уж страшна. Но давайте рассмотрим конструкцию типа<$M[R5-7]>
[Jan|Feb|Mar|Apr|May|Jun|Jul|Aug|Sep|Oct|Nov|Dec]
Теперь при каждой попытке выполняется 12 отдельных проверок.
А теперь вернемся к выражениям для поиска даты, приведенным в главе 4 (с. <$R[P#,R4-10]>) — например, [31|[123]0|[012]?[1-9]]. Если объединить это выражение с произвольным выбором месяца, получится следующее выражение:
[(Jan|Feb|…|Nov|Dec)?(31|[123]0|[012]?[1-9])]
В действительности поиск даты — задача более сложная, поэтому настоящий пример не следует воспринимать серьезно. Он всего лишь наглядно показывает, сколько работы приходится выполнять даже при поиске коротких строк. Чтобы проверить совпадение, для каждой начальной позиции приходится последовательно проверять все альтернативы для месяца. Затем перебираются все альтернативы для дат. Только после того, как механизм переберет все комбинации и все попытки завершатся неудачей, можно будет переходить к следующей начальной позиции. Помимо многочисленных возвратов, приходится учитывать затраты, связанные с наличием круглых скобок.
<$M[R5-4]>Одним из важных факторов эффективности, хотя и не связанным напрямую с возвратом, являются затраты, связанные с количеством входов и выходов из круглых скобок. Например, после совпадения начальной кавычки в выражении ["(.*)"] механизм регулярных выражений входит в пару круглых скобок, в которую заключено подвыражение [.*]. При этом механизм выполняет некоторые вспомогательные операции по сохранению совпадающего текста вплоть до выхода из скобок. Внутренняя реализация устроена сложнее, чем кажется на первый взгляд, поскольку «текущее состояние» каждой пары скобок должно быть частью сохраненного состояния, поддерживаемого механизмом.
Рассмотрим четыре разных выражения, совпадающих с одной и той же строкой.
|
|
Регулярное выражение |
Текст в круглых скобках |
|
1. |
".*" |
|
|
2. |
(".*") |
Вся строка (с кавычками) |
|
3. |
"(.*)" |
Текст строки (без кавычек) |
|
4. |
"(.)*" |
Последний символ строки (перед завершающей кавычкой) |
Выражения различаются по тому, какой текст совпадает с подвыражением в круглых скобках, и по эффективности поиска. В приведенных примерах круглые скобки не влияют на логику самого выражения и используются только для сохранения текста. В таких случаях использование скобок зависит от конкретной задачи, но нас интересуют прежде всего проблемы относительного быстродействия.
<$M[R5-21]>Сначала посмотрим, какие затраты связаны с простейшим «входом в круглые скобки» в среднестатистическом случае, когда попытка начинается с символа, отличного от кавычки (то есть во всех позициях, где проверка почти сразу же прерывается). В выражениях 3 и 4 круглые скобки достигаются лишь после совпадения начальной кавычки, поэтому здесь лишние затраты вообще отсутствуют. Однако в выражении 2 каждая попытка сопровождается входом в скобки, и только после этого необходимость совпадения кавычки приводит к неудаче. Это приводит к непроизводительным затратам даже в том случае, если проверка первого же символа завершается неудачей. Тем не менее, оптимизация исключения по первому символу, описанная в следующем разделе, позволяет избавиться от этих непроизводительных затрат. Если механизм понимает, что шансы на успех есть только у совпадений, начинающихся с кавычки, он может быстро обойти все начальные позиции, в которых текст начинается с других символов.
Даже при отсутствии подобной оптимизации один лишний вход в круглые скобки за попытку — не так уж много, поскольку в выражении не используется возврат с вложенными скобками, ни особые действия при выходе. Существенно больше проблем возникает с выражением 4, где вход и выход из круглых скобок происходит для каждого символа в строке.
Более того, поскольку [(.)*] сначала распространяется до самого конца логической строки (или фрагмента — в зависимости от того, совпадает ли точка с символом новой строки), появляются немалые затраты, связанные с возвратом, «отдачей» символов до перехода к завершающей кавычке. На каждом шаге механизм должен проследить за правильным сохранением «последнего символа, совпавшего с точкой», потому что именно этот символ должен храниться в переменной $1 после успешного завершения. Затраты могут оказаться существенными, поскольку этот символ может изменяться с каждым возвратом. Поскольку ["(.)*"] наверняка будет возвращаться от конца строки до последней кавычки, теоретически это приведет к большому количеству возвратов.
В примере 3 затраты существенно меньше, чем в примере 4, хотя, вероятно, все же больше, чем в примере 2 (по крайней мере при наличии полного или частичного совпадения). Как упоминалось выше, выражение 3 не влечет никаких затрат, связанных с круглыми скобками, до того момента, как будет найдено совпадение для начальной кавычки. После завершения поиска [.*] происходит выход из круглых скобок для поиска завершающей кавычки. Это происходит на каждом шаге до тех пор, пока механизм не вернется достаточно далеко и не найдет завершающую кавычку. В целом возникает впечатление, что затраты этого примера менее существенны, чем в примере 4.
Я провел хронометраж для несколько примеров, написанных на Tcl (версия 7.4), Python (версия 1.4b1) и Perl (версия 5.003). На рис. 5.6 показаны результаты замеров для нескольких длинных строк. Строки начинаются и кончаются кавычками, а также не содержат внутренних кавычек — эти факторы в сочетании с длиной строк помогают исключить затраты, не связанные с центральной проверкой [.*]. Обозначения «скобки без сохранения» и «минимальный квантификатор *» относятся к регулярным выражениям, которые используют круглые скобки Perl, обеспечивающие только группировку элементов (и поэтому не обладающие затратами, связанными с сохранением текста), и минимальной версии квантификатора *.
Рис. 5.6. Результаты нескольких тестов с круглыми скобками
Большей частью результаты тестов соответствуют ожиданиям. Для первых трех выражений особой разницы нет, если не считать минимального квантификатора * в Perl, который должен выходить из круглых скобок при каждом перемещении вдоль длинной строки (чтобы увидеть, может ли последующий текст обеспечить совпадение). Как и ожидалось, для выражения ["(.)*"] время выполнения резко возрастает. Это происходит даже для не-сохраняющих круглых скобок Perl, что на первый взгляд кажется странным. Теоретически скобки, не сохраняющие текста и ограничивающиеся группировкой, не должны влиять на работу выражения.
Причины относительно низкой эффективности выражения 4 связаны с оптимизацией простых повторений, рассмотренной в следующем разделе. Большинство механизмов НКА, в том числе и реализованный в Perl, оптимизируют<$M[R5-24]> ситуации, когда квантификатор относится к чему-то «простому», чтобы при каждой итерации механизму не приходилось проходить нормальный цикл проверки. В выражении [(.)*] круглые скобки создают относительно «непростую» ситуацию, поэтому оптимизация отключается. В Python такая оптимизация вообще не выполняется, поэтому все тесты работают одинаково медленно. Увеличение времени для выражения 4, похоже, объясняется только дополнительными затратами по обработке круглых скобок.
Рисунок 5.6 наглядно демонстрирует соотношение скорости работы выражения 4 с остальными примерами. С относительным быстродействием других примеров дело обстоит не столь очевидно, поэтому я подготовил другое представление тех же данных (см. рис. 5.7). Данные каждой программы были по отдельности нормализованы по результату выражения 1 (разному для каждого примера). На рис. 5.7 сравнивать различные линии по любому выражению бессмысленно, поскольку все линии нормализовались независимо. Например, линия Python проходит ниже остальных, но это ничего не говорит о ее быстродействии по отношению к другим линиям — а только о том, что полученные результаты были наиболее похожими для всех трех выражений — одинаково быстрыми или, что более вероятно, одинаково медленными.
Рис. 5.7. Нормализованные результаты тестов
Рисунок 5.7 тоже соответствует ожидаемым результатам. В большинстве случаев характерно небольшое увеличение времени в примере 3, причем для минимального квантификатора * в Perl наблюдается более значительный рост, поскольку он должен выходить из круглых скобок при каждой итерации *. Единственная загадка — почему выражение 2 в Perl работает настолько медленнее выражения 1? Причина относится к специфике Perl, а не к механизму регулярных выражений. В двух словах — это связано с особенностями реализации $1 в Perl. Данная тема подробно рассматривается в главе 7 (с. <$R[P#,R7-4]>).
Из всего сказанного нужно запомнить одно: желательно уменьшить количество круглых скобок и тщательно выбирать их место в регулярном выражении. Если вы используете квантификатор, постарайтесь вынести круглые скобки за его пределы и даже удалить их из выражения, если это возможно. Если вы действительно ищете [".*"], но при этом хотите сохранить последний символ строки (как в ["(.)*"]), гораздо эффективнее будет использовать выражение [(".*")] и затем вручную извлечь предпоследний символ переменной $1 (перед завершающей кавычкой) функцией substr или иным способом.
<$M[R5-17]>Работа механизма регулярных выражений делится на две фазы: анализ выражения в процессе его преобразования во внутреннее представление и последующее сравнение целевой строки с этим внутренним представлением. Если выражение используется многократно (например, при последовательной проверке строк файла), анализ и преобразование не обязательно выполнять каждый раз. Эти операции можно выполнить однократно при первом использовании выражения и сохранить внутреннее представление для всех последующих применений. Таким образом, небольшие «капиталовложения» на анализ выражения и построение внутреннего представления, обеспечивающего ускоренный поиск, принесут большие дивиденды в будущем. Это пример так называемого кэширования при компиляции — одного из способов оптимизации (см. с. <$R[P#,R5-6]>).
Ниже перечислены некоторые стандартные приемы оптимизации. Учтите, что твердо рассчитывать на их реализацию не следует, поэтому в важных приложениях лучше придерживаться более надежного стиля программирования. А там, где это действительно существенно — проведите серию тестов.
Вернемся к примеру [(Jan|Feb|…|Nov|Dec)?(31|[123]0|[012]?[1-9])] со с. <$R[P#,R5-7]>. В каждой позиции, где механизм пытается найти совпадение, требуется выполнить немалое количество возвратов — только для того, чтобы понять, что выражение не совпадает уже с самого первого символа.
Вместо того, чтобы мириться с этими затратами, механизм на стадии предварительного анализа может сделать вывод, что совпадение может начинаться только с некоторых символов (в данном примере — представленных классом [[JFMASOND0-9]]), быстро просканировать строку в поисках этих символов и начать нормальный поиск лишь при нахождении символа. Нахождение возможного начального символа означает не то, что совпадение будет найдено, а лишь то, что оно потенциально возможно. Любые попытки поиска с позиций, начинающихся с других символов, заведомо бесполезны, поэтому такие позиции быстро пропускаются.
Как я уже упоминал, этот вид оптимизации в действительности относится к подсистеме выбора начальных позиций поиска, поэтому он может применяться в механизме любого типа. Специфика предварительной компиляции выражений в ДКА особенно хорошо подходит для исключения по первому символу. С другой стороны, в НКА составление списка возможных начальных символов требует дополнительной работы, которая в полной мере выполняется лишь немногими механизмами. Например, Perl и Tcl останавливаются на середине пути — даже для такой простой конструкции, как [am|pm], они не смогут составить список начальных символов [[ap]].
GNU Emacs поддерживает лишь очень малую часть оптимизаций, упомянутых в этой главе, однако исключение по первому символу выполняется, притом очень хорошо<$M[R5-14]> (что отчасти и позволяет широко использовать регулярные выражения в Emacs). Хотя Perl в этой области отстает от Emacs, зато в Perl эту задачу можно решить вручную. Об этой возможности кратко упоминалось в сноске на с. <$R[P#,R5-8]>, а более подробное описание приведено в главе 7 (с. <$R[P#,R7-1]>).
Конечно, существует множество выражений, в которых исключение по первому символу невозможно — например, любое выражение, начинающееся с [.], поскольку совпадение может начаться с любого символа (кроме новой строки и нуль-символа в некоторых диалектах).
<$M[R5-13]>Если анализ на стадии предварительной компиляции показывает, что в любом совпадении должна присутствовать некоторая фиксированная строка (как, например, строка Subject:spc в выражении [^Subject:spc(Re:spc)?(.*)], или простая кавычка в выражении [".*"], механизм может воспользоваться другой технологией для быстрого исключения целевых текстов, не содержащих этой строки. Дело в том, что эта технология работает гораздо быстрее общего механизма регулярных выражений, поэтому дополнительные затраты времени на предварительную проверку в итоге приводят к экономии времени. Обычно при этом используется алгоритм Бойера-Мура (Boyer-Moore).
Как и в случае с предыдущей оптимизацией, аналитический механизм ДКА обеспечивает тщательную проверку фиксированных строк, но механизмы НКА обычно не столь аккуратны. Например, можно посмотреть на выражение [this|that|them] и сразу понять, что совпадение возможно лишь при наличии в целевой строке th, однако в большинстве механизмов НКА это не происходит — механизм всего лишь убеждается в том, что в выражении присутствует конструкция выбора. Многие механизмы НКА на этом прекращают анализ и отказываются от данного вида оптимизации.
Обратите внимание: если вручную привести это выражение к виду [th(is|at|em)], механизм НКА найдет на верхнем уровне «фиксированную строку th, за которой следует конструкция выбора». Такая формулировка лучше подходит для этой (и предыдущей) оптимизации.
Perl может сообщать о том, когда возможны подобные оптимизации. Если ваша версия была откомпилирована с поддержкой внутренних отладочных средств, вы можете воспользоваться ключом командной строки -Dr (-D512 в старых версиях Perl), чтобы Perl выдавал информацию обо всех регулярных выражениях. В частности, для приведенного примера среди прочего выводится текст start 'th' minlen 2. Атрибут minlen относится к оптимизации учета длины (см. ниже).
В Perl существует интересная оптимизация, имеющая некоторое отношение к проверке фиксированных строк. Perl пытается выполнить ее при использовании функции study (с. <$R[P#,R7-5]>). Он тратит довольно много времени и памяти на подробный анализ строки (обычно длинной), чтобы позднее, когда в этой строке будет производиться поиск, механизм мог немедленно узнать, присутствуют ли в этой строке, скажем, кавычки. Если кавычки отсутствуют, поиск выражения [".*"] на этом прекращается.
<$M[R5-2]>Применение + и других квантификаторов к простым элементам (например, литеральным символам и символьным классам) часто оптимизируется для исключения большей части пошаговых затрат, характерных для стандартного поиска НКА (к механизму ДКА этот способ оптимизации неприменим, поскольку этот механизм управляется текстом). Пошаговые затраты можно сравнить с принципом работы механизма внутреннего сгорания: чтобы повернуть коленчатый вал, необходимо смешать бензин с воздухом и подать смесь в цилиндр поршня. Смесь сжимается при движении поршня вверх и воспламеняется в нужный момент. Происходит маленький взрыв, который толкает поршень вниз, затем клапаны открываются и выпускают выхлопные газы.
Все эти операции заново выполняются на каждом такте двигателя, но в двигателе с наддувом некоторые из них выполняются более эффективно (за счет использования перегретого воздуха для получения более эффективных микровзрывов). Аналогия выглядит в лучшем случае искусственной, но общий принцип понятен: механизм НКА умеет повышать эффективность применения квантификатора к очень простому подвыражению. Основной контрольный цикл в механизме регулярных выражений должен быть достаточно универсальным, чтобы справляться со всеми конструкциями, поддерживаемыми двигателем, а в программировании «универсальный» часто означает «медленный».
В особых ситуациях (например, [x*], [[a-f]+], [.?] и т. д.) специализированный мини-механизм работает быстрее универсального механизма, предназначенного «на все случаи жизни». Этот способ оптимизации широко распространен и обычно обеспечивает существенный выигрыш. Например, результаты тестирования часто показывают, что [.*] работает гораздо быстрее [(.)*]; это объясняется как оптимизацией, так и отсутствием затрат, связанных с круглыми скобками. В этом случае скобки причиняют двойной вред — выражение перестает быть «простым», поэтому оптимизация простого повторения отключается, и к этому добавляются отдельные затраты, связанные с присутствием скобок.
На рис. 5.8 изображены те же данные, что и на рис. 5.7, но добавлен новый случай ["(.)*"]. Другими словами, рисунок повторяет рис. 5.6, но каждая линия независимо нормализована по выражению 1. Рис. 5.8 наглядно демонстрирует результаты оптимизации простого повторения. В выражении ["(.)"] «не-сохраняющие» круглые скобки Perl теоретически ни на что влияют, но на практике выясняется, что из-за присутствия скобок Perl не замечает возможности применения этой оптимизации, что приводит к 50-кратному замедлению работы. С обычными, «сохраняющими» круглыми скобками Perl дело обстоит аналогично, поэтому разность этих двух результатов (16 единиц по вертикальной оси) определяет затраты, связанные с входом и выходом из скобок.
Наконец, как объяснить результаты для минимального квантификатора *? Поскольку механизм должен постоянно выходить из минимального подвыражения [.*] и проверять возможность совпадения дальнейших элементов, оптимизация простого повторения невозможна. Следовательно, в выражении 3 также присутствуют затраты, связанные с входом и выходом из круглых скобок на уровне отдельных символов. Это объясняет, почему для минимального квантификатора * относительное замедление при переходе от выражения 3 к выражению 4 не так уж велико.
<$M[R5-26]>Конструкция вида [xxx] работает намного быстрее, чем [x{3}]. Запись {число} полезна, но если она применяется к небольшому количеству простых элементов, механизм можно освободить от подсчета экземпляров, явно перечисляя нужные элементы.
Рис. 5.8. Нормализованные результаты тестов (полные данные)
Небольшая, но полезная оптимизация. Если на стадии компиляции выясняется, что длина совпадения не может быть меньше некоторой пороговой величины, более короткие строки можно смело игнорировать. Аналогично, попытки поиска, начальная позиция которых приближается к концу строки на меньшее расстояние, также можно пропустить. Как и при других видах оптимизации, требующих глубокого анализа всего регулярного выражения, в ДКА учет длины выполняется хорошо, а НКА часто действует кое-как.
Если POSIX НКА находит совпадение, продолжающееся до конца строки, то найти более длинное совпадение заведомо не удастся, поэтому незачем тратить время на продолжение поиска. Из-за принципа максимализма те совпадения, которые могут продолжаться до конца строки, часто обнаруживаются на относительно ранней стадии поиска — в таких ситуациях этот способ оптимизации приносит огромную пользу.
Если регулярное выражение используется в ситуации, когда точные границы совпадения не важны (то есть когда важен результат — существует совпадение или нет), механизм может прекратить работу при первом же найденном совпадении. Этот способ оптимизации представляет интерес в первую очередь для ДКА и POSIX НКА. Например, egrep вообще не думает о том, какой текст совпал в строке — программа интересуется лишь тем, существует совпадение в строке или нет. Программа GNU grep также понимает это, поэтому ее механизм ДКА ищет самое короткое совпадение, ближнее к левому краю текста, вместо того, чтобы тратить время на поиск самого длинного совпадения. Аналогично, mawk (версия awk Майкла Бреннана) использует POSIX НКА, но переходит на традиционный НКА в тех случаях, когда знать точные границы совпадения не нужно.
Очень простая оптимизация<$M[R5-3]>: если механизм видит, что регулярное выражение (или каждая альтернатива) начинается с метасимвола ^, то совпадение либо начинается от начала строки, либо вообще не существует, поэтому поиск совпадения в других начальных позициях можно исключить. Если ^ может совпасть после внутреннего символа новой строки (с. <$R[P#,R3-15]>), перемещение начальной позиции необходимо, но подсистема перемещения может быстро перейти к следующему символу новой строке, минуя все (вероятно, многочисленные) промежуточные проверки.
Еще одна оптимизация<$M[R5-25]> из той же серии: любое выражение, начинающееся с [.*] и не совпадающее в начале строки, не сможет совпасть со всех дальнейших позиций. В этом случае во внутреннее представление можно смело включить префикс [^]. Мы встречались с этим эффектом в примере с поиском имени файла на с. <$R[P#,R4-36]>. При попытке найти совпадение [.*/] в строке some.long.filename начальное подвыражение [.*] распространяется до конца строки, после чего начинает бесполезные возвраты, пытаясь найти совпадение для косой черты. Таким образом, попытка от начала строки завершается неудачей, но без якорного метасимвола ^ механизм продолжит искать регулярное выражение от последующих начальных позиций. Поскольку начальная конструкция [.*] фактически уже применила остальные элементы выражения (в данном случае — косую черту) к каждой позиции строки, не остается ни малейшей возможности обнаружить совпадение — все последующие попытки будут абсолютно напрасными.
Впрочем, остается еще случай «точки, не совпадающей с символом новой строки». Если существуют некоторые символы, с которыми точка совпасть не может, совпадение может начаться после них (обычно это символ новой строки или нуль-символ). Ситуация аналогична совпадению якорных метасимволов после внутренних новых строк. Если совпадение не будет найдено от начала строки, механизм все равно сможет оптимизировать поиск — для этого последующие попытки начинаются только после очередного символа, не совпадающего с точкой.
<$M[R5-6]>Как кратко упоминалось на с. <$R[P#,R4-37]> и в начале этого раздела, перед непосредственным применением регулярного выражения для поиска оно компилируется во внутреннее представление. Компиляция требует некоторого времени, но после ее выполнения результат может использоваться произвольное количество раз. Например, grep один раз компилирует регулярное выражение и затем применяет его ко всем строкам проверяемого файла.
Откомпилированное представление может использоваться многократно, но всегда ли это происходит? В таких языках, как awk, GNU Emacs, Perl и т. д., регулярные выражения обычно используются непредсказуемым образом, поэтому обеспечение парадигмы «однократной компиляции с многократным использованием» далеко не всегда является тривиальной задачей. Рассмотрим простой пример — grep-образные фрагменты на Tcl и Perl, предназначенные для вывода строк файла, в которых совпадает выражение [[Tt]ubby].
l Tcl
while {[gets $file line]!=-1} {
if {[regexp {[Tt]ubby} $line]} {
puts $line
}
}
l Perl
while (defined($line = <FILE>)) {
if ($line =~ /[Tt]ubby/) {
print $line;
}
}
В приведенных примерах регулярное выражение компилируется и используется (однократно!) в каждой итерации цикла while. Зная общую логику работы программы, мы видим, что каждый раз применяется одно и то же выражение, и многократное использование откомпилированной формы привело бы к немалой экономии времени. К сожалению, для Tcl и Perl это не очевидно. Теоретически они должны заново компилировать регулярное выражение при каждом использовании. Впрочем, на практике существуют средства, позволяющие избавиться от части этой работы. Давайте сравним реализацию средств поиска в Perl и Tcl.
<$M[R5-20]>В Tcl для поиска совпадений используется обычная функция regexp. Эта функция ничего не знает о происхождении своих аргументов. Запись {…} в Tcl обозначает не интерполируемую, литеральную строку, поэтому мы можем взглянуть на {[Tt]ubby} и понять, что это выражение не изменяется между применениями. Однако функция regexp видит лишь только что полученную строку {[Tt]ubby} — она не знает, что аргумент относится к литеральной строке, интерполированной строке, переменной или чему-нибудь еще.
Сравним с Perl, где поиск совпадения осуществляется при помощи оператора. Оператор знает о себе и своих операндах больше, чем может знать функция о своем вызове или способе передаче аргументов. В нашем примере оператор знает, что выражение [[Tt]ubby] представляет собой фиксированную строку, не изменяющуюся от применения к применению, поэтому он может сохранить откомпилированную форму и многократно использовать ее. Это обеспечивает огромную экономию. Но если бы регулярное выражение передавалось в переменной $regex, интерполируемой в команду поиска ($line =~ /$regex/), Perl делал бы вывод о том, что регулярное выражение может измениться между применениями, поскольку оно каждый раз определяется значением $regex.
Даже в этом примере видно, что значение $regex не изменяется внутри цикла, но Perl не умеет мыслить на столь высоком уровне. Тем не менее, поскольку оператор поиска совпадения не является обобщенной функцией, он знает, каким оператором в программе он является, и может запомнить, какое регулярное выражение использовалось при последнем вызове. Оператор просто сравнивает старое и новое выражения (после интерполяции всех переменных) и использует откомпилированную форму, если выражения совпадают. Если строки отличаются, все регулярное выражение компилируется заново.
Поскольку функция Tcl regexp ничего не знает о происхождении своих аргументов или о том, в какой точке сценария она была вызвана, можно подумать, что выражение приходится каждый раз компилировать заново, однако у Tcl в запасе есть свои козыри. Tcl<$M[R5-16]> поддерживает кэш внутренних представлений для пяти последних регулярных выражений, использовавшихся текущим сценарием. При первом проходе цикла regexp компилирует регулярное выражение и использует его для проведения поиска. При всех последующих итерациях цикла regexp передается то же самое выражение, поэтому внутреннее представление берется из кэша. Конечно, каждый раз приходится осуществлять поиск в кэше, но отказ от компиляции все равно обеспечивает большую экономию.
Даже учитывая интеллектуальный подход Perl к компиляции, программист иногда знает, что проверка «а не встречалось ли нам такое регулярное выражение?» является заведомо лишней. Perl предоставляет в распоряжение программиста некоторые средства борьбы с этой неэффективностью. См. раздел «Проблемы эффективности в Perl» главы 7 (с. <$R[P#,R7-6]>).
Python идет еще дальше и позволяет программисту полностью контролировать происходящее. В Python существуют обычные средства работы с регулярными выражениями «на месте», аналогичные функции Tcl regexp, но в дополнение к ним с откомпилированными регулярными выражениями можно работать как с обычными объектами (с. <$R[P#,R3-16]>). Таким образом, у программиста появляется возможность отделить компиляцию выражения от его применения. В нашем примере регулярное выражение достаточно откомпилировать всего один раз, перед входом в цикл. Полученный объект откомпилированного регулярного выражения затем может использоваться в цикле:
CompiledRegex = regex.compile("[Tt]ubby"); # Откомпилировать и сохранить
# регулярное выражение
while 1: # Для всего файла
line = file.readline() # прочитать строку
if not line: break # если пусто, выйти из цикла
if (CompiledRegex.search(line) >= J): # Применить откомпилированное
# регулярное выражение к строке
print line, # вывести, если есть совпадение
Такой подход означает дополнительную работу для программиста, но именно он обеспечивает наибольший контроль за происходящим. При искусном применении этот контроль оборачивается повышением эффективности. Пример на с. <$R[P#,R5-10]> показывает, насколько важную роль могут играть эти проблемы. GNU Emacs, как и Tcl, кэширует пять<$M[R5-15]> регулярных выражений, но замена этого значения на 20 почти в три раза ускорила работу Emacs-версии этого примера.
Процесс определения типа<$M[R5-5]> механизма в незнакомой программе состоит из двух этапов. На первом этапе определяется, какую технологию использует механизм — НКА или ДКА. Если используется механизм НКА, на следующем этапе следует определить, соответствует ли он стандарту POSIX или нет.
Теоретически определение базового типа механизма сводится к простой проверке бесконечного перебора. На практике в некоторых программах используются оптимизации, полностью обходящие этот тест. В результате создается иллюзия того, что никакого бесконечного перебора нет, и механизм можно ошибочно принять за ДКА. Приведу способ проверки grep, который обходит все известные мне оптимизации:
echo =XX================================== | egrep "X(.+)+X"
Кавычки предназначены для командного интерпретатора; используется регулярное выражение [X(.+)+X]. Поиск совпадения должен завершиться неудачей; если это произойдет немедленно, используется механизм ДКА[4]. Если поиск занимает более нескольких секунд, это механизм НКА (и тогда программу следует прервать вручную, потому что при вашей жизни она так и не завершится). Вы также можете попробовать выражение [X(.+)*X] (которое должно совпасть), чтобы узнать, будет ли совпадение найдено немедленно или на это потребуется целая вечность.
Подобные тесты можно применять к любому механизму, хотя возможно, вам придется внести некоторые исправления в соответствии с используемым диалектом регулярных выражений. Например, в GNU Emacs следует занести строку =X===… в буфер и воспользоваться командой isearch-forward-regexp (стандартная комбинация клавиш — M-C-s) для поиска выражения [X\(.+\)+X] (в GNU Emacs группировка осуществляется конструкцией [\(…\)]). Поиск проводится в интерактивном режиме, поэтому в тот момент, когда вы введете вторую букву X, программа «зависает» до тех пор, пока поиск не будет отменен клавишами C-g, или пока механизм не найдет окончательное совпадение. Как показывает этот тест, в GNU Emacs используется механизм НКА. С другой стороны, для тестирования awk можно воспользоваться командой
echo =XX=…=== | awk "/X(.+)*X/{print}"
Если будет немедленно выведена строка =X==…, в вашей версии awk используется механизм ДКА (как и в большинстве существующий версий). Например, если вы используете mawk или Mortice Kern Systems awk, то обнаружите, что в них используется механизм НКА.
Традиционный НКА может остановиться в тот момент, когда он находит совпадение, поэтому при наличии возможного совпадения «бесконечный» перебор быстро завершается. Простой пример для GNU Emacs: введите строку =XX===============X (обратите внимание на завершающий X) и снова примените выражение [X\(.+\)+X]. Вы убедитесь в том, что на этот раз совпадение будет найдено немедленно. Теперь попробуйте использовать то же регулярное выражение с командой posix-search-forward, поисковой функцией механизма POSIX — поиск «зависнет».
Определение разновидности механизма НКА часто затрудняется оптимизациями, о которых упоминалось выше. Если попытаться использовать пример, описанный для awk, в программе mawk (использующей POSIX НКА), окажется, что успешное совпадение возвращается немедленно, несмотря на то, что POSIX-совместимый механизм теоретически должен перебрать те же бесчисленные комбинации, как и при отсутствии совпадения. Причина заключается в применении оптимизации учета границ совпадения — логический результат поиска («есть совпадение или нет») означает, что границы совпадения несущественны, и механизму незачем тратить время на поиски самого длинного совпадения (и вообще какого-нибудь конкретного совпадения).
С другой стороны, если использовать это регулярное выражение там, где важно точное совпадение, mawk в полном соответствии со стандартом POSIX зависает:
echo =XX=…===X | mawk "{sub(/X(.+)*X/, replacement)}"
Если в механизме используется оптимизация учета длины совпадения, он сможет остановиться сразу же после выполнения теста, поскольку некоторое совпадение до конца строки будет найдено немедленно, а благодаря оптимизации механизм поймет, что найти более длинное совпадение невозможно. В данном случае тестирование потребует несколько большей изобретательности. Например, можно просто добавить === в конец строки — механизм подумает, что возможно наличие совпадения большей длины, и продолжит поиск.
От подробного описания базовых принципов мы переходим к приемам повышения эффективности. Методика, которую я называю «раскруткой цикла», хорошо ускоряет работу некоторых распространенных выражений. Цикл, о котором идет речь, создается квантификатором * в выражении, построенном по шаблону [(альтернатива1|альтернатива2|…)*]. Возможно, вы увидели, что наше выражение «бесконечного перебора», ["(\\.|[^"\\])+)*"], подходит под этот шаблон. Учитывая, что для сообщения о несовпадении приходится ждать целую вечность или около того, было бы неплохо как-нибудь ускорить поиск!
При реализации этой методики можно пойти по одному из двух путей:
1. Можно проанализировать, какие части [(\\.|[^"\\])+)*] фактически совпадают при поиске в разных текстах. После этого можно заново сконструировать эффективное выражение на основании шаблонов, выявленных в результате анализа. Я представляю себе происходящее так: большой шар, изображающий [(…)*], прокатывается по тексту. Элементы, находящиеся внутри [(…)], «прилипают» к совпавшему тексту. Если после этого прокатить шар по бумаге, за ним останется цепочка отпечатков (как от грязного мяча, который катится по ковру).
2. В другом варианте используется высокоуровневый анализ той конструкции, для которой ищется совпадение. После этого мы принимаем обоснованное допущение относительно вероятного целевого текста, что позволяет нам смоделировать то, что по нашему мнению, является стандартной ситуацией. Располагая этими сведениями, можно сконструировать эффективное регулярное выражение.
Выражения, полученные в обоих случаях, будут идентичными. Я начну с первого способа, а затем покажу, как придти к тому же результату с позиций высокоуровневого анализа.
При работе с выражением ["(\\.|[^"\\])+)*"] стоит проанализировать некоторые примеры совпадений и выяснить, какие подвыражения использовались в процессе поиска общего совпадения. Например, в строке "hi" фактически используется только выражение ["[^"\\]+"]. Другими словами, в общем совпадении используется только начальная кавычка ["], один экземпляр альтернативы [[^"\\]+] и завершающая кавычка ["]. В тексте
"he said \"hi there\" and left"
фактически используется конструкция ["[^"\\])+\\.[^"\\])+\\.[^"\\]+"]. В этих примерах, а также в табл. 5.2, я пометил выражения, чтобы шаблоны выглядели более наглядно. Нам хотелось бы построить специализированное регулярное выражение для каждой входной строки. Конечно, сделать это невозможно, однако мы можем выделить стандартные шаблоны и сконструировать более эффективное, но при этом достаточно общее регулярное выражение.
Таблица 5.2. Примеры для раскрутки цикла
|
Целевая строка |
Фактическое выражение |
|
"hi there" |
"[^"\\]+" |
|
"just one \" here" |
"[^"\\]+\\.[^"\\]+" |
|
"some \"quoted\" things" |
"[^"\\])+\\.[^"\\])+\\.[^"\\]+" |
|
"with \"a\" and \"b\"." |
"[^"\\])+\\.[^"\\])+\\.[^"\\]+\\.[^"\\])+\\.[^"\\]+" |
|
"\"ok\"\n" |
"\\.[^"\\])+\\.\\." |
|
"empty \"\" quote" |
"[^"\\]+\\.\\.[^"\\]+" |
В табл. 5.2 приведены дополнительные примеры. Пока давайте ограничимся первыми четырьмя примерами. В них подчеркнуты те части, которые обозначают «экранированный элемент, за которым следуют обычные символы». Ключевой момент: в каждом случае выражение между кавычками начинается с [[^"\\]+], после чего следует некоторое количество повторений [\\.[^"\\]+]. Перефразируя сказанное на языке регулярных выражений, мы получаем [[^"\\]+(\\.[^"\\]+)*]. Перед вами частный случай общего шаблона, используемого при конструировании многих полезных выражений.
При поиске строк, заключенных в кавычки, сама кавычка и обратная косая черта являются «специальными» символами. Кавычка — потому что она может завершить строку. Обратная косая черта — потому что она означает, что следующий символ не является завершением строки. Все остальные символы, [[^"\\]], являются «нормальными». Если внимательнее присмотреться к структуре выражения [[^"\\]+(\\.[^"\\]+)*], можно заметить, что оно соответствует общему шаблону [нормальный+(специальный нормальный+)*].
Добавляя кавычки, начальную и завершающую, мы получаем ["[^"\\]+(\\.[^"\\]+)*"]. К сожалению, это выражение не совпадает с двумя последними примерами в табл. 5.2. Проблема состоит в том, что два [[^"\\]] в этом выражении требуют присутствия нормального символа в начале строки и после любого специального символа. Как видно из примеров, это не всегда возможно — строка может начинаться или заканчиваться экранированным символом, или в ней могут идти два экранированных символа подряд.
Можно попытаться заменить плюсы звездочками: ["[^"\\]*(\\.[^"\\]*)*"]. Приведет ли это к желаемому результату? И что еще важнее, не возникнут ли при этом нежелательные побочные эффекты?
Что касается положительных эффектов — видно, что все примеры теперь совпадают. Более того, совпадает даже строка \"\"\"". Это хорошо, но при внесении столь принципиальных изменений нужно быть абсолютно уверенным в том, что при этом не будет отрицательных последствий. Не совпадет ли выражение с чем-нибудь, кроме допустимой строки, заключенной в кавычки? Может ли допустимая строка в кавычках не совпасть? И как насчет эффективности?
Присмотритесь к ["[^"\\]*(\\.[^"\\]*)*"] повнимательнее. Начальное подвыражение ["[^"\\]*] совпадает всего один раз и выглядит безвредным; оно соответствует обязательной начальной кавычке и всем нормальным символам, следующим непосредственно за ней. Никакой опасности в этом нет. Следующее подвыражение [(\\.[^"\\]*)*] заключено в (…)*, поэтому оно может совпасть ноль раз. Это означает, что при его исключении должно остаться правильное выражение. В самом деле, остается ["[^"\\]*"], что вполне нормально — перед нами стандартная ситуация, при которой строка не содержит ни одного экранированного элемента.
С другой стороны, если [(\\.[^"\\]*)*] совпадает один раз, мы фактически приходим к выражению ["[^"\\]*\\.[^"\\]*"]. Даже если завершающее подвыражение ["[^"\\]] не совпадает ни с чем (при этом выражение фактически превращается в ["[^"\\]*\\."]), проблем не возникает. Продолжая аналогичные рассуждения (насколько я помню школьный курс логики, это называется «индукцией»), мы приходим к выводу, что предложенные изменения действительно не вызывают никаких проблем.
Объединяя все сказанное, мы приходим к окончательному варианту выражения для поиска строк в кавычках: ["[^"\\]*(\\.[^"\\]*)*"]. Это выражение совпадает точно с теми же строками, что и старое выражение с конструкцией выбора, и не находит совпадения в тех же строках, где их не находит старое выражение. Но «раскрученная» версия обладает дополнительным преимуществом: она завершит свою работу еще при вашей жизни, потому что работает гораздо эффективнее и избегает проблемы «бесконечного перебора».
Обобщенный шаблон подобных выражений выглядит так<$M[R5-28]>:
[начало норм*(спец норм*)* конец]
Бесконечный перебор в выражении ["[^"\\]*(\\.[^"\\]*)*"] предотвращается тремя правилами, имеющими чрезвычайно большое значение.
Во-первых, подвыражения спец и норм должны быть написаны так, чтобы они никогда не совпадали с одной начальной позиции. Например, [\\.] и [[^"\\]] могут совпадать, начиная с позиции "Hellolwr\n", поэтому они не подходят для пары спец и норм. Если в какой-то ситуации они могут совпасть, начиная с одной позиции, будет непонятно, какое из подвыражений должно использоваться в этом случае, и неопределенность приведет к бесконечному перебору. В примере m a k u d o n a r u d o (с. <$R[P#,R5-11]>) это продемонстрировано наглядно. При отсутствии совпадения (или при любой попытке поиска в механизме POSIX НКА) механизму придется проверить все возможные комбинации элементов. Допустить этого никак нельзя, поскольку выражение строилось заново как раз для того, чтобы избежать подобного перебора.
Если вы проследите за тем, чтобы спец и норм никогда не совпадали с одной позиции, подвыражение спец будет использоваться для разрешения ситуаций, когда несколько экземпляров норм в разных итерациях цикла [(…)*] могут совпасть с одним и тем же текстом. Если спец и норм никогда не совпадают с одной позиции, всегда будет существовать ровно одна возможная «последовательность» подвыражений спец и норм, которая может совпасть с конкретной строкой. Одна последовательность проверяется гораздо быстрее, чем сто миллионов последовательностей; таким образом, нам благополучно удается избежать бесконечного перебора.
Это правило выполняется в приведенном выше примере, где норм соответствует выражение [[^"\\]], а спец — выражение [\\.]. Они никогда не могут начинаться с одного символа — во втором случае обязателен префикс \, а в первом он явно исключен из класса.
Второе важное правило состоит в том, что выражение спец всегда должно совпадать хотя бы с одним символом (если оно вообще с чем-нибудь совпадает). Если это выражение может совпадать без поглощения символов, соседние нормальные символы смогут разделяться разным количеством итераций [(спец норм*)*], и мы вернемся с прежней проблеме (…*)*.
Например, выбор в качестве спец выражения [(\\.)*] нарушает это правило. При попытке найти злосчастное[5] выражение ["[^"\\]*((\\.)*[^"\\]*)*"] в строке "Tubby (при отсутствии совпадения) механизм должен проверить все комбинации совпадения нескольких экземпляров [[^"\\]] в Tubby, и только после этого придти к выводу о неудаче. Если выражение спец может совпадать с пустой строкой, оно утрачивает свои функции «устранения неоднозначности».
Третье важное правило лучше всего пояснить на примере. Рассмотрим задачу поиска последовательности, состоящей из необязательных комментариев Pascal {…} и пробелов. Регулярное выражение для поиска комментариев имеет вид [\{[^}]*\}], поэтому при бесконечном переборе все выражение выглядит так: [(\{[^}]*\}|spc+)*]. На первый взгляд хочется выбрать следующие выражения спец и норм:
|
спец |
норм |
|
[spc+] |
[\{[^}]*\}] |
Подставляя эти выражения в построенный ранее шаблон [норм*(спец норм*)*], мы получаем: [(\{[^}]*\})*(spc+(\{[^}]*\})*)*]. А теперь рассмотрим строку:
{comment}spcspcspc{another}spcspc
Последовательность из нескольких пробелов может совпадать с одним подвыражением [spc+], с несколькими подвыражениями [spc+] (каждое из которых совпадает с одним пробелом) или с различными комбинациями [spc+], совпадающими с разными количествами пробелов. Наблюдается прямая аналогия с нашим примером m a k u d o n a r u d o.
Корень проблемы заключается в том, что спец может совпасть с меньшим фрагментом текста внутри большего фрагмента, с которым это выражение тоже может совпасть, причем из-за [(…)*] это может происходить неоднократно. Подобная неопределенность порождает уже знакомую проблему «разных вариантов совпадения одного текста».
Если общее совпадение существует, вероятно, все пробелы будут отнесены на счет внутренней конструкции [spc+], но при отсутствии совпадения (например, если выражение используется внутри большего регулярного выражения, для которого поиск может оказаться неудачным) механизм должен рассмотреть все комбинации совпадения [(spc+)*] в серии из нескольких пробелов. На это тратится время, но без малейшей надежды на совпадение. Поскольку подвыражение спец само должно устранять неопределенность, нет ничего, что позволило бы избавиться от неопределенности внутри этого выражения.
Решение проблемы — позаботиться о том, чтобы выражение спец совпадало только с фиксированным количеством пробелов. Поскольку оно должно совпадать по крайней мере один раз (но может и больше), мы просто выбираем [spc] и разрешаем совпадение нескольких экземпляров спец с несколькими пробелами через внешний квантификатор [(…)*].
Приведенный пример хорошо подходит для анализа, но если бы мне действительно потребовалось такое выражение, я бы переставил спец и норм:
[spc*(\{[^}]*\}spc*)*]
Это связано с тем, что программа на языке Pascal содержит больше пробелов, чем комментариев, а выражение норм должно относиться к более распространенному случаю.
После того, как вы усвоите эти правила (возможно, для этого придется несколько раз перечитать их и немного поэкспериментировать), вы сможете выделить общие признаки регулярных выражений, подверженных «бесконечному перебору». Многоуровневые квантификаторы (такие, как [(…*)*]) часто предупреждают об опасности, но они встречаются и во многих вполне допустимых выражениях:
l [(Re:spc*)*] — выделение цепочек префиксов Re: произвольной длины (например, выражение может использоваться для «очистки» строки темы «Subject:spcRe:spcRe:spcRe:spchey»).
l [(spc*\$[0-9]+)*] — поиск денежных сумм в долларах (возможно, разделенных пробелами).
l [(.*\n)+] — поиск одной или нескольких логических строк. Обратите внимание: если точка может совпадать с символом новой строки, а после этого подвыражения следует нечто, приводящее к неудаче, снова возникает ситуация «бесконечного перебора».
Все эти выражения вполне допустимы, поскольку в каждом из них присутствует «маркер», предотвращающий опасную ситуацию «разных вариантов совпадения одного текста». В первом примере это [(Re:], во втором — [\$], а в третьем (если точка не совпадает с символом новой строки) — [\n].
Как я говорил выше, к одному и тому же выражению можно придти двумя<$M[R5-13]> путями. Давайте попробуем разобраться, чего добивается выражение [(\\.|[^"\\]+)*], и в какой ситуации оно будет в основном использоваться. Вероятно, строка в кавычках в основном состоит из обычных, а не экранированных символов, поэтому основная работа достанется подвыражению [[^"\\]+]. Подвыражение [\\.] необходимо лишь для того, чтобы разобраться с редкими экранированными символами. Конструкция выбора учитывает оба случая и позволяет использовать это выражение на практике, но все же не хочется снижать эффективность всего поиска ради редких (а то и вовсе отсутствующих) экранированных символов.
Если мы полагаем, что [[^"\\]+] обычно совпадает с большей частью символов в строке, то после его совпадения должна следовать либо кавычка, либо обратная косая черта. Если это обратная косая черта, мы добавляем еще один символ (каким бы он ни был) и находим новую порцию основного текста [[^"\\]+]. Каждый раз, когда совпадение [[^"\\]+] завершается, мы оказываемся в той же ситуации — следующим символом является либо завершающая кавычка, либо очередная обратная косая черта.
Выражая все сказанное на языке регулярных выражений, мы приходим к тому же, что уже встречалось нам в методе 1: ["[^"\\]+(lwr\\.[^"\\]+)*"]. Каждый раз, когда поиск достигает позиции, обозначенной lwr, мы знаем, что следующим символом будет либо обратная косая черта, либо кавычка. Если обратная косая черта совпадает, мы берем ее, следующий символ и текст до следующей точки перед кавычкой или обратной косой.
Как и в предыдущем методе, необходимо предусмотреть ситуации, при которых начальный сегмент или сегменты между кавычками пусты. Для этого плюсы заменяются звездочками, и мы приходим к уже знакомому выражению.
Я обещал описать два пути, по которым можно придти к окончательному выражению «раскрутки цикла», но в дополнение к ним я представлю похожий метод, который можно считать третьим. Я столкнулся с ним во время работы над регулярным выражением для поиска доменных имен (prez.whitehouse.gov или www.yahoo.com), которые в сущности представляют собой списки имен субдоменов, разделенных точками. В этом примере для идентификации субдомена будет использоваться простое (хотя и неполное) выражение [[a-z]+].
Если субдомен определяется выражением [[a-z]+], и мы хотим найти список субдоменов, разделенных точками, поиск должен начинаться с одного имени субдомена. После него может следовать перечень необязательных имен других субдоменов, начинающийся с точки. Если выразить все сказанное на языке регулярных выражений, мы получим [[a-z]+(\.[a-z]+)*]. А если записать это выражение в виде [[a-z]+(\.[a-z]+)*], оно становится очень знакомым!
Чтобы продемонстрировать сходство, мы проведем аналогию с выражением для поиска строк в кавычках. Если рассматривать строку как последовательность нормальных символов [[^\\"]], разделенных специальными символами [\\.], то все, что находится внутри ["…"], можно подставить в шаблон «раскрутки цикла». Получается ["[^"\\]+(\\.[^"\\]+)*"] — в точности то же самое, что мы получили на определенной стадии при обсуждении метода 1. Возможно, интерпретация содержимого строки в кавычках как «последовательности неэкранированных символов, разделенных экранированными символами» выглядит несколько неестественно, но она открывает новый интересный путь к уже знакомому результату.
Между этими двумя примерами (строки в кавычках и доменные имена) существуют два принципиальных отличия:
l Доменные имена не заключаются во внешние ограничители.
l Подвыражение норм в доменном имени, то есть имя субдомена, никогда не бывает пустым (иначе говоря, точки не могут стоять подряд и не могут начинать или заканчивать совпадение). В строке, заключенной в кавычки, наличие хотя бы одного совпадения норм вообще не требуется, хотя такие совпадения весьма вероятны, учитывая наши предположения относительно данных. Вот почему мы заменили ["[^"\\]+] на ["[^"\\]*]. В примере с субдоменами это невозможно, поскольку спец представляет собой обязательный разделитель.
Подведем итоги. Можно заметить, что наше выражение ["[^"\\]*(\\.[^"\\]*)*"] обладает как достоинствами, так и недостатками.
l Неудобочитаемость. Вероятно, самый большой недостаток заключается в том, что исходное выражение ["([^"\\]|\\.)*"] выглядело более понятно. Наглядностью пришлось отчасти пожертвовать ради эффективности.
l Сложность сопровождения. Выражение ["[^"\\]*(\\.[^"\\]*)*"] труднее поддерживать, поскольку любые изменения приходится синхронизировать в двух экземплярах [[^"\\]]. Затрудненное сопровождение искупается повышением эффективности.
l Исключение зависаний. Новое выражение не приводит к зависанию при отсутствии совпадений (или в POSIX НКА). Благодаря тщательно продуманной структуре выражения, допускающей лишь один вариант совпадения с конкретным фрагментом, механизм быстро приходит к выводу, что несовпадающий текст действительно не совпадает.
l Скорость. В серии тестов, проведенных мной для традиционного НКА, раскрученная версия стабильно работала быстрее старой версии с конструкцией выбора. Это относится даже к успешным совпадениям, где в старой версии не возникало проблем с зависанием.
Рассмотрим пример раскрутки цикла для более сложного целевого текста. В языке C комментарии начинаются с символов /*, завершаются символами */ и могут распространяться на несколько строк (однако вложение комментариев не допускается). Выражение, совпадающее с таким комментарием, может использоваться в разнообразных ситуациях — например, при написании программы-фильтра для удаления комментариев. Работая над этой задачей, я впервые пришел к идее раскрутки цикла, и с тех пор она заняла почетное место в моем арсенале регулярных выражений.
В комментариях C не существует последовательностей, которые бы интерпретировались особым образом — как, например, экранированные кавычки внутри строки, заключенной в кавычки. Это упрощает задачу, однако поиск комментариев C затрудняется тем, что «завершающая кавычка» */ состоит из нескольких символов. Простое решение [/\*[^*]*\*/] не работает, поскольку оно не совпадет с вполне допустимым комментарием /** some comment here **/, содержащим внутренние символы *. Нам потребуется более сложное решение.
Вероятно, вы обратили внимание, что выражение [/\*[^*]*\*/] очень плохо читается — к сожалению, один из символов-ограничителей комментария, *, также является метасимволом регулярного выражения. От обилия префиксов \ начинает болеть голова. Чтобы выражение выглядело более понятно, мы будем считать, что комментарий заключается в ограничители /x…x/, а не /*…*/. Это искусственное изменение позволит записать [/\*[^*]*\*/] в наглядной форме [/x[^x]*x/]. В процессе анализа этого примера выражение станет еще более сложным, и вы оцените это упрощение по достоинству.
В главе 4 (с. <$R[P#,R4-38]>) я привел стандартный алгоритм поиска текста, заключенного между ограничителями:
1. Найти открывающий ограничитель.
2. Найти основной текст (фактически это означает «все, что не является закрывающим ограничителем»).
3. Найти закрывающий ограничитель.
Похоже, наши псевдокомментарии /x…x/ подходят под этот шаблон. Трудности начинаются, когда вы попытаетесь найти «все, что не является закрывающим ограничителем». Если закрывающий ограничитель представляет собой одиночный символ, можно воспользоваться инвертированным символьным классом, совпадающим со всеми символами, кроме ограничителя. Однако не существует общего обозначения «всего, что не является многосимвольным ограничителем»[6], поэтому выражение придется строить более тщательно. К поиску совпадения до первого x/ можно подойти двумя способами. Первый — рассматривать x как начало закрывающего ограничителя. В этом случае мы ищем все, что не совпадает с x, и допускаем x в том случае, если за ним следует что-то отличное от символа /. Таким образом, «все, что не является закрывающим ограничителем» может быть:
l любым символом, кроме x: [^x];
l x, если за ним не следует символ /: [x[^/]].
В результате основному тексту соответствует выражение [(х[^x]|x[^/])*], а всему псевдокомментарию — [/x(х[^x]|x[^/])*x/].
Другой способ заключается в том, чтобы рассматривать / как закрывающий ограничитель, но лишь в том случае, если ему предшествует x. Таким образом, «все, что не является закрывающим ограничителем» может быть<$M[R5-12]>:
l любым символом, кроме /: [^/];
l символом /, если ему не предшествует x: [[^x]/].
В результате основному тексту соответствует выражение [([^/]|[^x]/)*], а всему комментарию — [/x([^/]|[^x]/)*x/].
К сожалению, ни один из этих способов не работает.
Начнем с [/x(х[^x]|x[^/])*x/]. Рассмотрим строку /xxspcfoospcxx/ — после совпадения с foospc первый символ x совпадает с [x[^/]], что вполне нормально. Но затем [x[^/]] совпадает с xx/, а этот символ x должен входить в закрывающий ограничитель комментария. В результате совпадение продолжится и после x/ (до конца следующего комментария, если он существует).
Что касается [/x([^/]|[^x]/)*x/], то это выражение не совпадает с /x/spcfoospc/x/ (вполне нормальным комментарием, который должен совпадать). В других случаях это выражение может выйти за конец комментария, за которым немедленно следует / (по аналогии с первым способом). Возврат, происходящий в таких случаях, несколько запутывает ситуацию, поэтому вам стоит разобраться, почему [/x([^/]|[^x]/)*x/] совпадает в строке
years = days /x divide x//365; /x assume non-leap year x/
с подчеркнутым текстом (эта задача остается читателю для самостоятельной работы).
Давайте попробуем исправить эти регулярные выражения. В первом выражении, где [x[^/]] непреднамеренно совпадает с …xx/ в завершении комментария, рассмотрим новый вариант [/x([^x]|x+[^/])*x/]. Предполагается, что благодаря дополнительному + [x+[^/]] совпадает с цепочкой x, после которой следует символ, отличный от /. И это действительно так, но из-за возврата «символ, отличный от /» может оказаться все тем же x. Сначала максимальный квантификатор [x+] совпадает с лишним x, как мы и хотели, но вследствие возврата этот символ может быть возвращен, если это необходимо для получения общего совпадения. К сожалению, выражение по-прежнему захватывает слишком много:
/xx A xx/ foo() /xx B xx/
Чтобы придти к правильному решению, нужно вспомнить то, что я говорил раньше: формулируйте выражение как можно точнее. Если мы хотим определить «цепочку x, после которой следует символ, отличный от /», и при этом подразумевается, что «символ, отличный от /» также отличен и от x, об этом нужно сообщить явно: [x+[^/x]]. Как и требовалось, эта запись предотвращает поглощение [xxx/] — последнего x в цепочке, завершающей комментарий. В качестве побочного эффекта предотвращается совпадение со всеми символами x, завершающими комментарий, поэтому мы оказываемся в позиции …lwrxxx/ перед закрывающим ограничителем. Поскольку часть выражения, относящаяся к завершающему ограничителю, допускает всего один символ x, в нее необходимо добавить квантификатор +: [x+/].
В результате получается следующее выражение: [/x([^x]|x+[^/x])*x+/].
Перевод на язык регулярных выражений
На с. <$R[P#,R5-12]>, при описании двух вариантов поиска в комментариях C «всего, что не является закрывающим ограничителем», я представил две идеи:
…x, если за ним не следует символ /: [x[^/]]
и
…символом /, если ему не предшествует x: [[^x]/]
При этом я выражался неформально — описания отличаются от приведенных регулярных выражений. Вы видите, о чем речь?
Чтобы понять, в чем заключаются отличия, примените первое описание к строке «regex». В ней присутствует символ x, за которым не следует косая черта, однако эта строка не совпадет с [x[^/]]. Символьный класс совпадает с символом, и хотя этот символ не может быть косой чертой, он все равно должен быть чем-то другим, а не «ничем», как в строке «regex». Во второй ситуации дело обстоит аналогично.
Кстати, обратите внимание: если вам действительно потребуется реализовать формулировку «x, если за ним не следует символ /», попробуйте использовать выражение [x([^/]|$)]. Оно по-прежнему совпадает как с символом x, но также может совпадать и с концом строки. Более удачное решение (если оно доступно) заключается в использовании негативной опережающей проверки. В Perl эта возможность реализуется конструкцией [x(?!…)]. Описание «x, если за ним не следует символ /» формулируется в виде [x(?!/)].
К сожалению, ретроспективная проверка (lookbehind) не поддерживается ни в одном из известных мне диалектов, поэтому оборот «символ /, если ему не предшествует x» можно записать разве что в виде [(^|[^x])/].
Выражение для настоящих комментариев, со звездочками вместо x, выглядит еще хуже:
[/\*([^*]|\*+[^/*])*\*+/]
Чтобы прочитать такое выражение, вам придется изрядно пошевелить мозгами.
Попробуем повысить эффективность выражения, избавившись от конструкции выбора. В табл. 5.3 приведены выражения, которые должны подставляться в шаблон раскрутки цикла. Как и в примере с доменными именами, [норм*] не может совпадать с «ничем». В предыдущем примере это было связано с тем, что «нормальная» часть (имя субдомена) не могла быть пустой. В данном случае это объясняется особенностями обработки двухсимвольного закрывающего ограничителя. Любая последовательность норм должна завершаться с первым символом закрывающего ограничителя, позволяя спец «перехватить» совпадение лишь в том случае, если следующий символ не завершает ограничитель.
Таблица 5.3. Компоненты раскрутки цикла для комментариев C
|
Компонент |
Аналог в тексте |
Регулярное выражение |
|
начало |
Начало комментария |
/x |
|
норм |
Текст комментария до одного или нескольких x включительно |
[^x]*x+ |
|
спец |
Символ, отличный от завершающей косой черты (и не являющийся x) |
[^/x] |
|
конец |
Завершающая косая черта |
/ |
Подставляя эти компоненты в общий шаблон раскрутки цикла, мы получаем:
[/x[^x]*x+(lwr[^/x][^x]*x+)*/]
Обратите внимание на помеченный фрагмент. Механизм регулярных выражений может придти к нему двумя путями (как и в выражении на с. <$R[P#,R5-13]>): либо продвижением через начальную конструкцию [/x[^x]*x+], либо циклическим перебором (…)*. В любом случае, оказавшись в этом позиции, мы знаем, что был найден символ x, и текущая позиция является критической точкой — возможно, в конце комментария. Если следующим символом является косая черта, поиск закончен. Если это любой другой символ (конечно, кроме x), мы знаем, что тревога была ложной и можно вернуться к поиску совпадений для компонента норм в ожидании следующего x. После того, как символ будет найден, мы снова оказываемся в критической точке.
Выражение [/x[^x]*x+([^/x][^x]*x+)*/] не совсем готово к практическому использованию. Во-первых, конечно, комментарии обозначаются ограничителями /*…*/, а не /x…x/. Проблема легко решается заменой каждого x на экранированную звездочку \* (в символьных классах — простой заменой x на *):
[/\*[^*]*\*+([^/*][^*]*\*+)*/]
Также следует учесть тот факт, что комментарии часто распространяются на несколько строк. Если искомый текст содержит весь многострочный комментарий, это выражение будет работать. Однако в строчно-ориентированных программах (таких, как egrep) не существует возможности применить регулярное выражение к полному комментарию (к тому же в большинстве версий egrep используется механизм ДКА, поэтому вам вообще не придется беспокоиться о раскрутке цикла). В Emacs, Perl и ряде других полезных программ, упомянутых в книге, это возможно, поэтому данное выражение может применяться, например, для удаления комментариев.
На практике возникает еще одна большая проблема. Наше регулярное выражение понимает комментарии C, но ничего не знает о других важных аспектах синтаксиса C. Например, оно может совпасть и при отсутствии комментария:
const char *cstart = "/*", *cend = "*/";
Наше выражение будет усовершенствовано в следующем разделе.
Мы потратили некоторое время на конструирование регулярного выражения, предназначенного для поиска комментариев C, и остановились на проблеме случайных совпадений, по своей структуре напоминающих комментарии. Например, в Tcl для удаления комментариев можно попытаться использовать следующий фрагмент:
set COMMENT {/\*[^*]*\*+([^/*][^*]*\*+)*/} # комментарий
regsub -all "$COMMENT" $text {} text
(примечание: неинтерполируемые строки в Tcl задаются в виде {...} )
Этот фрагмент берет содержимое переменной COMMENT, интерпретирует его как регулярное выражение и заменяет все его совпадения в строке, заданной переменной text. Совпадающий текст заменяется «ничем» (то есть пустой строкой Tcl, { }). После завершения подстановки результат снова заносится в переменную text.
Проблема<$M[R5-23]> заключается в том, что в процессе перемещения начальной позиции начало совпадения может быть случайно обнаружено внутри строки. Наша задача — сделать так, чтобы механизм регулярных выражений в процессе поиска игнорировал строки, заключенные в кавычки.
Рассмотрим следующий фрагмент:
set COMMENT {/\*[^*]*\*+([^/*][^*]*\*+)*/} # комментарий
set DOUBLE {"(\\.|[^"\\])*"} # строка в кавычках
regsub -all "$DOUBLE|$COMMENT" $text {} text
Если поиск начинается в позиции, где может совпасть выражение $DOUBLE, вся строка в кавычках игнорируется. Возможность включения обеих альтернатив в поиск обусловлена полным отсутствием неоднозначности между ними. Начиная с левого края, любая начальная позиция в строке…
l является началом комментария, что приводит к немедленному пропуску символов до конца комментария; или…
l является началом строки в кавычках, что также приводит к немедленному пропуску до конца строки; или…
l не обеспечивает совпадения ни для одного из этих выражений. В этом случае механизм смещает начальную позицию только на один символ.
В этом случае начальная позиция совпадения никогда не будет находиться внутри строки или комментария — в этом и заключается секрет успеха.
Пока этот фрагмент остается бесполезным, поскольку вместе с комментариями он удаляет и строки, заключенные в кавычки. Впрочем, небольшое изменение ставит все на свои места.
set COMMENT {/\*[^*]*\*+([^/*][^*]*\*+)*/} # комментарий
set DOUBLE {"(\\.|[^"\\])*"} # строка в кавычках
regsub -all "($DOUBLE)|$COMMENT" $text {\1} text
В этот фрагмент были внесены следующие изменения:
l Добавлены круглые скобки для заполнения \1 (аналог переменной Perl $1, используемый в Tcl при замене) в том случае, если обнаруживается строка в кавычках. Если будет найдена альтернатива-комментарий, переменная \1 остается пустой.
l В качестве заменяющей строки была подставлена та же переменная \1. Если теперь будет найдена строка в кавычках, она заменяется той же самой строкой — происходит тождественная замена, поэтому строки в кавычках из текста не удаляются. С другой стороны, при совпадении альтернативы комментария переменная \1 остается пустой, поэтому комментарий, как и было запланировано, заменяется пустой строкой.
Наконец, мы должны позаботиться о константах C, заключенных в апострофы ('\t' и т. д.). Задача решается просто — включением в круглые скобки новой альтернативы. Если вы захотите удалять и комментарии C++ //; для этого достаточно добавить четвертую альтернативу [//[^\n]*], не заключая ее в круглые скобки. В регулярных выражениях Tcl запись \n отсутствует, зато она поддерживается в строках Tcl, заключенных в кавычки, поэтому для создания [//[^new]*] следует использовать строку "//\[^\n]*":
set COMMENT {/\*[^*]*\*+([^/*][^*]*\*+)*/} # комментарий
set COMMENT2 "//\[^\n]*" # комментарий C++ //
set DOUBLE {"(\\.|[^"\\])*"} # строка в кавычках
set SINGLE {'(\\.|[^"\\])*'} # константа в апострофах
regsub -all "($DOUBLE|$SINGLE)|$COMMENT|$COMMENT2" $text {\1} text
В основу этого решения заложена довольно изящная идея: во время проверки текста механизм быстро находит (и в нужных ситуациях — удаляет) эти специальные конструкции. Я провел небольшой тест: для удаления всех комментариев из файла объемом 1,6 Мбайт, состоящего из 60 000 строк, на моем компьютере Tcl затратил всего 37 секунд.
Если приложить некоторые дополнительные усилия, процесс поиска совпадений можно значительно ускорить. Рассмотрим длинные последовательности символов обычного кода C между комментариями и строками в кавычках. Для каждого такого символа механизм регулярных выражений должен опробовать все четыре альтернативы и определить, не относится ли он к одному из четырех «поглощаемых» фрагментов. Только если проверка всех четырех альтернатив завершается неудачей, символ отвергается как «неинтересный», и механизм переходит к следующей позиции. Таким образом, выполняется большая работа, которую на самом деле выполнять не обязательно.
Например, мы знаем, что для совпадения какой-либо из четырех альтернатив начальный символ должен быть косой чертой, апострофом или кавычкой. Выполнение этого условия еще не гарантирует совпадения, но его невыполнение заведомо говорит о том, что совпадения нет. Итак, вместо того, чтобы заставлять механизм выполнять медленный и мучительный перебор, мы прямо укажем на этот факт и включим символьный класс [[^'"/]] в качестве отдельной альтернативы. Более того, в файле эти «неинтересные» символы могут следовать подряд, поэтому мы воспользуемся выражением [[^'"/]+]. Если вы помните пример с бесконечным перебором, возможно, вас обеспокоит появление нового плюса. В самом деле, плюс внутри конструкции (…)* способен причинить массу хлопот, но как самостоятельная конструкция он вполне допустим (за ним нет ничего, что могло бы принудить механизм к возврату и стать причиной бесконечного перебора). Итак, в наш тест включаются новые строки:
set OTHER {[^"'/]} # Символ, который не может быть
… # началом любой другой альтернативы
regsub -all "($DOUBLE|$SINGLE|$OTHER+)|$COMMENT|$COMMENT2" $text {\1} text
Я заново запускаю свой тест. Изумленная публика ликует — всего одно изменение сократило время обработки с 36 секунд до 3,2 секунды! Обработка ускорилась на целый порядок. В построенном нами выражении исключена большая часть непроизводительных затрат по перебору альтернатив и последующему смещению начальной позиции. Остаются еще относительно редкие ситуации, при которых не совпадает ни одна из альтернатив (например, «cspclwr/spc3.14»). В этом случае для перебора приходится довольствоваться стандартным механизмом смещения текущей позиции.
Но даже сейчас работа еще не закончена — работу механизма можно еще ускорить:
l Как правило, чаще всего будет совпадать альтернатива [$OTHER+], поэтому мы поставим ее на первое место в круглых скобках. Для механизма POSIX НКА это несущественно, поскольку он всегда проверяет все альтернативы, но в Tcl реализован традиционный механизм НКА, прекращающий поиск сразу же после нахождения совпадения. Стоит ли заставлять его подолгу разыскивать то, что, по нашему мнению, является самой частой альтернативой?
l После нахождения строки, заключенной в апострофы или кавычки, за ней с большой вероятностью последуют повторения $OTHER, после чего последует другая строка или комментарий. Если добавить [$OTHER*] после каждой строки, мы тем самым сообщим механизму, что он может перейти немедленно к поиску совпадения для $OTHER без обработки цикла -all. Происходящее напоминает методику раскрутки цикла. В сущности, выигрыш в скорости от раскрутки цикла в значительной степени обусловлен тем, что мы «направляем» механизм регулярных выражений к совпадению, используя общие сведения о целевом тексте для создания локальных оптимизаций. Механизм регулярных выражений получает именно те сведения, которые необходимы для его быстрой работы.
Очень важно, чтобы выражение $OTHER, которое добавляется после каждого подвыражения, совпадающего со строкой в кавычках или апострофах, квантифицировалось звездочкой, а начальное выражение $OTHER (то, которое мы переместили в начало конструкции выбора) квантифицировалось плюсом. Если вам это покажется непонятным, подумайте, что произойдет, если суффиксное выражение $OTHER будет квантифицироваться плюсом, и в тексте встретятся, скажем, две строки в кавычках подряд. А если в начальном выражении $OTHER будет использоваться квантификатор *, оно будет совпадать всегда!
Описанные изменения приводят к следующему результату:
"($OTHER+|$DOUBLE$OTHER*|$SINGLE$OTHER*)|$COMMENT|$COMMENT2"
Это выражение, передаваемое в качестве аргумента regsub, уменьшает время обработки еще примерно на 6 процентов, сокращая его до 2,9 секунды. За счет управления поиском совпадений нам удалось ускорить работу выражения в 12 раз!
Давайте вернемся на шаг назад и проанализируем два последних изменения. Поскольку мы «вычерпываем» $OTHER* после каждой строки в апострофах или кавычках, исходное подвыражение $OTHER+ (поставленное нами на первое место в конструкции выбора) может совпасть только в двух случаях:
1. в самом начале работы regsub, до того, как была найдена хотя бы одна строка в кавычках или апострофах;
2. после любого комментария.
Возникает соблазнительная мысль: почему бы нам не разобраться с пунктом 2, добавив $OTHER* и после комментариев? На первый взгляд все хорошо, если не считать того, что весь оставляемый текст должен находиться внутри круглых скобок — располагая его после комментариев, мы вместе с водой (то есть комментариями) выплескиваем из ванны и ребенка (код).
Итак, если исходное выражение $OTHER+ используется в основном после комментариев, стоит ли перемещать его на первое место? Вероятно, ответ на этот вопрос зависит от данных — если комментариев больше, чем строк в кавычках и апострофах, тогда такое перемещение оправдано. В противном случае я не стал бы выносить эту альтернативу вперед. Как показали мои тесты, при расположении этого выражения на первом месте были показаны лучшие результаты. При перемещении его в конец выражения была потеряна примерно половина выигрыша, достигнутого на предыдущем шаге.
Как, это еще не все? Нет! Не забывайте о том, что каждое выражение для строк, заключенных в кавычки и апострофы, прекрасно подходит для раскрутки — методики, которой в этой главе был посвящен длинный раздел. Замена выражений SINGLE и DOUBLE раскрученными версиями:
set DOUBLE {"[^"\\]*(\\.[^"\\]*)*"}
set SINGLE {'[^'\\]*(\\.[^'\\]*)*'}
сокращает время обработки до 2,3 секунды, то есть обеспечивает еще 25-процентный выигрыш. Все оптимизации, рассмотренные до настоящего момента, изображены на рис. 5.9.
Переменные заметно облегчают построение регулярных выражений в Tcl, поскольку неинтерполируемая конструкция {…} не вызывает неоднозначной интерпретации символов. Вдобавок полное выражение, приведенное ниже (с разбиением на строки по ширине страницы), оказывается смехотворно длинным:
([^"'/]+|"[^"\\]*(\\.[^"\\]*)*"[^"'/]*|'[^'\\]*(\\.[^'\\]*)*'[^"'/]*)|
/\*[^*]*\*+([^/*][^*]*\*+)*/\//[^\n]*
Например, аналогичная строка Perl, заключенная в апострофы, не столь наглядна, поскольку \\ в ней означает \, а не \\. Для построения удобочитаемых регулярных выражений в Perl существуют другие средства. Вы убедитесь в этом, когда мы вернемся к этому примеру в главе 7 (с. <$R[P#,R7-7]>).
Рис. 5.9. Выигрыш от различных способов оптимизации
Наибольший выигрыш по быстродействию в механизме НКА, вероятно, достигается все же не приемами общей оптимизации, а тщательным построением выражения с учетом того, что нужно и не нужно делать для достижения поставленной цели. Конечно, при этом необходимо хорошо знать, как механизм НКА будет действовать для решения поставленной задачи.
Рассмотрим пример, с которым я недавно столкнулся при работе в Emacs (в этой программе используется традиционный механизм НКА). Я хотел, чтобы регулярное выражение находило сокращения типа «don’t», «I’m», «we’ll» и т. д., но не совпадало в других ситуациях. У меня получилось регулярное выражение, в котором за обозначением слова [\<\w+] следовал Emacs-эквивалент выражения ['([tdm]|re|ll|ve)]. Это решение работало, но я вдруг понял, что использовать [\<\w+] глупо — вполне достаточно \w. Ведь если апострофу непосредственно предшествует \w, то и \w+ там заведомо присутствует; лишняя проверка не добавит никакой новой информации, если нас не интересуют точные границы совпадения (а меня они не интересовали — я хотел лишь найти строку). Использование \w ускорило работу выражения более чем в 10 раз.
Допустим, вы собираетесь использовать выражение<$M[R5-10]>
[\bchar\b|\bconst\b|\bdouble\b…\bsigned\b|\bunsigned\b|\bwhile\b]
для поиска строк, содержащих ключевые слова языка C. С точки зрения регулярных выражений конструкция выбора обходится дорого — каждая альтернатива ищется в каждой позиции строки до тех пор, пока не будет найдено совпадение.
С другой стороны, если бы регулярное выражение состояло только из одного слова (например, [\bchar\b]), мы могли бы воспользоваться оптимизацией проверки фиксированных строк (с. <$R[P#,R5-13]>), чтобы быстро просканировать строку в поисках одного совпадения. Серия из нескольких элементарных проверок часто выполняется быстрее, чем одна большая проверка.
Чтобы продемонстрировать сказанное на конкретном примере, я написал короткий сценарий Perl для подсчета строк в исходном тексте Perl, содержащих эти ключевые слова. Одна версия выглядит так<$M[R5-18]>:
$count = 0;
while (<>)
{
$count++ if m< \bchar\b
| \bconst\b
| \bdouble\b
…
| \bsigned\b
| \bunsigned\b
| \bwhile\b >x;
}
В этом примере используется особая возможность Perl, обеспечивающая произвольную расстановку пропусков в регулярных выражениях (кроме классов). В длинной, многострочной конструкции [m<…>x] все символы, за исключением пропусков, составляют одно регулярное выражение (с многими альтернативами). Другой тестовый сценарий выглядит так[7]:
$count = 0;
while (<>) {
$count++, next if m/\bchar\b/;
$count++, next if m/\bconst\b/;
$count++, next if m/\bdouble\b/;
…
$count++, next if m/\bsigned\b/;
$count++, next if m/\bunsigned\b/;
$count++, next if m/\bwhile\b/;
}
Обе версии выдают одинаковые результаты, но вторая работает примерно в шесть раз быстрее. В ней исключается большинство затрат, связанных с возвратом, вдобавок к каждому отдельному совпадению могут быть применены внутренние оптимизации.
Впрочем, и это еще не все. Как упоминалось на с. <$R[P#,R5-14]>, GNU Emacs<$M[R5-19]> очень хорошо выполняет оптимизацию исключения по первому символу — гораздо лучше, чем Perl, Tcl, Python или любая другая известная мне программа с механизмом НКА. При наличии нескольких альтернатив подсистема смещения текущей позиции знает, что регулярное выражение следует применять лишь в позициях, совпадающих с [[cdsuw]], поскольку альтернативы могут начинаться только с этих символов (точнее, для полных, не приведенных выше данных теста, используется класс [[cdfinrsuw]]). Избавляясь от необходимости применения всего механизма в каждой позиции, можно добиться существенного выигрыша. Если бы регулярное выражение начиналось с [.*] или другой конструкции, из-за которой совпадение может начинаться с произвольного символа, возможность оптимизации была бы утрачена, однако в нашем примере она действует: в той же серии тестов для Emacs версия с несколькими альтернативами работает в 3,8 раза быстрее версии с несколькими регулярными выражениями.
Но и это еще не все. Как упоминалось в разделе «Кэширование при компиляции» (с. <$R[P#,R5-15]>), Emacs кэширует только пять регулярных выражений, использовавшихся последними. В версии с несколькими регулярными выражениями из-за проверки каждого слова отдельным регулярным выражением (в моем тесте их было 14) кэш становится практически бесполезным. Увеличение его размера до величины, позволяющей кэшировать все регулярные выражения, приводит к троекратному повышению скорости! В результате версия с несколькими регулярными выражениями работает уже не в 3,8, а всего в 1,4 раза медленнее, более реально демонстрируя возможности исключения по первому символу в Emacs.
Кстати говоря, учтите, что сравнение этих двух версий (с несколькими альтернативами и несколькими регулярными выражениями) возможно лишь потому, что нас интересует наличие совпадения, а не его точные границы. Простое выражение типа [char|const|…] находит первое слово в строке (независимо от порядка следования альтернатив в списке), а отдельные проверки обнаруживают первое слово в списке (независимо от его положения в строке). На самом деле это огромная разница, но мы знаем, что в данном примере она несущественна.
Продолжая действовать в том же направлении, но только вручную, можно попытаться вынести общий префикс каждой альтернативы перед конструкцией выбора — по аналогии с преобразованием [this|that|thespcother] в [th(is|at|espcother)], о котором говорилось выше. Такое изменение передает управление относительно медленной конструкции выбора лишь после совпадения [th], даже в том случае, если исключение по первому символу не используется. Кроме того, при этом появляется общая фиксированная строка «th», хорошо подходящая для оптимизации проверки фиксированных строк. В результате достигается довольно существенный выигрыш. В примере с ключевыми словами C это означает вынесение префикса [\b], с которого начинается каждая альтернатива, в начало регулярного выражения: [\b(char\b|const\b|…)]. При проведении тестов на Perl после этого простого изменения выражение стало работать почти так же быстро, как при раздельной проверке, о которой говорилось выше.
Этот принцип может использоваться за пределами регулярного выражения, с использованием других операторов языка. Например:
/this/ || /that/ || /the other/
|| за пределами регулярного выражения означает «или». Регулярные выражения будут последовательно проверяться до тех пор, пока одно из них не совпадет, и в этот момент обработка всей конструкции …||…||… прекращается. Все последствия первого совпадения при этом остаются в силе.
Итак, размышления и логика помогут вам пройти большую часть пути к эффективному программированию — но не весь путь. Например, без тестирования на Perl примера с ключевыми словами C я мог бы утверждать, что любой из быстрых методов работает быстрее медленного, но вряд мне удалось бы сказать, какой из быстрых методов работает быстрее. Возможно, из-за какой-нибудь внутренней оптимизации в следующей версии Perl или из-за того, что я воспользуюсь для тестирования другой программой, самым быстрым окажется другой метод.
[1] Я работаю на IBM ThinkPad 755CX с процессором Pentium 75 Мгц и операционной системой Linux. Приведенное время вычислено на основании других эталонных тестов; я не проверял его на практике.
[2] Для любознательных: количество возвратов, выполняемых для строки длины n, равно 2n+1. Количество проверок равно 2n+1+2n.
[3] Конструкция опережающей проверки в Perl имеет вид [(?=…)]. Следовательно, чтобы проверить присутствие [['"]], мы должны вставить в начало выражения [(?=['"])]. В результате тестирования этого примера на разных данных я обнаружил, что дополнительная проверка уменьшает время выполнения на 20 – 30 процентов. В примере с месяцами, описанном ниже, добавление [(?=[ADFJMNOS])] ускорило работу на целых 60 процентов.
[4] Впрочем, это может быть и механизм НКА с оптимизацией, которую я не предусмотрел.
[5] Многие механизмы НКА запрещают конструкцию [(x*y*)*], использованную в этом выражении. Поскольку внутреннее выражение может совпадать с пустой строкой, внешний квантификатор может «немедленно» найти для нее бесконечное число совпадений. Другие программы (например, Emacs и современные версияи Perl) с честью выходят из затруднительной ситуации. Python преспокойно сообщает о неудачном поиске всех выражений, в которых встречается эта конструкция.
[6] Вообще-то в Perl версии 5 эта возможность реализуется при помощи конструкции негативного опережения (?!…), но поскольку она относится к специфике Perl, мы рассмотрим ее в главе 7 (с. <$R[P#,R7-8]>).
[7] В Perl конструкция:
команда, next if условие;
представляет собой распространенную и полезную идиому, которая означает следующее:
if (условие) {
команда;
next # Начать следующую итерацию внешнего цикла
}