09 марта 2010

Boost.Spirit in practice

Я заметил, у разработчиков совершенно полярное отношение к библиотеке Boost.Spirit: либо она им жутко не нравится, либо они фанатеют от нее. Конечно, описывать грамматику на C++ – занятие на любителя. Таким любителем оказался и я, когда познакомился со Спиритом. Хочу показать, как с помощью Спирита можно довольно просто решать повседневные задачи разбора текста.

Простая задача – как два пальца

На Спирите очень удобно писать маленькие парсеры «не отходя от кассы» – прямо в C++ коде. Вот например, как вы поступите если нужно распарсить строку вида «число-число», которая задает диапазон страниц для печати? На Спирите – одна строчка:

bool ok = parse(First, Last, (uint_ >> L".." >> uint_), MinMax) && (First == Last));

Посложнее…

Более того – можно ненамного сложнее создавать и парсеры побольше. В качестве примера рассмотрю парсер мини-языка, который я делал для API Яндекс.Бара. Задача была такова: для облегчения загрузки плагинов в баре используется XML, который довольно избыточный сам по себе. Но зато XML легче грузить из JavaScript-а, чем парсить произвольный формат (на JS пишутся расширения под FireFox, в том числе и Я.Бар).

Итак, что мне было нужно – имея на входе обычную инфиксную нотацию:

Hello * Interval * 60 + xpath("number(//hello[id='" # id # "')", World)

получить на выходе обычное AST в XML-формате:

<add>
<mul>
<value-of name="Hello"/>
<value-of name="Interval"/>
<value type="number">60</value>
</mul>
<xpath>
<concat>
number(//hello[id='<value-of name="id"/>')
</concat>
<value-of name="World"/>
</xpath>
</add>

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

root
child1: текст
@attribute1: text
@attribute2 = формула
grandchild
grand-grand-child
child2 = формула

То есть вложенность задается количеством табуляций, далее идет имя XML-ноды (элемента или атрибута). За ним - определенный символ, определяющий что идет далее: текст или формула. Текст нужно передавать на выход в «голом» виде, формулы – в виде AST.

Итого у меня два парсера – один разбирает строку чтобы получить имя ноды и текст или формулу. Второй – разбирает формулы, генерируя AST. Обработку количества табов я провожу снаружи старым добрым std::find_if.

Парсинг строки. Semantic actions – через Boost.Bind

Начну с более простого – разбора строк. Строки могут быть такие:

tag
tag: тест
tag = формула
= формула
name :: (instance|widget) (setting|variable)
name := формула

Парсер получается очень простой:

bool parse_definition(string::const_iterator &iter, string::const_iterator end, mini_xml &root)
{
qi::rule<string::const_iterator, string(), space_type> id, any_string, scope, type;
id %= raw[lexeme[-char_('@') >> alpha >> *(alnum | '_' | '-' | (':' >> alnum))]];
any_string %= lexeme[+char_];
scope %= raw[lit("widget") | lit("instance")];
type %= raw[lit("setting") | lit("variable")];

return phrase_parse(iter, end,
(
(id >> "::" >> scope >> type) [bind(&add_identifier, ref(root), _1)] |
(id >> ":=" >> any_string) [bind(&add_definition, ref(root), _1)] |
(id >> ':' >> any_string) [bind(&add_raw, ref(root), _1)] |
(id >> '=' >> any_string) [bind(&add_calculated, ref(root), _1)] |
( '=' >> any_string) [bind(&add_expression, ref(root), _1)] |
id [bind(&add_subnode, ref(root), _1)]
),
space) && (iter == end);
}

Использование phrase_parse() вместо parse() позволило мне переложить на Спирит обработку white space (пробелов, табуляций и т.п.) внутри выражений. Это позволит писать как «tag:text», так и «tag : text». Причем мой код, как видно, освобожден от обработки пробелов – все делает phrase_parse(). Мне остается только использовать lexeme[] там, где я хочу отключить такое поведение, и raw[] там, где я хочу получить исходный текст без вырезания пробелов.

Кстати, напомню что синтаксис правил у Spirit-а такой:

rule [semantic_action]

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

В моем случае на каждый тип строки – свое поведение, плюс в самом начале для упрощения последующего кода я ввел отдельные правила типа id, any_string. Код, вызываемый при соответствии строки определенному правилу – указан через лямбда-функции, создаваемые с помощью boost::bind. Синтаксис bind-а очень прост:

boost::bind(функция, аргумент, аргумент, ...)

В качестве аргументов можно указывать специальные placeholder-ы (вида _1, _2, …), указывающие куда вставлять аргументы лямбда-функции. На выходе каждого парсера получается одно значение, его и передаем в качестве аргумента нашей функции. Например, парсер

id >> '=' >> any_string

сгенерирует на выходе пару строк (в виде boost::fusion::vector<string, string>), которую я передаю в качестве второго параметра моей функции add_calculated, которая имеет такой вот интерфейс:

void add_calculated(mini_xml &root, fusion::vector<string, string> const &);

Первый параметр, который мне нужно передать этой функции – это ссылка на root, поэтому вызов boost::bind выглядит так:

bind(&add_calculated, ref(root), _1)

Суммируя вместе правило и семантическое действие:

(id >> '=' >> any_string) [bind(&add_calculated, ref(root), _1)]

Парсинг формулы. Semantic actions – через Boost.Phoenix

Напомню какого вида функции мне нуно парсить:

Hello * Interval * 60 + xpath("number(//hello[id='" # id # "')", World)

При разборе формул могут встретиться:

  • числа
  • булевы константы (true, false)
  • строки (в кавычках)
  • идентификаторы
  • вызовы функций
  • операции

Для обработки результатов парсинга я создал один большой функтор и во всех семантических действиях использую его с помощью Booost.Phoenix. Как и у всех функторов, действия различаются не по именам, а по количеству и типам параметров.

struct compiler
{
// метки нужны для того, чтобы отличать друг от друга функции с одинаковыми аргументами
struct identifier{}; // метка «идентификатор»
struct function{}; // метка «функция»
struct parameter{}; // метка «параметр»
struct assignment{}; // метка «присваивание»

void operator()(mini_xml &node, std::string const &id, identifier) const; // идентификатор
void operator()(mini_xml &node, std::string const &id, function) const; // функция
void operator()(mini_xml &node, std::string const &id, parameter) const; // параметр функции
void operator()(mini_xml &node, std::string const &id, assignment) const; // присваивание
void operator()(mini_xml &node, std::string const &value, char const *type) const; // <value>
void operator()(mini_xml &node, mini_xml const &subnode) const;
void operator()(mini_xml &node, mini_xml const &subnode, std::string const &id, bool allow_join = false) const;
};

Внутри своей грамматики я добавил член класса - тот самый мой функтор:

template <typename Iterator>
struct expression_grammar : grammar<Iterator, mini_xml(), space_type>
{
expression_grammar() : expression_grammar::base_type(expressions)
{
expressions = ...;
}

rule<Iterator, mini_xml(), space_type> expressions, ...;
boost::phoenix::function<compiler> op;
}

PS. Тип mini_xml – это генерируемый XML.

Правила для парсинга идентификаторов, строк, чисел и булевых констант очень просты:

id %= raw[lexeme[alpha >> *(alnum | '_' | ('-' >> alnum))]];
quoted_string %= lexeme['"' >> *(char_ - '"') >> '"'];
numeric_value %= raw[lexeme[-(char_('+') | char_('-')) >> +digit >> -(char_('.') >> +digit)]];
boolean_value %= raw[lit("true") | lit("false")];

Все эти правила на выходе выдают строку (например, название идентификатора). Оператор %= в конструкции “правило %= парсер” позволяет сгенерированное парсером значение передать прямо на выход парсера. Далее можно прямо в других правилах использовать их результаты:

string = quoted_string [op(_val, _1, "string")];
number = numeric_value [op(_val, _1, "number")];
boolean = boolean_value [op(_val, _1, "bool")];
empty = lit("empty") [op(_val, std::string(), "empty")];
identifier = id [op(_val, _1, compiler::identifier())];

Как видно, здесь в каждом случае вызывается парсер, например, quoted_string, а далее его значение используется для вызова функтора op. В первом случае (правило string) на вход функтора придет: в качестве первого аргумента – то значение, которое формируется (в моем случае – элемент дерева XML), в качестве второго – результат работы парсера quoted_string, в третьем – срока “string”. И уже функтор сделает все необходимые действия с XML-деревом.

Определение функции не намного сложнее – в частности брагодаря тому, что я генерирую XML. Параметры функции достаточно просто «прикрепить» к xml-узлу функции в качестве «детей»:

function =
id [op(_val, _1, compiler::function())]
>> '('
>> -(parameter [op(_val, _1)] % ',')
>> ')';

Выражение «parameter [op(_val, _1)]» как раз прикрепляет детей к функции: в функтор op передается родитель (узел функции, который только что заполнен с помощью «op(_val, _1, compiler::function())») и «ребенок» (узел параметра, который сгенерировал парсер parameter).

Итого, без учета бинарных и тернарных операций (операций с 2 и 3 аргументами, такие как */+-?:) получается следующее правило:

factor =
function [_val = _1]
| boolean [_val = _1]
| empty [_val = _1]
| identifier [_val = _1]
| string [_val = _1]
| number [_val = _1]
| ('(' >> expression [_val = _1] >> ')')
| (lit('!') [op(_val, "not", compiler::function())] >> factor [op(_val, _1)])
| (lit('-') [op(_val, "neg", compiler::function())] >> factor [op(_val, _1)])
| ('+' >> factor [_val = _1])
;

При обработке операций не следует забывать об их приоритете. Его легко реализовать «вкладывая» определения одной операции в определение другой:

addition =
multiplication [_val = _1]
>> *( ('+' >> multiplication [op(_val, _1, "add", true)])
| ('-' >> multiplication [op(_val, _1, "sub", true)])
)
;

multiplication =
factor [_val = _1]
>> *( ('*' >> factor [op(_val, _1, "mul", true)])
| ('/' >> factor [op(_val, _1, "div", true)])
)
;

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

Суммируя все вместе

Весь исходный код можно взять здесь: http://download.yandex.ru/bar/tools/easierxb-src.zip (внутри архива – проект для сборки под Windows и MacOS).

Пример входного файла: http://download.yandex.ru/bar/tools/easierxb-example.zip

5 комментариев:

strelok комментирует...

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

strelok комментирует...
Этот комментарий был удален автором.
Raider комментирует...

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

Alex Ott комментирует...

спирит очень удобен во время прототипирования, но на сложных грамматиках он либо убивает компилятор (у меня было такое на 1-м спирите + gcc 3.x 64-bit), либо объем исполняемого файла становится слишком большим.
я сейчас остановился на комбинированном решении - adhoc-задачи и прототипы пишу на спирите, а потом, если нужно переписываю на собственную комбинаторную библиотеку (plain C), а-ля parsec в хаскеле (очень приблизительное сравнение)...

GooRoo комментирует...

Прочитал Вашу статью, вдохновился и начал использовать Spirit.Qi. Есть трабла.

В общем, пишу небольшой парсер одного формата. Имеется текстовый файл, представленный блоками вида
[SOME BLOCK]
SomeProperty=Blabla
AnotherProperty=Blablabla
[END-SOME BLOCK]

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

Итак, унаследовал qi::grammar, описал правила для разбора. Для каждого блока создаётся объект соответствующей ему структурки. На выходе получаю объект структуры со служебной инфой и вектором «объектов» (для каждого блока).

Так вот если входной текстовый файл имеет размер килобайт триста, то разбирает моментально, но уже на килобайтах 600 парсер может уйти в раздумья минуты на 3-4. А мне надо 10-метровый файл распарсить. В чём может быть проблема?