Boost.Spirit in practice

Я заметил, у разработчиков совершенно полярное отношение к библиотеке Boost.Spirit: либо она им жутко не нравится, либо они фанатеют от нее. Конечно, описывать грамматику на C++ – занятие на любителя. Таким любителем оказался и я, когда познакомился со Спиритом. Хочу показать, как с помощью Спирита можно довольно просто решать повседневные задачи разбора текста.

Простая задача – как два пальца

На Спирите очень удобно писать маленькие парсеры «не отходя от кассы» – прямо в C++ коде. Вот например, как вы поступите если нужно распарсить строку вида «число-число», которая задает диапазон страниц для печати? На Спирите – одна строчка:

bool ok = parse(First, Last, (uint_ >> L".." >> uint_), MinMax) && (First == Last));

Посложнее…

Более того – можно ненамного сложнее создавать и парсеры побольше. В качестве примера рассмотрю парсер мини-языка, который я делал для API Яндекс.Бара. Задача была такова: для облегчения загрузки плагинов в баре используется XML, который довольно избыточный сам по себе. Но зато XML легче грузить из JavaScript-а, чем парсить произвольный формат (на JS пишутся расширения под FireFox, в том числе и Я.Бар).

Итак, что мне было нужно – имея на входе обычную инфиксную нотацию:

Hello * Interval * 60 + xpath("number(//hello[id='" # id # "')", World)

получить на выходе обычное AST в XML-формате:

<add>
    <mul>
        <value-of name="Hello"/>
        <value-of name="Interval"/>
        <value type="number">60</value>
    </mul>
    <xpath>
        <concat>
            number(//hello[id='<value-of name="id"/>')
        </concat>
        <value-of name="World"/>
    </xpath>
</add>

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

root
    child1: текст
        @attribute1: text
        @attribute2 = формула
        grandchild
            grand-grand-child
    child2 = формула

То есть вложенность задается количеством табуляций, далее идет имя XML-ноды (элемента или атрибута). За ним - определенный символ, определяющий что идет далее: текст или формула. Текст нужно передавать на выход в «голом» виде, формулы – в виде AST.

Итого у меня два парсера – один разбирает строку чтобы получить имя ноды и текст или формулу. Второй – разбирает формулы, генерируя AST. Обработку количества табов я провожу снаружи старым добрым std::find_if.

Парсинг строки. Semantic actions – через Boost.Bind

Начну с более простого – разбора строк. Строки могут быть такие:

tag
tag: тест
tag = формула
= формула
name :: (instance|widget) (setting|variable)
name := формула

Парсер получается очень простой:

bool parse_definition(string::const_iterator &iter, string::const_iterator end, mini_xml &root)
{
    qi::rule<string::const_iterator, string(), space_type> id, any_string, scope, type;
    id %= raw[lexeme[-char_('@') >> alpha >> *(alnum | '_' | '-' | (':' >> alnum))]];
    any_string %= lexeme[+char_];
    scope %= raw[lit("widget") | lit("instance")];
    type %= raw[lit("setting") | lit("variable")];

    return phrase_parse(iter, end,
        (
            (id >> "::" >> scope >> type) [bind(&add_identifier, ref(root), _1)] |
            (id >> ":=" >> any_string) [bind(&add_definition, ref(root), _1)] |
            (id >> ':'  >> any_string) [bind(&add_raw, ref(root), _1)] |
            (id >> '='  >> any_string) [bind(&add_calculated, ref(root), _1)] |
            (      '='  >> any_string) [bind(&add_expression, ref(root), _1)] |
            id [bind(&add_subnode, ref(root), _1)]
        ),
        space) && (iter == end);
}

Использование phrase_parse() вместо parse() позволило мне переложить на Спирит обработку white space (пробелов, табуляций и т.п.) внутри выражений. Это позволит писать как «tag:text», так и «tag : text». Причем мой код, как видно, освобожден от обработки пробелов – все делает phrase_parse(). Мне остается только использовать lexeme[] там, где я хочу отключить такое поведение, и raw[] там, где я хочу получить исходный текст без вырезания пробелов.

Кстати, напомню что синтаксис правил у Spirit-а такой:

rule [semantic_action]

То есть после каждого правила можно в квадратных скобках задать действие, которое будет выполняться, если правило «сработало».

В моем случае на каждый тип строки – свое поведение, плюс в самом начале для упрощения последующего кода я ввел отдельные правила типа id, any_string. Код, вызываемый при соответствии строки определенному правилу – указан через лямбда-функции, создаваемые с помощью boost::bind. Синтаксис bind-а очень прост:

boost::bind(функция, аргумент, аргумент, ...)

В качестве аргументов можно указывать специальные placeholder-ы (вида _1, _2, …), указывающие куда вставлять аргументы лямбда-функции. На выходе каждого парсера получается одно значение, его и передаем в качестве аргумента нашей функции. Например, парсер

id >> '=' >> any_string

сгенерирует на выходе пару строк (в виде boost::fusion::vector<string, string>), которую я передаю в качестве второго параметра моей функции add_calculated, которая имеет такой вот интерфейс:

void add_calculated(mini_xml &root, fusion::vector<string, string> const &);

Первый параметр, который мне нужно передать этой функции – это ссылка на root, поэтому вызов boost::bind выглядит так:

bind(&add_calculated, ref(root), _1)

Суммируя вместе правило и семантическое действие:

(id >> '=' >> any_string) [bind(&add_calculated, ref(root), _1)]

Парсинг формулы. Semantic actions – через Boost.Phoenix

Напомню какого вида функции мне нуно парсить:

Hello * Interval * 60 + xpath("number(//hello[id='" # id # "')", World)

При разборе формул могут встретиться:

• числа
• булевы константы (true, false)
• строки (в кавычках)
• идентификаторы
• вызовы функций
• операции

Для обработки результатов парсинга я создал один большой функтор и во всех семантических действиях использую его с помощью Booost.Phoenix. Как и у всех функторов, действия различаются не по именам, а по количеству и типам параметров.

struct compiler
{
    // метки нужны для того, чтобы отличать друг от друга функции с одинаковыми аргументами
    struct identifier{}; // метка «идентификатор»
    struct function{}; // метка «функция»
    struct parameter{}; // метка «параметр»
    struct assignment{}; // метка «присваивание»

    void operator()(mini_xml &node, std::string const &id, identifier) const; // идентификатор
    void operator()(mini_xml &node, std::string const &id, function) const; // функция
    void operator()(mini_xml &node, std::string const &id, parameter) const; // параметр функции
    void operator()(mini_xml &node, std::string const &id, assignment) const; // присваивание
    void operator()(mini_xml &node, std::string const &value, char const *type) const; // <value>
    void operator()(mini_xml &node, mini_xml const &subnode) const;
    void operator()(mini_xml &node, mini_xml const &subnode, std::string const &id, bool allow_join = false) const;
};

Внутри своей грамматики я добавил член класса - тот самый мой функтор:

template <typename Iterator>
struct expression_grammar : grammar<Iterator, mini_xml(), space_type>
{
    expression_grammar() : expression_grammar::base_type(expressions)
    {
         expressions = ...;
    }

    rule<Iterator, mini_xml(), space_type> expressions, ...;
    boost::phoenix::function<compiler> op;
}

PS. Тип mini_xml – это генерируемый XML.

Правила для парсинга идентификаторов, строк, чисел и булевых констант очень просты:

id %= raw[lexeme[alpha >> *(alnum | '_' | ('-' >> alnum))]];
quoted_string %= lexeme['"' >> *(char_ - '"') >> '"'];
numeric_value %= raw[lexeme[-(char_('+') | char_('-')) >> +digit >> -(char_('.') >> +digit)]];
boolean_value %= raw[lit("true") | lit("false")];

Все эти правила на выходе выдают строку (например, название идентификатора). Оператор %= в конструкции “правило %= парсер” позволяет сгенерированное парсером значение передать прямо на выход парсера. Далее можно прямо в других правилах использовать их результаты:

string = quoted_string [op(_val, _1, "string")];
number = numeric_value [op(_val, _1, "number")];
boolean = boolean_value [op(_val, _1, "bool")];
empty = lit("empty") [op(_val, std::string(), "empty")];
identifier = id [op(_val, _1, compiler::identifier())];

Как видно, здесь в каждом случае вызывается парсер, например, quoted_string, а далее его значение используется для вызова функтора op. В первом случае (правило string) на вход функтора придет: в качестве первого аргумента – то значение, которое формируется (в моем случае – элемент дерева XML), в качестве второго – результат работы парсера quoted_string, в третьем – срока “string”. И уже функтор сделает все необходимые действия с XML-деревом.

Определение функции не намного сложнее – в частности брагодаря тому, что я генерирую XML. Параметры функции достаточно просто «прикрепить» к xml-узлу функции в качестве «детей»:

function =
    id [op(_val, _1, compiler::function())]
    >> '('
    >> -(parameter [op(_val, _1)] % ',')
    >> ')';

Выражение «parameter [op(_val, _1)]» как раз прикрепляет детей к функции: в функтор op передается родитель (узел функции, который только что заполнен с помощью «op(_val, _1, compiler::function())») и «ребенок» (узел параметра, который сгенерировал парсер parameter).

Итого, без учета бинарных и тернарных операций (операций с 2 и 3 аргументами, такие как */+-?:) получается следующее правило:

factor =
     function [_val = _1]
     | boolean [_val = _1]
     | empty [_val = _1]
     | identifier [_val = _1]
     | string [_val = _1]
     | number [_val = _1]
     | ('(' >> expression [_val = _1] >> ')')
     | (lit('!') [op(_val, "not", compiler::function())] >> factor [op(_val, _1)])
     | (lit('-') [op(_val, "neg", compiler::function())] >> factor [op(_val, _1)])
     | ('+' >> factor [_val = _1])
     ;

При обработке операций не следует забывать об их приоритете. Его легко реализовать «вкладывая» определения одной операции в определение другой:

addition =
    multiplication [_val = _1]
    >> *( ('+' >> multiplication [op(_val, _1, "add", true)])
        | ('-' >> multiplication [op(_val, _1, "sub", true)])
        )
    ;

multiplication =
    factor [_val = _1]
    >> *( ('*' >> factor [op(_val, _1, "mul", true)])
        | ('/' >> factor [op(_val, _1, "div", true)])
        )
    ;

В данном случае функции умножения и деления распарсятся раньше, чем сложение и вычитание, так как умножение «вложено» в сложение. Это произойдет потому, что для сложения нужно разобрать сначала все внутренние правила, в том числе умножение, которое я вложил внутрь. Собственно, что и требовалось.

Суммируя все вместе

Весь исходный код можно взять здесь: http://download.yandex.ru/bar/tools/easierxb-src.zip (внутри архива – проект для сборки под Windows и MacOS).

Пример входного файла: http://download.yandex.ru/bar/tools/easierxb-example.zip