Я заметил, у разработчиков совершенно полярное отношение к библиотеке Boost.Spirit: либо она им жутко не нравится, либо они фанатеют от нее. Конечно, описывать грамматику на C++ – занятие на любителя. Таким любителем оказался и я, когда познакомился со Спиритом. Хочу показать, как с помощью Спирита можно довольно просто решать повседневные задачи разбора текста.
На Спирите очень удобно писать маленькие парсеры «не отходя от кассы» – прямо в C++ коде. Вот например, как вы поступите если нужно распарсить строку вида «число-число», которая задает диапазон страниц для печати? На Спирите – одна строчка:
Более того – можно ненамного сложнее создавать и парсеры побольше. В качестве примера рассмотрю парсер мини-языка, который я делал для API Яндекс.Бара. Задача была такова: для облегчения загрузки плагинов в баре используется XML, который довольно избыточный сам по себе. Но зато XML легче грузить из JavaScript-а, чем парсить произвольный формат (на JS пишутся расширения под FireFox, в том числе и Я.Бар).
Итак, что мне было нужно – имея на входе обычную инфиксную нотацию:
получить на выходе обычное AST в XML-формате:
При этом нужно было оставить возможность кроме собственно формул писать обычный XML. Но все это обилие угловых скобочек, знаков равенства, кавычек и закрывающих тегов вводило меня в уныние и я решил очистить свой язык от этих сущностей. XML я решил записывать в таком виде:
То есть вложенность задается количеством табуляций, далее идет имя XML-ноды (элемента или атрибута). За ним — определенный символ, определяющий что идет далее: текст или формула. Текст нужно передавать на выход в «голом» виде, формулы – в виде AST.
Итого у меня два парсера – один разбирает строку чтобы получить имя ноды и текст или формулу. Второй – разбирает формулы, генерируя AST. Обработку количества табов я провожу снаружи старым добрым std::find_if.
Начну с более простого – разбора строк. Строки могут быть такие:
Парсер получается очень простой:
Использование phrase_parse() вместо parse() позволило мне переложить на Спирит обработку white space (пробелов, табуляций и т.п.) внутри выражений. Это позволит писать как «tag:text», так и «tag: text». Причем мой код, как видно, освобожден от обработки пробелов – все делает phrase_parse(). Мне остается только использовать lexeme[] там, где я хочу отключить такое поведение, и raw[] там, где я хочу получить исходный текст без вырезания пробелов.
Кстати, напомню что синтаксис правил у Spirit-а такой:
То есть после каждого правила можно в квадратных скобках задать действие, которое будет выполняться, если правило «сработало».
В моем случае на каждый тип строки – свое поведение, плюс в самом начале для упрощения последующего кода я ввел отдельные правила типа id, any_string. Код, вызываемый при соответствии строки определенному правилу – указан через лямбда-функции, создаваемые с помощью boost::bind. Синтаксис bind-а очень прост:
В качестве аргументов можно указывать специальные placeholder-ы (вида _1, _2, …), указывающие куда вставлять аргументы лямбда-функции. На выходе каждого парсера получается одно значение, его и передаем в качестве аргумента нашей функции. Например, парсер
сгенерирует на выходе пару строк (в виде boost::fusion::vector<string, string>), которую я передаю в качестве второго параметра моей функции add_calculated, которая имеет такой вот интерфейс:
Первый параметр, который мне нужно передать этой функции – это ссылка на root, поэтому вызов boost::bind выглядит так:
Суммируя вместе правило и семантическое действие:
Напомню какого вида функции мне нуно парсить:
При разборе формул могут встретиться:
Для обработки результатов парсинга я создал один большой функтор и во всех семантических действиях использую его с помощью Booost.Phoenix. Как и у всех функторов, действия различаются не по именам, а по количеству и типам параметров.
Внутри своей грамматики я добавил член класса — тот самый мой функтор:
PS. Тип mini_xml – это генерируемый XML.
Правила для парсинга идентификаторов, строк, чисел и булевых констант очень просты:
Все эти правила на выходе выдают строку (например, название идентификатора). Оператор %= в конструкции “правило %= парсер” позволяет сгенерированное парсером значение передать прямо на выход парсера. Далее можно прямо в других правилах использовать их результаты:
Как видно, здесь в каждом случае вызывается парсер, например, quoted_string, а далее его значение используется для вызова функтора op. В первом случае (правило string) на вход функтора придет: в качестве первого аргумента – то значение, которое формируется (в моем случае – элемент дерева XML), в качестве второго – результат работы парсера quoted_string, в третьем – срока “string”. И уже функтор сделает все необходимые действия с XML-деревом.
Определение функции не намного сложнее – в частности брагодаря тому, что я генерирую XML. Параметры функции достаточно просто «прикрепить» к xml-узлу функции в качестве «детей»:
Выражение «parameter [op(_val, _1)]» как раз прикрепляет детей к функции: в функтор op передается родитель (узел функции, который только что заполнен с помощью «op(_val, _1, compiler::function())») и «ребенок» (узел параметра, который сгенерировал парсер parameter).
Итого, без учета бинарных и тернарных операций (операций с 2 и 3 аргументами, такие как */+-?:) получается следующее правило:
При обработке операций не следует забывать об их приоритете. Его легко реализовать «вкладывая» определения одной операции в определение другой:
В данном случае функции умножения и деления распарсятся раньше, чем сложение и вычитание, так как умножение «вложено» в сложение. Это произойдет потому, что для сложения нужно разобрать сначала все внутренние правила, в том числе умножение, которое я вложил внутрь. Собственно, что и требовалось.
Весь исходный код можно взять здесь: http://download.yandex.ru/bar/tools/easierxb-src.zip (внутри архива – проект для сборки под Windows и MacOS).
Пример входного файла: http://download.yandex.ru/bar/tools/easierxb-example.zip
Простая задача – как два пальца
На Спирите очень удобно писать маленькие парсеры «не отходя от кассы» – прямо в 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</f:value> </f:mul> <xpath> <concat> number(//hello[id='<value-of name="id"/>') </f:concat> <value-of name="World"/> </f:xpath> </f: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