Обработка текста
“Ничто не может быть настолько очевидным,
чтобы быть действительно очевидным...
Употребление слова “очевидно” свидетельствует
об отсутствии логических аргументов”.
Эррол Моррис (Errol Morris)
В этой главе речь идет в основном об извлечении информации из текста. Мы храним свои знания в виде слов, зафиксированных в документах, таких как книги, сообщения электронной почты, или распечатанных таблиц, чтобы впоследствии извлечь их оттуда в форме, удобной для вычислений. Здесь мы опишем возможности стандартной библиотеки, которые интенсивнее остальных используются для обработки текстов: классы
string
, iostream
и map
. Затем введем регулярные выражения (класс regex
), позволяющие выражать шаблонные фрагменты текстов. В заключение покажем, как с помощью регулярных выражений находить и извлекать из текста специфические элементы данных, такие как почтовые индексы, а также верифицировать форматы текстовых файлов.23.1. Текст
По существу, мы постоянно работаем с текстом. Наши книги заполнены текстом, большая часть того, что мы видим на экране компьютера, — это текст, и исходный код наших программ является текстом. Наши каналы связи (всех видов) переполнены словами. Всю информацию, которой обмениваются два человека, можно было бы представить в виде текста, но не будем заходить так далеко. Изображения и звуки обычно лучше всего представлять в виде изображений и звуков (т.е. в виде совокупности битов), но все остальное можно обрабатывать с помощью программ анализа и преобразования текста.
Начиная с главы 3 мы использовали классы
iostreams
и string
, поэтому здесь кратко опишем библиотеки, которым они принадлежат. Особенно полезны для обработки текстов ассоциативные массивы (раздел 23.4), поэтому мы приводим пример их использования для анализа электронной почты. Кроме этого обзора, в главе рассматриваются вопросы поиска шаблонных фрагментов в тексте с помощью регулярных выражений (разделы 23.5–23.10).23.2. Строки
Класс string содержит последовательность символов и несколько полезных операций, таких как добавление символа к строке, определение длины строки и конкатенация двух строк. На самом деле стандартный класс string содержит довольно мало операций, но большинство из них оказываются полезными только при низкоуровневой обработке действительно сложных текстов. Здесь мы лишь упомянем о нескольких наиболее полезных операциях. При необходимости их полное описание (и исчерпывающий список операций из класса
string
) можно найти в справочнике или учебнике повышенной сложности. Эти операции определены в заголовке
(но не
).
Операции ввода-вывода описаны в главах 10-11, а также в разделе 23.3. Обратите внимание на то, что операции ввода в объект класса string при необходимости увеличивают его размер, поэтому переполнение никогда не происходит.
Операции
insert()
и append()
перемещают символы, чтобы освободить место для новых. Операция erase()
сдвигает символы влево, чтобы заполнить пробел, оставшийся после удаления символа. На самом деле стандартная строка в библиотеке описывается шаблонным классом
basic_string
, поддерживающим множество наборов символов, например, Unicode, в котором предусмотрены тысячи символов (таких как £, Ω, ∞, δ, ζ, и ♫, кроме обычных символов). Скажем, если у вас есть шрифт, содержащий символ из набора Unicode, например Unicode, можете написать следующий фрагмент кода:
basic_string a_unicode_string;
Стандартный класс
string
, который мы используем, является просто классом basic_string
, конкретизированным обычным типом char
.
typedef basic_string string; // строка — это basic_string
Мы не будем описывать символы или строки кода Unicode, но при необходимости вы можете работать с ними точно так же, как и с обычными символами и строками (к ним применяются точно такие же конструкции языка, класс
string
, потоки класса iostream
и регулярные выражения). Если вам нужны символы кода Unicode, то лучше всего попросить совета у опытных пользователей; для того чтобы ваша программа стала полезной, вы должны не только выполнять правила языка, но и некоторые системные соглашения.В контексте обработки текста важно помнить, что практически все можно представить в виде строки символов. Например, на этой странице число
12.333
представлено в виде строки, состоящей из шести символов и окруженной пробелами. Если вы считываете это число, то должны сначала превратить эти символы в число с плавающей точкой и лишь потом применять к нему арифметические операции. Это приводит к необходимости конвертирования чисел в объекты класса
string
и объектов класса string
в числа. В разделе 11.4 мы видели, как превратить целое число в объект класса string
, используя класс ostringstream. Этот прием можно обобщить для любого типа, имеющего оператор <<
.
template string to_string(const T& t)
{
ostringstream os;
os << t;
return os.str();
}
Рассмотрим пример.
string s1 = to_string(12.333);
string s2 = to_string(1+5*6–99/7);
Значение строки
s1
равно "12.333
", а значение строки s2
— "17
". Фактически функцию to_string()
можно применять не только к числовым значениям, но и к любому классу T
с оператором <<
.Обратное преобразование, из класса
string
в число, так же просто, как и полезно.
struct bad_from_string:std::bad_cast
// класс для сообщений об ошибках при преобразовании строк
{
const char* what() const // override bad_cast’s what()
{
return "bad cast from string";
}
};
template T from_string(const string& s)
{
istringstream is(s);
T t;
if (!(is >> t)) throw bad_from_string();
return t;
}
Рассмотрим пример.
double d = from_string("12.333");
void do_something(const string& s)
try
{
int i = from_string(s);
// ...
}
catch (bad_from_string e) {
error ("Неправильная строка ввода",s);
}
Дополнительная сложность функции
from_string()
по сравнению с функцией to_string()
объясняется тем, что класс string
может представлять значения многих типов. Это значит, что каждый раз мы должны указывать, какой тип значений хотим извлечь из объекта класса string
. Кроме того, это значит, что класс string
, который мы изучаем, может не хранить значение типа, который мы ожидаем. Рассмотрим пример.
int d = from_string("Mary had a little lamb"); // Ой!
Итак, возможна ошибка, которую мы представили в виде исключения типа
bad_from_string
. В разделе 23.9 мы покажем, что функция from_string()
(или эквивалентная) играет важную роль в серьезных текстовых приложениях, поскольку нам необходимо извлекать числовые значения из текстовых полей. В разделе 16.4.3 было показано, как эквивалентная функция get_int()
используется в графическом пользовательском интерфейсе.Обратите внимание на то, что функции
to_string()
и from_string()
очень похожи. Фактически они являются обратными друг другу; иначе говоря (игнорируя детали, связанные с пробелами, округлением и т.д.), для каждого “разумного типа T
” имеем
s==to_string(from_string(s)) // для всех s
и
t==from_string(to_string(t)) // для всех t
Здесь слово “разумный” означает, что тип
T
должен иметь конструктор по умолчанию, оператор >>
и соответствующий оператор <<
. Следует подчеркнуть, что реализации функций
to_string()
и from_string()
используют класс stringstream
для выполнения всей работы. Это наблюдение было использовано для определения универсальной операции конвертирования двух произвольных типов с согласованными операциями <<
и >>
.
struct bad_lexical_cast:std::bad_cast
{
const char* what() const { return "bad cast"; }
};
template
Target lexical_cast(Source arg)
{
std::stringstream interpreter;
Target result;
if (!(interpreter << arg) // записываем arg в поток
|| !(interpreter >> result) // считываем result из потока
|| !(interpreter >> std::ws).eof()) // поток пуст?
throw bad_lexical_cast();
return result;
}
Довольно забавно и остроумно, что инструкция
!(interpreter>>std::ws).eof()
считывает любой пробел, который может остаться в потоке stringstream
после извлечения результата. Пробелы допускаются, но кроме них в потоке ввода может не остаться никаких других символов, и мы должны реагировать на эту ситуацию, как на обнаружение конца файла. Итак, если мы пытаемся считать целое число int
из объекта класса string
, используя класс lexical_cast
, то в результате выражения lexical_cast("123")
и lexical_cast("123")
будут считаться допустимыми, а выражение lexical_cast("123.5")
— нет из-за последней пятерки.Довольно элегантное, хотя и странное, имя
lexical_cast
используется в библиотеке boost
, которую мы будем использовать для сравнения регулярных выражений в разделах 23.6–23.9. В будущем она станет частью новых версий стандарта языка С++ .23.3. Потоки ввода-вывода
Рассматривая связь между строками и другими типами, мы приходим к потокам ввода-вывода. Библиотека ввода-вывода не просто выполняет ввод и вывод, она осуществляет преобразования между форматами и типами строк в памяти. Стандартные потоки ввода-вывода обеспечивают возможности для чтения, записи и форматирования строк символов. Библиотека
iostream
описана в главах 10-11, поэтому просто подведем итог.
Стандартные потоки организованы в виде иерархии классов (см. раздел 14.3).
В совокупности эти классы дают нам возможность выполнять ввод-вывод, используя файлы и строки (а также все, что выглядит как файлы и строки, например клавиатуру и экран; см. главу 10). Как указано в главах 10-11, потоки
iostream
предоставляют широкие возможности для форматирования. Стрелки на рисунке обозначают наследование (см. раздел 14.3), поэтому, например, класс stringstream
можно использовать вместо классов iostream
, istream
или ostream
. Как и строки, потоки ввода-вывода можно применять и к широким наборам данных, и к обычным символам. Снова следует подчеркнуть, что, если вам необходимо работать с вводом-выводом символов Unicode, лучше всего спросить совета у экспертов; для того чтобы стать полезной, ваша программа должна не просто соответствовать правилам языка, но и выполнять определенные системные соглашения.
23.4. Ассоциативные контейнеры
Ассоциативные контейнеры (ассоциативные массивы и хеш-таблицы) играют ключевую роль (каламбур) в обработке текста. Причина проста — когда мы обрабатываем текст, мы собираем информацию, а она часто связана с текстовыми строками, такими как имена, адреса, почтовые индексы, номера карточек социального страхования, место работы и т.д. Даже если некоторые из этих текстовых строк можно преобразовать в числовые значения, часто более удобно и проще обрабатывать их именно как текст и использовать его для идентификации. В этом отношении ярким примером является подсчет слов (см. раздел 21.6). Если вам неудобно работать с классом
map
, пожалуйста, еще раз прочитайте раздел 21.6.Рассмотрим сообщение электронной почты. Мы часто ищем и анализируем сообщения электронной почты и ее регистрационные записи с помощью какой-то программы (например, Thunderbird или Outlook). Чаще всего эти программы скрывают детали, характеризующие источник сообщения, но вся информация о том, кто его послал, кто получил, через какие узлы оно прошло, и многое другое поступает в программы в виде текста, содержащегося в заголовке письма. Так выглядит полное сообщение. Существуют тысячи инструментов для анализа заголовков. Большинство из них использует регулярные выражения (как описано в разделе 23.5–23.9) для извлечения информации и какие-то разновидности ассоциативных массивов для связывания их с соответствующими сообщениями. Например, мы часто ищем сообщение электронной почты для выделения писем, поступающих от одного и того же отправителя, имеющих одну и ту же тему или содержащих информацию по конкретной теме.
Приведем упрощенный файл электронной почты для демонстрации некоторых методов извлечения данных из текстовых файлов. Заголовки представляют собой реальные заголовки RFC2822 с веб-страницы www.faqs.org/rfcs/rfc2822.html. Рассмотрим пример.
xxx
xxx
––––
From: John Doe
To: Mary Smith
Subject: Saying Hello
Date: Fri, 21 Nov 1997 09:55:06 –0600
Message–ID: <1234@local.machine.example>
This is a message just to say hello.
So, "Hello".
––––
From: Joe Q. Public
To: Mary Smith <@machine.tld:mary@example.net>, , jdoe@test
.example
Date: Tue, 1 Jul 2003 10:52:37 +0200
Message–ID: <5678.21–Nov–1997@example.com>
Hi everyone.
––––
To: "Mary Smith: Personal Account"
From: John Doe
Subject: Re: Saying Hello
Date: Fri, 21 Nov 1997 11:00:00 –0600
Message–ID:
In–Reply–To: <3456@example.net>
References: <1234@local.machine.example><3456@example.net>
This is a reply to your reply.
––––
––––
По существу, мы сократили файл, отбросив большинство информации и облегчив анализ, завершив каждое сообщение строкой, содержащей символы –––– (четыре пунктирные линии). Мы собираемся написать “игрушечное приложение”, которое будет искать все сообщения, посланные отправителем John Doe, и выводить на экран их тему под рубрикой “Subject”. Если мы сможем это сделать, то научимся делать много интересных вещей.
Во-первых, мы должны решить, хотим ли мы иметь произвольный доступ к данным или анализировать их как входные потоки. Мы выбрали первый вариант, поскольку в реальной программе нас, вероятно, интересовали бы несколько отправителей или несколько фрагментов информации, поступившей от конкретного отправителя. Кроме того, эту задачу решить труднее, поэтому нам придется проявить больше мастерства. В частности, мы снова применим итераторы.
Наша основная идея — считать весь почтовый файл в структуру, которую мы назовем
Mail_file
. Эта структура будет хранить все строки почтового файла (в объекте класса vector
) и индикаторы начала и конца каждого отдельного сообщения (в объекте класса vector
).Для этого мы добавим итераторы, а также функции
begin()
и end()
, чтобы иметь возможность перемещаться по строкам и сообщениям, как обычно. Эта схема обеспечит нам удобный доступ к сообщениям. Имея такой инструмент, мы напишем наше “игрушечное приложение”, позволяющее собирать вместе все сообщения, поступившие от одного и того же адресата, чтобы их было легче найти.
В заключение выведем на экран все темы сообщений, поступивших от John Doe, чтобы проиллюстрировать созданный нами механизм доступа к структурам. Мы используем для этого основные средства стандартной библиотеки.
#include
#include
#include
#include
#include
using namespace std;
Определим класс
Message
как пару итераторов в классе vector
(наш вектор строк).
typedef vector::const_iterator Line_iter;
class Message { // объект класса Message ссылается
// на первую и последнюю строки сообщения
Line_iter first;
Line_iter last;
public:
Message(Line_iter p1, Line_iter p2) :first(p1), last(p2) { }
Line_iter begin() const { return first; }
Line_iter end() const { return last; }
// ...
};
Определим класс
Mail_file
как структуру, содержащую строки текста и сообщения.
typedef vector::const_iterator Mess_iter;
struct Mail_file { // объект класса Mail_file содержит все строки
// из файла и упрощает доступ к сообщениям
string name; // имя файла
vector lines; // строки по порядку
vector m; // сообщения по порядку
Mail_file(const string& n); // считываем файл n в строки
Mess_iter begin() const { return m.begin(); }
Mess_iter end() const { return m.end(); }
};
Отметьте, что мы добавили в структуры данных итераторы, чтобы иметь возможность систематически перемещаться по структуре. На самом деле мы не собираемся использовать здесь стандартные библиотечные алгоритмы, но если захотим, то итераторы позволят нам сделать это.
Для того чтобы найти и извлечь информацию, содержащуюся в сообщении, нужны две вспомогательные функции.
// Ищет имя отправителя в объекте класса Message;
// возвращает значение true, если имя найдено;
// если имя найдено, помещает имя отправителя в строку s:
bool find_from_addr(const Message* m,string& s);
// возвращает тему сообщения, если ее нет, возвращает символ " ":
string find_subject(const Message* m);
Итак, мы можем написать код для извлечения информации из файла.
int main()
{
Mail_file mfile("my–mail–file.txt"); // инициализируем структуру
// mfile данными из файла
// сначала собираем сообщения, поступившие от каждого
// отправителя, в объекте класса multimap:
multimap sender;
for (Mess_iter p = mfile.begin(); p!=mfile.end(); ++p) {
const Message& m = *p;
string s;
if (find_from_addr(&m,s))
sender.insert(make_pair(s,&m));
}
// Теперь перемещаемся по объекту класса multimap
// и извлекаем темы сообщений, поступивших от John Doe:
typedef multimap::const_iterator MCI;
pair pp =
sender.equal_range("John Doe ");
for(MCI p = pp.first; p!=pp.second; ++p)
cout << find_subject(p–>second) << '\n';
}
Рассмотрим подробнее использование ассоциативных массивов. Мы использовали класс
multimap
(разделы 20.10 и Б.4), поскольку хотели собрать в одном месте много сообщений, поступивших из одного адреса. Стандартный класс multimap
делает именно это (облегчая доступ к элементам с помощью одного и того же ключа). Очевидно (и типично), что наша задача распадается на две подзадачи:• создать ассоциативный массив;
• использовать ассоциативный массив.
Мы создаем объект класса
multimap
путем обхода всех сообщений и их вставки с помощью функции insert()
:
for (Mess_iter p = mfile.begin(); p!=mfile.end(); ++p) {
const Message& m = *p;
string s;
if (find_from_addr(&m,s))
sender.insert(make_pair(s,&m));
}
В ассоциативный массив включаются пары (ключ, значение), созданные с помощью функции
make_pair()
. Для того чтобы найти имя отправителя, используем “кустарную” функцию find_from_addr()
.Почему мы используем ссылку
m
и передаем ее адрес? Почему не использовать итератор p
явно и не вызвать функцию так: find_from_addr(p,s)
? Потому что, даже если мы знаем, что итератор Mess_iter
ссылается на объект класса Message
, нет никакой гарантии, что он реализован как указатель.Почему мы сначала записали объекты класса
Message
в вектор, а затем создали объект класса multimap
? Почему сразу не включить объекты класса Message
в ассоциативный массив класса map
? Причина носит простой и фундаментальный характер.• Сначала мы создаем универсальную структуру, которую можно использовать для многих вещей.
• Затем используем ее в конкретном приложении.
Таким образом, мы создаем коллекцию в той или иной степени повторно используемых компонентов. Если бы мы сразу создали ассоциативный массив в объекте класса
Mail_file
, то вынуждены были бы переопределять его каждый раз, когда хотим использовать его для решения другой задачи. В частности, наш объект класса multimap
(многозначительно названный sender
) упорядочен по полю Address
. Большинство других приложений могут использовать другой критерий сортировки: по полям Return, Recipients, Copy-to fields, Subject fields, временным меткам и т.д.Создание приложений по этапам (или слоям (layers), как их иногда называют) может значительно упростить проектирование, реализацию, документацию и эксплуатацию программ. Дело в том, что каждая часть приложения решает отдельную задачу и делает это вполне очевидным образом. С другой стороны, для того чтобы сделать все сразу, нужен большой ум. Очевидно, что извлечение информации и заголовков сообщений электронной почты — это детский пример приложения. Значение разделения задач, выделения модулей и поступательного наращивания приложения по мере увеличения масштаба приложения проявляется все более ярко.
Для того чтобы извлечь информацию, мы просто ищем все упоминания ключа "John Doe", используя функцию
equal_range()
(раздел Б.4.10). Затем перемещаемся по всем элементам в последовательности [first,second]
, возвращаемой функцией equal_range()
, извлекая темы сообщений с помощью функции find_subject()
.
typedef multimap::const_iterator MCI;
pair pp = sender.equal_range("John Doe");
for (MCI p = pp.first; p!=pp.second; ++p)
cout << find_subject(p–>second) << '\n';
Перемещаясь по элементам объекта класса map, мы получаем последовательность пар (ключ,значение), в которых, как в любом другом объекте класса
pair
, первый элемент (в данном случае ключ класса stringkey
) называется first
, а второй (в данном случае объект класса Message
) — second
(см. раздел 21.6).23.4.1. Детали реализации
Очевидно, что мы должны реализовать используемые нами функции. Соблазнительно, конечно, сэкономить бумагу и спасти дерево, предоставив читателям самостоятельно решить эту задачу, но мы решили, что пример должен быть полным.
Конструктор класса
Mail_file
открывает файл и создает векторы lines
и m
.
Mail_file::Mail_file(const string& n)
// открывает файл с именем "n"
// считывает строки из файла "n" в вектор lines
// находит сообщения в векторе lines и помещает их в вектор m,
// для простоты предполагая, что каждое сообщение заканчивается
// строкой "––––" line
{
ifstream in(n.c_str()); // открываем файл
if (!in) {
cerr << " нет " << n << '\n';
exit(1); // прекращаем выполнение программы
}
string s;
while (getline(in,s)) lines.push_back(s); // создаем вектор
// строк
Line_iter first = lines.begin(); // создаем вектор сообщений
for (Line_iter p = lines.begin(); p!=lines.end(); ++p) {
if (*p == "––––") { // конец сообщения
m.push_back(Message(first,p));
first = p+1; // строка –––– не является частью
// сообщения
}
}
}
Обработка ошибок носит слишком элементарный характер. Если бы писали эту программу для своих друзей, то постарались бы сделать ее лучше.
ПОПРОБУЙТЕ
Что значит “более хорошая обработка ошибок”? Измените конструктор класса
Mail_file
так, чтобы он реагировал на ошибки форматирования, связанные с использованием строки “––––”.
Функции
find_from_addr()
и find_subject()
не имеют конкретного содержания, пока мы не выясним, как идентифицировать информацию в файле (используя регулярные выражения и из разделов 23.6–23.10).
int is_prefix(const string& s, const string& p)
// Является ли строка p первой частью строки s?
{
int n = p.size();
if (string(s,0,n)==p) return n;
return 0;
}
bool find_from_addr(const Message* m, string& s)
{
for(Line_iter p = m–>begin(); p!=m–>end(); ++p)
if (int n = is_prefix(*p,"From: ")) {
s = string(*p,n);
return true;
}
return false;
}
string find_subject(const Message* m)
{
for(Line_iter p = m.begin(); p!=m.end(); ++p)
if (int n = is_prefix(*p,"Subject: "))
return
string(*p,n);
return "";
}
Обратите внимание на то, как мы используем подстроки: конструктор
string(s,n)
создает строку, состоящую из хвоста строки s
, начиная с элемента s[n]
(т.е. s[n]..s[s.size()–1]
), а конструктор string(s,0,n)
создает строку, состоящую из символов s[0]..s[n–1]
. Поскольку эти операторы на самом деле создают новые строки и копируют символы, они должны использоваться очень осторожно, чтобы не снизить производительность программы. Почему функции
find_from_addr()
и find_subject()
так отличаются друг от друга? Например, одна из них возвращает переменную типа bool
, а другая — объект класса string
. Потому что мы хотели подчеркнуть следующие моменты.• Функция
find_from_addr()
различает поиск пустой строки адреса (""
) и поиск отсутствующей строки адреса. В первом случае функция find_from_addr()
возвращает значение true
(поскольку она нашла адрес) и присваивает строке s
значение ""
(потому что адресная строка просто оказалась пустой). Во втором случае она возвращает значение false
(поскольку в файле вообще не оказалось адресной строки).• Функция
find_subject()
возвращает строку ""
и когда строка темы сообщения оказалась пустой, и когда ее вообще нет.
Насколько полезным является такое различие, которое проводит функция
find_from_addr()
? Необходимо ли это? Мы считаем, что это полезно и необходимо. При поиске информации в файле данных это различие проявляется снова и снова: нашли ли мы искомую строку и содержит ли она то, что нам нужно? В реальной программе обе функции, find_from_addr()
и find_subject()
, следовало бы написать в стиле функции find_from_addr()
, чтобы дать пользователям возможность проводить такое различие.Эта программа не является оптимальной с точки зрения производительности, но мы надеемся, что в типичных ситуациях она работает достаточно быстро. В частности, она считывает входной файл только один раз и не хранит несколько копий текста из этого файла. Для крупных файлов было бы целесообразно заменить класс
multimap
классом unordered_multimap
, но без испытаний невозможно сказать, насколько это повысит эффективность программы.Введение в стандартные ассоциативные контейнеры (
map
, multimap
, set
, unordered_map
и unordered_multimap
) см. в разделе 21.6.23.5. Проблема
Потоки ввода-вывода и класс
string
помогают нам считывать и записывать последовательности символов, хранить их и выполнять над ними основные операции. Однако при работе с текстом во многих случаях необходимо анализировать контекст строки или рассматривать много аналогичных строк. Рассмотрим тривиальный пример. Возьмем сообщение электронной почты (последовательность слов) и посмотрим, содержит ли оно аббревиатуру U.S. и почтовый код (две буквы, за которыми следуют пять цифр).
string s;
while (cin>>s) {
if (s.size()==7
&& isalpha(s[0]) && isalpha(s[1])
&& isdigit(s[2]) && isdigit(s[3]) && isdigit(s[4])
&& isdigit(s[5]) && isdigit(s[6]))
cout << " найдена " << s << '\n';
}
Здесь значение
isalpha(x)
равно true
, если x
— это буква, а значение isdigit(x)
равно true
, если x
— цифра (см. раздел 11.6). В этом (слишком) простом решении кроется несколько проблем.• Оно громоздко (четыре строки, восемь вызовов функций).
• Мы пропускаем (умышленно?) почтовые индексы, не отделенные от своего контекста пробелом (например, "TX77845", TX77845–1234 и ATX77845).
• Мы пропускаем (умышленно?) почтовые индексы с пробелом между буквами и цифрами (например, TX 77845).
• Мы принимаем (умышленно?) почтовые индексы, в которых буквы набраны в нижнем регистре (например, tx77845).
• Если вы решите проанализировать почтовые индексы, имеющие другой формат (например, CB3 0FD), то будете вынуждены полностью переписать весь код.
Должен быть более хороший способ! Перед тем как его описать, рассмотрим поставленные задачи. Предположим, что мы хотим сохранить “старый добрый код”, дополнив его обработкой указанных ситуаций.
• Если мы хотим обрабатывать не один формат, то следует добавить инструкцию
if
или switch
.• Если мы хотим учитывать верхний и нижний регистры, то должны явно конвертировать строки (обычно в нижний регистр) или добавить дополнительную инструкцию
if
.• Мы должны как-то (как?) описать контекст, в котором выполняется поиск. Это значит, что мы должны работать с отдельными символами, а не со строками, т.е. потерять многие преимущества, предоставляемые потоками
iostream
(см. раздел 7.8.2).
Если хотите, попробуйте написать код в этом стиле, но нам очевидно, что в этом случае вы запутаетесь в сети инструкций
if
, предназначенных для обработки особых ситуаций. Даже в этом простом примере мы стоим перед выбором (например, учитывать ли пяти- и девятизначные почтовые индексы). Во многих других примерах нам необходимо работать с восклицательными знаками (например, любым количеством цифр, за которыми следует знак восклицания, такими как 123!
и 123456!
). В конце концов, нельзя забывать о префиксах и суффиксах. Как мы уже указывали (см. разделы 11.1 и 11.2), предпочтения пользователей по отношению к разным форматам не ограничиваются стремлением программистов к систематичности и простоте. Просто подумайте о разнообразных способах записи одной только даты.
2007–06–05
June 5, 2007
jun 5, 2007
5 June 2007
6/5/2007
5/6/07
...
В этот момент, если не раньше, опытный программист воскликнет: “Должен быть более хороший способ!” (чем нагромождение ординарного кода) и станет его искать. Простейшим и наиболее широко распространенным решением этой задачи является использование так называемых регулярных выражений (regular expressions).
Регулярные выражения являются основой большинства методов обработки текстов и команды
grep
в системе Unix (см. упр. 8), а также важной частью языков программирования, интенсивно применяющихся для решения этих задач (таких как AWK, Perl и PHP).Регулярные выражения, которые мы будем использовать, реализованы в библиотеке, которая станет частью следующего стандарта языка С++ (C++0x). Они сопоставимы с регулярными выражениями из языка Perl. Этой теме посвящено много книг, учебников и справочников, например, рабочий отчет комитета по стандартизации языка C++ (в сети веб он известен под названием WG21), документация Джона Мэддокса (John Maddock)
boost::regex
и учебники по языку Perl. Здесь мы изложим фундаментальные понятия, а также основные и наиболее полезные способы использования регулярных выражений.
ПОПРОБУЙТЕ
В последних двух абзацах “неосторожно” упомянуты несколько имен и аббревиатур без каких-либо объяснений. Поищите в веб информацию о них.
23.6. Идея регулярных выражений
Основная идея регулярного выражения заключается в том, что оно определяет шаблон (pattern), который мы ищем в тексте. Посмотрим, как мы могли бы точно описать шаблон простого почтового кода, такого как TX77845. Результат первой попытки выглядит следующим образом:
wwddddd
где символ w означает любую букву, а символ d — любую цифру. Мы используем символ w (от слова “word”), поскольку символ l (от слова “letter”) слишком легко перепутать с цифрой 1. Эти обозначения вполне подходят для нашего простого примера, но что произойдет, если мы попробуем применить их для описания формата почтового кода, состоящего из девяти цифр (например, TX77845–5629). Что вы скажете о таком решении?
wwddddd–dddd
Они выглядят вполне логичными, но как понять, что символ d означает “любая цифра”, а знак – означает “всего лишь” дефис? Нам необходимо как-то указать, что символы w и d являются специальными: они представляют классы символов, а не самих себя (символ w означает “a или b или c или ...”, а символ d означает “1 или 2, или 3, или ...”). Все это слишком сложно. Добавим к букве, обозначающей имя класса символов, обратную косую черту, как это сделано в языке С++ (например, символ \n означает переход на новую строку). В этом случае получим такую строку:
\w\w\d\d\d\d\d–\d\d\d\d
Выглядит довольно некрасиво, но, по крайней мере, мы устранили неоднозначность, а обратные косые черты ясно обозначают то, что за ними следует “нечто необычное”. Здесь повторяющиеся символы просто перечислены один за другим. Это не только утомительно, но и провоцирует ошибки. Вы можете быстро сосчитать, что перед обратной косой чертой до дефиса действительно стоят пять цифр, а после — четыре? Мы смогли, но просто сказать5 и 4 мало, чтобы в этом убедиться, поэтому придется их пересчитать. После каждого символа можно было бы поставить счетчик, указывающий количество его повторений.
\w2\d5–\d4
Однако на самом деле нам нужна какая-то синтаксическая конструкция, чтобы показать, что числа 2, 5 и 4 в этом шаблоне являются значениями счетчиков, не просто цифрами 2, 5 и 4. Выделим значения счетчиков фигурными скобками.
\w{2}\d{5}–\d{4}
Теперь символ { является таким же специальным символом, как и обратная косая черта, \, но этого избежать невозможно, и мы должны просто учитывать этот факт.
Итак, все бы ничего, но мы забыли о двух обстоятельствах: последние четыре цифры в почтовом коде ZIP являются необязательными. Иногда допустимыми являются оба варианта: TX77845 и TX77845–5629. Этот факт можно выразить двумя основными способами:
\w{2}\d{5} или \w{2}\d{5}–\d{4}
и
\w{2}\d{5} и необязательно –\d{4}
Точнее говоря, сначала мы должны выразить идею группирования (или частичного шаблона), чтобы говорить о том, что строки \w{2}\d{5} и –\d{4} являются частями строки \w{2}\d{5}–\d{4}. Обычно группирование выражается с помощью круглых скобок.
(\w{2}\d{5})(–\d{4})
Теперь мы должны разбить шаблон на два частичных шаблона (sub-patterns), т.е. указать, что именно мы хотим с ними делать. Как обычно, введение новой возможности достигается за счет использования нового специального символа: теперь символ ( является специальным, как и символы \ и {. Обычно символ | используется для обозначения операции “или” (альтернативы), а символ ? — для обозначения чего-то условного (необязательного). Итак, можем написать следующее:
(\w{2}\d{5})|(\w{2}\d{5}–\d{4})
и
(\w{2}\d{5})(–\d{4})?
Как и фигурные скобки при обозначении счетчиков (например, \w{2}), знак вопроса (?) используется как суффикс. Например, (–\d{4})? означает “необязательно –\d{4}”; т.е. мы интерпретируем четыре цифры, перед которыми стоит дефис, как суффикс. На самом деле мы не используем круглые скобки для выделения пятизначного почтового кода ZIP (\w{2}\d{5}) для выполнения какой-либо операции, поэтому их можно удалить.
\w{2}\d{5}(–\d{4})?
Для того чтобы завершить наше решение задачи, поставленной в разделе 23.5, можем добавить необязательный пробел после двух букв.
\w{2} ?\d{5}(–\d{4})?
Запись “?” выглядит довольно странно, но знак вопроса после пробела указывает на то, что пробел является необязательным. Если бы мы хотели, чтобы пробел не выглядел опечаткой, то должны были бы заключить его в скобки.
\w{2}( )?\d{5}((–\d{4})?
Если бы кто-то сказал, что эта запись выглядит слишком неразборчивой, то нам пришлось бы придумать обозначение для пробела, например \s (s — от слова “space”). В этом случае запись выглядела бы так:
\w{2}\s?\d{5}(–\d{4})?
А что если кто-то поставит два пробела после букв? В соответствии с определенным выше шаблоном это означало бы, что мы принимаем коды TX77845 и TX 77845, но не TX 77845. Это неправильно.
Нам нужно средство, чтобы сказать “ни одного, один или несколько пробелов”, поэтому мы вводим суффикс *.
\w{2}\s*\d{5}(–\d{4})?
Было бы целесообразно выполнять каждый этап в строгой логической последовательности. Эта система обозначения логична и очень лаконична. Кроме того, мы не принимали проектные решения с потолка: выбранная нами система обозначений очень широко распространена. При решении большинства задач, связанных с обработкой текста, нам необходимо читать и записывать эти символы. Да, эти записи похожи на результат прогулки кошки по клавиатуре, и ошибка в единственном месте (наш лишний или пропущенный пробел) полностью изменяет их смысл, но с этим приходится смириться. Мы не можем предложить ничего радикально лучшего, и этот стиль обозначений за тридцать лет распространился очень широко. Впервые он был использован в команде
grep
в системе Unix, но и даже тогда его нельзя было назвать совершенно новым.23.7. Поиск с помощью регулярных выражений
Теперь применим шаблон почтовых кодов ZIP из предыдущего раздела для поиска почтовых кодов в файле. Программа определяет шаблон, а затем ищет его, считывая файл строка за строкой. Когда программа находит шаблон в какой-то строке, она выводит номер строки и найденный код.
#include
#include
#include
#include
using namespace std;
int main()
{
ifstream in("file.txt"); // файл ввода
if (!in) cerr << "нет файла \n";
boost::regex pat ("\\w{2}\\s*\\d{5}(–\\d{4})?"); // шаблон
// кода ZIP
cout << "шаблон: " << pat << '\n';
int lineno = 0;
string line; // буфер ввода
while (getline(in,line)) {
++lineno;
boost::smatch matches; // записываем сюда совпавшие строки
if (boost::regex_search(line, matches, pat))
cout << lineno << ": " << matches[0] << '\n';
}
}
Эта программа требует объяснений. Сначала рассмотрим следующий фрагмент:
#include
...
boost::regex pat ("\\w{2}\\s*\\d{5}(–\\d{4})?"); // шаблон кода ZIP
boost::smatch matches; // записываем сюда совпавшие строки
if (boost::regex_search(line, matches, pat))
Мы используем реализацию библиотеки
Boost.Regex
, которая скоро станет частью стандартной библиотеки. Для того чтобы использовать библиотеку Boost.Regex
, ее необходимо инсталлировать. Для того чтобы показать, какие возможности относятся к библиотеке Boost.Regex
, мы явно указываем пространство имен boost
в качестве квалификатора, т.е. boost::regex
.Вернемся к регулярным выражениям! Рассмотрим следующий фрагмент кода:
boost::regex pat ("\\w{2}\\s*\\d{5}(–\\d{4})?");
cout << "шаблон: " << pat << '\n';
Здесь мы сначала определили шаблон
pat
(типа regex
), а затем вывели его на печать. Обратите внимание на то, что мы написали:
\\w{2}\\s*\\d{5}(–\\d{4})?
Если бы вы запустили программу, то увидели бы на экране следующую строку:
pattern: \w{2}\s*\d{5}(–\d{4})?
В строковых литералах языка С++ обратная косая черта означает управляющий символ (раздел A.2.4), поэтому вместо одной обратной косой черты (\) в литеральной строке необходимо написать две (\\).
Шаблон типа
regex
на самом деле является разновидностью объекта класса string
, поэтому мы можем вывести его на печать с помощью оператора <<
. Класс regex
— это не просто разновидность класса string
, но его довольно сложный механизм сопоставления шаблонов, созданных при инициализации объекта класса regex
(или при выполнении оператора присваивания), выходит за рамки рассмотрения нашей книги. Однако, поскольку мы инициализировали объект класса regex
шаблоном почтовых кодов, можем применить его к каждой строке нашего файла.
boost::smatch matches;
if (boost::regex_search(line, matches, pat))
cout << lineno << ": " << matches[0] << '\n';
Функция
regex_search(line, matches, pat)
ищет в строке line
любое соответствие регулярному выражению, хранящемуся в объекте pat
, и если она находит какое-либо соответствие, то сохраняет его в объекте matches
. Естественно, если соответствие не обнаружено, функция regex_search(line, matches, pat)
возвращает значение false
.Переменная
matches
имеет тип smatch
. Буква s
означает “sub.” По существу, тип smatch
представляет собой вектор частичных совпадений. Первый элемент matches[0]
представляет собой полное совпадение. Мы можем интерпретировать элемент matches[i]
как строку, если i
. Итак, если для данного регулярного выражения максимальное количество частичных шаблонов равно N
, выполняется условие matches.size()==N+1
. Что такое частичный шаблон (sub-pattern)? Можно просто сказать: “Все, что заключено в скобки внутри шаблона”. Глядя на шаблон "\\w{2}\\s*\\d{5}(–\\d{4})?", мы видим скобки вокруг четырехзначного кода ZIP. Таким образом, мы видим только один частичный шаблон, т.е.
matches.size()==2
. Кроме того, можно догадаться, что у нас есть простой доступ к этим четырем последним цифрам. Рассмотрим пример.
while (getline(in,line)) {
boost::smatch matches;
if (boost::regex_search(line, matches, pat)) {
cout << lineno << ": " << matches[0] << '\n'; // полное
// совпадение
if (1
cout << "\t: " << matches[1] << '\n'; // частичное
// совпадение
}
}
Строго говоря, мы не обязаны проверять выражение
1
, поскольку уже рассмотрели шаблон, но к этому нас подталкивает легкая паранойя (поскольку мы экспериментируем с разными шаблонами, хранящимися в объекте pat
, и не все они содержат только один частичный шаблон). Мы можем проверить, обнаружен ли частичный шаблон, просматривая его член matched
, в данном случае matches[1].matched
. Нас интересует следующая ситуация: если значение matches[i].matched
равно false
, то частичные шаблоны matches[i]
, у которых нет соответствия, выводятся как пустые строки. Аналогично, если частичный шаблон не существует, например matches[17]
для приведенного выше шаблона, то он рассматривается как шаблон, у которого нет соответствия.Мы применили нашу программу к файлу, содержащему следующие строки:
address TX77845
ffff tx 77843 asasasaa
ggg TX3456–23456
howdy
zzz TX23456–3456sss ggg TX33456–1234
cvzcv TX77845–1234 sdsas
xxxTx77845xxx
TX12345–123456
Результат приведен ниже.
pattern: "\w{2}\s*\d{5}(–\d{4})?"
1: TX77845
2: tx 77843
5: TX23456–3456
: –3456
6: TX77845–1234
: –1234
7: Tx77845
8: TX12345–1234
: –1234
Следует подчеркнуть несколько важных моментов.
• Мы не дали себя запутать неверно отформатированным кодом ZIP в строке, начинающейся символами ggg (кстати, что в нем неправильно?).
• В строке, содержащей символы zzz, мы нашли только первый код ZIP (мы ищем только один код в строке).
• В строках 5 и 6 мы нашли правильные суффиксы.
• В строке 7 мы нашли код ZIP, скрытый среди символов xxx.
• Мы нашли (к сожалению?) код ZIP, скрытый в строке TX12345–123456.
23.8. Синтаксис регулярных выражений
Мы рассмотрели довольно элементарный пример сравнения регулярных выражений. Настало время рассмотреть регулярные выражения (в форме, использованной в библиотеке
regex
) более полно и систематично.Регулярные выражения (regular expressions, regexps или regexs), по существу, образуют небольшой язык для выражения символьных шаблонов. Этот мощный (выразительный) и лаконичный язык иногда выглядит довольно таинственным. За десятилетия использования регулярных выражений в этом языке появилось много тонких свойств и несколько диалектов. Здесь мы опишем подмножество регулярных выражений (большое и полезное), которое, возможно, в настоящее время является наиболее распространенным диалектом (язык Perl). Если читателям понадобится более подробная информация о регулярных выражениях или возникнет необходимость объяснить их другим людям, они могут найти все, что нужно, в веб. Существует огромное количество учебников (очень разного качества) и спецификаций. В частности, в веб легко найти спецификацию
boost::regex
и ее эквивалент, принятый Комитетом по стандартизации (WG21 TR1). Библиотека
boost::regex
поддерживает также системы обозначений языков ECMAScript, POSIX и awk, а также утилит grep и egrep. Кроме того, она содержит массу возможностей для поиска. Это может оказаться чрезвычайно полезным, особенно, если вам необходимо сравнить шаблон, описанный на другом языке. Если вам понадобятся языковые средства, которые выходят за рамки тем, которые мы описываем, поищите их самостоятельно. Однако помните, что использование как можно большего числа свойств — это не самоцель качественного программирования. При любой возможности постарайтесь сжалиться над бедным программистом, который будет эксплуатировать вашу программу (возможно, им окажетесь вы сами через несколько месяцев), читать ее и пытаться разобраться в вашем коде: код следует писать так, чтобы он не был заумным без особой причины и не содержал малопонятных мест.23.8.1. Символы и специальные символы
Регулярные выражения определяют шаблон, который можно использовать для сопоставления символов из строки. По умолчанию символ в шаблоне соответствует самому себе в строке. Например, регулярное выражение (шаблон) "abc" соответствует подстроке abc строки Is there an abc here?
Реальная мощь регулярных выражений заключается в специальных символах и сочетаниях символов, имеющих особый смысл в шаблоне.
Например, выражение
x.y
соответствует любой строке, состоящей из трех символов, начинающейся с буквы
x
и заканчивающейся буквой y
, например xxy
, x3y
и xay
, но не yxy
, 3xy
или xy
.Обратите внимание на то, что выражения
{...}
, *
, +
и ?
являются постфиксными операторами. Например, выражение \d+ означает “одна или несколько десятичных цифр”.Если хотите использовать в шаблоне один из специальных символов, вы должны сделать его управляющим, поставив перед ним обратную косую черту; например, символ
+
в шаблоне является оператором “один или несколько”, а символ \+
— это знак “плюс”.23.8.2. Классы символов
Самые распространенные сочетания символов в сжатом виде представлены как специальные символы.
Символы в верхнем регистре означают “не вариант специального символа в нижнем регистре”. В частности, символ \W означает “не буква”, а не “буква в верхнем регистре”.
Элементы третьего столбца (например,
[[:digit:]]
) представляют собой альтернативные синтаксические конструкции, использующие более длинные имена.Как и библиотеки
string
и iostream
, библиотека regex
может обрабатывать большие наборы символов, такие как Unicode. Как и в случае библиотек string
и iostream
, мы просто упоминаем об этом, чтобы при необходимости читатели могли самостоятельно найти информацию. Обсуждение манипуляций текстами в кодировке Unicode выходит за рамки рассмотрения нашей книги.23.8.3. Повторения
Повторяющиеся шаблоны задаются постфиксными операторами.
Например, выражение
Ax*
соответствует символу A, за котором не следует ни одного символа или следует несколько символов x:
A
Ax
Axx
Axxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Если мы требуем, чтобы символ
x
встречался хотя бы один раз, то следует использовать оператор +
, а не *
. Например, выражение
Ax+
соответствует символу A, за которым следует один или несколько символов x:
Ax
Axx
Axxxxxxxxxxxxxxxxxxxxxxxxxxxxx
но не
A
В общем случае необязательный символ (ни одного или несколько) указывается с помощью знака вопроса. Например, выражение
\d–?\d
соответствует двум цифрам с необязательным дефисом между ними:
1–2
12
но не
1––2
Для задания конкретного количества вхождений или конкретного диапазона вхождений используются фигурные скобки. Например, выражение
\w{2}–\d{4,5}
соответствует только строкам, содержащим две буквы и дефис, за которым следуют четыре или пять цифр:
Ab–1234
XX–54321
22–54321
но не
Ab–123
?b–1234
Да, цифры задаются символами \w.
23.8.4. Группировка
Для того чтобы указать, что некое регулярное выражение является частичным шаблоном (sub-pattern), его следует заключить в круглые скобки. Рассмотрим пример.
(\d*:)
Данное выражение определяет частичный шаблон, не содержащий ни одной или содержащий несколько цифр, за которыми следует двоеточие. Группу можно использовать как часть более сложного шаблона. Рассмотрим пример.
(\d*:)?(\d+)
Данное выражение задает необязательную и, возможно, пустую последовательность цифр, за которыми следуют двоеточие и последовательность из одной или нескольких цифр. Этот лаконичный и точный способ выражения шаблонов изобрели обычные люди!
23.8.5. Варианты
Символ “или” (|) задает альтернативу. Рассмотрим пример.
Subject: (FW:|Re:)?(.*)
Это выражение распознает тему сообщения электронной почты с необязательными символами FW: или Re:, за которыми может не стоять ни одного символа или может стоять несколько символов. Рассмотрим пример.
Subject: FW: Hello, world!
Subject: Re:
Subject: Norwegian Blue
но не
SUBJECT: Re: Parrots
Subject FW: No subject!
Пустая альтернатива не допускается.
(|def)
// ошибка
Однако мы можем указать несколько альтернатив сразу.
(bs|Bs|bS|BS)
23.8.6. Наборы символов и диапазоны
Специальные символы представляют собой обозначение наиболее распространенных классов символов: цифр (\d); букв, цифр и знака подчеркивания (\w) и др. (см. раздел 23.7.2). Однако часто бывает полезно определить свой собственный специальный символ. Сделать это очень легко. Рассмотрим пример.
В спецификации класса символов дефис (–) используется для указания диапазона, например, [1–3] (1, 2 или 3) и [w–z] (w, x, y или z). Пожалуйста, будьте аккуратны при использовании таких диапазонов: не все языки содержат одинаковые буквы, и порядки их следования в алфавитах разных языков могут отличаться. Если вам необходим диапазон, не являющийся частичным диапазоном букв и цифр, принятых в английском языке, то обратитесь к документации.
Следует подчеркнуть, что мы используем специальные символы, такие как \w (означающий “любой словообразующий символ”), в спецификации класса символов. Как же нам вставить обратную косую черту (\) в класс символов? Как обычно, превращаем ее в управляющий символ: \\.
Если первым символом в спецификации класса символов является символ
^
, это означает отрицание ^
. Например:
В последнем регулярном выражении символ ^ стоит не на первом месте после квадратной скобки ([), значит, это простой символ, а не оператор отрицания. Регулярные выражения могут быть очень хитроумными.
Реализация библиотеки
regex
также содержит набор именованных классов символов, используемых для сравнения. Например, если хотите сравнивать буквенноцифровые символы (т.е. буквы или цифры: a–z, или A–Z, или 0–9), то это можно сделать с помощью регулярного выражения [[:alnum:]]
. Здесь слово alnum представляет собой имя совокупности символов (набор буквенно-цифровых символов). Шаблон для непустой строки буквенно-цифровых символов, заключенной в квадратные скобки, может выглядеть так: "[[:alnum:]]+
". Для того чтобы поместить это регулярное выражение в строковый литерал, мы должны сделать кавычки управляющими символами.
string s = "\"[[:alnum:]]+\"";
Более того, чтобы поместить строковый литерал в объект класса
regex
, мы должны сделать управляющими символами не только кавычки, но и саму обратную косую черту и использовать для инициализации круглые скобки, так как конструктор класса regex
является явным:
regex s("\\\"[[:alnum:]]+\\\"");
Использование регулярных выражений вынуждает вводить множество обозначений. Перечислим стандартные классы символов.
Реализация библиотеки
regex
может содержать и другие классы символов, но если вы решили использовать именованный класс, не указанный в этом списке, убедитесь, что он не ухудшает переносимость программы.23.8.7. Ошибки в регулярных выражениях
Что произойдет, если мы зададим неправильное регулярное выражение? Рассмотрим пример.
regex pat1("(|ghi)"); // пропущенный оператор альтернативы
regex pat2("[c–a]"); // не диапазон
Когда мы присваиваем шаблон объекту класса
regex
, он подвергается проверке. Если механизм сравнения регулярных выражений не может работать из-за того, что регулярное выражение неправильное или слишком сложное, генерируется исключение bad_expression
.Рассмотрим небольшую программу, позволяющую исследовать механизм сравнения регулярных выражений.
#include
#include
#include
#include
#include
using namespace std;
using namespace boost; // если вы используете реализацию библиотеки
// boost
// получаем извне шаблон и набор строк
// проверяем шаблон и ищем строки, содержащие этот шаблон
int main()
{
regex pattern;
string pat;
cout << "введите шаблон: ";
getline(cin,pat); // считываем шаблон
try {
pattern = pat; // проверка шаблона
cout << "Шаблон: " << pattern << '\n';
}
catch (bad_expression) {
cout << pat
<< "Не является корректным регулярным выражением\n";
exit(1);
}
cout << "Введите строки:\n";
string line; // входной буфер
int lineno = 0;
while (getline(cin,line)) {
++lineno;
smatch matches;
if (regex_search(line, matches, pattern)) {
cout << " строка " << lineno << ": " << line << '\n';
for (int i = 0; i
cout << "\tmatches[" << i << "]: "
<< matches[i] << '\n';
}
else
cout << "не соответствует \n";
}
}
ПОПРОБУЙТЕ
Запустите эту программу и попробуйте применить ее для проверки нескольких шаблонов, например abc, x.*x, ( .* ), \([^)]*\) и \ w+\w+(Jr\.) ?.
23.9. Сравнение регулярных выражений
Регулярные выражения в основном используются в двух ситуациях.
• Поиск строки, соответствующей регулярному выражению в (произвольно длинном) потоке данных, — функция
regex_search()
ищет этот шаблон как подстроку в потоке.• Сравнение регулярного выражения со строкой (заданного размера) — функция
regex_match()
ищет полное соответствие шаблона и строки.
Одним из примеров является поиск почтовых индексов в разделе 23.6. Рассмотрим извлечение данных из следующей таблицы.
Эта совершенно типичная и не очень сложная таблица (количество учеников в 2007 году в средней школе, в которой учился Бьярне Страуструп) извлечена с веб страницы, на которой она выглядела именно так, как нам нужно.
• Содержит числовые поля.
• Содержит символьные поля в строках, понятных только людям, знающим контекст, из которого извлечена таблица. (В данном случае ее могут понять только люди, знающие датский язык.)
• Символьные строки содержат пробелы.
• Поля отделены друг от друга разделителем, роль которого в данном случае играет символ табуляции.
Мы назвали эту таблицу совершенно типичной и не очень сложной, но следует иметь в виду, что одна тонкость в ней все же скрывается: на самом деле мы не можем различить пробелы и знаки табуляции; эту проблему читателям придется устранить самостоятельно.
Проиллюстрируем использование регулярных выражения для решения следующих задач.
• Убедимся, что таблица сформирована правильно (т.е. каждая строка имеет правильное количество полей).
• Убедимся, что суммы подсчитаны правильно (в последней строке содержатся суммы чисел по столбцам).
Если мы сможем это сделать, то сможем сделать почти все! Например, мы смогли бы создать новую таблицу, в которой строки, имеющие одинаковые первые цифры (например, годы: первый класс должен иметь номер 1), объединены или проверить, увеличивается или уменьшается количество студентов с годами (см. упр. 10-11).
Для того чтобы проанализировать эту таблицу, нам нужны два шаблона: для заголовка и для остальных строк.
regex header( "^[\\w ]+( [\\w ]+)*$");
regex row( "^[\\w ]+(\\d+)(\\d+)(\\d+)$");
Помните, мы хвалили синтаксис регулярных выражений за лаконичность и полезность, а не за легкость освоения новичками? На самом деле регулярные выражения имеют заслуженную репутацию языка только для письма (write-only language). Начнем с заголовка. Поскольку он не содержит никаких числовых данных, мы могли бы просто отбросить первую строку, но — исключительно для приобретения опыта — попробуем провести ее структурный анализ. Она содержит четыре словарных поля (буквенно-цифровых поля”, разделенных знаками табуляции). Эти поля могут содержать пробелы, поэтому мы не можем просто использовать управляющий символ
\w
, чтобы задать эти символы. Вместо этого мы используем выражение [\w]
, т.е. словообразующий символ (букву, цифру или знак подчеркивания) или пробел. Один или несколько словообразующих символов задается выражением [\w]+
. Мы хотим найти тот из них, который стоит в начале строки, поэтому пишем выражение ^[\w ]+
. “Шапочка” (^
) означает “начало строки”. Каждое из оставшихся полей можно выразить как знак табуляции, за которым следуют некие слова: ([\w]+)
. До конца строки их может быть сколько угодно: ([\w]+)*$
. Знак доллара ($
) означает “конец строки”. Теперь напишем строковый литерал на языке C++ и получим дополнительные обратные косые черты.
"^[\\w ]+( [\\w ]+)*$"
Мы не можем проверить, что знак табуляции действительно является таковым, но в данном случае он раскрывается в ходе набора текста и распознается сам.
Приступим к самой интересной части упражнения: к шаблону для строк, из которых мы хотим извлекать числовые данные. Первое поле вновь имеет шаблон
^[\w]+
. За ним следуют ровно три числовых поля, перед каждым из которых стоит знак табуляции: (\d+
), следовательно, получаем следующий шаблон:
^[\w ]+( \d+)(\d+)(\d+)$
После его вставки в строковый литерал он превращается в такую строку:
"^[\\w ]+(\\d+)(\\d+)(\\d+)$"
Теперь мы сделали все, что требовалось. Сначала проверим, правильно ли сформирована таблица.
int main()
{
ifstream in("table.txt"); // входной файл
if (!in) error("Нет входного файла\n");
string line; // буфер ввода
int lineno = 0;
regex header( "^[\\w ]+( [\\w ]+)*$"); // строка заголовка
regex row("^[\\w]+(\\d+)(\\d+)(\\d+)$"); // строка данных
if (getline(in,line)) { // проверяем строку заголовка
smatch matches;
if (!regex_match(line,matches,header))
error("Нет заголовка");
}
while (getline(in,line)) { // проверяем строку данных
++lineno;
smatch matches;
if (!regex_match(line,matches,row))
error("неправильная строка",to_string(lineno));
}
}
Для краткости мы не привели здесь директивы
#include
. Проверяем все символы в каждой строке, поэтому вызываем функцию regex_match()
, а не regex_search()
. Разница между ними заключается только в том, что функция regex_match()
должна сопоставлять с шаблоном каждый символ из потока ввода, а функция regex_search()
проверяет поток ввода, пытаясь найти соответствующую подстроку. Ошибочное использование функции regex_match()
, когда подразумевалось использовании функции regex_search()
(и наоборот), может оказаться самой трудно обнаруживаемой ошибкой. Однако обе эти функции используют свои совпадающие аргументы совершенно одинаково.Теперь можем перейти к верификации данных в таблице. Мы подсчитаем количество мальчиков (“drenge”) и девочек (“piger”), учащихся в школе. Для каждой строки мы проверим, действительно ли в последнем поле (“ELEVER IALT”) записана сумму первых двух полей. Последняя строка (“Alle klasser”) содержит суммы по столбцам. Для проверки этого факта модифицируем выражение row, чтобы текстовое поле содержало частичное совпадение и можно было распознать строку “Alle klasser”.
int main()
{
ifstream in("table.txt"); // входной файл
if (!in) error("Нет входного файла");
string line; // буфер ввода
int lineno = 0;
regex header( "^[\\w ]+( [\\w ]+)*$");
regex row("^([\\w ]+)(\\d+)(\\d+)( \d+)$");
if (getline(in,line)) { // проверяем строку заголовка
boost::smatch matches;
if (!boost::regex_match(line, matches, header)) {
error("Нет заголовка");
}
}
// суммы по столбцам:
int boys = 0;
int girls = 0;
while (getline(in,line)) {
++lineno;
smatch matches;
if (!regex_match(line, matches, row))
cerr << "Неправильная строка: " << lineno << '\n';
if (in.eof()) cout << "Конец файла\n";
// проверяем строку:
int curr_boy = from_string(matches[2]);
int curr_girl = from_string(matches[3]);
int curr_total = from_string(matches[4]);
if (curr_boy+curr_girl != curr_total)
error("Неправильная сумма\n");
if (matches[1]=="Alle klasser") { // последняя строка
if (curr_boy != boys)
error("Количество мальчиков не сходится\n");
if (curr_girl != girls)
error("Количество девочек не сходится\n");
if (!(in>>ws).eof())
error("Символы после итоговой строки");
return 0;
}
// обновляем суммы:
boys += curr_boy;
girls += curr_girl;
}
error("Итоговой строки нет");
}
Последняя строка по смыслу отличается от остальных: в ней содержатся суммы. Мы распознаем ее по метке (“Alle klasser”). Мы решили, что после последнего символа не должны стоять символы, не являющиеся разделителями (для распознавания этого факта используется функция
lexical_cast()
(см. раздел 23.2)), и выдаем сообщение об ошибке в случае их обнаружения.Для того чтобы извлечь числа из полей данных, мы использовали функцию
from_string()
из раздела 23.2. Мы уже проверили, что эти поля содержат только цифры, поэтому проверять правильность преобразования объекта класса string
в переменную типа int
не обязательно.23.10. Ссылки
Регулярные выражения — популярный и полезный инструмент, доступный во многих языках программирования и во многих форматах. Они поддерживаются элегантной теорией, основанной на формальных языках, и эффективной технологией реализации, основанной на конечных автоматах. Описание регулярных выражений, их теории, реализации и использования конечных автоматов выходит за рамки рассмотрения настоящей книги. Однако поскольку эта тема в компьютерных науках является довольно стандартной, а регулярные выражения настолько популярны, найти больше информации при необходимости не составляет труда.
Перечислим некоторые из этих источников.
Aho, Alfred V., Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman. Compilers: Principles, Techniques, and Tools, Second Edition (обычно называемая “The Dragon Book”). Addison-Wesley, 2007. ISBN 0321547985.
Austern, Matt, ed. “Draft Technical Report on C++ Library Extensions”. ISO/IEC DTR 19768, 2005. www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n2336.pdf.
Boost.org. Хранилище библиотек, согласованных со стандартной библиотекой языка С++. www.boost.org.
Cox, Russ. “Regular Expression Matching Can Be Simple and Fast (but Is Slow in Java, Perl, PHP, Python, Ruby, ...)”. http://swtch.com/~rsc/regexp/regexp1.html.
Maddoc, J. boost::regex documentation. www.boost.org/libs/regex/doc/index.html.
Schwartz, Randal L., Tom Phoenix, and Brian D. Foy. Learning Perl, Fourth Edition.
O’Reilly, 2005. ISBN 0596101058.
Задание
1. Выясните, является ли библиотека
regex
частью вашей стандартной библиотеки. Подсказка: ищите std::regex
и tr1::regex
.2. Запустите небольшую программу из раздела 23.7; для этого может понадобиться инсталлировать библиотеку
boost::regex
на вашем компьютере (если вы этого еще не сделали) и настроить опции проекта или командной строки для установления связи с библиотекой regex
, а затем использовать заголовки regex
.3. Используйте программу из задания 2 для проверки шаблонов из раздела 23.7.
Контрольные вопросы
1. Где мы находим “text”?
2. Какие возможности стандартной библиотеки чаще всего используются для анализа текста?
3. Куда вставляет элемент функция
insert()
— перед или после указанной позиции (или итератора)?4. Что такое Unicode?
5. Как конвертировать тип в класс
string
и наоборот?6. В чем заключается разница между инструкцией
cin>>s
и вызовом функции getline(cin,s)
, если s
— это объект класса string
?7. Перечислите стандартные потоки.
8. Что собой представляет ключ ассоциативного массива
map
? Приведите примеры полезных типов для ключей.9. Как перемещаться по элементам контейнера класса
map
?10. В чем заключается разница между классами
map
и multimap
? Какой полезной операции, существующей в классе map
, нет в классе multimap
и почему?11. Какие операции требуются для однонаправленного итератора?
12. В чем заключается разница между пустым и отсутствующим полем? Приведите два примера.
13. Зачем нужен символ управляющей последовательности при формировании регулярных выражений?
14. Как превратить регулярное выражение в переменную типа
regex
?15. Какие строки соответствуют шаблону
\w+\s\d{4}
? Приведите три примера. Какой строковый литерал нужно использовать для инициализации переменной типа regex
заданным шаблоном?16. Как (в программе) выяснить, является ли строка корректным регулярным выражением?
17. Что делает функция
regex_search()
?18. Что делает функция
regex_match()
?19. Как представить символ точки (
.
) в регулярном выражении?20. Как выразить понятие “не меньше трех” в регулярном выражении?
21. Относится ли символ 7 к группе
\w
? А символ _
(подчеркивания)?22. Какое обозначение используется для символов в верхнем регистре?
23. Как задать свой собственный набор символов?
24. Как извлечь значение из целочисленного поля?
25. Как представить число с плавающей точкой с помощью регулярного выражения?
26. Как извлечь число с плавающей точкой из строки, соответствующей шаблону?
27. Что такое частичное совпадение (sub-match)? Как его обнаружить?
Термины
Упражнения
1. Запустите программу, работающую с файлом сообщений электронной почты; протестируйте ее, используя свой собственный, более длинный файл. Убедитесь, что в этом файле есть сообщения, вызывающие сообщения об ошибках, например, сообщения с двумя адресными строками, несколько сообщений с одинаковыми адресами и/или темами и пустые сообщения. Кроме того, протестируйте программу на примере, который вообще не является сообщением и не соответствует программной спецификации, например, на файле, не содержащем строк ----.
2. Добавьте класс
multimap
и поместите в него темы сообщений. Пусть программа вводит строки с клавиатуры и выводит каждое сообщение, у которого тема совпадает с заданной строкой.3. Модифицируйте пример из раздела 23.4 и примените регулярные выражения для выявления темы и отправителя сообщения электронной почты.
4. Найдите реальный файл с сообщениями электронной почты (т.е. файл, содержащий реальные сообщения) и модифицируйте программу так, чтобы она могла выявлять темы по именам отправителей, которые вводятся пользователем с клавиатуры.
5. Найдите большой файл с сообщениями электронной почты (тысячи сообщений), а затем запишите его в объекты класса
multimap
и unordered_multimap
. Обратите внимание на то, что в нашем приложении никак не используется преимущество упорядоченности объекта класса multimap
.6. Напишите программу, обнаруживающую даты в текстовом файле. Выведите на печать каждую строку, содержащую хотя бы одну дату в формате
linenumber:line
. Начните с регулярного выражения для простого формата, например 12/24/2000, и протестируйте ее на нем. Затем добавьте новые форматы.7. Напишите программу (аналогичную предыдущей), которая находит номера кредитных карточек в файле. Разберитесь в том, какие форматы на самом деле используются для записи номеров кредитных карточек, и реализуйте их проверку в вашей программе.
8. Модифицируйте программу из раздела 23.8.7 так, чтобы на ее вход поступали шаблон и имя файла. Результатом работы программы должны быть пронумерованные строки (
line–number:line
), соответствующие шаблону. Если соответствия не выявлены, ничего выводить не надо.9. Используя функцию
eof()
(раздел Б.7.2), можно определить, какая строка в таблице является последней. Используйте эту функцию для упрощения программы, анализирующей таблицу (см. раздел 23.9). Проверьте вашу программу на файлах, содержащих пустую строку после таблицы, а также на файлах, которые не заканчиваются переходом на новую строку.10. Модифицируйте программу для проверки таблицы из раздела 23.9 так, чтобы она выводила новую таблицу, в которой строки, имеющие одинаковые первые цифры (означающие год: первому классу соответствует число 1), были объединены.
11. Модифицируйте программу для проверки таблицы из раздела 23.9 так, чтобы проверить, возрастает или убывает количество учеников с годами.
12. Напишите программу, основываясь на программе, выявляющей строки, содержащие даты (упр. 6), найдите все даты и переведите их в формат ISO год/месяц/день. Эта программа должна считывать информацию из входного файла и выводить ее в выходной файл, идентичный входному, за одним исключением: даты в нем записаны в другом формате.
13. Соответствует ли точка (
.
) шаблону '\n'
? Напишите программу, которая отвечает на этот вопрос.14. Напишите программу, которую, подобно программе из раздела 23.8.7, можно использовать для экспериментирования с сопоставлением шаблонов с помощью их ввода извне. Однако теперь программа должна считывать данные из файла и записывать их в память (разделение на строки производится с помощью символа перехода на новую строку
'\n'
), чтобы можно было экспериментировать с шаблонами, содержащими разрывы строк. Протестируйте программу на нескольких десятках шаблонов.15. Опишите шаблон, который нельзя представить с помощью регулярного выражения.
16. Только для экспертов: докажите, что шаблон из предыдущего упражнения действительно не является регулярным выражением.
Послесловие
Легко впасть в заблуждение, считая, что компьютеры и вычисления относятся только к числам, что вычисления являются частью математики. Очевидно, это не так. Просто посмотрите на экран компьютера; он заполнен текстом и пикселями. Может быть, ваш компьютер еще и воспроизводит музыку. Для каждого приложения важно выбрать правильный инструмент. В контексте языка С++ это значит правильно выбрать подходящую библиотеку. Для манипуляций текстом основным инструментом часто является библиотека регулярных выражений. Кроме того, не следует забывать об ассоциативных контейнерах map и стандартных алгоритмах.
Глава 24