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

Note

В общем,Spirit.Qiгенерирует рекурсивный парсер спуска, который требует обратного анализа парсеров по дизайну. По этой причине мы должны предоставить, по крайней мере, передовые итераторы для любой из функций APISpirit.Qi. Однако это не является абсолютным требованием. В будущем мы увидим более детерминированные парсеры, которые требуют не более 1 символа (токена) внешнего вида. Такие парсеры позволяют использовать итераторы ввода, такие как<std::istream_iterator>, как есть.

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

Using the multi_pass

<multi_pass>итератор преобразует любой входной итератор в передний итератор, подходящий для использования сSpirit.Qi.<multi_pass>будет буферизировать данные, когда это необходимо, и будет отбрасывать буфер, когда его содержимое больше не нужно. Это происходит, если существует только одна копия итератора или если не может произойти обратное отслеживание.

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

Последовательности формы<a>>b>также будут буферизовать данные. Это отличается от поведенияДуха.Классика, но по уважительной причине. Последовательности должны сбросить текущий итератор до его начального состояния, если один из компонентов последовательности не соответствует. Чтобы компенсировать это поведение, мы добавили функциональность в парсеры<expect>(т.е. конструкции, подобные<a >b>). Точки ожидания вводят детерминированные точки в грамматику, гарантируя, что отступление не может произойти, если они совпадают. По этой причине мы очищаем буферы любого мульти-проходного итератора на каждой точке ожидания, обеспечивая минимальное содержание буфера даже для больших грамматик.

Important

Если вы используете обработчик ошибок в сочетании с парсером<expect>при использовании итератора<multi_pass>, и вы намереваетесь использовать обработчик ошибок для принудительной обработки<retry>или<fail>(см. описание обработчиков ошибок -FIXME: вставить ссылку), то вам необходимо инстанцировать обработчик ошибок, используя<retry>или<fail>, например: rule r<iterator_type> r; on_error<retry>(r, std::cout << phoenix::val("Error!")); Если вы этого не сделаете, полученный код вызовет утверждение во время выполнения.

Любое повторяющееся правило, такое как 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>в своей грамматике, чтобы гарантировать, что данные не буферизируются, когда они не нужны (55 доступен изSpirit.QiпарсерРепозиторий).

Здесь мы приводим минимальный пример, показывающий минимальный вариант использования. Итератор<multi_pass>очень настраиваемый, но политики по умолчанию были выбраны так, чтобы его можно было легко использовать с итераторами ввода, такими как<std::istreambuf_iterator>. Полный исходный код этого примера см. вmulti_pass.cpp.

int main()
{
    namespace spirit = boost::spirit;
    using spirit::ascii::space;
    using spirit::ascii::char_;
    using spirit::qi::double_;
    using spirit::qi::eol;
    std::ifstream in("multi_pass.txt");    // we get our input from this file
    if (!in.is_open()) {
        std::cout << "Could not open input file: 'multi_pass.txt'" << std::endl;
        return -1;
    }
    typedef std::istreambuf_iterator<char> base_iterator_type;
    spirit::multi_pass<base_iterator_type> first =
        spirit::make_default_multi_pass(base_iterator_type(in));
    std::vector<double> v;
    bool result = spirit::qi::phrase_parse(first
      , spirit::make_default_multi_pass(base_iterator_type())
      , double_ >> *(',' >> double_)              // recognize list of doubles
      , space | '#' >> *(char_ - eol) >> eol      // comment skipper
      , v);                                       // data read from file
    if (!result) {
        std::cout << "Failed parsing input file!" << std::endl;
        return -2;
    }
    std::cout << "Successfully parsed input file!" << std::endl;
    return 0;
}

Using the flush_multi_pass parser

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

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

The multi_pass Policies

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

Класс multi_pass имеет два шаблонных параметра:

Реализовать весь необходимый функционал объединенной политики можно в одном классе. Но оказалось более удобным разделить это на четыре различные группы функций, то есть четыре отдельные, но хорошо скоординированные политики. По этой причине в библиотеке<multi_pass>реализован шаблон<iterator_policies::default_policy>, позволяющий комбинировать несколько различных политик, каждая из которых реализует одну из функциональных групп:

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

Predefined policies

Все предопределенные<multi_pass>политики определены в пространстве имен<boost::spirit::iterator_policies>.

Combinations: How to specify your own custom multi_pass

Прелесть дизайна, основанного на политике, заключается в том, что вы можете смешивать и сопоставлять политики, чтобы создать свой собственный пользовательский итератор, выбрав политики, которые вы хотите. Вот пример того, как указать пользовательский<multi_pass>, который обертывает<std::istream_iterator<char>>, и немного более эффективен, чем по умолчанию<multi_pass>(как генерируется функцией<make_default_multi_pass()>API), потому что он использует<iterator_policies::first_owner>Политика владения и<iterator_policies::no_check>Проверка политики:

typedef multi_pass<
    std::istream_iterator<char>
  , iterator_policies::default_policy<
        iterator_policies::first_owner
      , iterator_policies::no_check
      , iterator_policies::buffering_input_iterator
      , iterator_policies::split_std_deque
    >
> first_owner_multi_pass_type;

Параметры шаблона по умолчанию для<iterator_policies::default_policy>:

Если вы будете использовать<multi_pass<std::istream_iterator<char> >>, вы получите эти предопределенные поведения при обертывании<std::istream_iterator<char>>.

Dealing with constant look ahead

Есть еще один предопределенный класс, называемый<look_ahead>. Класс<look_ahead>является другим предопределенным<multi_pass>типом итератора. Он имеет два шаблонных параметра:<Input>, тип входного итератора для обертывания и<std::size_tN>, который определяет размер буфера в политике<fixed_size_queue>. Конфигурация multi_pass по умолчанию предназначена для обеспечения безопасности, а конфигурация<look_ahead>— для скорости.<look_ahead>является производным от multi_pass со следующими политиками:<input_iterator>InputPolicy,<first_owner>OwnershipPolicy,<no_check>CheckingPolicy и<fixed_size_queue<N>>StoragePolicy.

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

// forwards to <boost/spirit/home/support/look_ahead.hpp>
#include <boost/spirit/include/support_look_ahead.hpp>

См. такжеВключите структуру.

Reading from standard input streams

Еще один предопределенный итератор для обертывания стандартных входных потоков (обычно a<std::basic_istream<>>) называется<basic_istream_iterator<Char,Traits>>. Этот класс можно использовать в качестве замены<std::istream_iterator<Char,Traits>>. Разница лишь в том, что это передний итератор (вместо<std::istream_iterator>, который является входным итератором).<basic_istream_iterator>является производным от multi_pass со следующими политиками:<istream>InputPolicy,<ref_counted>OwnershipPolicy,<no_check>CheckingPolicy и<split_std_deque>StoragePolicy.

Существует дополнительный предварительно определенный типдеф:

typedef basic_istream_iterator<char, std::char_traits<char> > istream_iterator;

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

// forwards to <boost/spirit/home/support/istream_iterator.hpp>
#include <boost/spirit/include/support_istream_iterator.hpp>

См. такжеВключите структуру.

How to write a functor for use with the functor_input InputPolicy

Если вы хотите использовать<functor_input>В InputPolicy можно написать свой собственный функциональный объект, который будет подавать ввод на<multi_pass>. Объект функции должен удовлетворять нескольким требованиям. Он должен иметь типдеф<result_type>, который определяет тип возврата<operator()>. Это стандартная практика в STL. Кроме того, он должен предоставить статическую переменную, называемую eof, которая сравнивается с тем, чтобы знать, достиг ли вход конца. И последнее, но не менее важное: объект функции должен быть конструируемым по умолчанию. Вот пример:

#include <iostream>
#include <boost/spirit/home/qi.hpp>
#include <boost/spirit/home/support.hpp>
#include <boost/spirit/home/support/multi_pass.hpp>
#include <boost/spirit/home/support/iterators/detail/functor_input_policy.hpp>
// define the function object
class iterate_a2m
{
public:
    typedef char result_type;
    iterate_a2m() : c_('A') {}
    iterate_a2m(char c) : c_(c) {}
    result_type operator()()
    {
        if (c_ == 'M')
            return eof;
        return c_++;
    }
    static result_type eof;
private:
    char c_;
};
iterate_a2m::result_type iterate_a2m::eof = iterate_a2m::result_type('M');
using namespace boost::spirit;
// create two iterators using the define function object, one of which is 
// an end iterator
typedef multi_pass<iterate_a2m
  , iterator_policies::first_owner
  , iterator_policies::no_check
  , iterator_policies::functor_input
  , iterator_policies::split_std_deque>
functor_multi_pass_type;
int main()
{
    functor_multi_pass_type first = functor_multi_pass_type(iterate_a2m());
    functor_multi_pass_type last;
    // use the iterators: this will print "ABCDEFGHIJKL"
    while (first != last) {
        std::cout << *first;
        ++first;
    }
    std::cout << std::endl;
    return 0;
}

How to write policies for use with multi_pass

Все политики, используемые с шаблоном<default_policy>, должны иметь два встроенных класса:<unique>и<shared>. Класс<unique>должен выполнять все необходимые функции для конкретного типа политики. Кроме того, он может содержать все элементы данных, являющиесяуникальнымидля конкретного экземпляра<multi_pass>(отсюда и название). Класс<shared>не раскрывает какие-либо функции-члены (за исключением иногда конструктора), но он может содержать все элементы данных-членов, которые являютсяобщимимежду всеми копиями конкретного<multi_pass>.

InputPolicy

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

struct input_policy
{
    // Input is the same type used as the first template parameter
    // while instantiating the multi_pass
    template <typename Input>
    struct unique
    {
        // these typedef's will be exposed as the multi_pass iterator
        // properties
        typedef __unspecified_type__ value_type;
        typedef __unspecified_type__ difference_type;
        typedef __unspecified_type__ distance_type;
        typedef __unspecified_type__ pointer;
        typedef __unspecified_type__ reference;
        unique() {}
        explicit unique(Input) {}
        // destroy is called whenever the last copy of a multi_pass is
        // destructed (ownership_policy::release() returned true)
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void destroy(MultiPass& mp);
        // swap is called by multi_pass::swap()
        void swap(unique&);
        // get_input is called whenever the next input character/token
        // should be fetched. 
        //
        //   mp:    is a reference to the whole multi_pass instance
        //
        // This method is expected to return a reference to the next 
        // character/token
        template <typename MultiPass>
        static typename MultiPass::reference get_input(MultiPass& mp);
        // advance_input is called whenever the underlying input stream 
        // should be advanced so that the next call to get_input will be 
        // able to return the next input character/token
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void advance_input(MultiPass& mp);
        // input_at_eof is called to test whether this instance is a 
        // end of input iterator.
        //
        //   mp:    is a reference to the whole multi_pass instance
        //
        // This method is expected to return true if the end of input is 
        // reached. It is often used in the implementation of the function
        // storage_policy::is_eof.
        template <typename MultiPass>
        static bool input_at_eof(MultiPass const& mp);
        // input_is_valid is called to verify if the parameter t represents 
        // a valid input character/token
        //
        //   mp:    is a reference to the whole multi_pass instance
        //   t:     is the character/token to test for validity
        // 
        // This method is expected to return true if the parameter t 
        // represents a valid character/token.
        template <typename MultiPass>
        static bool input_is_valid(MultiPass const& mp, value_type const& t);
    };
    // Input is the same type used as the first template parameter passed
    // while instantiating the multi_pass
    template <typename Input>
    struct shared
    {
        explicit shared(Input) {}
    };
};

Можно вывести структуру<unique>из типа<boost::spirit::detail::default_input_policy>. Этот тип реализует минимальный достаточный интерфейс для некоторых необходимых функций, упрощая задачу написания новой политики ввода.

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

OwnershipPolicy

<OwnershipPolicy>должен иметь следующий интерфейс:

struct ownership_policy
{
    struct unique
    {
        // destroy is called whenever the last copy of a multi_pass is
        // destructed (ownership_policy::release() returned true)
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void destroy(MultiPass& mp);
        // swap is called by multi_pass::swap()
        void swap(unique&);
        // clone is called whenever a multi_pass is copied
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void clone(MultiPass& mp);
        // release is called whenever a multi_pass is destroyed
        //
        //   mp:    is a reference to the whole multi_pass instance
        //
        // The method is expected to return true if the destructed 
        // instance is the last copy of a particular multi_pass. 
        template <typename MultiPass>
        static bool release(MultiPass& mp);
        // is_unique is called to test whether this instance is the only 
        // existing copy of a particular multi_pass
        //
        //   mp:    is a reference to the whole multi_pass instance
        //
        // The method is expected to return true if this instance is unique
        // (no other copies of this multi_pass exist).
        template <typename MultiPass>
        static bool is_unique(MultiPass const& mp);
    };
    struct shared {};
};

Можно вывести структуру<unique>из типа<boost::spirit::detail::default_ownership_policy>. Этот тип реализует минимальный интерфейс, достаточный для некоторых необходимых функций, упрощая задачу написания новой политики владения.

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

CheckingPolicy

<CheckingPolicy>должен иметь следующий интерфейс:

struct checking_policy
{
    struct unique
    {
        // swap is called by multi_pass::swap()
        void swap(unique&);
        // destroy is called whenever the last copy of a multi_pass is
        // destructed (ownership_policy::release() returned true)
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void destroy(MultiPass& mp);
        // docheck is called before the multi_pass is dereferenced or 
        // incremented. 
        //
        //   mp:    is a reference to the whole multi_pass instance
        //
        // This method is expected to make sure the multi_pass instance is
        // still valid. If it is invalid an exception should be thrown.
        template <typename MultiPass>
        static void docheck(MultiPass const& mp);
        // clear_queue is called whenever the function 
        // multi_pass::clear_queue is called on this instance
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void clear_queue(MultiPass& mp);
    };
    struct shared {};
};

Можно вывести структуру<unique>из типа<boost::spirit::detail::default_checking_policy>. Этот тип реализует минимальный интерфейс, достаточный для некоторых необходимых функций, упрощая задачу написания новой политики проверки.

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

StoragePolicy

<StoragePolicy>должен иметь следующий интерфейс:

struct storage_policy
{
    // Value is the same type as typename MultiPass::value_type
    template <typename Value>
    struct unique
    {
        // destroy is called whenever the last copy of a multi_pass is
        // destructed (ownership_policy::release() returned true)
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void destroy(MultiPass& mp);
        // swap is called by multi_pass::swap()
        void swap(unique&);
        // dereference is called whenever multi_pass::operator*() is invoked
        //
        //   mp:    is a reference to the whole multi_pass instance
        //
        // This function is expected to return a reference to the current
        // character/token.
        template <typename MultiPass>
        static typename MultiPass::reference dereference(MultiPass const& mp);
        // increment is called whenever multi_pass::operator++ is invoked
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void increment(MultiPass& mp);
        //
        //   mp:    is a reference to the whole multi_pass instance
        template <typename MultiPass>
        static void clear_queue(MultiPass& mp);
        // is_eof is called to test whether this instance is a end of input 
        // iterator.
        //
        //   mp:    is a reference to the whole multi_pass instance
        //
        // This method is expected to return true if the end of input is 
        // reached. 
        template <typename MultiPass>
        static bool is_eof(MultiPass const& mp);
        // less_than is called whenever multi_pass::operator==() is invoked
        //
        //   mp:    is a reference to the whole multi_pass instance
        //   rhs:   is the multi_pass reference this instance is compared 
        //          to
        //
        // This function is expected to return true if the current instance
        // is equal to the right hand side multi_pass instance
        template <typename MultiPass>
        static bool equal_to(MultiPass const& mp, MultiPass const& rhs);
        // less_than is called whenever multi_pass::operator<() is invoked
        //
        //   mp:    is a reference to the whole multi_pass instance
        //   rhs:   is the multi_pass reference this instance is compared 
        //          to
        //
        // This function is expected to return true if the current instance
        // is less than the right hand side multi_pass instance
        template <typename MultiPass>
        static bool less_than(MultiPass const& mp, MultiPass const& rhs);
    };
    // Value is the same type as typename MultiPass::value_type
    template <typename Value>
    struct shared {};
};

Можно вывести структуру<unique>из типа<boost::spirit::detail::default_storage_policy>. Этот тип реализует минимальный достаточный интерфейс для некоторых необходимых функций, упрощая задачу написания новой политики хранения.

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

Как правило,<StoragePolicy>является самой сложной политикой для реализации. Вы должны изучить и понять существующие<StoragePolicy>классы, прежде чем пытаться писать свои собственные.