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

Деревья разбора и абстрактные синтаксические деревья — концепции.

Когда мы пользуемся тем или иным языком, будь то языком программирования или естественным языком, мы составляем фразы в соответствии с обпределённой иерархией подчинения. Одни смысловые конструкции включают в себя другие и сами являются составными частями более общих. Например: программа может состоять из функций; функции состоят из названия, типа возвращаемого значения, типов параметров, и исполняемого кода; исполняемый код состоит из операторов, ну и так далее.
Генерацией таких иерархических структур из текстового представления языка программирования занимается парсер. Обычно на выходе парсера мы получаем дерево разбора, то есть сущность, описывающую синтаксическую структуру программы в соответствии с описывающей её формальной грамматикой. Далее такие деревья уже преобразовываются в абстрактные синтаксические деревья (на русском) — структуры, которые избавлены от несущественных синтаксических деталей, из коих обычно состоит дерево разбора, и где присутствующие в них конструкции уже наполнены неким смысловым дополнительным содержанием, которое обычно добавляется на стадии семантического (контекстного) анализа.

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

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

Union-контейнер boost::variant и рекурсивная обёртка boost::recursive_wrapper.

Начнём писать всё необходимое для простого дерева с помощью контейнера boost::variant.

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

Как представлять узел дерева? Он может быть либо целым числом, в случае если это листовой узел, либо унарной или бинарной операцией. Бинарные операции, в свою очередь, имеют два отходящих узла дерева и в себе содержат знак операции. Унарные операции имеют только один подчинённый узел и также знак операции. Выглядеть это могло бы примерно так (если очень схематично):

typedef boost::variant<
    int,
    binary_op,
    unary_op
> ast_node;

struct binary_op
    {
    ast_node left, right;
    char op;
    };

struct unary_op
    {
    ast_node subj;
    char op;
    };

Вроде бы проблем нет, всё очень просто. Только вот загвоздка: на момент определения типа ast_node типы binary_op и unary_op ещё не определены, а это нелегально, так как контейнеру boost::variant нужно знать размер класса и размещение (layout) полей внутри класса. Что хотелось бы сделать — написать сначала определения этих двух классов, а потом уже определить сам узел дерева, да вот тоже незадача: внутри классов операций есть член ещё не определённого (или неполного) типа ast_node. Точно так же: для того, чтобы создать объект ast_node, на момент объявления его размер и размещение должны быть известны. Получается циклическая зависимость типов — хреново. Конечно, можно было бы выкрутиться с указателями, ибо для того, чтобы объявить указатель, низлежащий тип не обязан быть полным. Но вся эта морока с указателями часто доставляет головную боль, да и в учебном примере совсем ни к чему заботиться об особой эффективности структур и того, как мы с ними работаем. Впрочем, нечто подобное указателю всё-равно будет использоваться, потому что boost::recursive_wrapper по своей сути является обёрткой над boost::shared_ptr, который является умным указателем с подсчётом ссылок.

Как будем выходить из положения: завернём binary_op и unary_op в такие обёртки в объявлении типа ast_node для узла дерева, а дальше уже спокойно определим необходимые классы unary_op и binary_op, описывающие унарные и бинарные операции соответственно.

struct binary_op;
struct unary_op;

typedef boost::variant<
    int,
    boost::recursive_wrapper,
    boost::recursive_wrapper
> ast_node;

struct binary_op
    {
    binary_op(ast_node const & left_,
              ast_node const & right_,
              char op_)
        : left(left_),
          right(right_),
          op(op_)
        {
        }

    char op;
    ast_node left;
    ast_node right;
    };

struct unary_op
    {
    unary_op(ast_node const & subj_,
             char op_)
        : subj(subj_),
          op(op_)
        {
        }

    char op;
    ast_node subj;
    };

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

Пишем семантические действия с помощью phoenix::function.

Теперь нужно позаботиться о том, как это дерево будет преобразовываться по мере того, как будет происходить парсинг выражения. Манипуляции с деревом мы будем осуществлять с помощью семантических действий в коде правил. Основную работу в этом деле возложим на boost::phoenix, в частности на ленивые функции phoenix::function. Определимся с тем, что нужно вообще делать при распознавании выражения:

1. Когда встречается число или выражение в скобках, или выражение с унарным плюсом, то мы просто распространяем атрибут правой части правила на левую: _val = _1.
2. В бинарной операции мы распознаём самый первый операнд (например, в выражении 1 + 2 + 3, парсим 1). В таком случае точно так же просто инициализируем значение атрибута левой части атрибутом от этого операнда, то же самое: _val = _1.
3. Операция унарного минуса. Здесь нужно завернуть узел дерева, описывающий выражение, к которому применён унарный минус, в узел унарной операции со знаком '-', для этого определим фениксовую функцию neg. Само действие запишется так: _val = neg(_1).
4. Парсим один из правых операндов в бинарной операции. Вот здесь стоит остановиться поподробнее. Например, дано выражение 1 + 2 + 3, какое представление в дереве мы собираемся получить:

          +
        /   \\
       +     3
     /   \\
    1     2

   В принципе, можно было бы ограничиться и более простым вариантом вида:

            root
            / | \\
           1  +  +
              |  |
              2  3

   Но в данном случае мы всё-таки определили узлы для унарных и для бинарных операций, так что имеет смысл использовать их по прямому назначению. Короче, нужно каноническое дерево. Все рассматриваемые нами операции — левоассоциативные, то есть выполняются слева направо, что хорошо видно на первой схемке, в отличие от второй. Таким образом, опять же исходя непосредственно из канонической схемы, при парсинге каждого очередного правого операнда в бинарной операции, надо создать новый узел бинарной операции и в него завернуть то поддерево, что уже есть от левого операнда, слева, а то, что мы только что распарсили, справа. Назовём функию такого преобразования wrap_into_operation_node. Семантическое правило с её использованием запишем так: _val = wrap_into_operation_node(_val, _1, '+').

С тем, что нужно дальше делать, примерно разобрались. Теперь к реализации, благо её тут совсем немного. Первая функция phoenix на очереди: neg, заворачивающая узел дерева в узел унарной операции минуса:

struct neg_impl
    {
    template
    struct result;

    template <
          typename This
        , typename Arg
    >
    struct result
        {
        typedef ast_node type;
        };

    ast_node operator() (ast_node const & node) const
        {
        return unary_op(node, '-');
        }
    };

phx::function const neg = neg_impl();

Далее пойдет функция wrap_into_operation_node, её реализация почти что такая же, за исключением того, что мы конструируем объект типа binary_op заместо unary_op:

struct wrap_into_operation_node_impl
    {
    template
    struct result;

    template <
          typename This
        , typename Arg1
        , typename Arg2
        , typename Arg3
    >
    struct result
        {
        typedef ast_node type;
        };

    ast_node operator() ( ast_node const & left
                        , ast_node const & right
                        , char op) const
        {
        return binary_op(left, right, op);
        }
    };

phx::function const
    wrap_into_operation_node = wrap_into_operation_node_impl();

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

Начало конца — парсинг в AST.

Наше знакомство с основами генератора парсеров Spirit.Qi уже подходит к концу. Последнее, что нужно сделать, для того, чтобы всё это заработало: чуть-чуть подправить семантические действия у имеющейся грамматики калькулятора, да написать посещатель узлов дерева для вычисления выражения.

Начнём с грамматики, здесь практически ничего не поменялось:

using qi::_val;
using qi::_1;
using qi::_2;
using qi::_3;
using qi::_4;
using qi::uint_;
using qi::grammar;
using qi::rule;
using qi::on_error;
using qi::fail;
using qi::space_type;
using phx::val;
using phx::construct;

template
struct calculator_ast
    : grammar
    {
    calculator_ast()
        : calculator_ast::base_type(expr)
        {
        expr =
            term                    [ _val = _1 ]
            >> *(   '+'     > term
                [ _val = wrap_into_operation_node(_val, _1, '+') ]
                |   '-'     > term
                [ _val = wrap_into_operation_node(_val, _1, '-') ]
                )
            ;

        term =
            factor                  [ _val = _1 ]
            >> *(   '*'     > factor
                [ _val = wrap_into_operation_node(_val, _1, '*') ]
                |   '/'     > factor
                [ _val = wrap_into_operation_node(_val, _1, '/') ]
                )
            ;

        factor =
                uint_               [ _val = _1 ]
            |   '('     > expr      [ _val = _1 ]   > ')'
            |   '-'     > factor    [ _val = neg(_1)]
            |   '+'     > factor    [ _val = _1]
            ;

        expr.name("expr");
        term.name("term");
        factor.name("factor");

        on_error(expr,
            std::cout << val("Error! Expecting ") << _4 << " at: \""
                << construct(_3, _2) << "\"\\n\\n");
        }

    rule expr, term, factor;
    };

Как я и говорил: в случаях, когда обрабатывается либо унарный плюс, либо число, либо выражение в скобках, либо левый операнд бинарной операции, мы просто переносим атрибут этого операнда в узел дерева без изменений. Если встречаем унарный минус, заворачиваем узел выражения, к которому применяется минус, в унарную операцию с тегом '-'. При распознавании правых частей бинарных операторов последовательно заворачиваем узлы дерева в узлы бинарных операций с учётом левой ассоциативности операций.

Теперь о посещении дерева: поскольку узел дерева описывается контейнером boost::variant, то для обхода будем использовать стандартный посещатель boost::static_visitor<int>, который обеспечивает возврат значения типа int при обходе — то, что нужно для вычисления выражения. Теперь собственно код:

// bring in the calculator grammar details
#include "calculator_grammar_ast.hpp"

#include 

struct ast_result_calculator
    : boost::static_visitor
    {

    // evaluate immediate value
    int operator() (int val) const
        {
        return val;
        }

    // evaluate binary operation
    int operator() (binary_op const & node) const
        {
        // evaluate the left branch
        int left_val  = boost::apply_visitor(*this, node.left);
        // evaluate the right branch
        int right_val = boost::apply_visitor(*this, node.right);

        switch(node.op)
            {
        case '+':
            return left_val + right_val;
        case '-':
            return left_val - right_val;
        case '*':
            return left_val * right_val;
        case '/':
            return left_val / right_val;
        default:
            return 0;
            }
        }

    // evaluate unary operation
    int operator() (unary_op const & node) const
        {
        // evaluate the subject
        int subj_val = boost::apply_visitor(*this, node.subj);

        switch(node.op)
            {
        case '-':
            return -subj_val;
        default:
            return 0;
            }
        }
    };

Теперь результат всего выражения можно посчитать совсем просто:

ast_node ast;
// ...
int result = boost::apply_visitor(ast_result_calculator(), ast);

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

А дальше что?

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

В следующих частях я более подробно опишу некоторые дополнительные моменты по поводу Spirit.Qi. Расскажу также о некоторых других директивах, парсерах ну и ещё парочке моментов, связанных с оптимизацией работы Spirit.Qi. Плюс к тому, сделаю небольшое введение в Spirit.Lex — генератор лексических анализаторов, входящий в состав Boost.Spirit, и покажу, как им можно пользоваться на практике. Но прежде попробуем-таки наваять несложный калькулятор с поддержкой математических констант и некоторых функций. В нём вы уже не увидите ничего нового, просто покажу пример, как примерно можно двигаться дальше в направлении расширения функционала вычислителя.