Регулярные выражения
Для grep абсолютно неважно, какое именно совпадение будет обнаружено, поскольку эта программа проверяет лишь наличие соответствий вообще и выводит всю строку, содержащую соответствие. Таким образом, поиск крайне левого максимального совпадения, жизненно необходимый для оператора замещения, хоть и делает некоторую ненужную для grep работу, все же может быть применен без изменений и для этой программы.
Наша версия grep вполне сравнима с версиями, поставляемыми с различными системами (неважно, что синтаксис наших регулярных выражений несколько скуднее). Существуют некоторые патологические выражения, которые приводят к экспоненциальному возрастанию трудоемкости поиска, – например, выражение а*а*а*а*а*b при введенном тексте ааааааааас, однако экспоненциальный поиск присутствует и в некоторых коммерческих реализациях. Вариант grep, применяемый в Unix (он называется egrep), использует более сложный алгоритм поиска соответствий; этот алгоритм гарантирует линейный поиск, избегая отката, когда не подходит частичное соответствие.
А как насчет того, чтобы match умела обрабатывать полноценные регулярные выражения? Для этого надо добавить возможность сопоставления классов символов типа [a-zA-Z] конкретному символу алфавита, возможность исключать значение метасимволов (например, для поиска точки нужно обозначить этот символ как литеральный), предусмотреть скобки для группировки, а также ввести альтернативы (аос или clef). Первый шаг здесь – облегчить match работу, скомпилировав шаблон в некое новое представление, которое было бы проще сканировать: слишком накладно производить разбор класса символов для каждого нового сравнения его с одним символом; предварительно вычисленное представление, основанное на битовых массивах, сделает классы символов гораздо более эффективными. Полная реализация регулярных выражений, со скобками и альтернативами, получится гораздо более сложной; облегчить написание помогут некоторые средства, о которых мы поговорим далее в этой главе.
Упражнение 9.6
Как соотносится быстродействие match и strstr при поиске простого текста (без метасимволов)?
Упражнение 9.7
Напишите версию matchhere без рекурсии и сравните ее быстродействие с рекурсивной версией.
Упражнение 9.8
Добавьте в grep несколько ключей командной строки. К наиболее популярным ключам относятся – у для инвертирования смысла шаблона, – i для поиска без учета регистра и ~n для вывода номеров строк. Как должны выводиться номера строк? Должны ли они печататься на той же строке, что и совпавший текст?
Упражнение 9.9
Добавьте в match операторы + (один или более) и ? (ноль или один). Шаблону a+bb? соответствует строка из одного или более а, за которыми следует одно или два b.
Упражнение 9.10
В нашей реализации match специальное значение символов и $ отключается, если они не стоят, соответственно, в начале или конце выражения, а звездочка * рассматривается как обычный символ, если она не стоит непосредственно после литерального символа или точки. Однако более стандартным поведением является отключение значения метасимвола постановкой перед ним символа обратной косой черты (\). Измените match так, чтобы она обрабатывала этот символ именно таким образом.
Упражнение 9.11
Добавьте в match классы символов. Класс символов определяет соответствие любому из символов, заключенных в квадратные скобки. Для Удобства лучше ввести диапазоны, например [a-z] соответствует любой строчной букве (английского алфавита!), а также определить способ инвертирования смысла, – например, [~0-9] соответствует любому символу, кроме цифры.
Упражнение 9.12
Измените match так, чтобы в ней использовалась версия matchstar, (которой ищется крайне левое максимальное соответствие. Кроме того, следует добиться возвращения позиции символов начала и конца текста, соответствующего шаблону. Теперь создайте новую версию grep, которая вела бы себя как старая, но выполняла замену текста, соответствующего шаблону, заданным новым текстом и выводила полученные строки. Пример вызова:
grep 'homoiousian' 'homoousian' mission.stmt
Упражнение 9.13
Измените match и grep так, чтобы они-работали со строками символов Unicode формата UTF-8. Поскольку UTF-8 и Unicode являются расширением набора 7-битового ASCII, такое изменение будет совместимо с предыдущей версией. Регулярные выражения, так же как и текст, в котором происходит поиск, должны корректно работать с UTF-8. Как в этом случае должны быть реализованы классы символов?
Упражнение 9.14
Напишите программу для автоматического тестирования регулярных выражений: она должна генерировать тестовые выражения и строки, в которых будет происходить поиск. Если можете, используйте уже существующую библиотеку как прототип для ответов, – возможно, вы найдете какие-то ошибки и в ней.