Trees

Boost , ,

Trees

Why use parse trees

Парсовые деревья представляют собой в памяти представление входа со структурой, которая соответствует грамматике.

Преимущества использования парсовых деревьев вместо семантических действий:

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

Пример

Теперь, когда вы думаете, что хотите использовать деревья, я приведу пример того, как их использовать. Итак, следуя традиции (и остальной документации), мы сделаем калькулятор. Вот грамматика:

    integer 
        =   token_node_d[ (!ch_p('-') >> +digit_p) ]
        ;

    factor
        =   integer
        |   '(' >> expression >> ')'
        |   ('-' >> factor)
        ;

    term
        =   factor 
            >> *(   ('*' >> factor)
                |   ('/' >> factor)
                )
        ;

    expression
        =   term
            >> *(   ('+' >> term)
                |   ('-' >> term)
                )
        ;

Теперь вы заметите, что единственное, что отличается в этой грамматике, это директива token_node_d. Это приводит к тому, что соответствие целого правила оказывается в одном узле. Без token_node_d каждый персонаж получит свой собственный узел. Далее отметим, что token_node_d является неявным lexeme (что означает, что для перехода на анализ уровня символов не требуется lexeme_d). Как вы скоро увидите, легче преобразовать вход в инт, когда все символы находятся в одном узле. Вот как делается анализ для создания дерева:

    tree_parse_info<> info = pt_parse(first, expression);

pt_parse() аналогично parse(). Существует четыре перегрузки: две для пар первого и последнего итераторов и две для струн персонажей. Две функции выполняют парсер шкипера, а две другие — нет.

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

Вот как вы можете использовать дерево для оценки входных данных:

    if (info.full)
    {
        cout << "parsing succeeded\n";
        cout << "result = " << evaluate(info) << "\n\n";
    }

Теперь вы спрашиваете, откуда взялась оценка ? Это часть духа? К сожалению, evaluate() является лишь частью выборки. Вот оно:

    long evaluate(const tree_parse_info<>& info)
    {
        return eval_expression(info.trees.begin());
    }

Таким образом, здесь вы видите, что оценка () просто вызывает eval_expression(), передавая итератор информации. деревья. Вот остальные примеры:

    // Here's some typedefs to simplify things
    typedef char const*                              iterator_t;
    typedef tree_match<iterator_t>                   parse_tree_match_t;
    typedef parse_tree_match_t::const_tree_iterator  iter_t;

    // Here's the function prototypes that we'll use.  One function for each
    // grammar rule.
    long evaluate(const tree_parse_info<>& info);
    long eval_expression(iter_t const& i);
    long eval_term(iter_t const& i);
    long eval_factor(iter_t const& i);
    long eval_integer(iter_t const& i);

    // i should be pointing to a node created by the expression rule
    long eval_expression(iter_t const& i)
    {
        // first child points to a term, so call eval_term on it
        iter_t chi = i->children.begin();
        long lhs = eval_term(chi);
        for (++chi; chi != i->children.end(); ++chi)
        {
            // next node points to the operator.  The text of the operator is
            // stored in value (a vector<char>)
            char op = *(chi->value.begin());
            ++chi;
            long rhs = eval_term(chi);
            if (op == '+')
                lhs += rhs;
            else if (op == '-')
                lhs -= rhs;
            else
                assert(0);
        }
        return lhs;
    }

    long eval_term(iter_t const& i)
    {
        //  ... see parse_tree_calc1.cpp for complete example
        //  (it's rather similar to eval_expression() ) ...
    }

    long eval_factor(iter_t const& i)
    {
        //  ... again, see parse_tree_calc1.cpp if you want all the details ...
    }

    long eval_integer(iter_t const& i)
    {
        // use the range constructor for a string
        string integer(i->value.begin(), i->value.end());
        // convert the string to an integer
        return strtol(integer.c_str(), 0, 10);
    }

Полный исходный код можно посмотреть здесь . Это часть духовного распределения.

Итак, вам нравится то, что вы видите, но, возможно, вы думаете, что дерево анализа слишком сложно обработать? С помощью еще нескольких директив можно сгенерировать абстрактное дерево синтаксиса (ast) и сократить объем кода оценки как минимум на 50%. Итак, без промедления, вот грамматика калькулятора:

    integer
        =   leaf_node_d[ (!ch_p('-') >> +digit_p) ]
        ;

    factor
        =   integer
        |   inner_node_d[ch_p('(') >> expression >> ch_p(')')]
        |   (root_node_d[ch_p('-')] >> factor)
        ;

    term
        =   factor 
            >> *(  (root_node_d[ch_p('*')] >> factor)
                |  (root_node_d[ch_p('/')] >> factor)
                )
        ;

    expression
        =   term
            >> *(  (root_node_d[ch_p('+')] >> term)
                | (root_node_d[ch_p('-')] >> term)
                )
        ;

Отличия от грамматики дерева разбора hi-lighted в bold-red. Директива inner_node_d приводит к тому, что первый и последний узлы, генерируемые прилагаемым парсером, отбрасываются, так как при оценке выражения скобки нас действительно не волнуют. Директива root_node_d является ключом к генерации ast. Узел, генерируемый парсером внутри root_node_d, помечается как корневой узел. Когда создается корневой узел, он становится корневым или родительским узлом других узлов, генерируемых тем же правилом.

Для начала анализа и генерации аста необходимо использовать функции ast_parse, которые аналогичны функциям pt_parse.

    tree_parse_info<> info = ast_parse(first, expression);

Вот функция eval_expression (обратите внимание, что для обработки аста нам нужна только одна функция вместо четырех):

    long eval_expression(iter_t const& i)
    {
        if (i->value.id() == parser_id(&integer))
        {
            // convert string to integer
            string integer(i->value.begin(), i->value.end());
            return strtol(integer.c_str(), 0, 10);
        }
        else if (i->value.id() == parser_id(&factor))
        {
            // factor can only be unary minus
            return - eval_expression(i->children.begin());
        }
        else if (i->value.id() == parser_id(&term))
        {
            if (*i->value.begin() == '*')
            {
                return eval_expression(i->children.begin()) *
                    eval_expression(i->children.begin()+1);
            }
            else if (*i->value.begin() == '/')
            {
                return eval_expression(i->children.begin()) /
                    eval_expression(i->children.begin()+1);
            }
        }
        else if (i->value.id() == parser_id(&expression))
        {
            if (*i->value.begin() == '+')
            {
                return eval_expression(i->children.begin()) +
                    eval_expression(i->children.begin()+1);
            }
            else if (*i->value.begin() == '-')
            {
                return eval_expression(i->children.begin()) -
                    eval_expression(i->children.begin()+1);
            }
        }

        return 0;
    }

Весь рабочий пример - ast_calc.cpp. Надеюсь, этого примера было достаточно, чтобы разжечь аппетит к деревьям. Для более мелких деталей, продолжайте читать остальную часть этой главы.

Usage

pt_parse

Для создания дерева разбора можно назвать одну из пяти свободных функций:

    template <typename FactoryT, typename IteratorT, typename ParserT, typename SkipT>    
    tree_parse_info<IteratorT, FactoryT>    
    pt_parse(        
        IteratorT const&        first_,        
        IteratorT const&        last_,        
        parser<ParserT> const&  parser,        
        SkipT const&            skip_,
        FactoryT const &        factory_ = FactoryT());    
    template <typename IteratorT, typename ParserT, typename SkipT>    
    tree_parse_info<IteratorT>    
    pt_parse(        
        IteratorT const&        first_,        
        IteratorT const&        last_,        
        parser<ParserT> const&  parser,        
        SkipT const&            skip_);    
    template <typename IteratorT, typename ParserT>    
    tree_parse_info<IteratorT>    
    pt_parse(        
        IteratorT const&        first_,        
        IteratorT const&        last_,        
        parser<ParserT> const&  parser);    
    template <typename CharT, typename ParserT, typename SkipT>    
    tree_parse_info<CharT const*>    
    pt_parse(        
        CharT const*            str,        
        parser<ParserT> const&  parser,        
        SkipT const&            skip);    
    template <typename CharT, typename ParserT>    
    tree_parse_info<CharT const*>    
    pt_parse(        
        CharT const*            str,        
        parser<ParserT> const&  parser);

ast_parse

Для создания абстрактного синтаксисного дерева (коротко говоря) вы называете одну из пяти свободных функций:

    template <typename FactoryT, typename IteratorT, typename ParserT, typename SkipT>    
    tree_parse_info<IteratorT, FactoryT>    
    ast_parse(        
        IteratorT const&        first_,        
        IteratorT const&        last_,        
        parser<ParserT> const&  parser,        
        SkipT const&            skip_,
        FactoryT const &        factory_ = FactoryT());    
    template <typename IteratorT, typename ParserT, typename SkipT>    
    tree_parse_info<IteratorT>    
    ast_parse(        
        IteratorT const&        first_,        
        IteratorT const&        last_,        
        parser<ParserT> const&  parser,        
        SkipT const&            skip_);    
    template <typename IteratorT, typename ParserT>    
    tree_parse_info<IteratorT>    
    ast_parse(        
        IteratorT const&        first_,        
        IteratorT const&        last,        
        parser<ParserT> const&  parser);    
    template <typename CharT, typename ParserT, typename SkipT>    
    tree_parse_info<CharT const*>    
    ast_parse(        
        CharT const*            str,        
        parser<ParserT> const&  parser,        
        SkipT const&            skip);    
    template <typename CharT, typename ParserT>    
    tree_parse_info<CharT const*>    
    ast_parse(        
        CharT const*            str,        
        parser<ParserT> const&  parser);

tree_parse_info

Структура tree_parse_info, возвращенная из pt_parse и ast_parse, содержит информацию о парсе:

    template <typename IteratorT = char const*>
    struct tree_parse_info
    {
        IteratorT   stop;
        bool        match;
        bool        full;
        std::size_t length;

        typename tree_match<IteratorT>::container_t trees;
    };

tree_match

Когда Дух генерирует дерево, функция члена парсера parse() возвращает объект, соответствующий дереву, вместо объекта соответствия. Tree_match имеет три параметра шаблона. Первый тип итератора по умолчанию char const*. Второй — это фабрика узлов, которая по умолчанию выполняет функцию node_val_data_factory. Третий — тип атрибута, хранящийся в матче. Дерево_матч имеет переменную члена, которая представляет собой контейнер (a std::vector) из tree_node объектов, называемых деревьями. По соображениям эффективности, когда дерево_матч копируется, деревья не копируются, они перемещаются на новый объект, а исходный объект остается с пустым контейнером дерева. tree_match поддерживает тот же интерфейс, что и класс матчей: он имеет оператор bool(), поэтому вы можете протестировать его для успешного матча: if(matched), и вы можете запросить длину матча через функцию long(). Класс имеет такой интерфейс:

    template <typename IteratorT = char const*, typename NodeFactoryT = node_val_data_factory<> >
    struct tree_match
    {
        typedef typename NodeFactoryT::template factory<IteratorT> node_factory_t;
        typedef typename node_factory_t::node_t                    parse_node_t;
        typedef          tree_node<parse_node_t>                   node_t;
        typedef typename node_t::children_t                        container_t;
        typedef typename container_t::iterator                     tree_iterator;
        typedef typename container_t::const_iterator               const_tree_iterator;

        tree_match();
        tree_match(std::size_t length, parse_node_t const& n);
        tree_match(tree_match const& x);
        explicit tree_match(match const& x);
        tree_match& operator=(tree_match const& x);
        void swap(tree_match& x);
        operator bool() const;
        int length() const;

        container_t trees;
    };

Когда анализ успешно завершен, элемент данных деревьев будет содержать корневой узел дерева.

vector? You may wonder, why is it a vector then? The answer is that it is partly for implementation purposes, and also if you do not use any rules in your grammar, then trees will contain a sequence of nodes that will not have any children.

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

    tree_match<> hit = expression.parse(tree_scanner);

    if (hit)
        process_tree_root(hit.trees[0]); // do something with the tree

tree_node

Как только вы создали дерево, позвонив pt_parse или ast_parse, у вас есть tree_parse_info, который содержит корневой узел дерева, и теперь вам нужно что-то сделать с деревом. Деревья данных tree_parse_info представляют собой std::vector. tree_node - структура дерева. Класс имеет один параметр шаблона под названием T. tree_node содержит экземпляр типа T. Он также содержит std::vector > которые являются детьми узла. Класс выглядит так:

    template <typename T>
    struct tree_node
    {
        typedef T parse_node_t;
        typedef std::vector<tree_node<T> > children_t;
        typedef typename children_t::iterator tree_iterator;
        typedef typename children_t::const_iterator const_tree_iterator;

        T value;
        children_t children;

        tree_node();
        explicit tree_node(T const& v);
        tree_node(T const& v, children_t const& c);
        void swap(tree_node<T>& x);
    };

Этот класс просто используется для отделения структуры дерева от данных, хранящихся в дереве. Это общий узел, и любой тип может храниться внутри него и передаваться через значение члена данных. Тип по умолчанию для T - node_val_data.

node_val_data

Класс node_val_data содержит фактическую информацию о каждом узле. Это включает в себя последовательность текста или токена, которая была проанализирована, id, которая указывает, какое правило создало узел, булев флаг, который указывает, был ли узел помечен как корневой узел, и необязательное значение, указанное пользователем. Это и есть интерфейс:

    template <typename IteratorT = char const*, typename ValueT = nil_t>
    struct node_val_data
    {
        typedef typename std::iterator_traits<IteratorT>::value_type value_type;
        typedef std::vector<value_type> container_t;
        typedef typename container_t::iterator iterator_t;
        typedef typename container_t::const_iterator const_iterator_t;

        node_val_data();
        node_val_data(IteratorT const& _first, IteratorT const& _last);
        template <typename IteratorT2>
        node_val_data(IteratorT2 const& _first, IteratorT2 const& _last);
        void swap(node_val_data& x);

        container_t::iterator begin();
        container_t::const_iterator begin() const;
        container_t::iterator end();
        container_t::const_iterator end() const;

        bool is_root() const;
        void is_root(bool b);

        parser_id id() const;
        void id(parser_id r);

        ValueT const& value() const;
        void value(ValueT const& v);
    };

parser_id, checking and setting

Если узел генерируется правилом, он будет иметь набор id. Каждое правило имеет идентификатор, который он устанавливает все узлы, генерируемые этим правилом. id имеет тип parser_id. Ид по умолчанию каждого правила устанавливается на адрес этого правила (преобразуется в целое число). Это не всегда удобно, так как код, обрабатывающий дерево, может не иметь доступа к правилам, а может и не иметь возможности сравнивать адреса. Таким образом, вы можете переопределить идентификатор по умолчанию, используемый каждым правилом, , предоставив ему конкретный идентификатор . Затем при обработке дерева можно вызвать node_val_data::id(), чтобы увидеть, какое правило создал этот узел.

structure/layout of a parse tree

parse tree layout

Дерево организовано по правилам. Каждое правило создает новый уровень в дереве. Все парсеры, прикрепленные к правилу, создают узел, когда производится успешный матч. Эти узлы становятся детьми узла, созданного правилом. Итак, следующий код:

    rule_t myrule = ch_p('a') >> ',' >> *ch_p('b');
    char const* input = "a,bb";
    scanner_t scanner(input, input + strlen(input));
    tree_match<> m = myrule.parse(scanner);

При выполнении код возвращает дерево_match, m. m.trees[0] будет содержать такое дерево:

Корневой узел не будет содержать никакого текста, и его идентификатор будет установлен на адрес myrule. У него будет четверо детей. Идентификатор каждого ребенка будет установлен по адресу myrule, будет содержать текст, как показано на диаграмме, и не будет иметь детей.

ast layout

При вызове ast_parse дерево генерируется по-разному. В основном он работает так же, как при создании дерева. Разница возникает, когда правило генерирует только один подузел. Вместо создания нового уровня ast_parse не будет создавать новый уровень, он просто покинет существующий узел. Итак, этот код:

    rule_t myrule = ch_p('a');
    char const* input = "a";
    ast_scanner_t scanner(input, input+strlen(input));
    tree_match<> m = myrule.parse(scanner);

он будет генерировать один узел, содержащий «a». Если бы вместо tree_match_policy использовали ast_match_policy, дерево выглядело бы так:

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

switching: gen_pt_node_d[] & gen_ast_node_d[]

Если вы хотите смешать и сопоставить поведение дерева разбора и аста в вашем приложении, вы можете использовать директивы gen_pt_node_d[] и gen_ast_node_d[]. При прохождении разбора по директиве gen_pt_node_d включается поведение создания дерева разбора. Когда используется директива gen_ast_node_d, замкнутый парсер генерирует дерево, используя поведение аста. Обратите внимание на то, как объявляются ваши правила, если вы используете правило в этих директивах. Политика соответствия сканера должна соответствовать желаемому поведению. Если вы избегаете правил и используете примитивные парсеры или грамматики, у вас не будет проблем.

Directives

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

no_node_d

Эта директива аналогична gen_pt_node_d и gen_ast_node_d, что изменяет политику соответствия сканера, используемую прилагаемым парсером. Как следует из названия, он не генерирует деревья, он полностью выключает их. Это полезно, если есть части вашей грамматики, которые не нужны в дереве. Например: ключевые слова, операторы (*, -, && и т.д.) Устраняя их из дерева, можно уменьшить использование памяти и время разбора. Эта директива имеет те же требования в отношении правил, что и gen_pt_node_d и gen_ast_node_d. См. пример файла xml_grammar.hpp (в libs/spirit/example/application/xml каталоге), например использование no_node_d[].

discard_node_d

Эта директива имеет аналогичную цель с no_node_d, но работает иначе. Он не переключает политику соответствия сканера, поэтому закрытый парсер по-прежнему генерирует узлы. Созданные узлы отбрасываются и не появляются в дереве. Использование discard_node_d медленнее, чем no_node_d, но оно не страдает от недостатка необходимости указывать другой тип правила для любого правила внутри него.

leaf_node_d/token_node_d

Оба leaf_node_t и token_node_d работают одинаково. Они создают единый узел для матча, генерируемого закрытым парсером. В отличие от предыдущих версий Spirit, эта директива является неявной лексемой и изменяет сканер (см. Scanner Business).

reduced_node_d

Эта директива объединяет все узлы, генерируемые закрытым парсером. Для более ранних версий Spirit leaf_node_d и token_node_d были реализованы таким образом. Новая реализация этих директив намного быстрее, поэтому reduced_node_d в первую очередь предусмотрена для переносимости и может быть полезна при использовании фабрики пользовательских узлов.

infix_node_d

Это полезно для удаления разделителей из списков. Он отбрасывает все узлы в четных положениях. Таким образом, это правило:

    rule_t intlist = infix_node_d[ integer >> *(',' >> integer) ];

отбросит все узлы запятой и сохранит все целые узлы.

discard_first_node_d

Это отбрасывает первый сгенерированный узел.

discard_last_node_d

Это отбрасывает последний созданный узел.

inner_node_d

Это отбрасывает первый и последний созданный узел.

root_node_d and ast generation

Директива root_node_d используется для поддержки генерации аста. Это не имеет никакого эффекта при создании дерева. Когда парсер заключен в root_node_d, генерируемый им узел помечается как корень. Это влияет на то, как он обрабатывается, когда он добавляется в список генерируемых узлов. Вот пример:

    rule_t add = integer >> *(root_node_d[ ch_p('+') ] >> integer);

При разборе 5+6 образуется следующее дерево:

При разборе 1+2+3 будет генерироваться следующее:

При создании нового узла для определения того, как будет генерироваться дерево, используются следующие правила:

    Let a be the previously generated node. 
    Let b be the new node.

    If b is a root node then

        b's children become a + b's previous children. 
        a is the new first child of b.

    else if a is a root node and b is not, then

        b becomes the last child of a.

    else

        a and b become siblings.

После разбора покидает текущее правило, флаг корневого узла на верхнем узле выключается. Это означает, что директива root_node_d влияет только на текущее правило.

Пример ast_calc.cpp демонстрирует использование root_node_d и ast_parse. Полный исходный код можно посмотреть здесь . Это часть духовного распределения.

parse_tree_iterator

Класс parse_tree_iterator позволяет сортировать дерево по духу. Класс повторяется над токенами в листовых узлах в том же порядке, в котором они были созданы. parse_tree_iterator шаблонизирован на ParseTreeMatchT. Он построен с контейнером из деревьев и возможностью запуска. Вот пример использования:

    rule_t myrule = ch_p('a');
    char const* input = "a";

    // generate parse tree
    tree_parse_info<> i = pt_parse(input, myrule);

    typedef parse_tree_iterator<tree_match<> > parse_tree_iterator_t;

    // create a first and last iterator to work off the tree
    parse_tree_iterator_t first(i.trees, i.trees.begin());
    parse_tree_iterator_t last;

    // parse the tree
    rule<parse_tree_iterator_t> tree_parser =...
    tree_parser.parse(first, last);

advanced tree generation

node value

node_val_data может содержать значение. По умолчанию он содержит void_t, который является пустым классом. Вы можете указать тип, используя параметр шаблона, который затем будет храниться в каждом узле. Тип должен быть по умолчанию конструируемым и присваиваемым. Вы можете получить и установить значение, используя

    ValueT node_val_data::value;

и

    void node_val_data::value(Value const& value);

Чтобы указать тип значения, вы должны использовать другую фабрику node_val_data , чем по умолчанию. Следующий пример показывает, как модифицировать фабрику для хранения и извлечения двойника внутри каждого node_val_data.

 typedef node_val_data_factory<> factory_t;
 my_grammar gram;
 my_skip_grammar skip;
iterator_tfactory_tast_parsefactory_t

access_node_d

Теперь вы можете задаться вопросом: «Что хорошего в том, чтобы иметь значение, которое я могу хранить в каждом узле, но не иметь никакого способа его настройки?» Для этого и существует access_node_d. access_node_d является директивой. Это позволяет прикрепить к нему действие, например:

    access_node_d[...some parsers...][my_action()]

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

Tree node factories

Установив завод, вы можете контролировать, какие типы узлов создаются и как они создаются. Существует 3 предопределенных фабрики: node_val_data_factory, node_all_val_data_factory и node_iter_data_factory. Вы также можете создать свою собственную фабрику для поддержки своих типов узлов.

Использование фабрик с грамматикой довольно просто, вам просто нужно указать тип фабрики как явный параметр шаблона для бесплатной функции ast_parse:

    typedef node_iter_data_factory<int> factory_t;
    my_grammar gram;
    my_skip_grammar skip;
    tree_parse_info<iterator_t, factory_t> i = 
        ast_parse<factory_t>(first, last, gram, skip);

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

    typedef spirit::void_t value_t;
    typedef node_val_data_factory<value_t> factory_t;
    typedef tree_match<iterator_t, factory_t> match_t;
    typedef ast_match_policy<iterator_t, factory_t> match_policy_t;
    typedef scanner<iterator_t, scanner_policies<iter_policy_t, match_policy_t> > scanner_t;
    typedef rule<scanner_t> rule_t;

    rule_t r =...;

    scanner_t scan = scanner_t(first, last);
    match_t hit = r.parse(scan);

node_val_data_factory

Это завод по умолчанию. Он создает узлы node_val_data. Узлы листьев содержат копию согласованного текста, а промежуточные узлы — нет. node_val_data_factory имеет один параметр шаблона: ValueT. ValueT определяет тип значения, которое будет храниться в node_val_data.

node_all_val_data_factory

Эта фабрика также создает node_val_data. Разница между ним и node_val_data_factory в том, что каждый узел содержит весь текст, который его охватывает. Это означает, что корневой узел будет содержать копию всей парсируемой входной последовательности. node_all_val_data_factory имеет один параметр шаблона: ValueT. ValueT определяет тип значения, которое будет храниться в node_val_data.

node_iter_data_factory

Эта фабрика создает parse_tree_iter_node. Этот узел хранит итераторы во входной последовательности вместо создания копии. Он может использовать гораздо меньше памяти. Однако входная последовательность должна оставаться действительной для срока службы дерева, и не рекомендуется использовать итератор multi_pass с этим типом узла. Все уровни дерева будут содержать итератор начала и конца. node_iter_data_factory имеет один параметр шаблона: ValueT. ValueT определяет тип значения, которое будет храниться в узле_val_data.

custom

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

    class my_factory
    {
    public:

        // This inner class is so that the factory can simulate
        // a template template parameter

        template <typename IteratorT>
        class factory
        {
        public:

            // This is your node type
            typedef my_node_type node_t;

            static node_t create_node(
                IteratorT const& first, IteratorT const& last, bool is_leaf_node)
            {
                // create a node and return it.
            }

            // This function is used by the reduced_node directive.
            // If you don't use it, then you can leave this function
            // unimplemented.

            template <typename ContainerT>
            static node_t group_nodes(ContainerT const& nodes)
            {
                // Group all the nodes into one and return it.
            }
        };
    };


    // Typedefs to use my_factory
    typedef my_factory factory_t;
    typedef tree_match<iterator_t, factory_t> match_t;
    typedef tree_match_policy<iterator_t, factory_t> match_policy_t;

    // Typedefs if you are using rules instead of grammars
    typedef scanner<iterator_t, scanner_policies<iter_policy_t, match_policy_t> > scanner_t;
    typedef rule<scanner_t> rule_t;

Copyright © 2001-2002 Daniel C. Nuffer
Revised 2007 Copyright © Tobias Schwinger

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)

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

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