Boost::Spirit и друзья. Краткий экскурс. Часть 4.
В предыдущих частях (первая, вторая, третья) мы занимались парсингом в простые структуры данных, не сложнее обычного списка величин. Сейчас же попробуем посмотреть, как можно с минимальными усилиями строить на выходе парсера иерархические структуры данных, такие как абстрактные синтаксические деревья.
Деревья разбора и абстрактные синтаксические деревья — концепции.
Когда мы пользуемся тем или иным языком, будь то языком программирования или естественным языком, мы составляем фразы в соответствии с обпределённой иерархией подчинения. Одни смысловые конструкции включают в себя другие и сами являются составными частями более общих. Например: программа может состоять из функций; функции состоят из названия, типа возвращаемого значения, типов параметров, и исполняемого кода; исполняемый код состоит из операторов, ну и так далее.Иными словами, конкретные синтаксические деревья занимаются тем, что отражают сугубо синтаксическую составляющую программы, тогда как абстрактные синтаксические деревья уже описывают более общие конструкции языка, наполненные необходимой смысловой информацией.
В этой части мы займёмся тем, что определим структуру совсем простенького абстрактного синтаксического дерева и посмотрим, как его в процессе парсинга заполнять, а потом и вычислять.
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. Определимся с тем, что нужно вообще делать при распознавании выражения: - Когда встречается число или выражение в скобках, или выражение с унарным плюсом, то мы просто распространяем атрибут правой части правила на левую:
_val = _1. - В бинарной операции мы распознаём самый первый операнд (например, в выражении
1 + 2 + 3, парсим1). В таком случае точно так же просто инициализируем значение атрибута левой части атрибутом от этого операнда, то же самое:_val = _1. - Операция унарного минуса. Здесь нужно завернуть узел дерева, описывающий выражение, к которому применён унарный минус, в узел унарной операции со знаком
'-', для этого определим фениксовую функциюneg. Само действие запишется так:_val = neg(_1). - Парсим один из правых операндов в бинарной операции. Вот здесь стоит остановиться поподробнее. Например, дано выражение
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, и покажу, как им можно пользоваться на практике. Но прежде попробуем-таки наваять несложный калькулятор с поддержкой математических констант и некоторых функций. В нём вы уже не увидите ничего нового, просто покажу пример, как примерно можно двигаться дальше в направлении расширения функционала вычислителя.
Коменты (4)