The multi_pass

Boost , ,

The multi_pass

Отслеживание в духе требует использования следующих типов итератора: прямой, двунаправленный или случайный доступ. Из-за обратного отслеживания итераторы ввода не могут использоваться. Поэтому стандартные библиотечные классы istreambuf_iterator и istream_iterator, подпадающие под категорию итераторов ввода, использовать нельзя. Другой интересующий итератор ввода - это тот, который обертывает лексер, такой как LEX.

Input Iterators In general, Spirit is a backtracking parser. This is not an absolute requirement though. In the future, we shall see more deterministic parsers that require no more than 1 character (token) of lookahead. Such parsers allow us to use input iterators such as the istream_iterator as is.

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

Многопропускной итератор преобразует любой входной итератор в передний итератор, подходящий для использования с Spirit. Multi_pass буферизирует данные при необходимости и отбрасывает буфер, когда существует только одна копия итератора.

Грамматика должна быть разработана с осторожностью, если используется итератор multi_pass. Любое правило, которое, возможно, потребуется отменить, например, правило, содержащее альтернативу, приведет к буферизации данных. Оптимальными для использования являются последовательность и повторение. Последовательности формыa >>bне будут буферизировать данные вообще. Любое повторяющееся правило, такое как kleene_star (*a) или положительное, такое как+a), будет только буферизировать данные для текущего повторения.

В типичных грамматиках двусмысленность и, следовательно, внешний вид часто локализованы. На самом деле, многие хорошо разработанные языки полностью детерминированы и не требуют никакого внимания. Заглядывая на первый символ с входа, сразу определится альтернативная ветвь, которую нужно взять. Тем не менее, даже при весьма неоднозначных грамматиках альтернативы часто имеют форму* (a | b | c | d). Входной итератор движется дальше и никогда не застревает в начале. Рассмотрим, например, фрагмент Паскаля:

    program =
        programHeading >> block >> '.'
        ;

    block =
       *(    labelDeclarationPart
        |    constantDefinitionPart
        |    typeDefinitionPart
        |    variableDeclarationPart
        |    procedureAndFunctionDeclarationPart
        )
        >>   statementPart
        ;

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

Будьте внимательны, если вы используете функции бесплатного анализа. Все они делают копию переданного им итератора.

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

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

    #include <boost/spirit/core.hpp>    
    #include <boost/spirit/iterator/multi_pass.hpp>
    using namespace boost::spirit;
    using namespace std;
    
    ifstream in("input_file.txt"); // we get our input from this file

    typedef char char_type;
    typedef multi_pass<istreambuf_iterator<char_type> > iterator_type;
    typedef skip_parser_iteration_policy<space_parser> iter_policy_type;
    typedef scanner_policies<iter_policy_type> scanner_policies_type;
    typedef scanner<iterator_type, scanner_policies_type> scanner_type;
    typedef rule<scanner_type> rule_type;
    iter_policy_type iter_policy(space_p);
    scanner_policies_type policies(iter_policy);
    iterator_type first(
        make_multi_pass(std::istreambuf_iterator<char_type>(in)));
    scanner_type scan(
        first, make_multi_pass(std::istreambuf_iterator<char_type>()),
        policies);

    rule_type   n_list = real_p >> *(',' >> real_p);
    match<>     m = n_list.parse(scan);

flush_multi_pass

Существует предопределенный псевдопарсер под названием flush_multi_pass. Когда этот парсер используется с multi_pass, он будет называться multi_pass::clear_queue(). Это приведет к удалению любых буферных данных. Это также сделает недействительными все другие копии multi_pass, и они не должны использоваться. Если это так, то будет добавлено дополнение::illegal_backtracking.

multi_pass Policies

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

Класс multi_pass имеет пять параметров шаблона:

• InputT - тип multi_pass, используемый для получения входных данных. Обычно это итератор ввода или функтор.
• InputPolicy - класс, который определяет, как multi_pass получает свой вход. Вводная политика параметризируется InputT.
• Политика владения — эта политика определяет, как multi_pass работает с общими компонентами.
• Проверка полиции - Эта политика определяет, как проводится проверка на недействительные итераторы.
• Схема буферизации, используемая multi_pass, определяется и управляется StoragePolicy.

Predefined policies

Все предопределенные политики multi_pass находятся в пространстве имен boost::spirit::multi_pass_policies.

Predefined InputPolicy classes

input_iterator

Эта политика направляет multi_pass на чтение с итератора ввода типа InputT.

lex_input

Эта политика получает свой вход, вызывая yylex(), который обычно предоставляется сканером, созданным LEX. Если вы используете эту политику, ваш код должен ссылаться на сканер, созданный LEX.

functor_input

Эта политика ввода получает данные, вызывая функтор типа InputT. Функтор должен соответствовать определенным требованиям. Он должен иметь типдеф, называемый result_type, который должен быть типом, возвращенным от оператора(). Кроме того, поскольку политика ввода требует способа определения того, когда был достигнут конец ввода, функтор должен содержать статическую переменную, называемую eof, которая сопоставима с переменной типа результата.

Predefined OwnershipPolicy classes

ref_counted

Этот класс использует схему подсчета ссылок. Multi_pass удалит общие компоненты, когда счет достигнет нуля.

first_owner

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

Predefined CheckingPolicy classes

no_check

Эта политика вообще не проверяется.

buf_id_check

buf_id_check имеет буферный идентификатор или буферный возраст. Каждый раз, когда в мультипассивном итераторе вызывается Clear_queue(), возможно, что все другие итераторы становятся недействительными. Когда называется clear_queue(), buf_id_check увеличивает буферный идентификатор. Когда итератор отменяется, эта политика проверяет, что буферный идентификатор итератора соответствует общему буферному идентификатору. Эта политика наиболее эффективна при использовании вместе с Std_deque StoragePolicy. Он не должен использоваться с фиксированной_size_queue StoragePolicy, потому что он не будет обнаруживать отклонения итератора, которые находятся вне диапазона.

full_check

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

Predefined StoragePolicy classes

std_deque

Эта политика хранит все буферизованные данные в std::deque. Все данные хранятся до тех пор, пока существует более одного итератора. Как только счетчик итератора опускается до одного, и очередь больше не нужна, он очищается, освобождая память. Очередь также может быть принудительно очищена путем вызова multi_pass::clear_queue().

fixed_size_queue<N>

Фиксированный_size_queue сохраняет круглый буфер размером N+1 и сохраняет N элементов. fix_size_queue - шаблон с параметром std::size_t, который определяет размер очереди. Вы несете ответственность за то, чтобы N был достаточно большим для вашего парсера. Всякий раз, когда главный итератор увеличивается, последний символ буфера автоматически стирается. В настоящее время нет возможности сказать, если итератор слишком далеко позади и стал недействительным. Никакое динамическое распределение не осуществляется этой политикой во время нормальной работы итератора, только при первоначальном строительстве. Использование памяти этой политики хранения устанавливается на N+1 байт, в отличие от std_deque, который не ограничен.

Combinations: How to specify your own custom multi_pass

Прелесть дизайна, основанного на политике, заключается в том, что вы можете смешивать и сопоставлять политики для создания собственного пользовательского класса, выбирая политики, которые вы хотите. Вот пример того, как указать пользовательский multi_pass, который обертывает istream_iteratorи немного более эффективен, чем по умолчанию, потому что он использует первую_owner OwnershipPolicy и контрольную политику no_check:

    typedef multi_pass<
        istream_iterator<char>,
        multi_pass_policies::input_iterator,
        multi_pass_policies::first_owner,
        multi_pass_policies::no_check,
        multi_pass_policies::std_deque
    > first_owner_multi_pass_type;

Параметрами шаблона по умолчанию для multi_pass являются: input_iterator InputPolicy, ref_counted OwnershipPolicy, buf_id_check CheckingPolicy и std_deque StoragePolicy. Таким образом, если вы используете multi_pass>вы получите эти предварительно определенные поведения при обертке istream_iterator.

Существует еще один класс под названием look_ahead. look_ahead имеет два шаблонных параметра: InputT, тип итератора ввода для обертывания и std::size_t N, который определяет размер буфера для политики фиксированной_size_queue. В то время как конфигурация multi_pass по умолчанию предназначена для безопасности, look_ahead предназначен для скорости. look_ahead происходит от multi_pass со следующими политиками: input_iterator InputPolicy, first_owner OwnershipPolicy, no_check CheckingPolicy и fixed_size_queueStoragePolicy.

How to write a functor for use with the functor_input InputPolicy

Если вы хотите использовать Functor_input InputPolicy, вы можете написать свой собственный Functor, который будет поставлять вход в multi_pass. Функтор должен удовлетворять двум требованиям. Он должен иметь тип typedef result_type, который определяет тип возврата оператора(). Это стандартная практика в STL. Кроме того, он должен предоставить статическую переменную, называемую eof, которая сравнивается с тем, чтобы знать, достиг ли вход конца. Вот пример:

    class my_functor
    {
    public:

        typedef char result_type;

        my_functor()
        : c('A') {}

        char operator()() const
        {
            if (c == 'M')
                return eof;
            else
                return c++;
        }

        static result_type eof;

    private:

        char c;
    };

    my_functor::result_type my_functor::eof = '\0';

    typedef multi_pass<
        my_functor,
        multi_pass_policies::functor_input,
        multi_pass_policies::first_owner,
        multi_pass_policies::no_check,
        multi_pass_policies::std_deque
    > functor_multi_pass_type;

    functor_multi_pass_type first = functor_multi_pass_type(my_functor());
    functor_multi_pass_type last;

How to write policies for use with multi_pass

InputPolicy

InputPolicy должна иметь следующий интерфейс:

    class my_input_policy // your policy name
    {
    public:

    //  class inner will be instantiated with the type given
    //  as the InputT parameter to multi_pass.

        template <typename InputT>
        class inner
        {
        public:

            // these typedefs determine the iterator_traits for multi_pass
            typedef x value_type;
            typedef x difference_type;
            typedef x pointer;
            typedef x reference;

        protected:

            inner();
            inner(InputT x);
            inner(inner const& x);
            // delete or clean up any state
            void destroy();
            // return true if *this and x have the same input
            bool same_input(inner const& x) const;
            void swap(inner& x);

        public:

            // get an instance from the input
            result_type get_input() const;
            // advance the input
            void advance_input();
            // return true if the input is at the end
            bool input_at_eof() const;
        };
    };

Из-за того, что multi_pass разделяет буфер и вход между несколькими копиями, внутренняя часть класса должна содержать указатель на вход. Конструктор должен просто скопировать указатель. Уничтожить (уничтожить). same_input должен сравнивать указатели. Более подробно см. различные реализации классов InputPolicy.

OwnershipPolicy

Политика владения должна иметь следующий интерфейс:

    class my_ownership_policy
    {
    protected:

        my_ownership_policy();
        my_ownership_policy(my_ownership_policy const& x);
        // clone is called when a copy of the iterator is made
        void clone();
        // called when a copy is deleted. Return true to indicate
        // resources should be released
        bool release();
        void swap(my_ownership_policy& x);

    public:
        // returns true if there is only one iterator in existence.
        // std_dequeue StoragePolicy will free it's buffered data if this
        // returns true.
        bool unique() const;
    };

CheckingPolicy

Контрольная политика должна иметь следующий интерфейс:

    class my_check
    {
    protected:

        my_check();
        my_check(my_check const& x);
        void destroy();
        void swap(my_check& x);
        // check should make sure that this iterator is valid
        void check_if_valid() const;
        void clear_queue();
    };

StoragePolicy

Политика хранения должна иметь следующий интерфейс:

    class my_storage_policy
    {
    public:

    // class inner will be instantiated with the value_type from the InputPolicy

        template <typename ValueT>
        class inner
        {
        protected:

            inner();
            inner(inner const& x);
            // will be called from the destructor of the last iterator.
            void destroy();
            void swap(inner& x);
            // This is called when the iterator is dereferenced. It's a template
            // method so we can recover the type of the multi_pass iterator
            // and access it.
            template <typename MultiPassT>
            static ValueT dereference(MultiPassT const& mp);
            // This is called when the iterator is incremented. It's a template
            // method so we can recover the type of the multi_pass iterator
            // and access it.
            template <typename MultiPassT>
            static void increment(MultiPassT& mp);
            void clear_queue();
            // called to determine whether the iterator is an eof iterator
            template <typename MultiPassT>
            static bool is_eof(MultiPassT const& mp);
            // called by operator==
            bool equal_to(inner const& x) const;
            // called by operator<
            bool less_than(inner const& x) const;
        };  // class inner
    };

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

Copyright © 2001-2002 Daniel C. Nuffer

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)

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

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