Остановитесь и подумайте об этом... В нашем последнем примере мы очень близки к созданию AST (абстрактного синтаксического дерева). Мы разобрали единую структуру и создали в памяти представление о ней в виде структуры:структурасотрудник. Если мы изменим реализацию, чтобы разобрать одного или нескольких сотрудников, результатом будетstd:вектор;Работник>. Мы можем продолжать и добавить больше иерархии: команды, отделы, корпорации. Тогда у нас будет представление AST всего этого.

В этом примере (на самом деле два примера) мы теперь рассмотрим, как создать АСТ. Мы будем анализировать минималистичный XML-подобный язык и компилировать результаты в наши структуры данных в виде дерева.

По пути мы увидим новые функции:

The full cpp files for these examples can be found here: ../../example/qi/mini_xml1.cpp and here: ../../example/qi/mini_xml2.cpp

В подкаталоге mini_xml_samples имеется несколько образцов файлов toy-xml:../../example/qi/mini_xml_samples/1.toyxml,../../example/qi/mini_xml_samples/2.toyxmlи../../example/qi/mini_xml_samples/3.toyxmlдля целей тестирования. Пример../../пример/qi/mini_xml_samples/4.toyxmlВ этом есть ошибка.

First Cut

Без дальнейших задержек, вот первая версия грамматики XML:

template <typename Iterator>
struct mini_xml_grammar : qi::grammar<Iterator, mini_xml(), ascii::space_type>
{
    mini_xml_grammar() : mini_xml_grammar::base_type(xml)
    {
        using qi::lit;
        using qi::lexeme;
        using ascii::char_;
        using ascii::string;
        using namespace qi::labels;
        using phoenix::at_c;
        using phoenix::push_back;
        text = lexeme[+(char_ - '<')        [_val += _1]];
        node = (xml | text)                 [_val = _1];
        start_tag =
                '<'
            >>  !lit('/')
            >>  lexeme[+(char_ - '>')       [_val += _1]]
            >>  '>'
        ;
        end_tag =
                "</"
            >>  string(_r1)
            >>  '>'
        ;
        xml =
                start_tag                   [at_c<0>(_val) = _1]
            >>  *node                       [push_back(at_c<1>(_val), _1)]
            >>  end_tag(at_c<0>(_val))
        ;
    }
    qi::rule<Iterator, mini_xml(), ascii::space_type> xml;
    qi::rule<Iterator, mini_xml_node(), ascii::space_type> node;
    qi::rule<Iterator, std::string(), ascii::space_type> text;
    qi::rule<Iterator, std::string(), ascii::space_type> start_tag;
    qi::rule<Iterator, void(std::string), ascii::space_type> end_tag;
};

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

rule<Iterator, std::string(), space_type> text;

и его определение:

text = lexeme[+(char_ - '<')        [_val += _1]];

Семантическое действие собирает проводники и прикладывает их (через +=) кstd::строкеатрибуту правила (представленному заполнителем_val).

Alternates

rule<Iterator, mini_xml_node(), space_type> node;

и его определение:

node = (xml | text)                 [_val = _1];

Мы увидим структуруmini_xml_nodeпозже. Глядя на определение правила, мы видим, что здесь происходит некоторое чередование. Узел xmlпредставляет собой либоxml, либотекст. Хмммм... держитесь за эту мысль...

rule<Iterator, std::string(), space_type> start_tag;

std::строка. Тогда это определение:

start_tag =
        '<'
    >>  !char_('/')
    >>  lexeme[+(char_ - '>')       [_val += _1]]
    >>  '>'
;

Not Predicate

start_tagаналогичнотекстовомуправилу, кроме добавленного'<'и'>'. Но подождите, чтобы убедиться, чтоstart_tagне анализируетend_tag, мы также добавим:!char_'/'. Это «не предикат»:

!p

Попробует парсерр. Если он увенчается успехом, потерпит неудачу; в противном случае, пропустите. Иными словами, он отрицает результатp. Как иэпс, он не потребляет никакого ввода. Он всегда будет перематывать положение итератора туда, где он был при входе. Итак, выражение:

!char_('/')

Мы не должны иметь'/'на данный момент.

Inherited Attribute

end_tag:

rule<Iterator, void(std::string), space_type> end_tag;

Ох! Теперь мы видим унаследованный атрибут там:std::строка.end_tagне имеет синтезированного атрибута. Рассмотрим его определение:

end_tag =
        "</"
    >>  lit(_r1)
    >>  '>'
;

_r1является еще однимзаполнителем Фениксадля первого унаследованного атрибута (у нас есть только один, используйте_r2,_r3и т. д., если у вас есть больше).

A Lazy Lit

Посмотрите, как мы использовалилитздесь, на этот раз, не с буквальной строкой, а со значением первого унаследованного атрибута, который указан какstd::строкав нашей декларации правил.

Наконец, наше правилоxml:

rule<Iterator, mini_xml(), space_type> xml;

mini_xmlявляется нашим атрибутом здесь. Посмотрим позже, что это. Рассмотрим его определение:

xml =
        start_tag                   [at_c<0>(_val) = _1]
    >>  *node                       [push_back(at_c<1>(_val), _1)]
    >>  end_tag(at_c<0>(_val))
;

Те, кто знаетBoost.Fusion, теперь заметятat_c<0>иat_c<>. Это дает нам намек на то, чтоmini_xmlявляется своего рода кортежом — последовательностью слияния.at_c<N>вот ленивая версия связочных аксессуаров, предоставленнаяPhoenix.

How it all works

Так что происходит?

Чтобы дать последнему пункту немного больше света, происходит следующее:

end_tag(at_c<0>(_val))

Звонки:

end_tag =
        "</"
    >>  lit(_r1)
    >>  '>'
;

прохождение вat_c<0>_val, строка от стартового тега. Это упоминается вend_tagтела как_r1.

The Structures

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

struct mini_xml;
typedef
    boost::variant<
        boost::recursive_wrapper<mini_xml>
      , std::string
    >
mini_xml_node;
struct mini_xml
{
    std::string name;                           // tag name
    std::vector<mini_xml_node> children;        // children
};

Of Alternates and Variants

Так выглядит мини-узел. У нас был намек, что это либо строка, либоmini_xml. Для этого мы используемBoost.Variant.boost::recursive_wrapperwrapsmini_xml, что делает его рекурсивной структурой данных.

Да, вы получили это право: атрибут альтернативного:

a | b

является

boost::variant<A, B>

гдеAявляется атрибутомaиBявляется атрибутомb.

Adapting structs again

mini_xmlне умнее. Это простая структура. Но, как мы видели на примере наших сотрудников, мы можем адаптировать это к последовательностиBoost.Fusion:

BOOST_FUSION_ADAPT_STRUCT(
    client::mini_xml,
    (std::string, name)
    (std::vector<client::mini_xml_node>, children)
)

One More Take

Вот другая версия. Структура АСТ остается прежней, но на этот раз вы увидите, что мы используем автоматические правила, делающие грамматику семантической. Вот оно:

template <typename Iterator>
struct mini_xml_grammar
  : qi::grammar<Iterator, mini_xml(), qi::locals<std::string>, ascii::space_type>
{
    mini_xml_grammar()
      : mini_xml_grammar::base_type(xml)
    {
        using qi::lit;
        using qi::lexeme;
        using ascii::char_;
        using ascii::string;
        using namespace qi::labels;
        text %= lexeme[+(char_ - '<')];
        node %= xml | text;
        start_tag %=
                '<'
            >>  !lit('/')
            >>  lexeme[+(char_ - '>')]
            >>  '>'
        ;
        end_tag =
                "</"
            >>  string(_r1)
            >>  '>'
        ;
        xml %=
                start_tag[_a = _1]
            >>  *node
            >>  end_tag(_a)
        ;
    }
    qi::rule<Iterator, mini_xml(), qi::locals<std::string>, ascii::space_type> xml;
    qi::rule<Iterator, mini_xml_node(), ascii::space_type> node;
    qi::rule<Iterator, std::string(), ascii::space_type> text;
    qi::rule<Iterator, std::string(), ascii::space_type> start_tag;
    qi::rule<Iterator, void(std::string), ascii::space_type> end_tag;
};

Это не должно быть более трудно понять после прохождения первого примера анализатора xml. Правила практически одинаковые, за исключением того, что мы избавились от смысловых действий и использовали автоправила (см. пример сотрудника, если вы пропустили это). Но есть кое-что новое. Это все в правилеxml:

Local Variables

rule<Iterator, mini_xml(), locals<std::string>, space_type> xml;

Вау, у нас сейчас четыре шаблонных параметра. Что там делают местные жители? Ну, он заявляет, что правилоxmlбудет иметь одну локальную переменную: строку. Рассмотрим, как это используется в действии:

xml %=
        start_tag[_a = _1]
    >>  *node
    >>  end_tag(_a)
;

Нет никаких действий, связанных с вставкой данных в наш атрибутxml. Обо всем позаботились благодаря авто-правилу.