Знакомство с фреймворком Spirit::Qi.

Несмотря на то, что данная статья имеет в большей степени ознакомительный характер, предполагается, что читатель знает (ну или хотя бы краем уха слышал) о таких вещах, как C++, шаблонное метапрограммирование, Boost, в противном случае горите в аду, сраные грешники возникнут проблемы с пониманием, на что мне совершенно будет наплевать — я же предупреждал, курите маны, если уж на то пошло. Впрочем, в некоторых местах всё же будут оставлены некоторые уточнения по той или иной теме, где я сочту нужным остановиться и рассказать чуть поподробнее о том, что вообще происходит.

Как это будет выглядеть?

Прежде, чем говорить о чём-либо, опишу, по какому принципу будут составляться части этой одной статьи.

В общей сложности планируется шесть частей. Первая, которую в данный момент вы читаете, представляет собой лишь очень маленькое и поверхностное ознакомление с предметной областью и один более-менее солидный примерчик в конце, много слов, мало кода, но прочитать всё же стоит, особенно тем, кто совершенно не в теме. Следующие три части будут посвящены различным реализациям задуманного проекта в соответствии с меняющимися нуждами и задачами, в рамках ознакомления с основами спирита, так сказать. На каждом следующем шаге предыдущий материал будет расширяться, пересматриваться и переосмысливаться. Пятую часть пока задумываю, как более подробное описание библиотеки boost::phoenix, делающей программирование с помощью функциональной парадигмы в C++ более наглядным и комфортным. Наконец, шестая глава (может быть, даже последняя, пока не уверен) будет посвящена брату-близнецу spirit::qi — spirit::karma и, возможно, ещё парочке сопутствующих спириту библиотек вроде boost::fusion, boost::mpl, boost::proto.

О чём речь-то, а?

А речь пойдет об одной, на мой взгляд, очень интересной библиотеке boost::spirit, входящей в состав дружного семейства open source библиотек boost. Занимается она парсингом и генерацией данных, с заданием правил распознавания и вывода через формальные грамматики в формате, близком к РБНФ. Оформлены основные части Спирита в виде DSEL‘ов (Domain Specific Embedded Language) — языков, достаточно близких по своему виду к EBNF нотации , построенных на конструкциях языка C++ (а именно: техники шаблонного метапрограммирования и так называемые expression templates — шаблоны выражений), что позволяет строить грамматики в удобном виде, так сказать, «не отходя от кассы», прямо в коде C++, без дополнительных шагов по интеграции этого дела с существующим кодом. К слову, на данный момент структура библиотеки boost::spirit такова:

1. Spirit::Classic. Наследие старых версий boost::spirit, а именно: то, чем был boost::spirit вплоть до версий за номерами 1.8.x. Ныне уже устарел, не рекомендуется к использованию в новых проектах, так как есть кое-что поновее и покруче (хотя в нём есть и очень удобные вещи, которых в новом spirit‘е нет, а жаль).
2. Spirit::Qi. Часть нового boost::spirit V2, отвечающая за создание парсеров.
3. Spirit::Karma. Библиотека для создания генераторов. Действие абсолютно противоположно тому, что делает spirit::qi: если в том случае мы из внешних байтовых строк парсим данные в различные внутренние структуры данных, то здесь наоборот, выводим эти данные обратно в удобочитаемом виде, в соответствии с определенными в грамматике генерации правилами вывода.
4. Spirit::Lex.  Генератор лексических анализаторов. Может использоваться как дополнение к spirit::qi, а может и не использоваться, целесообразность выделения отдельного лексического анализатора иногда находится под вопросом.

Говорить обо всём сразу сложно, да и не очень продуктивно, так что далее разговор пойдет в основном лишь об одной части: spirit::qi — генераторе парсеров из нового spirit V2, ибо всё остальное в Спирите либо довольно похоже за некоторыми небольшими отличиями на него, либо является дополнением к нему, собственно основной модуль большой и сложной библиотеки Boost.Spirit.

Начало.

Что же есть spirit::qi? Вообще говоря, генератор нисходящих рекурсивных парсеров (на русском). То есть, предвосхищая вопли любителей YACC/BISON о беспомощности этого инструмента, ждать от парсеров Спирита функционала LR/GLR (на русском: LR/GLR) парсеров просто нелепо, в конце концов, для большого перечня представимой информации вполне подойдет и такая функциональность. Зачем усложнять, если можно не усложнять? Тем более, что знакомиться с библиотекой мы будем на примере самого обычного калькулятора, эдакого "Hello, World!" в мире парсеров, ибо наверняка каждый программюга хотя бы раз в жизни либо хотел написать, либо таки написал какой-нибудь интерпретатор собственного мини-языка, недалеко уходящего по своему могуществу от того самого обычного калькулятора. Так что не будем отклоняться от традиции и ознакомимся с этим процессом, а потом уже, в следующий раз, перейдём к чему-то более интересному.

Boost.Spirit тесно связан с такими библиотеками, как boost::phoenix (который до недавнего времени являлся лишь его частью, ныне же самостоятельная boost‘овская библиотека), boost::mpl, boost::fusion, boost::proto, ну и ещё кое-чем по мелочи, и как бы я ни хотел избежать упоминания сторонних библиотек, сделать это всё-равно придётся, так что, если что, необходимые разъяснения будут даны по ходу дела.

Впрочем, пока только много слов, да мало дела, так что займёмся наконец делами. Для начала стоит упомянуть, как же именно похож язык spirit::qi на нотацию РБНФ, и в чём наблюдаются различия.

Какие нам потребуются правила для нашего калькулятора:

<expression> ::= <term> ( ('+' | '-') <term> )*
<term>       ::= <factor> ( ('*' | '/') <factor> )*
<factor>     ::= <число> | '+' <factor> | '-' <factor> | '(' <expression> ')'

Собственно, обычная элементарная грамматика с учётом операций сложения, вычитания, умножения и деления. А теперь поглядим, как будет выглядеть эта грамматика в синтаксисе spirit::qi:

expression = term >> *( '+' >> term | '-' >> term );
term       = factor >> *( '*' >> factor | '/' >> factor );
factor     = uint_ | '+' >> factor | '-' >> factor | '(' >> expression >> ')';

Какие видны отличия: в БНФ следование одного символа грамматики за другим обозначается просто пробелом, в qi же мы должны явно указывать что после чего следует с помощью оператора следования >>. Также '*' в классической РБНФ нотации — постфиксный оператор, равно как и операторы '+', '?'. Увы, в C++ нет постфиксной звёздочки или плюса, зато есть префиксные, так что эти два оператора стали из постфиксных префиксными. Оператора '?' в C++ тоже нет, вместо него используется унарный минус, то есть выражение "expr?" в РБНФ будет эквивалентно "-expr" в нотации Spirit. Оператор выбора альтернативы '|' перешел в Спирит без особых изменений, единственное, что следует иметь ввиду — альтернативы действуют по «жадному» принципу, то есть все альтернативы пробуются по очереди, от первой до последней. Есть и другие элементарные операторы, но сейчас они нам не понадобятся, так что об этом чуть позже.

Теперь о некоторых подробностях, которые следует также помнить при работе с Spirit.Qi. Как уже мог заметить читатель, основную работу в грамматике spirit::qi делают правила, которым мы присваиваем то, что должно делаться в каждом. Но из чего состоят сами правила? Вот, собственно, основные объекты, которые могут находиться в правых частях наших правил:

• Элементарные парсеры. В нашем коде таким элементарным парсером является uint_, парсер, распознающий целые беззнаковые числа. Другими примерами таких парсеров могут быть, например: int_, double_, bool_, char_ (распознающие значения типов int, double, bool и char соответственно). В основном, самые низкоуровневые нетерминалы используют последовательности таких вот элементарных сущностей, а из них уже строятся более высокоуровневые конструкции. К слову, те операторы >>, * и другие, что мы рассмотрели чуть ранее, тоже подчиняются модели парсера, но я считаю, что стоит всё-таки выделить их в отдельную категорию. Элементарные парсеры бывают с параметрами и без параметров, например, int_ распознает любые целые числа, в то время как int_(2) распознает только число 2.
• Правила. Здесь должно быть всё понятно, это мы уже видели. Основная часть правил в составных грамматиках оперируют по большей части с другими правилами.
• Грамматики. Грамматика в данном случае работает точно так же, как и обыкновенное правило, просто если мы распознаём правило, то парсинг начинается с самого первого парсера, входящего в состав правила, тогда как при распознавании с помощью грамматики парсинг начинается со стартового нетерминала. Хорошим подходом является объединение различных логических частей больших грамматик в отдельные грамматики, это, во-первых, удобно, лучше, чем возня с кучей правил, а во-вторых, такой подход благотворно влияет на время компиляции, что не актуально настолько ни для одной другой известной мне библиотеки для C++, что является самым больным местом boost::spirit.
• Таблицы символов.
• Токены лексического анализатора spirit::lex.
• Директивы парсеров. Такая штука, будучи помещённым в которую, парсер начинает плясать в соответствии с тем, что предъявляет парсеру директива. Примером может служить директива lexeme[], которая запрещает автоматическое считывание пробелов в строке для заключенного в неё парсера. Синтаксис применения директивы к парсеру такой: <directive>[<parser>].
• Операторы парсинга. Собственно, с частью из них мы уже имели возможность познакомиться. Проще говоря, это то, что определяет, каким образом, в каком порядке и как считывать имеющиеся парсеры.
• Семантические действия. Действие, выполняемое тогда, когда успешно отрабатывает тот парсер, к которому оно прицеплено. Синтаксис такой: <parser>[<semantic action>].

Таким образом, условно говоря, всё, из чего состоят правила, является парсерами, даже сами правила и грамматики подчиняются точно такой же семантике и будучи использованными в других правилах и грамматиках, могут выступать в качестве парсеров. Иными словами, всё, что входит в правые части правил, должно являться валидным парсером. Из простых парсеров мы можем строить более сложные выражения, которые, в свою очередь, тоже являются парсерами. Наверняка у кого-нибудь возникнет вопрос вроде этого: «А вот это '+' >> factor что такое тогда? Слева же не парсер, просто символьная константа!» В данном случае это вполне законно, потому что qi догадается, что '+' нужно тоже переделать в парсер, который считает плюс. А догадается он об этом по перегрузке оператора следования >>.  Как мы знаем, перегружая какой либо оператор, хотя бы один операнд должен быть «пользовательского» типа, иначе никак не получится. В данном примере таким пользовательским типом является парсер factor, так что qi внутри перегрузки оператора >> незаметно для нас переконвертирует левый операнд в парсер (если быть точным, в парсер lit), чтобы можно было скомбинировать левую и правую часть и получить новый парсер. Удобное упрощение, не таскать же каждый раз за собой эти lit(...), а?! Впрочем, иногда без этого действительно не обойтись и приходится подсказать компилятору, что от него вообще хотят. Делается это, очевидно, тогда, когда оба операнда и контролирующего оператора являются сущностями элементарного типа. Например:

assign = ':' >> '=' >> operand;

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

assign = lit(':') >> '=' >> operand;

Пример синтетический и абсолютно высосанный из пальца, так что тапками не кидать, зато суть проблемы описана явно! Поскольку lit(':') — парсер, то lit(':') >> '=' тоже вернёт парсер и всё будет просто замечательно.

Данные рассуждения применимы также и к строковым литералам, здесь всё без особых изменений.

Упоминая директиву lexeme[], я, между делом, совершенно ничего не сказал о том, как же регулируются пропуски в строках и как указать парсеру, что пропустить, а что надо считывать в настройке по-умолчанию. Устраню же теперь эту маленькую оплошность: наряду с обыкновенными парсерами в Spirit.Qi есть ещё одна концепция — парсеры пропусков. Если при объявлении правила или грамматики явно не указывать парсер пропусков, то по-умолчанию никакого пропуска симоволов не будет, строка пробегается посимвольно, со всеми пробелами и прочим «ненужным» мусором. Объявляются и пишутся они точно так же, как и обычные парсеры, только если указать такой в качестве парсера пропусков другому, то всякий раз между считанными лексемами главного парсера будет вызываться написанный парсер пропусков, который будет съедать то, что мы захотим считать незначащими символами. Поведение парсеров относительно пропускаемых символов может быть локально изменено либо некоторыми директивами парсинга (например, lexeme[], skip[], no_skip[]), либо, как вариант, явным указанием в управляющей функции phrase_parse парсера пробелов для данной грамматики.

Ближе к делу.

Парсинг осуществляется с помощью нескольких вариантов, через специальные функции: либо используя итераторы для доступа к разбираемой строке (parse, phrase_parse), либо используя интерфейс, реализованный в виде манипуляторов для потоков (match, phrase_match).

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

namespace boost { namespace spirit { namespace qi
{
    template <typename Iterator, typename Expr>
    inline bool
    parse(
        Iterator& first
      , Iterator last
      , Expr const& expr);

    template <typename Iterator, typename Expr
      , typename Attr1, typename Attr2, ..., typename AttrN>
    inline bool
    parse(
        Iterator& first
      , Iterator last
      , Expr const& expr
      , Attr1& attr1, Attr2& attr2, ..., AttrN& attrN);

    template <typename Iterator, typename Expr, typename Skipper>
    inline bool
    phrase_parse(
        Iterator& first
      , Iterator last
      , Expr const& expr
      , Skipper const& skipper
      , BOOST_SCOPED_ENUM(skip_flag) post_skip = skip_flag::postskip);

    template <typename Iterator, typename Expr, typename Skipper
      , typename Attr1, typename Attr2, ..., typename AttrN>
    inline bool
    phrase_parse(
        Iterator& first
      , Iterator last
      , Expr const& expr
      , Skipper const& skipper
      , Attr1& attr1, Attr2& attr2, ..., AttrN& attrN);

    template <typename Iterator, typename Expr, typename Skipper
      , typename Attr1, typename Attr2, ..., typename AttrN>
    inline bool
    phrase_parse(
        Iterator& first
      , Iterator last
      , Expr const& expr
      , Skipper const& skipper
      , BOOST_SCOPED_ENUM(skip_flag) post_skip
      , Attr1& attr1, Attr2& attr2, ..., AttrN& attrN);
}}}

Как видим, функция parse просто принимает итераторы в начало и конец контейнера для строки, парсер выражения и выходные атрибуты, которые вернёт парсер при успешном распознавании выражения. Функция phrase_parse дополнительно принимает кастомный skipper (парсер пропусков), разница на этом между ними и заканчивается. Есть и ещё парочка прототипов на случай, когда парсер подбирается автоматически для подставляемого выходного атрибута, но нам это будет неинтересно, так что просто забьём на этот момент. Возвращаемое значение функции parse есть true тогда и только тогда, когда парсер выражения Expr отработал успешно. Также стоит заметить, что итератор в начало строки передаётся по ссылке, это неспроста: во время парсинга этот итератор будет сдвигаться, так что для того, чтобы выяснить, есть ли полное совпадение при парсинге (была ли съедена вся строка или только её часть), одного возвращаемого значения функции parse было бы недостаточно, нужно будет ещё посмотреть, равны ли те конечные итераторы, которые мы передавали в функцию распарсивания.

Также стоит посмотреть на прототипы классов, описывающих грамматики и правила.

template <
        typename Iterator, typename T1, typename T2, typename T3
      , typename T4>
    struct grammar;

template <
        typename Iterator, typename T1, typename T2, typename T3
      , typename T4>
    struct rule;

Замечаем, что шаблонные параметры одинаковые. Теперь о том, что тут к чему: Iterator задаёт тип итератора для входных данных, которыми будет питаться грамматика или правило. Следующие четыре параметра описаны не слишком уж информативным образом, связано это с тем, что порядок передаваемых параметров может быть неоднозначным, кое-что можно поменять местами. В общем случае, каждый из параметров T1, …, T4 может быть одной из следующих сущностей:

1. Сигнатура грамматики. Записывается так: "RT(A1, A2, ..., AN)", где RT — синтезируемый атрибут грамматики, а A1, …, AN — атрибуты-параметры.
2. Список используемых локальных переменных.
3. Парсер пропусков.
4. Кодировка символов с строке.

Все эти параметры T1, …, T4 необязательные и могут быть опущены, если они не используются, так что нет нужды заботиться о каждом из них.

Всё, что нужно сделать, чтобы получить готовую к использованию грамматику, это:

1. Унаследовать нашу грамматику от qi::grammar, прототип которой мы рассматривали чуть выше.
2. Описать необходимые нетерминалы (да и вообще всё, что может понадобиться) в классе.
3. В конструкторе грамматики инициализировать сущность базового типа грамматики начальным нетерминалом (сигнатура начального нетерминала должна совпадать с сигнатурой грамматики).
4. В конструкторе же описать реализацию всех правил грамматики.

Если совсем на пальцах, то выглядеть это может примерно так (предполагается, что есть using namespace boost, остальные пространства имён квалифицировать буду явно, чтобы было ясно, где что лежит):

template <typename Iterator>
struct my_simple_grammar
	: spirit::qi::grammar<Iterator>
	{
	my_simple_grammar()
		: my_simple_grammar::base_type(start_rule)
		{
		// implementing nonterminals
		start_rule = spirit::qi::eps;
		}

	// declaring rules
	spirit::qi::rule<Iterator> start_rule;
	};

eps — парсер для эпсилон-цепочек, то есть парсер, который возвращает результат считывания строки нулевой длины, как следствие этого, никогда не проваливается.

Ок, а что подключать?

Для каждой компоненты Spirit.Qi имеется свой заголовочный файл, так, например, для функций parse, phrase_parse есть заголовок "boost/spirit/include/qi_parse.hpp", для грамматик — "boost/spirit/include/qi_grammar.hpp", для операторов — "boost/spirit/include/qi_operator.hpp" и так далее. Хоть включение лишь необходимых заголовков сделало бы картину более понятной и хорошо повлияло бы на время компиляции, мы всё же пойдем по лёгкому пути, просто будем подключать заголовок "boost/spirit/include/qi.hpp", который автоматически подключит всё сразу, дабы не отвлекаться на всякие мелочи.
Где нам понадобится phoenix, тоже можно поначалу ограничиться лишь включением заголовка "boost/spirit/inlcude/phoenix.hpp". До версии boost 1.47 по-умолчанию подключается phoenix V2, который уже немножко старый стал, а начиная с версии буста за номером 1.47, появился phoenix V3, ставший наконец самостоятельной библиотекой в семействе boost. Для того, чтобы воспользоваться третьей версией феникса, можно либо определить макрос BOOST_SPIRIT_USE_PHOENIX_V3 и включить указанный выше заголовок,  либо включать заголовок от нового феникса напрямую: "boost/phoenix/phoenix.hpp".

План дальнейших действий.

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

1. Парсер. Здесь мы просто напишем распознаватель для простых математических выражений, имея лишь одну цель — валидировать или отвергнуть входные правильные, как неправильные.
2. Интерпретатор. На данном этапе мы узнаем, что такое синтезируемые атрибуты и семантические действия и научимся их применять, вычисляя заданные выражения по ходу его разбора.
3. Компилятор. Теперь мы уже чуть больше знаем об атрибутах и семантических действиях, строим промежуточный код для стековой машины, вычисляем наше выражения с его помощью, также знакомимся с простой обработкой ошибок. Начинаем знакомство с boost::phoenix.
4. Абстрактное синтаксическое дерево. Результатом парсинга становится структура данных, представленная деревом (на русском), где будут храниться наши выражения в удобном для манипуляций виде. Также познакомимся с достаточно простым и вместе с тем очень мощным способом обхода и совершения манипуляций над деревом. Совершая обход, также вычисляем выражение.

Реализация парсера.

Наконец-то дело, сколько уже можно резину тянуть! Итак, напомню описание примитивнейшей грамматики для нашего вычислятора:

<expression> ::= <term> ( ('+' | '-') <term>)*
<term>       ::= <factor> ( ('*' | '/') <factor>)*
<factor>     ::= число | '+'<factor> | '-'<factor> | '(' <expression> ')'

Пишем код для нашей грамматики

///////////////////////////////////////////////////////////////////////////////
// calculator_grammar_simple.hpp
#ifndef __CALCULATOR_GRAMMAR_SIMPLE_HPP__
#define __CALCULATOR_GRAMMAR_SIMPLE_HPP__

#ifdef _MSC_VER
#pragma once
#endif

#include <boost/spirit/include/qi.hpp>

namespace qi = boost::spirit::qi;

template <typename Iterator>
struct calculator_simple : qi::grammar<Iterator>
	{
	calculator_simple()
		: calculator_simple::base_type(expression)
		{
		expression = term   >> *( '+' >> term   | '-' >> term );

		term	   = factor >> *( '*' >> factor | '/' >> factor );

		factor	   = qi::uint_
		           |  '(' >> expression >> ')'
		           | '+' >> factor
		           | '-' >> factor;
		}

	qi::rule<Iterator> expression, term, factor;
	};

#endif

Тестовый код для контроллера

///////////////////////////////////////////////////////////////////////////////
// main.cpp
#include <iostream>
#include <string>

#include <boost/spirit/include/qi.hpp>

#include "calculator_grammar_simple.hpp"

int main()
	{
	std::cout << "Welcome to the expression parser!\n\n";
	std::cout << "Type an expression or [q or Q] to quit\n\n";

	typedef std::string 	str_t;
	typedef str_t::iterator str_t_it;

	str_t expression;

	calculator_simple<str_t_it> calc;

	while(true)
		{
		std::getline(std::cin, expression);
		if(expression == "q" || expression == "Q") break;
		str_t_it begin = expression.begin(), end = expression.end();

		bool success = qi::parse(begin, end, calc);

		std::cout << "---------------------\n";
		if(success && begin == end)
			std::cout << "Parsing succeeded\n";
		else
			std::cout << "Parsing failed\nstopped at: "\""
		                  << str_t(begin, end) << "\"\n";
		std::cout << "---------------------\n";
		}
	}

Вот, собственно, и весь код, это было не так уж сложно, неправда ли? Код, довольно таки самокомментирующийся, так что сложностей здесь возникнуть никаких не должно: создаём объект нашей грамматики, передаём в функцию qi::parse, проверяем результат выполнения функции и смотрим конечные итераторы на равенство, вот и всё.
Таким образом, на данный момент мы уже можем распознавать строчки типа: 2+2, (1+2)*3, -1+2-4*(+10/(5+4)) и так далее. Пока что приложение сил минимальное, вот бы и дальше так… Впрочем, дальше будет тоже несложно. Стоит сказать об одной вещи, которой я не сделал: учёта пробелов нет, так что если в каком-то выражении будет пробел, результат парсинга будет отрицательный, впрочем, как окажется, данное упрощение настолько несущественно, что его не стоило бы даже брать во внимание, тем не менее мне всё же нужно было предупредить о такой мелочи, дабы избежать преждевременных вопросов по этому поводу, всему своё время.
Впрочем, кого-то, может быть, такой результат и устроил бы, но на деле мы обычно хотим нечто большее, нежели просто узнать, правильно ли написано выражение или нет, информацию ещё какую-нибудь было бы полезно извлечь что ли, хотя бы посчитать, сколько же там получается…

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