Практическое использование Boost.Spirit

    Я заметил, у разработчиков совершенно полярное отношение к библиотеке 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</f:value>
        </f:mul>
        <xpath>
            <concat>
                number(//hello[id='<value-of name="id"/>')
            </f:concat>
            <value-of name="World"/>
        </f:xpath>
    </f: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
    Share post

    Comments 31

      0
      Да, удобная штука.
        0
        В новых версиях boost'a появились boost::qi, boost::karma, boost::lex. Вы что-нибудь из этого пробовали использовать?
          0
          в данному случае как раз используется qi
          qi — это как раз часть нового спирита, на которой парсеры пишутся
          0
          XML-фанатики, которые так и не перешли на JSON :)
            0
            А статья интересная. Будет возможность, попробую :)
              +1
              Кстати предлагаемый сокращенный синтаксис визуально очень похож на YAML (который в свежих инкарнациях совместим с JSON)
                0
                JSON является подмножеством YAML, но с одним важным отличием, в нём нет конечного перевода строки (если не ошибаюсь).

                Использование JSON для любой коммуникации с Javascript более православно, чем использование XML, по множеству причин (более красивый код, меньшее потребление памяти, большая производительность).

                Более того, тенденция к переходу от XML к JSON существует даже в таких системах, где Javascript и не пахнет.
                +1
                а для JSON есть аналог XSLT? я не в плане наехать на JSON, а в познавательном?
              0
              В примере для парсинга число-число ошибка, скобки не совпадают, поправьте плиз
                0
                ага, спасибо
                +4
                Круто, только надо сразу сказать, что чуть более сложный парсер на boost::spirit превращается в кашу, а его компиляция отжирает гигабайты оперативки и может выполняться минутами и десятками минут. Я уж не говорю о километровых выводов ошибок в темплейтах, если что нибудь накосячить или спирит поменяется в следующей версии. Используйте ANTLR или Bison+FLEX и ваши волосы будут мягкими и шелковистыми :)
                  0
                  И все проекты — опенсорсными.
                    0
                    ну я же в начале написал, чтобы не разводить холивар — каждому свое.
                    кому-то нравятся блондинки, другому — рыжие. кому-то большие большие груди, а кому-то сандра баллок :)

                    по теме: сложные парсеры может быть лучше писать на чем-то, отличном от Спирита. но мелкие — самое оно.
                    0
                    да, boost удобен и очень хорош. Не представляю себе жизнь на С++ без boosta. Будет возможность, попробую boost::spirit. Пока довольствовался другими библиотеками: boost::asio (кроссплатформенные сокеты), boost::thread и boost::program_options (для парсинга параметров программы) и многие другие.
                      +1
                      кстати, если уж нужно использовать XML " без скобочек", то лучше уж использовать более стандартный YAML — к нему есть стандартные парсеры.
                        0
                        да и выглядит получше =)
                        +4
                        > Вот например, как вы поступите если нужно распарсить строку вида «число-число», которая задает диапазон страниц для печати?

                        scanf("%d-%d", &a, &b);
                          +1
                          ответ неправильный, так как не учитывает пробелы
                            0
                            Удачи :)
                            Пример из жизни. Проект около 600мб исходников, все id-шники хранятся в int-ах. Выводятся в лог, и при формировании запросов с в 70% случаев с помощью sprintf. Читаются хоть и редко, но с помощью sscanf.
                            У одних из клиентов заканчиваются айдишники. Внезапно… (с запасом пол-года)

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

                            И вот случаи с sprintf и sscanf — отливливались дольше всего…
                            очень редко, но до сих пор qa специалисты ловят коры.
                              0
                              Забыл добавить. Самая большая проблема вашего scanf("%d-%d", &a, &b); — в том что при изменении типа a и b — нужно делать два изменения.
                              Менять тип у переменной, и менять тип во всех использованиях scanf.
                                0
                                Ну так граждане. Надо было изначально завести typedef. А вот с %d хз что делать. наверное только макросом. В таких случаях лучше перейти на с++ с iostream.
                                  0
                                  >> Надо было изначально завести typedef.
                                  ага. тайпдеф был, только лет пять назад, на этом проекте еще не применялось код-ревью и в большинстве мест тайпдеф не ипользовался.

                                  >> А вот с %d хз что делать. наверное только макросом. В таких случаях лучше перейти на с++ с iostream.
                                  Согласен, использую stream-ы.
                                  Я просто немного покритиковал вариант со scanf.
                            +1
                            От обилия всяких @<":>.>>,<<&|{][ рябит в глазах. Я после третьего-четвертого такого символа в строке теряю нить повествования (как, например, после пятой-шестой вложенности цикла или массива). Вы считаете это хорошим стилем программирования? (Я не о стиле автора статьи, а о том, к чему вынуждает spirit).
                              0
                              Вы, видимо, не видели программы на perl :)
                                0
                                это револьвер, детка, револьвер.
                                0
                                Парсер это, конечно, вещь нужная и всё такое, но для xml чем не угодил кошерный tinyxml и биндинги к нему на плюсах?
                                  0
                                  ты имеешь ввиду использовать tinyxml для генерации xml? можно конечно, просто там кода-то на генерацию xml — кот наплакал. что с tinyxml, что без него
                                    0
                                    Да. Не понимаю зачем изобретать велосипед.
                                  –1
                                  господи, какой ужас.
                                    0
                                    Первый пример, число-число, без Boost.Spirit — одна строчка:

                                    bool ok = (std::cin >> res.first) && (std::cin.get() == '-') && (std::cin >> res.second);
                                    

                                    Only users with full accounts can post comments. Log in, please.