Boost::Spirit и друзья. Краткий экскурс. Часть 3.

В предыдущих частях (первая, вторая) мы познакомились непосредственно с основами фреймворка для написания парсеров Spirit.Qi.
Основное время в этой части я посвящу описанию библиотеки boost::phoenix, которая в некоторых случаях очень сильно помогает облегчить написание семантических правил для грамматик, написанных на Спирите. Далее, увидим применение этого товарища на практике, сначала на демонстративных примерах, затем при реализации третьего шага нашего плана — написании компилирующего калькулятора.

boost::phoenix — что за зверь такой?

Изначально phoenix был дополнительной библиотекой для boost::spirit, нужный для того, чтобы предоставлять функционал, замещающий возможности boost::bind и boost::lambda для использования по большей части в семантических правилах. А вообще говоря, как было сказано ранее, phoenix представляет собой библиотеку для функционального программирования в C++ и включает в себя следующие вещи:

Сам по себе, phoenix оформлен в том же духе, что и boost::spirit, в том плане, что он тоже является DSEL’ом внутри языка C++.

Как говорят сами авторы данной библиотеки: тогда как Спирит пытается имитировать синтаксис БНФ в C++, Феникс пытается имитировать C++ в C++. То есть в тех местах, где требуется использование не слишком наглядных конструкций из функторов и прочих сложных сущностей со сложным синтаксисом (например, передача функтора в алгоритм), Феникс пытается сделать так, чтобы это было намного проще синтаксически и при том, чтобы было похоже на всё тот же C++. Возможно, такое объяснение выглядит не очень хорошо, так что приведу пару примеров на этот счёт. Так может выглядеть стандартное применение алгоритма std::accumulate:

int init = 0;
std::accumulate(c.begin(), c.end(), init, std::plus());

А так будет выглядеть то же самое, но с использованием phoenix:

int init = 0;
std::accumulate(c.begin(), c.end(), init, _1 + _2);

В принципе, здесь накладные расходы от использования std::plus<T> невелики, потому как функтор элементарный и писать и различать его ничуть не сложнее, чем _1 + _2, но вот ещё пример, когда написание стандартного функтора стоило бы уже несколько больших усилий:

std::for_each(c.begin(), c.end(), std::cout << _1 << std::endl);

Это примеры использования одной из фич данной библиотеки — лямбда-функий. Конечно, многие могут сразу же закидать меня тапками, потому что все знают, что в C++11 появляется аналогичная возможность языка C++, но, тем не менее, функторы Феникса имеют несколько особенностей, которыми лямбды из C++11 не обладают (например, создание полиморфных функциональных объектов).

Сущности _1, _2 и так далее в принципе аналогичны таковым для spirit::qi, выполняют они ту же самую роль — являются именами-заместителями, которые можно использовать в качестве места для подстановки аргумента в лямбда-функциях и при частичном применении функций. Находятся они, к слову, в пространстве имён boost::phoenix::placeholders, также для этих имён можно использовать и иные названия, кому как нравится: arg1, arg2, ... .

Всё есть функции. Значения.

Именно так. С точки зрения Феникса, абсолютно всё является функциональными объектами, даже значения! Примеры:

phoenix::val(1);// nullary function returning int(1)
phoenix::val("Hello, World!");// nullary function returning char const(&)[14], "Hello, World!"
phoenix::val(1.5);// nullary function returning double(1.5)

В данном случае, непосредственные значения заворачиваются в функциональные объекты, перегрузка operator() которых возвращает нульарную функцию, вызвав которую мы уже можем получить «завёрнутый» внутрь объект.

«Ленивые» вычисления.

Поскольку val(1) возвращает нульарную функцию, значит её можно вызвать, чтобы получить необходимое значение 1 типа int. Например:

int value = val(1)();

«Ленивыми» вычисления называются потому, что после первого вызова функции никакого фактического вычисления не происходит, val(1) по сути ещё ничего не делает, «откладывая» вычисление самого значения на потом, до момента когда явно потребуется ещё раз сделать вычисление функции, чтобы получить нужное значение (иногда это ещё называется отложенными вычислениями).

А вообще наиболее часто все эти функциональные объекты используются в виде callback-функций, что и делает Феникс очень удобным в плане составления сложных выражений из элементарных функций — примитивов. Примерчик:

template 
void f(Func F)
    {
    std::cout << F() << std::endl;
    }
int main()
    {
    f(phoenix::val(1));
    f(phoenix::val("Hello, World!"));
    }

Ссылки.

Ссылки точно так же являются функциями. Например, если у нас есть такие объявления:

int a = 1;
char const * b = "Hello, World!";

Фениксовые ссылки на них будут выглядеть так:

phoenix::ref(a);
phoenix::ref(b);

Точно так же, как и val, ref возвращает нульарную функцию; в первом случае возвращается int &, во втором — char const *&.

Аргументы.

Аргументы тоже являются функциями. До нынешнего момента, мы имели дело лишь с val и ref, которые возвращали нульарные функции. Аргументы, напротив, возвращают N-арные функции. Каждый аргумент представляет N-ный аргумент функции. Как уже было сказано ранее, имеется несколько предопределённых аргументов: _1, _2, ..., _N (дополнительная нотация: arg1, arg2, ..., argN). На самом деле, максимальное N точно так же, как и в Спирите, предопределено препроцессорной константой BOOST_PHOENIX_LIMIT, которая тоже по-умолчанию установлена равной 10.

Не стану что-то изобретать в плане примеров и пояснений, потому как гораздо лучше пока что следовать тому пути, что предлагает нам туториал из официальной документации к Фениксу (что я пока и делал почти что всюду), так что будем просто брать некоторые выжимки из того, что уже написано до нас хорошими людьми. А потом уже, возможно, посмотрим некоторые вещи, не входящие в программу «минимум» и попробуем ознакомиться с дополнительными фичами, которые предоставляет эта библиотека. Пример по поводу аргументов:

arg1 // one-or-more argument function that returns its first argument
arg2 // two-or-more argument function that returns its second argument
arg3 // three-or-more argument function that returns its third argument

Ещё один примерчик на эту тему:

int i = 3;
char const* s = "Hello World";
std::cout << arg1(i) << std::endl;        // prints 3
std::cout << arg2(i, s) << std::endl;     // prints "Hello World"

Ленивые операторы

Мы имеем возможность использовать все стандартные операторы для того, чтобы образовывать более сложные выражения. Один пример мы уже видели в начале этой части: _1 + _2. Ещё примерчики:

arg1 * arg1
ref(x) = arg1 + ref(z)
arg1 = arg2 + (3 * arg3)
ref(x) = arg1[arg2] // assuming arg1 is indexable and arg2 is a valid index

Заметим одну вещь: в выражении 3 * arg3 один из операндов не является phoenix-функтором, здесь мы имеем точно такую же ситуацию, когда говорили о парсерах Спирита и встречающихся в коде символьных литералах. Для того, чтобы выражение было валидным phoenix-выражением нужно, чтобы хотя бы один из операндов был легальным phoenix-примитивом или выражением. В данном случае, незаметно для нас непосредственное значение 3 конвертируется в val(3), так что этот код эквивалентен следующему: val(3) * arg3. Впрочем, имеются случаи, когда всё же приходится явно оборачивать наше значение в val, но это приходится делать достаточно редко.

Немного примеров составления выражений:

ref(x) = 123    // lazy
x = 123         // immediate

ref(x)[0]       // lazy
x[0]            // immediate

ref(x)[ref(i)]  // lazy
ref(x)[i]       // lazy (equivalent to ref(x)[val(i)])
x[ref(i)]       // illegal (x is not a phoenix primitive or expression)
ref(x[ref(i)])  // illegal (x is not a phoenix primitive or expression)

Первый практический пример.

Теперь мы вроде бы знаем достаточно, чтобы написать первый жизнеспособный и более-менее применимый в реальном мире пример.

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

struct is_odd
    {
    bool operator() (int val) const
        {
        return val % 2 == 1;
        }
    };

Передаём это дело в алгоритм:

std::find_if(c.begin(), c.end(), is_odd());

А если мы будем использовать phoenix, то можно написать нечто подобное:

std::find_if(c.begin(), c.end(), _1 % 2 == 1);

Так же естественно можно задавать и более сложные предикаты для поиска. Для этого нам доступны все привычные операторы: +,-,*,/,==,!=,&&,||, ...
Запись столь же простая, как если бы мы просто воткнули if прямо на том месте, где нам нужен предикат поиска — это радует. Плюс ко всему прочему, в то время, когда при написании функтора мы ограничивались лишь типом int (ну можно было бы и шаблон сделать, но тогда всё равно надо было бы явно его указывать при инстанцировании предиката в алгоритме), версия с phoenix сама разберётся с тем, что там нужно и будет работать в любом случае, когда для _1 будет допустимо данное сложное выражение.

Ленивые statement’ы.

В phoenix так же определены все основные операторы контроля выполнения в ленивой версии, которыми мы привыкли пользоваться в обычной C++ жизни, здесь вам и for, и if, и while, и do-while… Короче, всё тут есть:

if_(_1 % 2 == 1)
    [
    std::cout << _1 << std::endl
    ]

Предположим, что нам нужно вывести в заданном контейнере целых чисел все нечётные. Вот как мы можем это сделать с использованием данной конструкции:

std::for_each(c.begin(), c.end(),
    if_(_1 % 2 == 1)
        [
        std::cout << _1 << ' '
        ]
);

Нехило, ага!? Стоит заметить одну вещь: для тех конструкций, которые называются так же, как и ключевые слова (if, for, ...), в имя добавлено хвостовое нижнее подчёркивание '_', чтобы конфликта с точки зрения синтаксиса C++ не было.

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

if_(cond)
    [
    statement1,
    statement2,
    ...
    statementN
    ]

На конце запятой нет, так как это бы шло вразрез с синтаксическими правилами C++! Точно так же, части заголовка ленивого цикла for отделяются не точкой с запятой, а запятой, так как валидного синтаксиса всё-таки придерживаться надо:

for_(initstmt1, cond, poststmt)
    [
    bodystmts
    ]

Как реализовывать более сложные случаи типа if-else, do-while? Выглядеть это будет примерно так:

if_(cond1)
    [
    true_stmts
    ]
.else_
    [
    false_stmts
    ]
do_
    [
    do_stmts
    ]
.while_(cond)

Сейчас задумываться над тем, как это реализовано внутри, не стоит, просто надо помнить о некоторых различиях между тем, как вы пишете обычный код, и как вы пишете phoenix-выражения.

Операции с объектами. Construct, delete, new, преобразования типов.

Ещё в phoenix есть ленивые (да там всё ленивое, впрочем) эквиваленты операций вызова конструкторов объектов, new, delete и набор C++ преобразований типов. Говорить тут особо не о чем, вот несколько примеров:

construct(arg1, arg2)  // constructs a std::string from arg1, arg2
new_(arg1, arg2)       // makes a new std::string from arg1, arg2
delete_(arg1)          // deletes arg1 (assumed to be a pointer)
static_cast_(arg1)     // static_cast's arg1 to an int*

Точно так же, как и в случае с if_, do_, for_, конструкции для операторов new, delete, и C++-кастов тоже снабжены оканчивающим нижним подчёркиванием всё по тем же причинам — дабы не было конфликта с ключевыми словами C++.

Ленивые функции — наши новые друзья.

По мере того, как вы будете писать лямбда-выражения, вы будете замечать, что некоторые куски кода было бы неплохо рефакторить в отдельные функции для повторного использования. Увы, простые функции сосуществовать с phoenix-функциями не могут — просто природа у них разная.

Выход есть в ленивых функциях. Коль скоро вы программируете с использованием библиотеки boost::phoenix, ленивые функции станут вашими самыми большими друзьями. Библиотека предоставляет необходимые средства для того, чтобы удобно создавать ленивые функции. Перепишем наш предикат is_odd в виде ленивой phoenix-функции:

struct is_odd_impl
    {
    typedef bool result_type;

    template 
    bool operator() (Arg arg1) const
        {
        return arg1 % 2 == 1;
        }
    };

phx::function const is_odd = is_odd_impl();

Теперь ленивая функция is_odd, которая является объектом класса boost::phoenix::function<is_odd_impl> и реализация которой находится в классе is_odd_impl, полностью совместима со всеми конструкциями phoenix и мы свободно можем её использовать, где понадобится. Пример:

std::find_if(c.begin(), c.end(), is_odd(arg1));

Вычисление типа результата производится с помощью средств boost::result_of. Также возможно и другое определение для возвращаемого значения нашей функции: заместо определения типа result_type возможно написать метафункцию result, возвращающую нужный тип:

template 
struct result
    {
    typedef bool type;
    };

Если получающаяся ленивая функция phoenix::function оказывается полиморфной, то есть существует несколько перегрузок operator() и тип возвращаемого значения вместе с параметрами различаются, то иногда указывают явно специализации шаблона для метафункции result с нужным типом возвращаемого значения:

template 
struct result;

template 
struct result 
    {
    typedef Arg type;
    };
// ...
template 
Arg operator() (Arg arg) const
    {
    // ...
    }
// ...

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

struct factorial_impl
    {
    template 
    struct result;

    template 
    struct result 
        {
        typedef Arg type;
        };

    template 
    Arg operator() (Arg const & value) const
        {
        return value  const factorial = factorial_impl();

Теперь мы можем использовать эту функцию как и любую другую ленивую phoenix-функцию:

std::cout << factorial(6)() << std::endl; // prints "720"

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

Ленивая STL.

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


Также существует адаптация и всех стандартных алгоритмов STL, для этого подключаем


Если же париться вы не хотите с тем, что подключать, можно подключить всё сразу заголовком


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

#include 
namespace phx = boost::phoenix;
namespace phxp = phx::placeholders;

Как пользоваться?

Все функции-члены контейнеров, адаптированные для phoenix, претерпевают минимальные изменения в интерфейсной части по сравнению со своими «непосредственными» вариантами: первым аргументом такой функции выступает сам контейнер, функцию которого мы хотим вызвать. Например, c.begin() перейдет в begin(c), c1.swap(c2) будет swap(_1, _2) в «ленивом» варианте. Все остальные аргументы передаются точно в таком же порядке, как и в обычном варианте, так что особо говорить не о чем. Табличку с перечнем этих функций можно подглядеть в документации.

С алгоритмами дело обстоит впринципе так же, только за исключением того, что тут, на манер того, как это сделано в библиотеке boost::mpl интервал, над которым выполняется алгоритм, задаётся не парой итераторов, а целым контейнером, например, вот «обычный» вариант копирования содержимого одного массива в другой:

int array[] = {1, 2, 3};
int output[3];
std::copy(array, array + 3, output);

А вот «ленивый» вариант:

int array[] = {1, 2, 3};
int output[3];
phx::copy(phxp::_1, phxp::_2)(array, output);

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

Ради интереса, можно написать собственную реализацию «ленивого» алгоритма for_each:

struct for_each_impl
    {
    template 
    struct result
        {
        typedef void type;
        };

    template 
    void operator() (Container & c, Function f) const
        {
        std::for_each(c.begin(), c.end(), f);
        }
    };

phx::function const for_each = for_each_impl();

В принципе, точно так же строятся и «ленивые» варианты функций-членов для контейнеров. Посмотрим, например, возможную реализацию функции push_back:

struct push_back_impl
    {
    template 
    struct result
        {
        typedef void type;
        };

    template 
    void operator() (Container & c, Arg & arg) const
        {
        c.push_back(arg);
        }
    };

phx::function
 const push_back = push_back_impl();

А что ещё есть?

А ещё в phoenix есть механизмы контроля областей видимости, локальные переменные а также привязывание функций (function binding) с помощью phoenix::bind для отложенного выполнения, адаптация существующих функций и функторов в «ленивые» варианты. К слову, phoenix::bind полностью совместим с boost::bind, так что те, кто знаком с такой штукой, могут радоваться, есть и в Фениксе такая удобная фича. Но об этом я расскажу позже. И так уже слишком много времени уделил нашему новому знакомому boost::phoenix, прилично отклонившись в сторону от основной темы повествования.

X-макросы.

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

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

Классический пример на эту тему: пусть имеются следующие определения для цветов в заголовке colors.hpp:

enum Color
    {
    Red,
    Green,
    Blue
    };

В соответствующем source-code файле colors.cpp имеется массив ColorStrings для того, чтобы мы могли распечатать нормальные названия для цветов:

char const * ColorStrings[] = { "red", "green", "blue" };

Используем этот код примерно следующим образом:

Color color;
// do something with 'color'
std::cout << "The color is: " << ColorStrings[color] << std::endl;

Пока вроде бы всё в порядке. Но нам захотелось добавить ещё один цвет, мы обновляем файл colors.hpp:

enum Color
    {
    Red,
    Yellow,
    Green,
    Blue
    };

А обновить массив ColorStrings[], конечно же, забываем. В итоге попытка вывести жёлтый цвет оканчивается выводом зелёного, а попытка вывести синий цвет и вовсе даёт ошибку выхода за границы массива.

Вся проблема в том, что эти определения цветов и соответствующих строк между собой, в принципе, никак не связаны. Так вот есть довольно классный способ сделать так, чтобы определения в одном и в другом случае были связаны вместе, вместе обновлялись, да ещё и писанины было бы, возможно, поменьше. И способ этот — использование X-макроса.

Итак, поместим в colors.hpp такой код:

#define COLORS        \\
    X(red, "red")     \\
    X(green, "green") \\
    X(blue, "blue")

В место, где должны объявлять enum Color, такое:

#define X(a, b) a,
enum Color { COLORS };
#undef X

А теперь наш массив ColorStrings[] в colors.cpp:

#define X(a, b) b,
char const * ColorStrings[] = { COLORS };
#undef X

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

Теперь добавление нового цвета станет совсем-таки тривиальной операцией:

#define COLORS          \\
    X(red, "red")       \\
    X(yellow, "yellow") \\
    X(green, "green")   \\
    X(blue, "blue")

Всё это дело может быть сделано ещё приятней и проще, если отказаться от одного из параметров для X-макроса:

#define COLORS   \\
    X(red)       \\
    X(yellow)    \\
    X(green)     \\
    X(blue)

// ...

#define X(a) a,
enum Color { COLORS };
#undef X

// ...

#define X(a) #a,
char const * ColorStrings[] = { COLORS };
#undef X

Однако, вполне возможно, что где-то в программе уже был определён макрос с названием X, а у нас этот X зашит в тело макроса — нехорошо. В связи с такой проблемой можно пользоваться немного другим вариантом этого паттерна, когда этот самый макрос X передаётся в качестве параметра:

#define FOR_EACH_COLOR(apply) \\
    apply(red)                \\
    apply(green)              \\
    apply(blue)

// ...

#define SELECT_COLOR(color) color,
enum Color { FOR_EACH_COLOR(SELECT_COLOR) };
#undef SELECT_COLOR

// ...

#define SELECT_STRING(color) #color,
char const * ColorStrings[] = { FOR_EACH_COLOR(SELECT_STRING) };
#undef SELECT_STRING

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

Reinventing the calculator again…

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

Для начала определим, какие опкоды должны присутствовать для работы вычислителя: операторы сложения, вычитания, умножения, деления, инвертирование знака операнда, а также псевдо-опкод, который сигнализировал о том, что нужно из стека забрать непосредственное значение операнда целочисленного типа.

Пишем тело макроса, в котором определяем необходимые опкоды:

#ifndef __OPERATIONS_HPP__
#define __OPERATIONS_HPP__

#define OPS(apply) \\
    apply(add_)     \\ // addition
    apply(sub_)     \\ // subtraction
    apply(mul_)     \\ // multiplication
    apply(div_)     \\ // division
    apply(neg_)     \\ // unary negate
    apply(int_)       // "integer value" pseudo-opcode

#endif

Ну это мы всё только что разбирали, когда говорили о X-макросах, так что здесь всё должно быть понятно.

Теперь главное — реализуем грамматику калькулятора с прицепленными семантическими действиями, плюс определения структур данных, в которые будет вестись парсинг:

#ifndef __CALCULATOR_GRAMMAR_COMPILER_HPP__
#define __CALCULATOR_GRAMMAR_COMPILER_HPP__

#include 
#include 
#include 

// using boost::phoenix V3
#define BOOST_SPIRIT_USE_PHOENIX_V3
#include 
#include 
// bring in boost::variant container
#include 

namespace spirit = boost::spirit;
namespace qi = spirit::qi;
namespace phx = boost::phoenix;

// include operation opcodes definitions
#include "operations.hpp"

// generate operation tags
#define GENERATE(op) struct op##tag {};
OPS(GENERATE)
#undef GENERATE

// define variant type to hold opcodes and immediate values
#define LIST_OPS(op) ,op##tag
typedef boost::variant<
    int
    OPS(LIST_OPS)
> code_var;
#undef LIST_OPS

// define container to hold opcode elements
typedef std::vector code_vec;

template 
struct calculator_compiler
    : qi::grammar
    {
    // pass the code container by reference to the grammar .ctor
    calculator_compiler(code_vec & code)
        : calculator_compiler::base_type(expression)
        {
        expression =
            term
            >> *(   '+' > term          [ phx::push_back(phx::ref(code)
                                        , phx::construct()) ]
                |   '-' > term          [ phx::push_back(phx::ref(code)
                                        , phx::construct()) ]
                )
            ;

        term =
            factor
            >> *(   '*' > factor        [ phx::push_back(phx::ref(code)
                                        , phx::construct()) ]
                |   '/' > factor        [ phx::push_back(phx::ref(code)
                                        , phx::construct
()) ]
                )
            ;

        factor =
                qi::uint_               [ phx::push_back(phx::ref(code)
                                        , phx::construct())
                                        , phx::push_back(phx::ref(code), qi::_1) ]
            |   '('     > expression > ')'
            |   '-'     > factor        [ phx::push_back(phx::ref(code)
                                        , phx::construct()) ]
            |   '+'     > factor
            ;

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

        qi::on_error(expression,
            std::cout << phx::val("Error. Expected ")
            << qi::_4 << " at: \""
            << phx::construct(qi::_3,qi::_2)
            << "\"\\n\\n");
        }

    qi::rule expression, term, factor;
    };

#endif

Здесь мы использовали технику X-макросов для того, чтобы определить нужные опкоды в виде структур-тегов и перечислить эти теги в списке параметров для контейнера boost::variant, который, как вы, возможно, помните, может в себе держать единовременно лишь один объект одного из типов, которые входят в список шаблонных параметров данного контейнера. То есть объект типа code_var может в себе держать либо int число, либо один из тегов опкодов — довольно удобно. Далее определяем вектор, который будет содержать в себе объекты такого универсального типа — он и будет основным хранилищем кодов.

А вот в самой грамматике появилось много интересного — обо всём сейчас расскажу по порядку.

Первое, что становится видимым — изменившиеся семантические правила. Что в них происходит: создаём объекты тегов операций с помощью phoenix::construct<T>, получаем ссылку на наш вектор кодов с помощью phoenix::ref и делаем push_back в этот вектор. После объяснений по поводу Феникса, вряд ли здесь должны возникнуть существенные сложности. В некоторых действиях в [] записано сразу несколько семантических действий через запятую, эту возможность нам обеспечивает перегруженный оператор запятой, определённый внутри phoenix.

Что ещё заметно: operator >> в некоторых случаях заменены на operator >. Это ещё один оператор Спирита, который называется «оператором ожидания» (expectation operator). Отличается он от оператора следования тем, что в случае неудачного распознавания парсера по правую сторону от оператора отката назад и пробы других альтернатив не производится, а сразу же возбуждается исключение, сигнализирущее о том, что в данном месте просто-таки должно быть нечто иное. И в любом случае, если уж в данном месте произошла ошибка, то остальные попытки парсинга уже не имеют смысла. Применение этого оператора полезно для контроля ошибок во время парсинга, а мы как раз задались целью распознавать хотя бы самые элементарные ошибки, дальше объясню, за счёт чего она производится.

Читаем дальше:

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

Зачем-то правилам даются имена — это для того, чтобы когда было отображено сообщение об ошибке при неправильном вводе, название правила, в котором это произошло, отображалось с нормальным именем, а не с чем-то вроде <unnamed-rule>. Для самой грамматики также возможно определить имя — достаточно для qi::grammar::base_type в конструкторе предоставить вторым параметром строку, которая будет именем грамматики.

А ещё чуть дальше видим вызов конструкции, которая устанавливает обработчик ошибки для заданного правила и действия при отлове ошибки:

on_error(rule, handler)

У нас эта конструкция выглядит следующим образом:

qi::on_error(expression,
    std::cout << phx::val("Error. Expected ")
    << qi::_4 << " at: \""
    << phx::construct(qi::_3,qi::_2)
    << "\"\\n\\n");

Если мы устанавливаем обработчик на какое-то правило, то автоматически такой же обработчик ставится и на все правила, которые попадаются по пути раскрытия данного правила. В качестве действия выставлено qi::fail, которое говорит о том, что при ошибке следует завершить процесс парсинга и вернуть no_match (false). Действие может быть одним из следующих:

  • fail — парсинг провалился, возвращаем no_match и вываливаемся.
  • retry — попробовать восстановиться после ошибки, возможно, со смещением позиции итератора.
  • accept — насильственно сигнализировать об успехе, соответственно сдвигая позицию итератора.
  • rethrow — перекидывает ошибку следующему обработчику.

В качестве обработчика ошибки мы на месте строим phoenix-лямбду, которая будет выводить некоторую информацию об ошибке: что за ошибка произошла и где она произошла. Вот здесь и пригодились остальные заместители, предоставляемые Spirit::Qi. Для чего каждый из них нужен в данном случае:

  • qi::_1 — итератор в то место, где начался разбор данного правила с соответствующим обработчиком.
  • qi::_2 — конец входной строки.
  • qi::_3 — итератор в то место, где конкретно произошла ошибка.
  • qi::_4 — что вызвало ошибку: строка, представляющая описание произошедшей ошибки.

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

#ifndef __CALC_THE_RESULT_HPP__
#define __CALC_THE_RESULT_HPP__

#include "calculator_grammar_compiler.hpp"

#include 

int calc_the_result(code_vec & code)
    {
    std::stack operands;
    int op;

    // while the code vector is not empty
    while(!code.empty())
        {
        // then get all the operands before the operation code
        while(!code.empty() && code.front().which() == 6)
            {
            operands.push(boost::get(*(code.begin() + 1)));
            code.erase(code.begin(), code.begin() + 2);
            }
        // if input consists only of one number then exit and return this number
        if(code.empty())
            break;
        // perform the necessary calculation depending on the operation code
        switch(code.front().which())
            {
        case 1:
            op = operands.top();
            operands.pop();
            operands.top() += op;
            break;
        case 2:
            op = operands.top();
            operands.pop();
            operands.top() -= op;
            break;
        case 3:
            op = operands.top();
            operands.pop();
            operands.top() *= op;
            break;
        case 4:
            op = operands.top();
            operands.pop();
            operands.top() /= op;
            break;
        case 5:
            operands.top() *= -1;
            }
        code.erase(code.begin());
        }

    return operands.top();
    }

#endif

В данном коде можно упомянуть разве что which(), который вызывается для первого элемента вектора опкодов — помня о том, что элементы вектора суть объекты типа boost::variant<...>, знаем, что у этого контейнера есть функция-член which(), которая возвращает целое число, которое обозначает то, какого типа сейчас значение в контейнере находится. Получаемые значения находятся в диапазоне от 0 до <количество шаблонных параметров, указанных при объявлении типа variant> - 1, как индексы в массиве, если хотите: число i обозначает то, что сейчас в контейнере находится значение того типа, который указан на (i+1)-й позиции в списке шаблонных параметров для variant. Для выбора значений определённого типа из контейнера boost::variant используется функция boost::get<T>. В стек operands набираются непосредственные целочисленные значения, которые используются в вычислениях — вот и всё, о чём тут можно сказать, всё должно быть предельно ясно.

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

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

6 Comments

  1. Ответить
    Andrey 27.09.2011

    Исправление:
    qi::on_error(expr, // тут наверное expression
    std::cout << phx::val("Error. Expected ")
    << qi::_4 << " at: \""
    << phx::construct(qi::_3,qi::_2)
    << "\"\n\n");
    }

  2. Ответить
    Andrey 27.09.2011

    обратите внимание на коммент (ошибка?):
    phoenix::val(1);// nullary function returning int(3)

  3. Ответить
    Аноним 25.04.2016

    День добрый!
    Пример ленивой функции для факториала обрезан?
    Или я что то не понял?

  4. Ответить
    Екатерина 19.06.2019

    В описании ленивой STL пропущены инклуды, и далее тоже. В коде местами «» заменены на &amp и тп.
    А пример с факториалом законченный? Или я чего-то не понимаю?)

Добавить комментарий

Ваш адрес email не будет опубликован.