Пособие по практике программирования

       

g rep абсолютно неважно, какое





Для g rep абсолютно неважно, какое именно совпадение будет обнаруже-ю, поскольку эта программа проверяет лишь наличие соответствий во-эбще и выводит всю строку, содержащую соответствие. Таким образом, поиск крайне левого максимального совпадения, жизненно необходимый для оператора замещения, хоть и делает некоторую ненужную для g rep работу, все же может быть применен без изменений и для этой программы.
Наша версия g rep вполне сравнима с версиями, поставляемыми с различными системами (неважно, что синтаксис наших регулярных выражений несколько скуднее). Существуют некоторые патологические выражения, которые приводят к экспоненциальному возрастанию трудоемкости поиска, — например, выражение а*а*а*а*а*Ь при введенном тексте ааааааааас, однако экспоненциальный поиск присутствует и в некоторых коммерческих реализациях. Вариант g rep, применяемый в Unix (он называется eg rep), использует более сложный алгоритм поиска соответствий; этот алгоритм гарантирует линейный поиск, избегая отката, когда не подходит частичное соответствие.
А как насчет того, чтобы match умела обрабатывать полноценные регулярные выражения? Для этого надо добавить возможность сопоставления классов символов типа [a-zA-Z] конкретному символу алфавита, возможность исключать значение метасимволов (например, для поиска точки нужно обозначить этот символ как литеральный), предусмотреть скобки для группировки, а также ввести альтернативы (аос или clef). Первый шаг здесь — облегчить match работу, скомпилировав шаблон в некое новое представление, которое было бы проще сканировать: слишком накладно производить разбор класса символов для каждого нового сравнения его с одним символом; предварительно вычисленное представление, основанное на битовых массивах, сделает классы символов гораздо более эффективными. Полная реализация регулярных выражений, со скобками и альтернативами, получится гораздо более сложной; облегчить написание помогут некоторые средства, о которых мы поговорим далее в этой главе.

Содержание раздела