Глава 30. Регулярные выражения

Машина регулярных выражений
Шаблоны поиска
Символы и метасимволы
Символьные классы
Анкеры (привязки)
Альтернативы
Квантификаторы
Группировка и захват
Опции поиска
«Прожорливость» шаблонов
Операторы поиска и замены
Оператор поиска
Оператор замены
Оператор связывания
Встроенная процедура split

Типичной задачей, связанной с обработкой информации, является поиск определённых фрагментов текста и их замена на другой текст. Вот конкретные примеры:

Если первая задача легко решается при помощи практически любого текстового редактора с функцией «поиск-замена», остальные решить не так просто. Программа, использующая только традиционные средства работы со строками, получается весьма громоздкой.

Для формулировки задач о поиске фрагментов текста придуман специальный язык. Он называется языком регулярных выражений (regular expressions). Мы рассмотрим один из диалектов этого языка.

Помимо перечисленных задач, встающих обычно перед редактором, корректором или цензором, имеются и другие, странные на первый взгляд, приложения регулярных выражений, вроде проверки делимости натуральных чисел. Мы обратимся к регулярным выражениям в главах 31. «Римская числовая нотация», 32. «Поиск простых чисел с помощью регулярных выражений», 33. «Диофантовы уравнения», 42. «Полимино».

Между прочим, программа XSLTHL, раскрашивающая фрагменты кода в этой книге, весьма интенсивно использует регулярные выражения.

Эта глава содержит лишь краткое введение в регулярные выражения. Для более глубокого погружения в тему мы рекомендуем книги [4], [5]. Исчерпывающее описание регулярных выражений в Perl можно найти на man-странице perlre. Краткое руководство по использованию регулярных выражений в Perl есть на man-странице perlretut.

Регулярные выражения находят применение во многих системах программирования. Обычно механизм поиска и замены встраивается в такие системы либо как набор библиотечных процедур, либо как набор синтаксических конструкций в алгоритмическом языке (в языке Perl это именно синтаксические конструкции).

Как работает этот механизм? Как только возникает нужда в сопоставлении строки с шаблоном, создаётся машина регулярных выражений — специальный исполнитель, умеющий производить поиск и замену в строках. Затем производится синтаксический разбор регулярного выражения, при котором проверяется его правильность. В результате разбора шаблон компилируется — преобразуется в программу для машины. Программа представляет собой набор инструкций, которые машина должна выполнить, чтобы осуществить поиск или замену.

Машина регулярных выражений устроена весьма сложно. Мы не ставим перед собой задачу изучить её работу во всех подробностях. Будем представлять её как чёрный ящик, на вход которого подаётся регулярное выражение (в откомпилированном виде) и строка. На выходе машина выдаёт ответ, подходит ли какая-то подстрока в строке под шаблон или нет. Машина может также выдавать, при успешном сопоставлении, кое-какую дополнительную информацию о том, какие части строки соответствуют определённым фрагментам шаблона (см. раздел «Группировка и захват»). Машина умеет также заменять найденную продстроку на другую строку.

Информатика-54© А. Н. Швец