Простейшая токенизация

Алгоритмы для строк, заданные в заголовочном файле <boost/algorithm/string.hpp>, предоставляют готовые шаблонные функции «replace_all» для поиска и замены подстроки, «trim» для обрезания пробелов слева и справа, «split» для разделения строки на массив подстрок, разделённых символом-разделителем и другие.

Для разбиения текста на слова подходит boost::split. Рассмотрим пример ниже:

vector<string> SplitWords(string const& text)

{

std::string trimmed = boost::trim_copy(text);

vector<string> words;

boost::split(words, trimmed, boost::is_space(), boost::token_compress_on);

return words;

}

• предикат, возвращённый функцией ‘boost::is_space()’, отмечает пробельные символы как разделители
• token_compress_on гарантирует склеивание нескольких пробельных символов в один
• ‘boost::trim’ убирает пробельные символы в начале и в конце текста (иначе в words окажутся пустые слова)

Токенизация на основе регулярных выражений

Стандартная библиотека регулярных выражений, которая появилась в C++ 2011 в виде заголовка . Он поддерживает поиск по регулярному выражению как на диапазоне итераторов, так и на объекте типа «std::basic_string».

Несколько примеров использования regex для задач лексического анализа есть в репозитории github.com/ps-group/compiler-theory-samples (подкаталог std-regex)

Разбор с возвратом (backtracking parssing) в старом стиле

Классы строк языка C++ обеспечивают простые и безопасные ввод, вывод, копирование и конкатенацию строк. Но для многих задач, таких как рекурсивный спуск или любой другой способ разбора грамматик, нужен доступ к произвольным символам (random access) и возможность переместить позицию сканнера. Есть два хороших и один сомнительный способ реализации random access:

1. Хранить саму строку и одну или с ней одну или несколько переменных типа «size_t», сохраняющих позицию считывающего автомата
2. Хранить итераторы начала, конца строки и вспомогательные итераторы, обеспечивающие доступ к сканируемым в данный момент символам. Это предпочтительный способ, начиная с C++ 2011.
3. Сомнительный способ: получить указатель на начало строки, и использовать арифметику указателей для random access и перемещения сканера. Проблемы могут возникнуть и при откате разбора строки, и при проверке выхода за пределы строки

Разбор с возвратом (backtracking parssing) на основе string_view

Проще всего сделать парсер, работающий с объектами string_view — невладеющими ссылками на строку. Реализацию string_view можно раздобыть несколькими способами:

1. Найти компилятор и IDE с поддержкой C++17, в котором <string_view> и объявленные в этом заголовке классы стали частью стандартной библиотеки
2. Либо взять тривиальную реализацию на Github, состоящую из одного заголовка: github.com/sergey-shambir/string_view
3. Либо получить Boost версии 1.61 или выше, в котором есть <boost/utility/string_view.hpp>

По сути string_view — это удобная замена такой структуры для чтения строки слева направо:

struct StringScanState

{

std::string text;

size_t position;

};

Ссылка на строку не выделяет память, не освобождает память и никак не влияет на время жизни последовательности символов, размещённой в куче. Задача класса – всего лишь предоставить программный интерфейс, аналогичный «std::string», более безопасный и простой, чем итераторы. Кроме интерфейса строки, у ссылки на строку есть методы «remove_prefix(size_t count)» и «remove_suffix(size_t count)», позволяющие сузить область сканирования строки, или отрезать уже просканированную левую/праву часть. Также есть метод «str()», копирующий и возвращающий владеющую памятью строку.