Регулярные выражения в конкретных программах
Разбираться в регулярных выражениях вообще — это лишь половина дела. Для полноты картины необходимо знать конкретный диалект, его ограничения и потенциальные возможности.
Как было показано в главе 3, никакого единства в этой области нет. Из табл. 3.4 (с. <$R[P#,R3-13]>) видно, что даже в такой простой области, как якорные метасимволы, возникает немало затруднений. Приведу еще один пример. В табл. 6.1 перечислены характеристики некоторых диалектов регулярных выражений для программ, существующих на разных платформах. Возможно, вы уже встречались с неполным вариантом табл. 6.1 (хотя бы в табл. 3.1 этой же книги), но пусть размер таблицы 6.1 вас не обманывает — она тоже не является полной. Почти к каждой ячейке таблицы необходимо привести пояснительную сноску.
При первом знакомстве с новым диалектом регулярных выражений в голову приходит множество вопросов. Некоторые из них перечислены в главе 3 (с. <$R[P#,R3-17]>). Пусть не все вопросы являются первоочередными и абсолютно необходимыми, вам все же следует познакомиться с ними. Одно из препятствий заключается в том, что между разными версиями одной программы иногда существуют заметные различия. Например, GNU-версии программ обычно обладают расширенными возможностями. В табл. 6.1 не отражен ни этот факт, ни целое поколение новых версий, соответствующих стандарту POSIX. Более того, даже если номер версии вашей программы точно совпадает с приведенным в табл. 6.1, это еще ни о чем не говорит. Даже такая простая программа, как grep, существует в нескольких разных вариантах.
Да, даже такая простая программы, как grep, существует в нескольких разных вариантах. В табл. 6.2 перечислены некоторые отличия между некоторыми из существующих версий. Таблицу 6.2 тоже не мешало бы сопроводить изрядным количеством сносок. В GNU grep версии 2.0 ^ и $ считаются метасимволами «там, где это имеет смысл» — например, в конструкциях […|^…] и [(…$)]. В большинстве других версий они допускаются лишь в начале и конце регулярного выражения соответственно. С другой стороны, в GNU grep версии 2.0 отсутствует класс POSIX [:blank:], а в версии SCO — класс [:xdigit:].<$M[R6-1]>
Таблица 6.1. Поверхностный обзор диалектов некоторых распространенных программ
См. расшифровку в файле pict!
Похоже, ключ командной строки -i является особенно благодатной почвой для всевозможных расхождений. В grep версии v7 jn 1979 г. действие ключа -i распространялось только на те символы регулярного выражения, которые были записаны в нижнем регистре. В версии r2v2, вышедшей несколько лет спустя, это неудобство было устранено, но в ней ключ -i не действовал на символы, определяемые символьным классом. Даже в современной версии GNU grep 2.0 ключ -i не действует при использовании обратных ссылок. В SCO он игнорируется для класса POSIX [:upper:], но действует для класса [:lower:]. Почему? Спросите что-нибудь попроще.
Надеюсь, вы уловили главное: различий хватает.
Невозможно уследить за всеми нюансами всех версий во всех реализациях всех существующих программ. Мне эта задача тоже не по силам, поэтому для большинства перечисленных программ я ограничусь сведениями, приведенными в табл. 6.1. Хорошо усвоив материал глав 4 и 5, вы сможете самостоятельно выделить важнейшие аспекты, а ваша квалификация позволит самостоятельно проанализировать возникающие проблемы и разобраться в них. Всю остальную информацию, необходимую для работы с конкретной программой, обычно можно почерпнуть из руководства. Perl — особый случай, которому будет посвящена вся следующая глава.
Таблица 6.2. Сравнительный анализ нескольких версий grep
См. расшифровку в файле pict!
В качестве примера в этой главе рассматриваются некоторые специфические особенности awk, Tcl и GNU Emacs elisp из области регулярных выражений. Предполагается, что вы уже в общих чертах знакомы с этими языками, и вас интересует четкое описание диалекта регулярных выражений, а также некоторые полезные советы и рекомендации. Я постарался излагать материал по возможности кратко, поэтому в этой главе часто встречаются ссылки на главу 3.
В первом разделе, «Awk», основное внимание уделяется отличиям между популярными реализациями awk в области регулярных выражений. Многие разработчики выпустили собственные версии awk, и у каждого из них, похоже, есть собственные представления о том, каким должен быть диалект регулярных выражений в этой программе. Оживленные дискуссии по поводу переносимости способны вызвать и смех, и слезы — в зависимости от того, как на них взглянуть.
С другой стороны, и Tcl, и GNU Emacs происходят из одного источника, поэтому скорее всего, ваша версия будет работать так же (или почти так же), как и версии остальных пользователей. Иногда приходится учитывать функциональные различия между версиями, но обычно больший интерес представляет их подход к обработке регулярных выражений, тип механизма НКА и его эффективность.
Программа awk была создана в 1977 году за одну неделю интенсивного программирования. Она стала первым мощным инструментом Unix, предназначенным для обработки текстов. Гораздо более универсальная и выразительная, чем sed, она породила новую культуру, которая распространилась на целое поколение программных средств. Авторам awk удалось объединить в одной программе совершенно разные интересы. Альфред Ахо, только что написавший egrep и участвовавший в работе над lex, внес поддержку регулярных выражений. Питер Вайнбергер ориентировался на базы данных, а Брайан Керниган интересовался программируемыми редакторами. Немалое влияние на awk оказала программа Марка Рошкинда (Marc Rochkind), преобразующая пары «регулярное выражение/строка» в программу на языке C, которая сканировала файл и выводила указанную строку при совпадении регулярного выражения. В awk эта идея была усовершенствована, однако общие концепции построчной обработки входных данных и регулярных выражений остались теми же.
Диалект регулярных выражений awk имеет с диалектом egrep больше общего, чем диалект любой другой программы, но эти диалекты не совпадают. К сожалению, в электронной документации утверждается обратное, и этот миф продолжает существовать и в наши дни (даже в книгах издательства O’Reilly!) Различия между диалектами становятся источником недоразумений. Некоторые из них очевидны — например, в awk поддерживаются метасимволы [\t] и [\n], а в egrep они отсутствуют (хотя о поддержке этих символов в awk в исходном варианте документации вообще не упоминалось!) Существуют и другие, менее очевидные различия. Утверждения об идентичности двух диалектов скрывали некоторые важные особенности awk и сбивали с толку пользователей.
Двадцать лет назад существовала единственная версия awk от Bell Labs. В наши дни их появилось великое множество. В этом разделе я подробно описал различия между некоторыми избранными реализациями. Я делаю это не для того, чтобы снабдить вас исчерпывающими сведениями о конкретных реализациях и различиях, а скорее для того, чтобы наглядно продемонстрировать — внешнее сходство бывает обманчивым. Помимо перечисленных реализаций (и различий), существует множество других, причем многие из этих различий могут исчезнуть в будущих версиях.
В частности, когда работа над книгой близилась к завершению, Арнольд Роббинс (Arnold Robbins), ответственный за GNU awk, работал с более ранним вариантом книги и исправлял ошибки версии 3.0.0, упоминавшиеся в тексте. Соответственно, в последующих версиях GNU awk часть ошибок была исправлена (информацию о некоторых из них мне удалось включить в это издание).
Таблица 6.3. Поверхностное сравнение некоторых версий awk
См. расшифровку в файле pict!
Наиболее заметные отличия между разными версиями awk перечислены в табл. 6.3, где исходная версия awk сравнивается с некоторыми версиями, распространенными в наши дни:
l oawk — исходный вариант awk, распространяемый AT&T в поставке Unix версии 7, по состоянию на 16 мая 1979 года.
l nawk — new awk, распространяемый в поставке SCO Unix Sys V 3.2v4.2.
l awk — One True Awk, поддерживаемый и распространяемый Брайаном Керниганом. Протестированная версия: 29 июня 1996 г.
l gawk — GNU awk. Протестированная версия: 3.0.0.
l MKS — Mortice Kern Systems awk для Windows NT.
l mawk — Mike’s awk (автор — Майкл Бреннан). Протестированная версия: 1.3b.
Жирный шрифт относится к конкретным программам из этого списка. Таким образом, название awk относится к программе вообще, а awk — к «One True Awk» Брайана Кернигана.
Напомню: не следует полагать, что в табл. 6.3 приведена вся информация, необходимая для написания переносимых сценариев awk. Существует много других аспектов. Впрочем, некоторые из них играют второстепенную роль — например, только в oawk, nawk и awk необходимо экранировать знак равенства, с которого начинается регулярное выражение (странно, не правда ли?) Некоторые различия относятся к специфике конкретной программы (например, в gawk квантификатор {мин,макс} может использоваться лишь при указании ключей командной строки --posix или --re-interval). Впрочем, некоторые важные, но порой неочевидные различия встречаются во многих реализациях. В нескольких ближайших подразделах будут описаны основные из этих различий.
В версиях awk, поддерживающих шестнадцатеричные коды символов в регулярных выражениях, было бы логично предположить, что [ora\x2Ecom] будет совпадать так же, как и [ora\.com] (2E — ASCII-код точки). Как упоминалось в главе 3 (с. <$R[P#,R3-18]>), причина заключается в том, что если вы решились на хлопоты с вводом шестнадцатеричного или восьмеричного кода, то вряд ли захотите интерпретировать результат как метасимвол. В самом деле, awk и mawk работают именно так, но gawk и MKS в соответствии с требованиями стандарта POSIX, действительно интерпретируют [\x2E] как метасимвол «точка» (хотя в gawk произойдет то же самое, если вы не укажете ключ командной строки --traditional).
Можно предположить, что шестнадцатеричный код в [ora\x2Ecom] состоит из символов \x2E, но некоторые реализации «захватывают» все шестнадцатеричные цифры, следующие после \x. В этом случае шестнадцатеричным кодом будет считаться \x2Ec (см. с. <$R[P#,R3-19]>). Это происходит в реализациях gawk и MKS, упоминавшихся в предыдущем разделе (хотя в gawk шестнадцатеричные коды из одной цифры не допускались до появления версии 3.0.1).
С восьмеричными кодами дело обстоит еще хуже. Во всех версиях разрешены восьмеричные коды, состоящие из одной, двух и трех цифр (кроме MKS, где коды из одной цифры зарезервированы для обратных ссылок — в документации об этом не сказано), но на этом сходство и кончается. awk, MKS и mawk закономерно игнорируют 8 или 9 после кода, состоящего из одной или двух цифр. nawk считает 8 и 9 восьмеричными (!) цифрами. gawk правильно обрабатывает 8 и 9, но выдает фатальную ошибку для \8 и \9 (одна из ошибок, исправленных в последней версии).
Конечно, конструкция типа [(this|that|)] вполне логична — пустое подвыражение означает, что совпадение должно находиться всегда (с. <$R[P#,R3-20]>). В ДКА она в точности эквивалентна [(this|that)?], но иногда для удобства или наглядности предпочитают использовать конструкцию с пустым подвыражением. К сожалению, не все реализации допускают такую запись: в awk, mawk и nawk она считается фатальной ошибкой.
Пустое регулярное выражение — другое дело. В awk и nawk пустое регулярное выражение также считается фатальной ошибкой, а в mawk, gawk и MKS оно совпадает с любой непустой строкой.
Вероятно, больше всего проблем вызывает возможность (вернее, невозможность) экранирования символов в символьных классах, а также интерпретация в них «]» и «-». Экранирование упоминается в табл. 6.3[1], но представьте себе класс, начинающийся с символа ]. В awk, gawk и MKS все пройдет нормально; в mawk произойдет фатальная ошибка, а в nawk этот класс будет попросту проигнорирован (как это было в oawk).
А что произойдет, если по ошибке указать «перевернутый» интервал [[z-a]]? Можно привести и более реалистичный пример — [[\-abc]]; предполагалось, что \- означает литеральный дефис, а не интервал от \ до a (такой интервал бесполезен, поскольку обратная косая черта в кодировке ASCII следует после a). В gawk и MKS это приведет к фатальной ошибке; awk автоматически инвертирует интервал; mawk интерпретирует всю конструкцию как не-интервальную (то есть два литеральных символа — дефис и a). Если этого недостаточно, nawk жаловаться не будет, но включит в класс только начальный символ (в данном случае — обратную косую черту).
В некоторых реализациях существуют ограничения для типов обрабатываемых данных. nawk и awk не допускают ничего, кроме 7-разрядных данных ASCII (другими словами, байты с установленным старшим битом никогда не совпадают), а обработка нуль-символов поддерживается только в gawk (MKS считает нуль-байт фатальной ошибкой, а другие реализации просто интерпретируют его как признак конца строки или регулярного выражения, в зависимости от ситуации).
В современных версиях awk (из числа рассматриваемых — во всех, кроме oawk) существует как минимум три варианта использования регулярных выражений: разбиение входных данных, операторы ~ и !~, а также функции match, sub, gsub и split (в gawk была добавлена функция gensub). Все эти средства достаточно просты, к тому же они хорошо описаны в любой документации awk, поэтому я не буду их пересказывать. В следующих разделах рассматриваются некоторые обстоятельства, заслуживающие особого внимания.
В большинстве реализаций регулярное выражение может передаваться как в строковом формате ("…"), так и в формате «сырого» регулярного выражения (/…/). Например, команды string ~ /regex/ и string ~ "regex" делают почти одно и то же. Одно важное отличие заключается в том, что в первом случае текст сначала интерпретируется как строка, заключенная в кавычки, а затем — как регулярное выражение. В частности, это означает, что строки "\t" и "\\t" приведут к одному регулярному выражению, совпадающему с одним символом табуляции. При передаче "\t" в результате обработки строки, заключенной в кавычки, механизму регулярных выражений передается символ табуляции tab (который не является метасимволом и просто совпадает «сам с собой»). При передаче "\\t" механизму регулярных выражений достается последовательность [\t], которая интерпретируется как метасимвол, совпадающий с символом табуляции. Аналогично, регулярное выражение /\\t/ и строка "\\\\t" совпадают с литеральным текстом \t.
Одна из проверенных мной реализаций, MKS, интерпретирует эти две версии (/…/ и "…") абсолютно одинаково. Даже несмотря на то, что регулярное выражение задается в строковом виде, оно, похоже, обходит механизм интерпретации строк и передается непосредственно механизму регулярных выражений.
Практически все проверенные мной реализации соглашаются с тем, что для разбиения строки функцией split регулярное выражение должно совпасть с каким-то текстом целевой строки (единственное исключение, при котором регулярное выражение отсутствует, будет рассмотрено ниже). В частности, это означает, что при использовании с функцией split выражение [,*] эквивалентно [,+].
Однако к функциям sub и gsub это не относится. В большинстве версий при выполнении следующего фрагмента:
string = "awk"
gsub(/(nothing)*/, "_", string)
переменной string присваивается строка «_a_w_k_». С другой стороны, в gawk переменной будет присвоена строка «_a_w_k». Заметили пропавший символ подчеркивания в конце строки? До выхода gawk версии 3.0.1 подобные регулярные выражения gsub не совпадали в конце строки при отсутствии метасимвола [$].
Другая проблема возникает в следующем фрагменте:
string = "sed_and_awk"
gsub(/_*/, "_", string)
Большинство реализаций возвращает «s_e_d_a_n_d_a_w_k_», но gawk (до версии 3.0.1) и MKS возвращают «s_e_d__a_n_d__a_w_k_». В этих реализациях даже после замены символа подчеркивания механизм снова применяет регулярное выражение в той же позиции, в результате чего выражение [_*], которое может совпасть с «ничем», совпадает перед каждым a (обычно совпадение с «ничем» не допускается в месте завершения предыдущего совпадения).
Если в третьем аргументе функции split() передается строка "spc", функция переходит в режим «разбиения по пропускам». В большинстве реализаций пропуск (whitespace) означает произвольную комбинацию пробелов, табуляций и символов новой строки. Тем не менее, gawk разделяет строки только по пробелам и табуляциям (в версии 3.0.2 gawk включает в разбиение и символы новой строки, если только при запуске не был указан ключ командной строки --posix).
А как насчет передачи /spc/ в операнде регулярного выражения — приведет ли это к специальной обработке пропусков? Это происходило в gawk (раньше версии 3.0.2), не происходило в awk и mawk (и в gawk, начиная с версии 3.0.2), и вызывало фатальную ошибку в nawk.
Что означает передача пустого операнда регулярного выражения (например, sub("",…) или sub(//,…))? В awk пустое регулярное выражение // абсолютно недопустимо, но иногда разрешается пустая строка "". В gsub пустое регулярное выражение может совпасть с чем угодно (не считая awk, где пустое регулярное выражение в gsub вызывает фатальную ошибку). С другой стороны, с функцией split наблюдается большее разнообразие: в nawk и MKS разбиение вообще не происходит, а другие реализации разбивают строку на каждом символе.
Tcl[2] использует пакет регулярных выражений НКА (автор — Генри Спенсер) с выхода его первой версии и обеспечивает простой, последовательный интерфейс для работы с функциями этого пакета. Диалект регулярных выражений прямолинеен и не перегружен излишествами, а две функции для работы с регулярными выражениями достаточно полезны и не преподносят особых сюрпризов. Механизм регулярных выражений Tcl — классический пример традиционного механизма НКА, описанного в главе 4.
Позвольте начать прямо с утверждения, которое вызовет немалое удивление у тех, кто не читал главу 3: в регулярных выражениях Tcl не поддерживается [\n] и другие метасимволы из этого семейства. В чем же дело?
Операнды, в которых передаются регулярные выражения, представляют собой обычные строки (в терминологии Tcl — слова), интерпретируемые как регулярные выражения при передаче их функциям regexp или regsub. В этом отношении Tcl напоминает GNU Emacs и Python. Общие сведения на эту тему приведены в разделе «Строки как регулярные выражения» главы 3 (с. <$R[P#,R3-21]>). Одно важное следствие заключается в том, что если регулярное выражение не передается как строка, а, скажем, читается из конфигурационного файла или включается в строку запроса CGI, оно не подвергается обычной строковой обработке, и вы можете использовать только те возможности, которые перечислены в табл. 6.4.
Таблица 6.4. Диалект регулярных выражений в Tcl
Метасимволы, действительные вне символьных классов |
|
. |
любой байт, кроме нуль-символа (включая символы новой строки) |
(…) |
группировка и сохранение (максимум 20 пар) |
*, +, ? |
стандартные квантификаторы (могут применяться к (…)) |
| |
конструкция выбора |
^, $ |
начало и конец строки |
\символ |
литерал символ |
[…], [^…] |
символьные классы (обычный и инвертированный) |
Метасимволы, действительные внутри символьных классов |
|
] |
конец класса (чтобы включить в класс литерал ], поставьте его на первое место после [ или [^) |
c1-с2 |
интервал (чтобы включить в класс литерал «дефис», поставьте его на первое или последнее место). |
Примечание: в классах символ \ не имеет специальной интерпретации. |
Механизм лексического анализа сценария в Tcl является одним из важнейших свойств языка, которое каждый пользователь должен усвоить до мельчайших подробностей. В руководстве Tcl приведена достаточно подробная информация, и я не буду повторять ее здесь. Особый интерес для нас представляет замена обратных косых черт в строках, не заключенных в {…}. При замене обратных косых черт распознаются многие стандартные условные обозначения (табл. 3.3, с. <$R[P#,R3-22]>)[3], а все экранированные символы новой строки (с последующими пробелами и табуляциями) заменяются одним пробелом. Это происходит на ранней стадии обработки сценария. Остальные символы \ воспринимаются либо как экранированные ограничители (в зависимости от типа строки), либо как неопознанные экранированные символы. В последнем случае обратная косая черта попросту удаляется.
С восьми- и шестнадцатеричными кодами дело тоже обстоит непросто. Например, в Tcl 8 и 9 считаются восьмеричными цифрами (с. <$R[P#,R3-23]>). Шестнадцатеричные коды Tcl могут содержать произвольное количество цифр. Кроме того (возможно, непреднамеренно) поддерживается особая последовательность \x0xdddd. Впрочем, особенно удивляться этому не приходится, поскольку \x0 (обозначение нуль-символа) вряд ли будет использоваться в сценариях — Tcl недолюбливает нуль-символы в строках.
В Tcl существуют две функции для работы с регулярными выражениями. Функция regexp предназначена для поиска, а функция regsub —для поиска с заменой в копии строки. Вряд ли я смогу сказать об этих функциях что-то такое, чего нет в руководстве, поэтому я буду краток.
Обобщенный вызов функции regexp выглядит следующим образом:
regexp [ключи] регулярное_выражение строка [имя_приемника…]
Если заданное регулярное выражение совпадает в заданной строке, функция возвращает 1; в противном случае возвращается 0. Если задано имя_приемника, копия фактически совпавшего текста присваивается переменной с указанным именем. Если указаны и другие имена переменных, им присваивается текст, совпавший с соответствующим подвыражением в круглых скобках (или пустая строка, если соответствующая пара скобок не существует или не является частью совпадения). Если регулярное выражение не совпадает, переменные с указанными именами остаются без изменений.
Рассмотрим пример:
if [regexp -nocase {^(this|that|other)="([^"]*)"} $string {} key value] {
…
Ключ -nocase означает, что поиск совпадения должен осуществляться без учета регистра. Регулярное выражение [^(this|that|other)="([^"]*)"] сравнивается с текстом, хранящимся в переменной $string. Вместо пары фигурных скобок после целевого текста обычно находится имя переменной, которой должен быть присвоен весь совпавший текст. В данном примере сохранять общее совпадение не требуется, поэтому я использую {}. Двум следующим переменным присваивается текст, совпавший с двумя подвыражениями в скобках — $1 и $2 в терминологии Perl, встречавшейся в этой книге. Если переменная $string содержит текст «That="123"spc#spcsample», переменной $key будет присвоена строка That, а переменной value — строка 123 (если бы вместо {} было указано имя переменной, то этой переменной был бы присвоен текст всего совпадения That="123").
Обобщенный вызов функции regsub выглядит следующим образом:
regsub [ключи] регулярное_выражение строка замена приемник
Переменной приемник присваивается копия заданной строки, в которой вместо первого совпадения (или вместо всех совпадений, если указан ключ -all) регулярного выражения подставляется замена. Функция возвращает количество подстановок. Если ни одна подстановка не была выполнена, переменная приемник остается без изменений.
В строке замена обозначения<$M[R6-2]> & и \0 относятся ко всему совпавшему тексту, а \1–\9 — к тексту, совпавшему с соответствующим подвыражением в круглых скобках. Однако следует помнить о том, что функция regsub должна «увидеть» эти экранированные последовательности, поэтому для их прохождения через главный интерпретатор Tcl обычно необходимы дополнительные символы \ или {…}.
Если вы хотите ограничиться простым подсчетом совпадений, просто укажите {} вместо параметров замена и приемник. При использовании регулярного выражения, совпадающего с любым текстом (например, пустого регулярного выражения {}) замена осуществляется перед каждым символом. Например, в двух следующих примерах строка подчеркивается с использованием комбинации «символ подчеркивания-забой»:
regsub -all {} $string _\b underlined
regsub -all . $string _\b& underlined
До настоящего момента упоминались два ключа командной строки, -nocase и -all, но существуют и другие. Функция regexp поддерживает ключи -indices, -- и -nocase, а функция regsub — ключи -all, -- и -nocase.
Ключ -indices означает, что вместо копии совпавшего текста в переменной(-ых) с заданными именами сохраняется строка, состоящая из двух чисел: начальный и конечный индекс совпавшей части в строке (индексация начинается с нуля). При отсутствии совпадения сохраняется строка -1 -1. В примере this|that|other переменной $key будет присвоена строка «0 3», а переменной $value — строка «6 8».
Несмотря на то, что в документации утверждается обратное, ключ -nocase работает именно так, как можно ожидать, без всяких сюрпризов. Если верить документации, [US] не совпадет с [us], даже при использовании ключа -nocase.
Обычно все аргументы, начинающиеся с дефиса, интерпретируются как ключи (неопознанный ключ считается ошибкой). Под это правило попадают и ситуации, когда регулярное выражение берется из переменной, содержимое которой начинается с дефиса. Помните: функция Tcl видит свои аргументы только после выполнения интерполяции и прочих вспомогательных операций. Специальный ключ -- означает, что перечисление ключей закончено, и следующий аргумент является регулярным выражением.
Tcl взваливает бремя эффективного поиска на плечи программиста, практически не пытаясь оптимизировать использование регулярных выражений. Каждое регулярное выражение заново компилируется при очередном использовании, хотя при этом в кэше сохраняются откомпилированные версии пяти последних использованных регулярных выражений (с. <$R[P#,R5-16]>).
Механизм регулярных выражений работает в точности так, как его реализовал Генри Спенсер в 1986 году. Из оптимизаций, упоминаемых в главе 5 (с. <$R[P#,R5-17]>), Tcl пытается выполнять исключение по первому символу, проверку фиксированных строк (но только если регулярное выражение начинается с элемента, к которому применяется квантификатор * или ?), простое повторение, а также помнит о том, что ^ в начале выражения может совпадать только в начале строки. Единственная важная оптимизация, которая в Tcl не выполняется — это косвенное добавление якорного метасимвола в том случае, если регулярное выражение начинается с [.*].
Регулярные выражения предназначены для обработки текста, поэтому они вполне естественно играют ведущую роль в одной из самых мощных сред обработки текста, существующих в наши дни — GNU Emacs[4] (в дальнейшем просто Emacs). Emacs — не просто редактор с присоединенным сценарным языком. Emacs — это полноценная среда программирования elisp с присоединенной системой вывода на экран. Пользователь редактора может непосредственно выполнять многие функции elisp, поэтому эти функции тоже можно считать командами.
Emacs elisp (в разговорном языке — просто Lisp) содержит почти тысячу встроенных примитивных функций (то есть написанных на C и откомпилированных вместе с основной системой Emacs). Стандартные библиотеки Lisp содержит еще около 1200 функций, реализующих все, что угодно, от простых команд редактирования (типа «переместить курсор влево») до целых пакетов — программ чтения электронных новостей, почтовых агентов и Web-броузеров.
В Emacs для работы с регулярными выражениями традиционно использовался традиционный механизм НКА, но с выходом версии 19.29 (июнь 1995 года) также поддерживается поиск стандарта POSIX (самое длинное совпадение, ближнее к левому краю). Из тысячи встроенных функций выделяются четыре пары, предназначенных для работы с регулярными выражениями. Они перечислены в табл. 6.5 вместе с другими примитивами, относящимися к регулярным выражениям. Популярные средства поиска (в частности, команды последовательного поиска isearch-forward и isearch-forward-regexp) представляют собой функции Lisp, в конечном счете использующие примитивы. Впрочем, они могут обладать некоторыми дополнительными возможностями — например, isearch-forward преобразует одиночный пробел во введенном регулярном выражении в конструкцию [\s-+], использующую синтаксический класс Emacs (см. ниже) для поиска любых пропусков.
Чтобы этот раздел был коротким и содержательным, я не стану описывать высокоуровневые функции Lisp или специфику использования каждого примитива. Для получения этой информации достаточно нажать клавиши C-h f (команда describe-function).
Регулярные выражения Emacs, как и в Tcl и Python, представляют собой обычные строки, которые передаются функциями механизму регулярных выражений. Механизм решает, что содержимое этих строк следует интерпретировать как регулярное выражение. Важные следствия описаны в главе 3 (с. <$R[P#,R3-21]>). В табл. 6.6 перечислены некоторые особенности строк Emacs.
В табл. 6.7 приведен список метасимволов, опознаваемых механизмом регулярных выражений Emacs. Перед вами причудливая смесь экранированных и простых метасимволов. А если учесть, что экранированные символы регулярных выражений и сами должны экранироваться в строках, результат часто напоминает рассыпанную коробку зубочисток — например, выражение ["\\(\\\[\\||\\|\\\]\\)"] взято из реального кода стандартной библиотеки Lisp. Другие примеры приведены на с. <$R[P#,R3-24]>.
Таблица 6.5. Примитивы GNU Emacs, относящиеся к поиску
Функции применения регулярных выражений |
|
Функция |
Описание |
looking-at posix-looking-at |
применить регулярное выражение к текущей позиции в буфере (традиционный механизм НКА) применить регулярное выражение к текущей позиции в буфере (псевдо-POSIX НКА) |
string-match posix-string-match |
применить регулярное выражение к заданной строке (традиционный механизм НКА) применить регулярное выражение к заданной строке (псевдо-POSIX НКА) |
re-search-forward posix-search-forward |
провести прямой поиск в буфере (традиционный поиск НКА) провести прямой поиск в буфере (псевдо-POSIX НКА) |
re-search-backward posix-search-backward |
провести обратный поиск в буфере (традиционный поиск НКА) провести обратный поиск в буфере (псевдо-POSIX НКА) |
Функции поиска литеральных строк |
|
search-forward search-backward |
провести прямой поиск фиксированной строки в буфере провести обратный поиск фиксированной строки в буфере |
Функции обработки результатов поиска (доступны после успешного применения функций, перечисленных выше) |
|
match-beginning match-end |
возвращает начальную позицию общего (или частичного) совпадения возвращает конечную позицию общего (или частичного) совпадения |
match-data store-match-data |
возвращает данные о позиции последнего совпадения заменяет данные последнего совпадения указанными данными |
match-string replace-match |
возвращает текст, совпавший с последним регулярным выражением (или подвыражением) заменяет последний совпавший текст в буфере строкой или шаблоном |
Функция regexp-quote: возвращает версию строки, предназначенную для использования в качестве регулярного выражения. Переменная case_fold_search: если переменная истинна, все операции поиска проводятся без учета регистра символов. |
Таблица 6.6. Строковые метасимволы GNU Emacs
Метасимвол |
Описание |
\a |
Звуковой сигнал (ASCII) |
\b |
Забой (ASCII) |
\d |
Удаление (ASCII) |
\e |
Escape (ASCII) |
\f |
Подача листа (ASCII) |
\C-символ |
Сontrol-символ (Emacs) |
\^символ |
Сontrol-символ (Emacs) |
\S-символ |
Shift-символ (Emacs) |
\s-символ |
Super-символ (Emacs) |
\n |
Новая строка (зависит от системы) |
\r |
Возврат курсора (ASCII) |
\t |
Табуляция (ASCII) |
\v |
Вертикальная табуляция (ASCII) |
\A-символ |
Alt-символ (Emacs) |
\H-символ |
Hyper-символ (Emacs) |
\M-символ |
Meta-символ (Emacs) |
\восьм |
байт с заданным восьмеричным кодом (от 1 до 3 цифр) |
\xшестн |
байт с заданным шестнадцатеричным кодом (0 и более цифр) |
Другие комбинации вида \символ, включая \\, вставляют в строку символ. |
Таблица 6.7. Диалект регулярных выражений НКА в Emacs
Метасимволы, действительные вне символьных классов |
||
Метасимвол |
Описание |
|
. |
любой байт, кроме нуль-символа |
|
\(…\) |
группировка и сохранение |
|
*, +, ? |
стандартные квантификаторы (могут применяться к \(…\)) |
|
\| |
конструкция выбора |
|
^ |
начало строки (если находится в начале регулярного выражения, а также после \| или \(). Совпадает в начале целевого текста или после внутренних символов новой строки. |
|
$ |
конец строки (если находится в конце регулярного выражения, перед \| или рядом с \)). Совпадает в конце целевого текста или перед внутренними символами новой строки. |
|
\w, \W |
символ слова (не является символом слова) (см. табл. 6.8) |
|
\<, \>, \b |
начало слова, конец слова, любая граница слова (см. табл. 6.8) |
|
\sкод, \Sкод |
символ, принадлежащий (не принадлежащий) синтаксическому классу Emacs (см. табл. 6.8) |
|
\цифра |
обратная ссылка (только с одной цифрой) |
|
прочие комбинации \символ |
литерал символ |
|
[…], [^…] |
символьные классы (обычный и инвертированный) |
|
Метасимволы, действительные внутри символьных классов |
||
] |
конец класса (чтобы включить в класс литерал ], поставьте его на первое место после [ или [^) |
|
c1-с2 |
интервал (чтобы включить в класс литерал «дефис», поставьте его на первое или последнее место). |
|
Примечание: в классах символ \ не имеет специальной интерпретации. |
||
<$M[R6-4]>Неотъемлемой частью диалекта регулярных выражений Emacs являются средства определения синтаксиса. В Emacs пользователь или сценарий elisp может определить, какие символы следует считать комментариями, пропусками, символами слов и т. д. Список синтаксических классов приведен в табл. 6.8 — подробную информацию можно получить командой describe-syntax, по умолчанию связанной с клавишами C-h s.
Динамическое определение синтаксиса обеспечивает интеллектуальную работу Emacs в различных режимах (text-mode, cperl-mode, c-mode и т. д.) Например, в режиме редактирования программ C++ конструкции /*…*/ и //…new определяются как комментарии, а в режиме elisp комментарием считается только ;…new.
Синтаксис оказывает разнообразное влияние на диалект регулярных выражений. Метасимволы синтаксических классов, в которых конструкции [\s…] и [\S…] объединяются с кодами из табл. 6.8, открывают прямой доступ к синтаксическим определениями. Например, метасимвол [\sw] означает «символ слова», а его фактическая интерпретация зависит от текущего режима. Алфавитно-цифровые символы считаются символами слов во всех режимах, но в дополнение к ним, например, в режиме text-mode к символам слов относятся апострофы, а в режиме cperl-mode — символы подчеркивания.
Синтаксическое определение символов слова также распространяется на метасимволы \w и \W (простые сокращения для \sw и \Sw), а также на границы слов \< и \>.
Таблица 6.8. Синтаксические классы Emacs
Название |
Код(-ы) |
Совпадение |
charquote |
/ |
символьный префикс |
close |
) |
конечный ограничитель |
comment |
< |
начало комментария |
endcomment |
> |
конец комментария |
escape |
\ |
экранирующий префикс в стиле C |
math |
$ |
для ограничителей типа $ в Tex |
open |
( |
начальный ограничитель |
punct |
. |
знак препинания |
quote |
' |
префикс (как ' в Lisp) |
string |
" |
группирующий символ строки (как "…") |
symbol |
_ |
знак, не являющийся символом слова |
whitespace |
- или spc |
пропуск |
word |
w или W |
символ слова |
Как упоминалось выше (см. табл. 6.5), в Emacs реализованы так называемые POSIX-версии поисковых примитивов. Использование этих версий не влияет ни на тип регулярных выражений (то есть диалект регулярных выражений не превращается в тот, что описан в табл. 3.2 (с. <$R[P#,R3-25]>)), ни на общий результат поиска (общее совпадение или несовпадение). От выбранной версии зависит лишь то, какой текст совпадет, и как быстро это произойдет.
Действительно, на уровне общего совпадения POSIX-подобные версии находят самое длинное совпадение, начинающееся ближе всего к левому краю, как бы это сделал настоящий механизм POSIX. Однако подвыражения в круглых скобках не заполняются максимальными совпадениями слева направо, как это описано в главе 4 (с. <$R[P#,R4-39]>) Механизм НКА в Emacs ищет совпадение так, как это делает обычный традиционный механизм НКА, но и после найденного совпадения он продолжает перебирать остальные комбинации. Похоже, в круглых скобках запоминается самое первое совпадение в том тексте, который в итоге обеспечил совпадение максимальной длины.
Например, с применением выражения [\(12\|1\|123\).*] к строке 1234 в стандарте POSIX для подвыражения в круглых скобках сохраняется текст 123, поскольку это самое длинное совпадение в рамках самого длинного общего совпадения. Однако в случае применения posix-команд Emacs будет получен результат 12 — текст первого совпавшего подвыражения, которое привело к самому длинному общему совпадению.
POSIX-подобный поиск в НКА требует дополнительных затрат, поэтому я не рекомендую использовать эти команды, если только вам не нужны именно они.
Все функции, перечисленные в верхней части таблицы 6.5, заполняют данные match-data. В свою очередь, эти данные влияют на значения, возвращаемые match-beginning и match-end, и на данные, используемые match-string и replace-match.
<$M[R6-3]>Функции (match-beginning число) и (match-end число) возвращают позиции целевого текста, в которых соответственно начинается и заканчивается успешное совпадение всего выражения или подвыражения. Если число равно нулю, возвращаются позиции всего совпадения; в противном случае возвращаются позиции для подвыражения \(…\) с заданным номером. Конкретный формат возвращения позиций зависит от того, какая функция использовалась при первоначальном поиске. Например, для string-match возвращаются целые числа (индексы в строке, нумеруемые с нуля), но для looking-at возвращаются маркеры в буфере. Для пар скобок, которые не существуют или не входят в совпадение, всегда возвращается nil.
Функции match-beginning и match-end всего лишь обеспечивают удобный интерфейс к функции match-data<$M[R6-6]>, которая возвращает информацию о позиции совпадения общего выражения и всех подвыражений. Информация возвращается в виде списка:
( (match-beginning 0) (match-end 0)
(match-beginning 1) (match-end 1)
(match-beginning 2) (match-end 2)
…
)
Если применить выражение [a\(b?\)\(c\)] к строке ac функцией string-match, функция match-data возвратит список (0 2 1 1 1 2). Средняя пара 1 1 означает, что первая пара круглых скобок (с [b?]) успешно совпала с «ничем» в позиции 1 (поскольку начальная позиция совпадает с конечной).
Тем не менее, если бы это выражение имело вид [a\(b\)?\(c\)] (обратите внимание на перемещение вопросительного знака), match-data возвращает (0 2 nil nil 1 2). Пара nil nil говорит о том, что первая пара круглых скобок не участвует в совпадении (вопросительный знак совпал успешно, но круглые скобки, к которым он относится — нет).
Функции match-string и replace-match используют информацию match-data для чтения и модификации совпавшего текста (и не только, как вы узнаете из следующего абзаца). Форма (match-string число) возвращает текст из текущего буфера от (match-beginning число) до (match-end число). В форме (match-string число строка) возвращается подстрока заданной строки.
Ответственность за использование match-string и replace-match с тем же целевым текстом, как и для функции, использовавшейся для заполнения списка match-data, возлагается на вас. Ничто не помешает вам модифицировать целевой текст между поиском и вызовом match-string, переключиться на другой буфер или передать другую строку. Вероятно, подобным выходкам тоже можно найти какое-нибудь интересное применение, но большей частью они лишь создают проблемы, и поэтому их следует избегать.
Emacs является полноценным редактором, что несколько затрудняет проведение хронометража — но конечно, эта задача вполне решаемая. В следующем листинге приведена одна из программ, которая использовалась для тестирования примера, приведенного в конце главы 5 (с. <$R[P#,R5-18]>). Я не принадлежу к корифеям программирования на elisp, поэтому к этой программе следует относиться с долей скепсиса. Впрочем, функция time-now вам наверняка пригодится.
Функция Emacs для проведения тестов из главы 5
;; -*- lisp-interaction -*-
(defun time-now()
"Returns the current time as the floating-point number of seconds
since 12:00 AM January 1970."
(+ (car (cdr (current-time)))
(/ (car (cdr (cdr (current-time)))) 1000000.0))
)
(defun dotest () "run my benchmark" (interactive)
(setq case-fold-search t) ;; Поиск без учета регистра
(goto-line 1) ;; Перейти в начало буфера
(setq count 0) ;; Пока не найдено ни одного совпадения
(message "testing...") ;; Сообщить пользователю о тестировании
(setq start (time-now)) ;; Зафиксировать начальное время
(while (< (point) (point-max)) ;; Пока не дойдем до конца...
(setq beg (point)) ;; Запомнить начало текущей строки
(forward-line 1) ;; Перейти к следующей строке
(setq end (point)) ;; Запомнить начало следующей строки
(goto-char beg) ;; Вернуться в начало текущей строки
(if
;; Последовательно проверить все совпадения
(or
(re-search-forward "\\<char\\>" end t)
(re-search-forward "\\<const\\>" end t)
…
(re-search-forward "\\<unsigned\\>" end t)
(re-search-forward "\\<while\\>" end t)
)
(setq count (+ count 1)) ;; Запомнить, что найдена еще одна строка
)
(goto-char end) ;; Перейти к следующей строке
)
;; Цикл закончен - вычислить и вывести затраченное время
(setq delta (- (time-now) start))
(message "results: count is %d, time = %.2f sec" count delta)
)
Несмотря на частое применение регулярных выражений, механизм регулярных выражений Emacs является наименее оптимизированным из всех нетривиальных программ на базе НКА, упоминавшихся в книге. Из всех приемов оптимизации, перечисленных в главе 5 (с. <$R[P#,R5-17]>), в Emacs выполняется только исключение по первому символу, простое повторение и жалкое подобие учета длины (механизм замечает, что если выражение не может совпасть с пустой строкой, то искать его в конце целевого текста бессмысленно).
С другой стороны, исключение по первому символу<$M[R6-5]> реализовано лучше, чем в любой другой программе с механизмом НКА. Если другие программы пасуют даже перед такими простыми конструкциями, как [a|b], то оптимизация Emacs разбирается даже в сложных выражениях. Например, при анализе выражения [^[spctab*\(with\|pragma\|use\)] Emacs правильно поймет, что совпадение должно начинаться с [[tabspc*puw]]. Именно этот фактор в значительной степени решает проблему эффективности регулярных выражений Emacs и позволяет использовать их в той степени, в которой они используются сегодня (см. с. <$R[P#,R5-19]>).
Как объяснялось в разделе «Кэширование при компиляции» (с. <$R[P#,R5-6]>), регулярные выражения обычно компилируются непосредственно перед использованием, но Emacs поддерживает кэш последних откомпилированных выражений. В версии 19.33 в кэше хранилось пять регулярных выражений, но в будущей версии будет храниться 20[5]. Увеличение размера кэша в высшей степени положительно отразилось на работе примера из главы 5 (с. <$R[P#,R5-18]>), но этот тест в определенной степени демонстрирует худшую ситуацию. Я провел некоторые простые, реальные проверки с автоматической расстановкой отступов и выбором шрифтов (при которых интенсивно используются регулярные выражения) и обнаружил, что увеличение объема кэша обеспечивает примерно 20-процентный выигрыш в скорости. Впрочем, 20 процентов — не так уж мало.
Если вы самостоятельно компилируете свою копию Emacs, вы можете задать любой нужный размер кэша. Для этого достаточно присвоить значение переменной REGEXP_CACHE_SIZE в начале файла src/search.c.
[1] В таблице 6.3 ничего не сказано об экранировании в символьных классах косой черты — ограничителя регулярных выражений. В исходном awk это было можно делать (хотя и не обязательно). В gawk экранирование / запрещено, а в других реализациях оно является обязательным требованием.
[2] Этот раздел написан для версии Tcl7.5p. Официальный сайт Tcl в World Wide Web расположен по адресу: http://www.sunlabs/com/research/tcl.
[3] Несмотря на то, что в последней документации Tcl (на момент написания — tcl7.5) утверждается обратное, метасимвол \n в строках Tcl не обязательно соответствует символу с шестнадцатеричным кодом 0A. Значение, которому он соответствует, зависит от системы (с. <$R[P#,R3-26]>). Тем не менее, когда эта книга уже направлялась в печать, Джон Устерхаут сообщил мне, что он намерен жестко закодировать 0A в программе. В будущем это может преподнести сюрпризы для пользователей MacOS.
[4] В оригинале этот раздел был написан в GNU Emacs версии 19.33.
[5] За несколько дней до завершения правки книги я сообщил Ричарду Столлмену о результатах тестов в главе 5. Он решил увеличить размер кэша до 20, а также несколько повысить эффективность поиска в кэше. Эти изменения должны появиться в следующей версии Emacs