Знакомство с Boost.Spirit.Qi

Библиотека Boost.Spirit состоит из нескольких частей: Classic, Qi, Lex и Karma. Classic — это старая реализация (1.x) Boost.Spirit, оставленная для совместимости. Lex — это токенайзер, позволяющий разбить входящий текст на токены. Karma служит для форматирования аутпута. В этой же статье речь пойдёт о Qi — второй версии парсера Boost.Spirit.

Boost.Spirit.Qi использует расширенную форму Бэкуса-Наура (EBNF), но, в отличие от yacc, не генерирует код парсера, а позволяет писать EBNF прямо в коде.

Для того, чтобы познакомиться с библиотекой, нам понадобится простой формальный язык. Пусть это будет арифметическое выражение со скобками и знаками «+» и «-«, например:

1
(1)
1 - 2
1 - 2 + 3
(1 + 2)
3 + (1 + 2)
(1 + 2) + 3
(1 + 2 + 3) + 4
(1 + 2) + (3 + 4)
(1 + (2 + 3)) + 4 + (5 + 6)
(1 + (2 + 3)) + (4 + 5) + 6
1 + 2 + (3 - 4 + (5 + 6 - (7 - 8 + 9) - 10) - 11 + 12) + 13 + 14

Этого примера достаточно для понимания того, что нужно делать для написания собственного парсера. Вместе с этим, этот пример достаточно прост, чтобы не загромождать эту статью кодом.

Первое и самое сложное, что необходимо для создания парсера — продумать EBNF языка. Для представленного выше языка EBNF будет следующей:

Оператор ::= "+" | "-"
Операнд ::= число | <Выражение в скобках>
<Выражение в скобках> ::= "(" Выражение ")"
<Правая часть выражения> ::= Оператор Операнд
Выражение ::= Операнд { <Правая часть выражения> }

Далее нужно описать структуры данных для хранения данных каждого правила. Для того, чтобы одно и то же поле могло хранить данные разных типов (что необходимо, например, для реализации правила Операнд), следует использовать библиотеку Boost.Variant, которая поддерживается парсерами Spirit. Эта же библиотека позволяет разрешить проблему с рекурсивным вхождением правил друг в друга.
Итак, давайте посмотрим на заголовочный файл нашего парсера.

#include <memory>
#include <string>
#include <ostream>
#include <vector>
#include <boost/variant.hpp>

namespace Parser {

enum class Operator
{
    plus,
    minus
};

typedef int Number;

struct Expression;

typedef boost::variant<Number, boost::recursive_wrapper<Expression>> Operand;

struct RightExpression
{
    Operator operator_;
    Operand operand;
};

struct Expression
{
    Operand operand;
    std::vector<RightExpression> right;
};

std::shared_ptr<Expression> parse(const std::string & _input);

} // namespace Parser

std::ostream & operator << (std::ostream & _stream, const Parser::Operator & _operator);
std::ostream & operator << (std::ostream & _stream, const Parser::Operand & _operand);
std::ostream & operator << (std::ostream & _stream, const Parser::Expression & _expression);

Как видно, структуры данных в точности повторяют описания в EBNF. Структура для правила <Выражение в скобках> отсутствует, так как это правило идентично правилу Выражение, за исключением скобок, которые не являются данными. Повторяющиеся вхождения правил может быть записано с помощью стандартного вектора, что мы и сделали для правила Выражение при записи вхождения <Правая часть выражения>.
Наибольший интерес вызывает строка

typedef boost::variant<Number, boost::recursive_wrapper<Expression>> Operand;

Здесь применяется библиотека Boost.Variant. Это выражение декларирует тип Operand, который может хранить либо число, либо Expression. Класс boost::recursive_wrapper позволяет избежать ошибки компиляции из-за использования незавершённых типов. Такая ошибка происходит, потому что для типа Operand требуется тип Expression, а для типа Expression требуется тип Operand.

Описав все необходимые типы, мы сталкиваемся с новой проблемой — Boost.Spirit не умеет с ними работать. Чтобы Boost.Spirit научился работать с нашими типами, необходимо сгенерировать дополнительную информацию с помощью макроса BOOST_FUSION_ADAPT_STRUCT, входящего в библиотеку Boost.Fusion.

BOOST_FUSION_ADAPT_STRUCT(
    RightExpression,
    (Operator, operator_)
    (Operand, operand)
)

BOOST_FUSION_ADAPT_STRUCT(
    Expression,
    (Operand, operand)
    (std::vector<RightExpression>, right)
)

Теперь мы можем приступить к написанию парсера.

namespace qi = boost::spirit::qi;

class OperatorSymbol : public qi::symbols<char, Operator>
{
public:
    OperatorSymbol()
    {
        add
            ("+", Operator::plus)
            ("-", Operator::minus);
    }
};

class ExpressionParser :
    public qi::grammar<typename std::string::const_iterator, Expression(), qi::space_type>
{
private:
    template<typename T>
    using Rule = qi::rule<typename std::string::const_iterator, T, qi::space_type>;

public:
    ExpressionParser();

private:
    OperatorSymbol m_operator;
    Rule<Operand()> m_operand;
    Rule<RightExpression()> m_right_exp;
    Rule<Expression()> m_bracketed_expression;
    Rule<Expression()> m_expression;
};

ExpressionParser::ExpressionParser() :
    ExpressionParser::base_type(m_expression)
{
    m_operand %= qi::int_ | m_bracketed_expression;
    m_right_exp %= m_operator >> m_operand;
    m_bracketed_expression %= '(' >> m_expression >> ')';
    m_expression %= m_operand >> *m_right_exp;
}

Здесь класс OperatorSymbol описывает правила преобразования символа в элемент перечисления. Подобные классы необходимо наследовать от класса boost::spirit::qi::symbols с указанием в шаблоне типа символа и результирующего типа. Экземпляры наследников класса symbols можно использовать в качестве правила. В данном случае, экземпляр класса OperatorSymbol используется для реализации правила Оператор.
Далее, класс парсера, ExpressionParser, наследуется от класса boost::spirit::qi::grammar. Шаблон этого класса первым параметром принимает тип итератора входящих данных. Второй, третий и четвёртый параметры опциональны, но почти всегда в них нужно передавать сигнатуру создания результирующей структуры данных (обычно это сигнатура конструктора по умолчанию) и тип символов, которые будут пропускаться парсером (обычно это пробелы). Более подробно с параметрами шаблона grammar можно ознакомиться в документации.
Для построения EBNF используются стандартные парсеры для чисел, символов и прочего, коих очень много, поэтому я отсылаю Вас за ними в документацию. В данном примере мы можем видеть использование персера boost::spirit::qi::int_. Необходимо отметить, что некоторые  парсеры, такие как char_ лежат внутри неймспейсов с именем, совпадающим с именем кодировки символов, например boost::spirit::qi::ascii::char_. Кроме стандартных парсеров, можно создавать свои правила, используя класс boost::spirit::qi::rule. Шаблон этого класса совпадает с шаблоном grammar.
Конструктор нашего ExpressionParser должен передать в конструктор базового класса правило, которое будет использовано для разбора всего входящего текста. Это правило должно иметь тип, совпадающий с типом, переданным в шаблон grammar. Базовый конструктор проще всего вызывать через typedef base_type, так как имя базового класса весьма длинное.
EBNF записывается в достаточно простом виде. Естественно, я не буду перечислять здесь все доступные операторы, это займёт много места и времени. Вместо этого снова отсылаю Вас в документацию.

Пришло время применить наш парсер.

std::shared_ptr<Expression> Parser::parse(const std::string & _input)
{
    ExpressionParser parser;
    Expression * expression = new Expression();
    std::shared_ptr<Expression> result(expression);
    if(qi::phrase_parse(_input.begin(), _input.end(), parser, qi::space, *expression))
        return result;
    return nullptr;
}

Есть несколько способов применения парсера, наиболее распространённым из них является вызов функции boost::spirit::qi::phrase_parse. Функция возвращает true, если строка распаршена удачно. Для того, чтобы получить место падения парсера, отсылаю Вас к статье на официальном сайте.

Для тестирования парсера нам понадобится выводить содержимое структур данных в консоль. Для этого реализуем операторы <<.

class DefaultPrintVisitor : public boost::static_visitor<>
{
public:
    explicit DefaultPrintVisitor(std::ostream & _stream) :
        mr_stream(_stream)
    {
    }

    template<typename T>
    void operator ()(const T & _value)
    {
        mr_stream << _value;
    }

private:
    std::ostream & mr_stream;
};

std::ostream & operator << (std::ostream & _stream, const Operator & _operator)
{
    switch(_operator)
    {
    case Operator::plus:
        _stream << "+";
        break;
    case Operator::minus:
        _stream << "-";
        break;
    }
    return _stream;
}

std::ostream & operator << (std::ostream & _stream, const Operand & _operand)
{
    DefaultPrintVisitor visitor(_stream);
    boost::apply_visitor(visitor, _operand);
    return _stream;
}

std::ostream & operator << (std::ostream & _stream, const Expression & _expression)
{
    _stream << '(' << _expression.operand;
    for(const RightExpression & rexp : _expression.right)
        _stream << ' ' << rexp.operator_ << ' ' << rexp.operand;
    _stream << ')';
    return _stream;
}

Для того, чтобы работать с boost::variant библиотекой предлагается использовать паттерн visitor. Для этого Вам нужно унаследовать Ваш Visitor от boost::static_visitor<>, и определить оператор () для каждого из типов, входящих в шаблон boost::variant. Экземпляр этого класса нужно передать функции boost::apply_visitor вместе со ссылкой на экземпляр boost::variant, что и продемонстрировано в operator << для Operand.

Протестируем то, что получилось на нескольких примерах. Уберём в некоторых местах пробелы и наставим побольше скобок.

#include <iostream>
#include "Parser.h"

using namespace Parser;

int main()
{
    const std::string sources[] =  {
        "1",
        "(1)",
        "1 - 2",
        "1 - 2 + 3",
        "1-2+3",
        "(1 + 2)",
        "3 + (1 + 2)",
        "(1 + 2) + 3",
        "(1-2)+3",
        "(1 + 2 + 3) + 4",
        "(1 + 2) + (3 + 4)",
        "(1 + (2 + 3)) + 4 + (5 + 6)",
        "(1 + (2 + 3)) + (4 + 5) + 6",
        "1 + 2 + (3 - 4 + (5 + 6 - (7 - 8 + 9) - 10) - 11 + 12) + 13 + 14"
    };
    for(const std::string & src : sources)
    {
        std::cout << "Parsing string: " << src << ": ";
        std::shared_ptr<Expression> expression = parse(src);
        if(expression)
            std::cout << "succeeded\nResult: " << *expression;
        else
            std::cout << "failed";
        std::cout << std::endl << std::endl;
    }
    return 0;
}

Parsing string: 1: succeeded
Result: (1)

Parsing string: (1): succeeded
Result: ((1))

Parsing string: 1 - 2: succeeded
Result: (1 - 2)

Parsing string: 1 - 2 + 3: succeeded
Result: (1 - 2 + 3)

Parsing string: 1-2+3: succeeded
Result: (1 - 2 + 3)

Parsing string: (1 + 2): succeeded
Result: ((1 + 2))

Parsing string: 3 + (1 + 2): succeeded
Result: (3 + (1 + 2))

Parsing string: (1 + 2) + 3: succeeded
Result: ((1 + 2) + 3)

Parsing string: (1-2)+3: succeeded
Result: ((1 - 2) + 3)

Parsing string: (1 + 2 + 3) + 4: succeeded
Result: ((1 + 2 + 3) + 4)

Parsing string: (1 + 2) + (3 + 4): succeeded
Result: ((1 + 2) + (3 + 4))

Parsing string: (1 + (2 + 3)) + 4 + (5 + 6): succeeded
Result: ((1 + (2 + 3)) + 4 + (5 + 6))

Parsing string: (1 + (2 + 3)) + (4 + 5) + 6: succeeded
Result: ((1 + (2 + 3)) + (4 + 5) + 6)

Parsing string: 1 + 2 + (3 - 4 + (5 + 6 - (7 - 8 + 9) - 10) - 11 + 12) + 13 + 14: succeeded
Result: (1 + 2 + (3 - 4 + (5 + 6 - (7 - 8 + 9) - 10) - 11 + 12) + 13 + 14)

Все исходники примера лежат тут.