Создание парсеров на C++ с помощью Boost::Spirit

Тэги: Programming, Boost, Cpp, Grammars, Parsing, 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)])
Другие парсеры можно найти в документации Spirit на страницах: Primitives, Numerics, Character Sets и других.

Базовые примитивы

Как, наверное, понятно из приведенного примера, для того чтоб конструировать новые парсеры, необходим набор примитивных парсеров и операторов, которые позволяют строить более сложные парсеры. Сначала, я приведу список некоторых базовых парсеров. Сразу хочу отметить, что он далеко не полон:
  • 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 ). То есть создает парсер, осуществляющий разбор непустого списка, где первый аргумент - элемент списка и второй аргемент - разделитель.
Другие операторы можно найти в документации Spirit на странице: Operators

Еще один пример

Для того, чтобы понять как все это работает, рассмотрим еще один пример. Предположим, мы хотим распарсить набор "свойство-значение", где имя состоит из букв и цифр, а значение свойства - произвольная строка в двойных кавычках. Элементы карты разделены запятой, ключ и значение разделено двоеточием. Будем строить грамматику сверху вниз:
  • На самый общий взгляд наш текст представляет из себя список некоторых элементов, разделенных запятой. Так и запишем:
    /*элемент*/ % ','
  • Что представляет из себя элемент? Это пара ключ-значение, разделенные двоеточием. Добавим это вместо /*элемент*/ 
    ( /*ключ*/ >> ':' >> /*значение*/ ) % ','
  • Что есть ключ? Непустая последовательность букв и цифр, без разделителей. Для того, чтобы показать, что какой-то участок текста не должен содержать разделителей используется директива lexeme_d. Тогда, парсер примет вид: 
    ( lexeme_d[ +alnum_p ] >> ':' >> /*значение*/ ) % ','
  • Значение это произвольная строка без кавычек, заключенная в кавычки. И все это без разделителей. Итоговый парсер принимает вид: 
    ( lexeme_d[ +alnum_p ] >> ':' >> lexeme_d[ '"' >> +~ch_p('"') >> '"' ] ) % ','
Теперь, необходимо как-то добавлять ключ и значение в std::map. Для этого будем использовать следующий подход: при считывании ключа сохраняем его в локальную переменную, а при считывании значения добавляем пару в std::map. Для этого необходимо использовать два встроенных функтора: assign_a и insert_at_a - которые сохраняют значение в переменную и вставляют элемент в контейнер соответственно. Другие встроенные функторы можно найти в документации Spirit на странице: Predefined Actors Полный текст примера примет вид: 

#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;
}
Далее: Boost::Spirit: Грамматики, функции и замыкания

 Подписаться на RSS

# # # # # # # # # #

Комментарии

  1. on April 16, 2009 at 14:04 Павел wrote:

    Нет, нет и еще раз нет.

    Boost::spirit - это совершенно ужасная библиотека с точки зрения разработчика. Пользуйтесь нормальными генераторами парсеров а не этой жуткой вещью.

    Решил заюзать boost::spirit в реальном проекте, парсится подмножество SQL. Компиляция жутко долгая, несколько минут!!! в режиме debug! Lexer прикрутить не смог - примеры из документации не работают! Пришлось правила для приминитвных типов писать. Процесс отладки УЖАСНЫЙ!!! Любая ошибка в грамматике = 5 страниц невообразимых ошибок с темпейтами. Error handler так и не заработал. В общем потратил несколько дней, уже давно бы все работало на AntLR.

  2. on June 26, 2009 at 14:06 lom2k wrote:

    спасибо за ценную статью

    сделал с ее помощью парсер CSV. В отличие от опубликованных вариантов, нормально работает с кавычками и т.п.

    #include <boost/spirit/include/classic_core.hpp>
    using namespace boost::spirit::classic;

    void example()
    {
    ifstream in;
    in.open("c:\\temp\\test.csv", ios_base::in);
    string str;
    if(in.is_open())
    {
    while (getline(in, str))
    {
    char delimiter(';');
    vector<string> fields;

    parse_info<> result = parse (str.c_str(), !(confix_p('"', *(!str_p("\"\"") || (+~ch_p('"'))) , '"') | +~ch_p(delimiter))[push_back_a(fields)] % delimiter, space_p);

    if (result.hit)
    {
    for (vector<string>::iterator it = fields.begin(); it != fields.end(); ++it)
    cout << *it << endl;
    }
    else
    cout << "Failed to parse CSV!" << endl;
    }
    }else
    cout << "Failed to open file!" << endl;
    }

  3. on January 04, 2010 at 14:01 Ответ Павлу wrote:

    *ехидно* только ANTLR на С++ нормально поставить почти невозможно. Даже хидеры С++ нельзя подгрузить в сгенерированные файлы, потому что их окружили extern "C" {...}.

  4. on January 08, 2010 at 08:01 Elfet wrote:

    Очень понравилась статья! То что нужно мне для начала. Спасибо!

Добавить комментарий