Типичной задачей, связанной с обработкой информации, является поиск определённых фрагментов текста и их замена на другой текст. Вот конкретные примеры:
В текстовом файле необходимо заменить всюду слово карова
на корова
.
Требуется заменить все нецензурные слова из некоторого списка на
[CENSORED]
.
В текстовом файле абзацы обозначены при помощи «красной строки» — отступа, состоящего из одного или нескольких символов пробела или табуляции. Нужно убрать эти отступы, вставив перед абзацем пустую строку.
Несколько идущих подряд пустых строк заменить на одну.
Заменить в тексте «однополые» кавычки "⋯"
(правильнее
назвать их знаками дюйма) на «ёлочки» «⋯»
. При этом нужно
правильно выбрать правую или левую кавычку-ёлочку в зависимости от символов,
расположенных по соседству. На клавиатуре компьютера обычно отсутствуют клавиши
с правильными кавычками, поэтому авторы текстов часто заменяют их на суррогаты.
Однако в хорошо оформленных книгах использование знака дюйма вместо ёлочек
совершенно недопустимо.
Заменить в тексте, где это нужно, знаки дефиса -
на знаки
длинного тире —
. Следует оставить знаки дефиса там, где они
разделяют части составных слов (то есть окружены буквами). Возьмите любую
приличную книгу и сравните дефисы и тире, и вы увидите, насколько они
различаются по ширине, высоте расположения на строке и по толщине.
Если первая задача легко решается при помощи практически любого текстового редактора с функцией «поиск-замена», остальные решить не так просто. Программа, использующая только традиционные средства работы со строками, получается весьма громоздкой.
Для формулировки задач о поиске фрагментов текста придуман специальный язык. Он называется языком регулярных выражений (regular expressions). Мы рассмотрим один из диалектов этого языка.
Помимо перечисленных задач, встающих обычно перед редактором, корректором или цензором, имеются и другие, странные на первый взгляд, приложения регулярных выражений, вроде проверки делимости натуральных чисел. Мы обратимся к регулярным выражениям в главах 31. «Римская числовая нотация», 32. «Поиск простых чисел с помощью регулярных выражений», 33. «Диофантовы уравнения», 42. «Полимино».
Между прочим, программа XSLTHL, раскрашивающая фрагменты кода в этой книге, весьма интенсивно использует регулярные выражения.
Эта глава содержит лишь краткое введение в регулярные выражения. Для более глубокого погружения в тему мы рекомендуем книги [4], [5]. Исчерпывающее описание регулярных выражений в Perl можно найти на man-странице perlre. Краткое руководство по использованию регулярных выражений в Perl есть на man-странице perlretut.
Регулярные выражения находят применение во многих системах программирования. Обычно механизм поиска и замены встраивается в такие системы либо как набор библиотечных процедур, либо как набор синтаксических конструкций в алгоритмическом языке (в языке Perl это именно синтаксические конструкции).
Как работает этот механизм? Как только возникает нужда в сопоставлении строки с шаблоном, создаётся машина регулярных выражений — специальный исполнитель, умеющий производить поиск и замену в строках. Затем производится синтаксический разбор регулярного выражения, при котором проверяется его правильность. В результате разбора шаблон компилируется — преобразуется в программу для машины. Программа представляет собой набор инструкций, которые машина должна выполнить, чтобы осуществить поиск или замену.
Машина регулярных выражений устроена весьма сложно. Мы не ставим перед собой задачу изучить её работу во всех подробностях. Будем представлять её как чёрный ящик, на вход которого подаётся регулярное выражение (в откомпилированном виде) и строка. На выходе машина выдаёт ответ, подходит ли какая-то подстрока в строке под шаблон или нет. Машина может также выдавать, при успешном сопоставлении, кое-какую дополнительную информацию о том, какие части строки соответствуют определённым фрагментам шаблона (см. раздел «Группировка и захват»). Машина умеет также заменять найденную продстроку на другую строку.