Techniques

Boost , ,

Techniques

• Темплатированные функторы
• Правило с несколькими сканерами
• Смотри, никаких правил!
• Тип
• Набиалек трюк

Templatized Functors

Для универсальности часто лучше сделать участника функтора оператором.Шаблон. Таким образом, нам не нужно беспокоиться о типе аргумента, который следует ожидать, пока поведение является уместным. Например, вместо жесткого кодированияchar const*в качестве аргумента родового семантического действия лучше сделать его шаблонной функцией члена. Таким образом, он может принимать любой тип итератора:

    struct my_functor
    {
        template <typename IteratorT>
        void operator()(IteratorT first, IteratorT last) const;
    };

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

Rule With Multiple Scanners

При использовании v1.8.0 можно использовать один или несколько типов сканеров. Например, есть случаи, когда нам нужно правило, которое может работать на уровне фраз и символов. Несоответствие правил/сканеров было источником путаницы и является «нет». 1FAQ. Для решения этой проблемы у нас теперь естьподдержка нескольких сканеров.

Вот пример грамматики с правиломr, которую можно назвать с 3 типами сканеров (уровень фразы, лексема и нижний регистр). См.правило,грамматика,lexeme_scannerикак_lower_scannerдля получения дополнительной информации.

Вот грамматика (см.multiple_scanners.cpp):

    struct my_grammar : grammar<my_grammar>
    {
        template <typename ScannerT>
        struct definition
        {
            definition(my_grammar const& self)
            {
                r = lower_p;
                rr = +(lexeme_d[r] >> as_lower_d[r] >> r);
            }
            typedef scanner_list<
                ScannerT
              , typename lexeme_scanner<ScannerT>::type
              , typename as_lower_scanner<ScannerT>::type
            > scanners;
            rule<scanners> r;
            rule<ScannerT> rr;
            rule<ScannerT> const& start() const { return rr; }
        };
    };

По умолчанию поддержка нескольких сканеров отключена. МакроBOOST_SPIRIT_RULE_SCANNERTYPE_LIMITдолжно быть определено максимальное количество сканеров, разрешенных в списке сканеров. Значение должно быть больше 1 для обеспечения работы нескольких сканеров. В приведенном выше примере для определения предела из трех сканеров списка перед включением заголовков Spirit в исходный файл должна быть вставлена следующая строка:

    #define BOOST_SPIRIT_RULE_SCANNERTYPE_LIMIT 3

Look Ma' No Rules

Ты используешь грамматики и много их используешь? Хотите грамматику без холестерина, супероптимизированную? Читайте в...

У меня отношения любви и ненависти с правилами. Думаю, вы знаете причины. Многие проблемы связаны с ограничением правил. Динамический полиморфизм и статический полиморфизм в C++ плохо сочетаются. В C++ нет понятия виртуальных шаблонных функций, по крайней мере, пока. Таким образом, правилопривязано к определенному типу сканера. Это приводит к таким проблемам, какбизнес сканера, наш No 1 FAQ. Кроме того, виртуальные функции в правилах замедляют разбор, убивают всю метаинформацию и убивают наложение, следовательно, раздувая сгенерированный код, особенно для очень маленьких правил, таких как:

    r = ch_p('x') >> uint_p;

Ограничение правила является основной причиной, по которой грамматика разработана так, как она есть сейчас, с вложенным классом определения шаблона. Ограничение правила также является причиной существования подправил. Действительно ли нам нужны правила? Конечно! До того, как C++ примет некоторый вид дедукции автотипа, такой как предложенный Дэвидом Абрахамсом в clc++m:

    auto r = ...definition ...

Мы привязаны к правилу как держатели RHS. В некоторых случаях мы можем обойтись без правил! Вместо того, чтобы писать:

    rule<> x = ch_p('x');

Лучше написать:

    chlit<> x = ch_p('x');

Это тривиально. Но что, если правило довольно сложное? Хорошо, давайте пошагово... Я изучу простой skip_parser на основе грамматики C от Хартмута Кайзера. В основном грамматика пишется как (см.no_rule1.cpp):

    struct skip_grammar : grammar<skip_grammar>
    {
        template <typename ScannerT>
        struct definition
        {
            definition(skip_grammar const& /*self*/)
            {
                skip
                    =   space_p
                    |   "//" >> *(anychar_p - '\n') >> '\n'
                    |   "/*" >> *(anychar_p - "*/") >> "*/"
                    ;
            }
            rule<ScannerT> skip;
            rule<ScannerT> const&
            start() const { return skip; }
        };
    };

Хорошо, пока так хорошо. Мы можем сделать лучше? Так как там нет рекурсивных правил (на самом деле есть только одно правило), вы можете расширить тип RHS правила как тип правила (см.no_rule2.cpp):

    struct skip_grammar : grammar<skip_grammar>
    {
        template <typename ScannerT>
        struct definition
        {
            definition(skip_grammar const& /*self*/)
            : skip
                (       space_p
                    |   "//" >> *(anychar_p - '\n') >> '\n'
                    |   "/*" >> *(anychar_p - "*/") >> "*/"
                )
            {
            }
            typedef
               alternative<alternative<space_parser, sequence<sequence<
               strlit<const char*>, kleene_star<difference<anychar_parser,
               chlit<char> > > >, chlit<char> > >, sequence<sequence<
               strlit<const char*>, kleene_star<difference<anychar_parser,
               strlit<const char*> > > >, strlit<const char*> > >
            skip_t;
            skip_t skip;
            skip_t const&
            start() const { return skip; }
        };
    };

Ухххх! Как я это сделал? Как мне удалось попасть в сложный типдеф? Я сумасшедший? Ну, на самом деле, нет... есть трюк! То, что вы делаете, это сначала определите typedefskip_tкак int:

    typedef int skip_t;

Попробуйте компилировать. Затем компилятор сгенерирует неприятное сообщение об ошибке, такое как:

    "cannot convert boost::spirit::alternative<... blah blah...to int".

Вот ты и идешь!У тебя такой тип! Я просто копирую и вставляю правильный тип (удаление явных квалификаций).

Мы можем пойти дальше? Да. Помните, что грамматика была разработана для правил. Класс определения вложенного шаблона необходим, чтобы обойти ограничения правила. Без правил я предлагаю новый класс, называемыйsub_grammar, аналог грамматики с низким содержанием жира:

    namespace boost { namespace spirit
    {
        template <typename DerivedT>
        struct sub_grammar : parser<DerivedT>
        {
            typedef sub_grammar self_t;
            typedef DerivedT const& embed_t;
            template <typename ScannerT>
            struct result
            {
                typedef typename parser_result<
                    typename DerivedT::start_t, ScannerT>::type
                type;
            };
            DerivedT const& derived() const
            { return *static_cast<DerivedT const*>(this); }
            template <typename ScannerT>
            typename parser_result<self_t, ScannerT>::type
            parse(ScannerT const& scan) const
            {
                return derived().start.parse(scan);
            }
        };
    }}

С классомsub_grammarмы можем определить нашу грамматику шкипера таким образом (см.no_rule3.cpp):

    struct skip_grammar : sub_grammar<skip_grammar>
    {
        typedef
           alternative<alternative<space_parser, sequence<sequence<
           strlit<const char*>, kleene_star<difference<anychar_parser,
           chlit<char> > > >, chlit<char> > >, sequence<sequence<
           strlit<const char*>, kleene_star<difference<anychar_parser,
           strlit<const char*> > > >, strlit<const char*> > >
        start_t;
        skip_grammar()
        : start
            (
                space_p
            |   "//" >> *(anychar_p - '\n') >> '\n'
            |   "/*" >> *(anychar_p - "*/") >> "*/"
            )
        {}
        start_t start;
    };

Но зачем, спросите вы? Вы можете просто использовать типstart_tвыше as-is. Это уже парсер! Мы можем просто напечатать:

    skipper_t skipper =
        space_p
        |   "//" >> *(anychar_p - '\n') >> '\n'     
        |   "/*" >> *(anychar_p - "*/") >> "*/"
        ;

Щиппер, как и любой парсер? Ну, тонкая разница в том, чтошкипер, используемый таким образом, будет встроенпо значению, когдавы сочиняете более сложные парсеры, используя его. То есть, если мы используемшкиперавнутри другого производства, то вся вещь будет храниться в композите. Тяжело!

ПредлагаемаяподграммаOTOH будет содержать ссылку. Примечание:

    typedef DerivedT const& embed_t;

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

The no-rules result So, how much did we save? On MSVCV7.1, the original code: no_rule1.cpp compiles to 28k. Eliding rules, no_rule2.cpp, we got 24k. Not bad, we shaved off 4k amounting to a 14% reduction. But you'll be in for a surprise. The last version, using the sub-grammar: no_rule3.cpp, compiles to 5.5k! That's a whopping 80% reduction. no_rule1.cpp 28k Стандартное правило и грамматика no_rule2.cpp 24k Стандартная грамматика, нет правил no_rule3.cpp 5.5k sub_grammar, нет правил, нет грамматики

typeof

Некоторые компиляторы уже поддерживаюттипключевого слова. Примерами являются g++ и Metrowerks CodeWarrior. Когда-нибудьтипстанет обычным явлением. Стоит отметить, что мы можем использоватьтипдля определения нерекурсивных правил без использования класса правил. Для примера мы будем использовать пример шкипера выше; на этот раз с использованиемтипа. Во-первых, чтобы избежать избыточности, мы введем макросRULE:

    #define RULE(name, definition) typeof(definition) name = definition

Тогда просто:

    RULE(
        skipper,
        (       space_p
            |   "//" >> *(anychar_p - '\n') >> '\n'
            |   "/*" >> *(anychar_p - "*/") >> "*/"
        )
    );

(см.typeof.cpp)

Вот так! Теперь вы можете использовать шкипера так же, как любой парсер. Следует помнить, однако, чтошкипервыше будет встроен в значение, когдавы сочиняете более сложные парсеры, используя его (см.подграммаобоснование выше). Вы можете использовать классsub_grammar, чтобы избежать этой проблемы.

Nabialek trick

Этот метод, я назову"Набиалек трюк"(от имени его изобретателя, Сэма Набиалека), может улучшить отправку правил от линейного недетерминированного к детерминистическому. Хитрость применима к грамматике, где ключевое слово (оператор и т.д.) предшествует производству. Есть много грамматик, похожих на это:

    r =
            keyword1 >> production1
        |   keyword2 >> production2
        |   keyword3 >> production3
        |   keyword4 >> production4
        |   keyword5 >> production5
        /*** etc ***/
        ;

Каскадные альтернативы проверяются по одному за раз методом проб и ошибок, пока что-то не совпадет. Хитрость Набиалека использует свойства поиска таблицы символовдля оптимизации отправки альтернатив. Например, см.nabialek.cpp. Грамматика работает следующим образом. Есть два правилаодинидва. Когда [[[[]]][[[[[]]]][[[[[]]]]][[[[[[[]]]]]][[[[[[[[[]]]]]]][[[[[[[[[[]]]]]]]][[[[[[[[[[[]]]]]]]]]][[[[[[[[[[[[[]]]]]]]]]][[[[[[[[[[[[[]]]]]]]]]][[[[[[[[[[[[[[]]]]]]]]]]][[[[[[[[[[[[[[]]]]]]]]]]][[[[[[[[[[[[[[[[]]]]]]]]]]]][[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]] Когда [[[[]]][[[[[]]]][[[[[]]]]][[[[[[[]]]]]][[[[[[[[]]]]]]][[[[[[[[[]]]]]]]][[[[[[[[[]]]]]]]][[[[[[[[[[[[]]]]]]]]][[[[[[[[[[[[[]]]]]]]]]][[[[[[[[[[[[]]]]]]]]]][[[[[[[[[[[[]]]]]]]]]]][[[[[[[[[[[[[[]]]]]]]]]]][[[[[[[[[[[[[]]]]]]]]]]][[[[[[[[[]]]]]]]]]][[[[[[[[[[ Вот грамматика:

    one = name;
    two = name >> ',' >> name;
    
    continuations.add
        ("one", &one)
        ("two", &two)
    ;
    
    line = continuations[set_rest<rule_t>(rest)] >> rest;

где продолжения - таблица символовс указателем на слоты rule_t. Один, два, имя, линия и отдых - правила:

    rule_t name;
    rule_t line;
    rule_t rest;
    rule_t one;
    rule_t two;
    
    symbols<rule_t*> continuations;

set_rest, смысловое действие, прилагаемое к продолжениям:

    template <typename Rule>
    struct set_rest
    {
        set_rest(Rule& the_rule)
        : the_rule(the_rule) {}
        void operator()(Rule* newRule) const
        { m_theRule = *newRule; }
        Rule& the_rule;
    };

Обратите внимание, как правило 108устанавливается динамически при вызове действия set_rule. Динамическая грамматика анализирует входы, такие как:

"one only"
"one again"
"two first, second"

Здоровая часть заключается в том, что правилопокояустанавливается (по действиюset_rest) в зависимости от того, что получила таблица символов. Если он получил"один", то отдых = один. Если он получил"два", то отдых = два. Очень изящно! Этот метод должен быть очень быстрым, особенно когда есть много ключевых слов. Было бы неплохо добавить специальные средства, чтобы сделать это простым в использовании. Представляю:

    r = keywords >> rest;

гдеключевых слов- специальный парсер (на основе таблицы символов), который автоматически устанавливает свой RHS (отдых) в зависимости от приобретенного символа. Это, я думаю, очень круто! Возможно, когда-нибудь...

Кроме того, см.переключатель парсерадля другого детерминированного трюка разбора для префиксов символов/токенов.

Copyright © 1998-2003 Joel de Guzman

Use, modification and distribution is subject to the Boost Software License, Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)

Статья Techniques раздела может быть полезна для разработчиков на c++ и boost.

:: Главная :: ::