Регулярные выражения
Спецификаторы формата для pack и unpack — достаточно простой юсоб записи, описывающий компоновку пакетов. Следующая тема iniero обсуждения — несколько более сложный, но гораздо более фазительный способ записи -- регулярные выражения (regular pressions), определяющие шаблоны текста (patterns of text). В этой [иге мы время от времени использовали регулярные выражения, не вая им точного описания; они достаточно знакомы, чтобы понять их без особых пояснений. Хотя регулярные выражения широко распространены в средах программирования под Unix, в других системах они применяются гораздо реже, поэтому в данном разделе мы решили показать некоторые их преимущества. На случай, если у вас нет под рукой библиотеки с регулярными выражениями, мы приведем ее простейшую реализацию.
Существует несколько разновидностей регулярных выражений, но суть у
них у всех одинакова — это способ описания шаблона буквенных символов,
включающего в себя повторения, альтернативы и сокращения для отдельных
классов символов вроде цифр или букв. Примером такого шаблона могут служить
всем знакомые символы замещения (wildcards), используемые в процессорах
командной строки или оболочках для задания образцов поиска имен файлов.
Как правило, символ * используется для обозначения "любой строки символов", так что команда
С:\> del *.exe
использует шаблон, которому соответствуют все имена файлов, оканчивающиеся на ".-. ехе". Как это часто бывает, детали меняются от системы к системе и даже от программы к программе.
Причуды отдельных программ могут навести на мысль, что регулярные выражения являются механизмом? создаваемым ad hoc, для каждого случая отдельно, но на самом деле регулярные выражения — это язык с формальной грамматикой и точным значением каждого выражения. Более того, при должной реализации конструкция работает очень быстро: благодаря соединению теории и практического опыта; вот пример в пользу специализированных алгоритмов, упоминавшихся нами в главе 2.
Регулярное выражение есть последовательность символов, которая определяет множество образцов поиска. Большинство символов просто-напросто соответствуют сами себе, так что регулярное выражение abc будет соответствовать именно этой строке символов, где бы она ни появлялась. Но, кроме того, существует несколько метасимволов, которые обозначают повторение, группировку или местоположение. В принятых в Unix регулярных выражениях символ ~ обозначает начало строки, а $ — конец строки, так что шаблон ~х соответствует только символу х в начале строки, х$ — только х в конце строки. Шаблону ~х$ соответствует только строка, содержащая единственный символ х, и, наконец, ~$ соответствует пустая строка.
Символ . (точка) обозначает любой символ, так что выражению х. у будут соответствовать хау, х2у и т. п., но не ху или xaby; выражению ~. $ соответствует строка из одного произвольного символа.
Набору символов внутри квадратных скобок соответствует любой ия этих символов. Таким образом, [0123456789] соответствует одной цифре, это выражение можно записать и в сокращенном виде: [0-9]1.
Эти строительные блоки комбинируются с помощью круглых скобок' для группировки, символа | — для обозначения альтернатив, * — для обозначения нуля или более совпадений, + — для обозначения одного или более совпадений и ? — для обозначения нуля или одного совпадения. Наконец, символ \ применяется в качестве префикса перед метасимволом для исключения его специального использования, то есть \* обозначает просто символ *, а \\ — собственно символ обратной косой черты \.
Наиболее известным инструментом работы с регулярными выраже-йийми является программа g rep, о которой мы уже несколько раз упоминали. Эта программа — чудесный пример, показывающий важность нотации. В ней регулярное выражение применяется к каждой строке вводимого файла и выводятся строки, которые содержат образцы поиска, описываемые этим выражением. Эта простая спецификация с помощью регулярных выражений позволяет справиться с большим количеством ежедневной рутинной работы. В приведенных ниже примерах обратите внимание на то, что синтаксис регулярных выражений, используемых в качестве аргументов g rep, отличается от шаблонов поиска, применяемых для задания набора имен файлов; различие обусловлено разным назначением выражений.
Какой исходный файл использует класс Regexp?
% grep Regexp *.java
В каком файле этот класс реализован?
% grep 'class.*Regexp' *.java
Куда я подевал это письмо от Боба?
% grep '"From:.* bob@' mail/*
Сколько непустых строк кода в этой программе?
grep *. с++ 1 we
Благодаря наличию флагов, позволяющих выводить номера соответствующих выражению строк, подсчитывать количество соответствий, осуществлять сравнение без учета регистра, инвертировать смысл выражения (то есть отбирать строки, не соответствующие шаблону) и т. п., программа grep используется сейчас настолько широко, что стала уже классическим примером программирования с помощью специальных инструментов.
К сожалению, не во всех системах имеется grep или ее аналог. Некоторые системы включают в себя библиотеку регулярных выражений, которая называется, как правило, regex или regexp, и ее можно использовать для создания собственной версии g rep. Если же нет ни того, ни другого, то на самом деле не так трудно реализовать какое-то скромное подмножество языка регулярных выражений. Здесь мы представляем реализацию регулярных выражений и grep, чтобы работать с ними; для простоты мы ограничимся метасимволами $ . и * , причем * обозначает повторение предыдущей точки или обычного символа. Выбор этого подмножества обеспечивает почти все возможности регулярных выражений, тогда как его программировать значительно проще, чем в исходном общем случае.
Начнем с самой функции, осуществляющей проверку на соответствие. Ее задача — определить, соответствует ли строка текста регулярному выражению:
Если регулярное выражение начинается с ", то текст должен начинаться
с символов, соответствующих остальной части выражения. При другом начале
мы проходим по тексту, используя matchhere для выяснения, соответствует
ли текст каждой позиции выражения. Как только мы находим соответствие,
миссия наша завершена. Обратите внимание на использование do-while: выражениям
может соответствовать пустая строка (например, шаблону $ соответствует
пустая строка, а шаблону . * — любое количество символов, включая и ноль),
поэтому вызвать matchhere мы должны даже в том случае, если строка текста
пуста.
Большая часть работы выполняется в рекурсивной функции matchhere:
Если регулярное выражение пусто, это означает, что мы дошли до его конца
и, следовательно, нашли соответствие. Если выражение оканчива- i ется
символом $, оно имеет соответствие только в том случае, если текст также
расположен в конце. Если выражение начинается с точки, то первый символ
соответствующего текста может быть любым. В противном случае выражение
начинается с какого-то обычного символа, который) в тексте соответствует
только самому себе. Символы ~ и $, встречающиеся в середине регулярного
выражения, рассматриваются как простые литеральные, а не метасимволы.
Отметьте, что matchhe re, убедившись в совпадении одного символа из; шаблона и подстроки, вызывает себя самое, таким образом, глубина ре] курсии может быть такой же, как и длина шаблона (при полном соответветствии).
Единственный сложный случай представляет собой выражение, начинающееся с символа и звездочки, например х*. В этом случае мы осуществляем вызов matchstar, где первым аргументом является операнд звездочки (то есть х), а следующими аргументами — шаблон после звездочки и сам текст.
Здесь мы опять используем do-while — из-за того, что регулярному выражению
х* может соответствовать и ноль символов. Цикл проверяет, совпадает ли
текст с остатком регулярного выражения, пытаясь сопоставить их, пока первый
символ текста совпадает с операндом звездочки.
Наша реализация получилась довольно простенькой, однако она работает и занимает всего лишь три десятка строк кода — можно утверждать, что для того, чтобы ввести в обращение регулярные выражения, не нужно применять никаких сложных средств.
Скоро мы представим некоторые соображения по расширению возможностей нашего кода, а пока напишем свою версию g rep, использующую match. Вот как выглядит основная часть:
По соглашению программы на С возвращают 0 при успешном заверше-и и ненулевое
значение — при различных сбоях. Наша программа Ф, так же как и Unix-версия,
считает выполнение успешным, если ла найдена строка, соответствующая шаблону.
Поэтому она возвращает 0, если было найдено хотя бы одно соответствие;
1 — если соответ-зий найдено не было, и 2 (посредством eprintf) — если
произошла шбка. Эти значения можно протестировать, использовав в качестве
олочки какую-то другую программу.
Функция grep сканирует один файл, вызывая match для каждой его строки:
Если открыть файл не удается, то программа не прекращает работу. Такое
поведение было выбрано для того, чтобы при вызове
% grep herpolhode *.*
даже если какой-то файл в каталоге не может быть открыт, g rep уведомляла об этом и продолжала работу; если бы на этом она останавливалась, пользователю пришлось бы вручную набивать список всех файлов в каталоге, кроме недоступного. Обратите внимание и на то, что grep выводит имя файла и строку, соответствующую шаблону, однако имя файла не выводится, если чтение происходит из стандартного потока ввода или из одного файла. Может быть, такое поведение покажется кому-то старомодным, однако оно отражает идиоматический стиль, в основе которого лежит опыт. Когда задан только один источник ввода, миссия дгер состоит, как правило, в выборе соответствующих строк, и имя файла никого не интересует. А. вот если поиск происходит в нескольких файлах, то, как правило, задачей является найти все совпадения с какой-то строкой, и здесь имя файла будет весьма информативно. Сравните
% strings markov.exe | grep 'DOS mode'
и
% grep grammer chapter*.txt
Продуманность нюансов — одна из тех черт, что сделали grep столь популярным инструментом; здесь мы видим, что для создания хороших программ нотация обязательно должна учитывать человеческую психологию.
В нашей реализации match завершает работу сразу же, как только найдено соответствие. Для g rep это вполне подходит в качестве поведения по умолчанию, но для реализации оператора подстановки (найти и заменить) в текстовом редакторе больше подошел поиск крайне левого самого длинного совпадения (leftmost longest). Например, если нам задан текст "ааааа", то шаблону а* соответствует, в частности, и пустая строка в начале текста, однако более естественным было бы включить в совпадение все пять а. Для того чтобы match искала крайне левую и самую длинную строку, matchstar надо переписать так, чтобы добиться жадного (greedy) поведения1 алгоритма: вместо того чтобы просматривать каждый символ текста слева направо, он должен каждый раз пытаться пройти до конца самой длинной строки, соответствующей оператору-звездочке, и откатываться назад, если оставшаяся часть обрабатываемого текста не соответствует оставшейся части шаблона. Другими словами, она должна выполняться справа налево. Вот как выглядит версия matchstar, осуществляющая поиск крайне левого максимального совпадения:
Для g rep абсолютно неважно, какое именно совпадение будет обнаруже-ю,
поскольку эта программа проверяет лишь наличие соответствий во-эбще и
выводит всю строку, содержащую соответствие. Таким образом, поиск крайне
левого максимального совпадения, жизненно необходимый для оператора замещения,
хоть и делает некоторую ненужную для g rep работу, все же может быть применен
без изменений и для этой программы.
Наша версия g rep вполне сравнима с версиями, поставляемыми с различными системами (неважно, что синтаксис наших регулярных выражений несколько скуднее). Существуют некоторые патологические выражения, которые приводят к экспоненциальному возрастанию трудоемкости поиска, — например, выражение а*а*а*а*а*Ь при введенном тексте ааааааааас, однако экспоненциальный поиск присутствует и в некоторых коммерческих реализациях. Вариант g rep, применяемый в Unix (он называется eg rep), использует более сложный алгоритм поиска соответствий; этот алгоритм гарантирует линейный поиск, избегая отката, когда не подходит частичное соответствие.
А как насчет того, чтобы match умела обрабатывать полноценные регулярные выражения? Для этого надо добавить возможность сопоставления классов символов типа [a-zA-Z] конкретному символу алфавита, возможность исключать значение метасимволов (например, для поиска точки нужно обозначить этот символ как литеральный), предусмотреть скобки для группировки, а также ввести альтернативы (аос или clef). Первый шаг здесь — облегчить match работу, скомпилировав шаблон в некое новое представление, которое было бы проще сканировать: слишком накладно производить разбор класса символов для каждого нового сравнения его с одним символом; предварительно вычисленное представление, основанное на битовых массивах, сделает классы символов гораздо более эффективными. Полная реализация регулярных выражений, со скобками и альтернативами, получится гораздо более сложной; облегчить написание помогут некоторые средства, о которых мы поговорим далее в этой главе.
Упражнение 9-6
Как соотносится быстродействие match и strstr при поиске простого текста (без метасимволов)?
Упражнение 9-7
Напишите версию matchhere без рекурсии и сравните ее быстродействие с рекурсивной версией.
Упражнение 9-8
Добавьте в g rep несколько ключей командной строки. К наиболее популярным ключам относятся -у для инвертирования смысла шаблона, -i для поиска без учета регистра и ~п для вывода номеров строк. Как должны выводиться номера строк? Должны ли они печататься на той же строке, что и совпавший текст?
Упражнение 9-9
Добавьте в match операторы + (один или более) и ? (ноль или один). Шаблону a+bb? соответствует строка из одного или более а, за которыми следует одно или два b.
Упражнение 9-10
В нашей реализации match специальное значение символов " и $ отключается, если они не стоят, соответственно, в начале или конце выражения, а звездочка * рассматривается как обычный символ, если она не стоит непосредственно после литерального символа или точки. Однако более стандартным поведением является~отключение значения метасимвола постановкой перед ним символа обратной косой черты (\). Измените match так, чтобы она обрабатывала этот символ именно таким образом.
Упражнение 9-11
Добавьте в match классы символов. Класс символов определяет соответствие любому из символов, заключенных в квадратные скобки. Для Удобства лучше ввести диапазоны, например [a-z] соответствует любой строчной букве (английского алфавита!), а также определить способ инвертирования смысла, — например, [~0-9] соответствует любому символу, кроме цифры.
Упражнение 9-12
Измените match так, чтобы в ней использовалась версия matchstar, ( которой ищется крайне левое максимальное соответствие. Кроме того, :ледует добиться возвращения позиции символов начала и конца текста, ;оответствующего шаблону. Теперь создайте новую версию дгер, кото- j рая вела бы себя как старая, но выполняла замену текста, соответству-. ющего шаблону, заданным новым текстом и выводила полученные стро-1 ки. Пример вызова:
grep 'homoiousian' 'homoousian' mission.stmt
Упражнение 9-13
Измените match и дгер так, чтобы они-работали со строками символов Unicode формата UTF-8. Поскольку UTF-8 и Unicode являются расширением набора 7-битового ASCII, такое изменение будет совместимо с предыдущей версией. Регулярные выражения, так же как и текст, в котором происходит поиск, должны корректно работать с UTF-8. Как в этом случае должны быть реализованы классы символов?
Упражнение 9-14
Напишите программу для автоматического тестирования регулярных выражений: она должна генерировать тестовые выражения и строки, в которых будет происходить поиск. Если можете, используйте уже существующую библиотеку как прототип для ответов, — возможно, вы найдете какие-то ошибки и в ней.
