Создание парсеров на C++ с помощью Boost::Spirit
Иногда в проектах на C++, (у кого-то чаще, у кого-то реже) возникает задача разбора какого-либо структурированного текста. То есть по сути, создание парсера того или иного языка. Обычно, к этой задаче подходят одним из следующих способов:
- Написание парсера вручную, анализируя строку средствами C++, возможно, используя регулярные выражения.
- Генерация парсера с использованием соответствующих утилит, например, Antlr, lex/yacc и т.п.
Несколько иной подход предоставляется библиотекой Spirit в составе Boost. О нем я расскажу ниже.
Boost::Spirit – библиотека, предназначенная для описания текста грамматики вместе с семантическими действиями прямо в C++ коде. Грамматика буквально конструируется из примитивных парсеров путем использования соответствующим образом перегруженных операторов C++. Таким образом, описание грамматики выглядит достаточно близко к классическому описанию, как например БНФ.
Простейшие парсеры
Приведу пример, который был мною честно списан с Википедии. Это разбор строки, содержащей набор чисел через запятую в список этих чисел. Возможно, то же самое можно было бы сделать и более простыми методами, однако этот пример позволяет понять некоторые базовые принципы Spirit.
#include <boost/spirit/core.hpp> // Основной заголовчный файл Boost::Spirit
#include <boost/spirit/actor/push_back_actor.hpp> // Конструкция push_back_a
#include <iostream>
#include <vector>
#include <string>
using namespace std;
using namespace boost::spirit; // Все типы и функции Boost::Spirit заключены в это пространство имен
/**
* Функция, которая разбирает строку - список чисел через запятую в вектор этих чисел.
* @param str строка, которую необходимо разобрать
* @param v вектор, в который добавляются результаты
* @return true, если разбор прошел успешно
*/
bool parse_numbers(const char* str, vector<double>& v)
{
return parse( // Вызываем функцию boost::spirit::parse
str, // В качестве первого аргумента передаем строку, которую необходимо разобрать
( real_p[push_back_a(v)] >> *(',' >> real_p[push_back_a(v)]) ), // Парсер, описывающий как разбирать строку
space_p // Грамматика, определяющая какие участки текста можно пропускать
).full;
// Функция возвращает структуру boost::spirit::parse_info
// но нас интересует только поле full - была ли строка полностью разобрана
}
Самое интересное здесь - определения грамматик. В частности, в примере приведены две грамматики.
Начнем со второй, поскольку она значительно проще: space_p - это встроенный примитив, принимающий последовательности пробельных символов, т.е. пробелов, табов и переносов строк.
Перейдем к первой грамматике:
real_p[push_back_a(v)] >> *(',' >> real_p[push_back_a(v)])- real_p - парсер, который считывает из строки число с плавающей точкой.
- Конструкции в квадратных скобках - это семантические действия, которые выполняются при успешном сопоставлении парсера, к которым они привязываются. В качестве семантического действия можно указать указатель на функцию или же функтор. В качестве параметра в действие будет передано значение, возвращаемое парсером. В данном случае, это прочитанное число.
- push_back_a - это встроенный функтор, определенный в заголовочном файле boost/spirit/actor/push_back_actor.hpp, выполняющий добавление передаваемого ему значение в указанную коллекцию. Таким образом, каждая конструкция real_p[push_back_a(v)] определяет парсер, считывающий число из строки и добавляющий его в вектор v.
- Оператор >> конструирует парсер, который последовательно применяет левостоящий парсер, а затем правостоящий. В частности, конструкция ',' >> real_p[push_back_a(v)] обозначает считывание из строки запятой, а затем дробного числа. Стоит отметить, что левым аргументом оператора является просто символ ','. Поскольку второй аргумент - парсер, компилятор C++ способен применить его, осуществив неявное преобразование символа к парсеру, который просто считывает заданный символ из строки.
- Оператор * конструирует парсер, который осуществляет применение правостоящего парсера 0 и более раз. Т.е. конструкция *(',' >> real_p[push_back_a(v)])
Базовые примитивы
Как, наверное, понятно из приведенного примера, для того чтоб конструировать новые парсеры, необходим набор примитивных парсеров и операторов, которые позволяют строить более сложные парсеры. Сначала, я приведу список некоторых базовых парсеров. Сразу хочу отметить, что он далеко не полон:- ch_p - парсер, считывающий заданный символ. То есть, парсер считывает один символ и проверяет его на соответствие заданному. Задается он следующим образом: ch_p('a'). К этому парсеру автоматически преобразуются символьные константы, которые встречаются в опеределении грамматики.
- str_p - аналогично, только считывает и проверяет не один символ, а непрерывную последовательность. Например: str_p("abcd"). К нему преобразуются строковые константы в определении грамматики.
- chseq_p - очень похож на предыдущий, также считывает последовательность символов, заданную в строке-параметре. Отличие: символы в последовательности могут быть разделены пробельными, т.е. теми, которые принимаются парсером, обозначающим какие участки можно пропускать. Т.е. chseq_p("abc") успешно примет "a bc", тогда как str_p("abc") не примет.
- anychar_p, alnum_p, alpha_p, digit_p, lower_p, upper_p - парсеры, которые принимают любой символ, букву или цифру, букву, цифру, символ в нижнем регистре и символ в верхнем регистре соответственно.
- uint_p, bin_p, oct_p, hex_p - парсеры, считывающие беззнаковое целое число в десятичной, двоичной, восьмеричной и шестнадцатиричной системе счисления соответственно.
- int_p - парсер, считывающий целое число в десятичной системе, возможно со знаком.
- real_p,ureal_p - парсеры, считывающие знаковое и беззнаковое числа с плавающей точкой соответственно.
Операторы
Опять же, неполный список операторов:- a >> b - оператор последовательного применения. Создает парсер,получаемый последовательным применением аргументов.
- a | b - альтернатива. Создает парсер, который пытается по очереди применить аргументы для того, чтобы разобрать строку, пока какой-либо не выдаст положительный результат.
- a & b - пересечение. Парсер, который применяется успешно тогда, когда оба аргумента успешно разбирают строку.
- a - b - разность. Получаемый парсер принимает строку тогда, когда первый аргумент ее принимает, а второй нет.
- ~ a - парсер который принимает все, что не принимает аргумент.
- * a - повторение аргумента 0 и более раз.
- + a - повторение аргумента 1 и более раз.
- ! a - опционально применение аргумента, т.е. его повторение 0 или 1 раз.
- a % b - оператор списка. Эквивалентен a >> * ( b >> a ). То есть создает парсер, осуществляющий разбор непустого списка, где первый аргумент - элемент списка и второй аргемент - разделитель.
Еще один пример
Для того, чтобы понять как все это работает, рассмотрим еще один пример. Предположим, мы хотим распарсить набор "свойство-значение", где имя состоит из букв и цифр, а значение свойства - произвольная строка в двойных кавычках. Элементы карты разделены запятой, ключ и значение разделено двоеточием. Будем строить грамматику сверху вниз:- На самый общий взгляд наш текст представляет из себя список некоторых элементов, разделенных запятой. Так и запишем:
/*элемент*/ % ','
- Что представляет из себя элемент? Это пара ключ-значение, разделенные двоеточием. Добавим это вместо /*элемент*/
( /*ключ*/ >> ':' >> /*значение*/ ) % ','
- Что есть ключ? Непустая последовательность букв и цифр, без разделителей. Для того, чтобы показать, что какой-то участок текста не должен содержать разделителей используется директива lexeme_d. Тогда, парсер примет вид:
( lexeme_d[ +alnum_p ] >> ':' >> /*значение*/ ) % ','
- Значение это произвольная строка без кавычек, заключенная в кавычки. И все это без разделителей. Итоговый парсер принимает вид:
( lexeme_d[ +alnum_p ] >> ':' >> lexeme_d[ '"' >> +~ch_p('"') >> '"' ] ) % ','
#include <string>
#include <map>
#include <boost/spirit/core.hpp>
#include <boost/spirit/actor/assign_actor.hpp>
#include <boost/spirit/actor/insert_at_actor.hpp>
using namespace boost::spirit;
bool parseConfig( const char * str, std::map<std::string,std::string> & mp ) {
std::string key;
return parse(
str,
( ( lexeme_d[+alnum_p][assign_a(key)] >> ':' >> lexeme_d[ '"' >> ( *~ch_p('"') )[insert_at_a(mp,key)] >> '"' ] ) % ',' ),
space_p
).full;
}
