Я заметил, у разработчиков совершенно полярное отношение к библиотеке 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
