Intereting Posts
Программа пропускает Getline () без ввода пользовательского ввода GDB жалуется на отсутствие рейза. Какая самая эффективная функция рекурсивной первичной проверки хвоста известна? log2 целого числа, которое является степенью 2 Изображение меняет форму при отображении Почему инициализация внешней переменной локально внутри функции дает ошибку? Ошибка компиляции C ++ при сопоставлении sizeof () в препроцессоре #if trim не входит в стандартную библиотеку c / c ++? функция друга std :: make_shared () в Visual Studio 2010 (не Boost) C ++ не может установить ссылку на дескриптор на родительский объект – круговые включения или неопределенные ошибки типа Два вопроса о встроенных функциях в C ++ «Std :: bad_alloc»: я использую слишком много памяти? В Visual Studio 2010 почему создается .NETFramework, файл Version = v4.0.AssemblyAttributes.cpp, и могу ли я отключить это? #error Пожалуйста, используйте ключ / MD для сборки _AFXDLL Прочитайте текстовый файл в массиве символов. C ++ ifstream

Использование атрибутов токена lexer в грамматических правилах с Lex и Qi от Boost.Spirit

Рассмотрим следующий код:

#include  #include  #include  #include  #include  #include  #include  #include  namespace lex = boost::spirit::lex; namespace qi = boost::spirit::qi; namespace phoenix = boost::phoenix; struct operation { enum type { add, sub, mul, div }; }; template class expression_lexer : public lex::lexer { public: typedef lex::token_def operator_token_type; typedef lex::token_def value_token_type; typedef lex::token_def variable_token_type; typedef lex::token_def parenthesis_token_type; typedef std::pair parenthesis_token_pair_type; typedef lex::token_def whitespace_token_type; expression_lexer() : operator_add('+'), operator_sub('-'), operator_mul("[x*]"), operator_div("[:/]"), value("\\d+(\\.\\d+)?"), variable("%(\\w+)"), parenthesis({ std::make_pair(parenthesis_token_type('('), parenthesis_token_type(')')), std::make_pair(parenthesis_token_type('['), parenthesis_token_type(']')) }), whitespace("[ \\t]+") { this->self += operator_add [lex::_val = operation::add] | operator_sub [lex::_val = operation::sub] | operator_mul [lex::_val = operation::mul] | operator_div [lex::_val = operation::div] | value | variable [lex::_val = phoenix::construct(lex::_start + 1, lex::_end)] | whitespace [lex::_pass = lex::pass_flags::pass_ignore] ; std::for_each(parenthesis.cbegin(), parenthesis.cend(), [&](parenthesis_token_pair_type const& token_pair) { this->self += token_pair.first | token_pair.second; } ); } operator_token_type operator_add; operator_token_type operator_sub; operator_token_type operator_mul; operator_token_type operator_div; value_token_type value; variable_token_type variable; std::vector parenthesis; whitespace_token_type whitespace; }; template class expression_grammar : public qi::grammar { public: template explicit expression_grammar(Tokens const& tokens) : expression_grammar::base_type(start) { start %= expression >> qi::eoi; expression %= sum_operand >> -(sum_operator >> expression); sum_operator %= tokens.operator_add | tokens.operator_sub; sum_operand %= fac_operand >> -(fac_operator >> sum_operand); fac_operator %= tokens.operator_mul | tokens.operator_div; if(!tokens.parenthesis.empty()) fac_operand %= parenthesised | terminal; else fac_operand %= terminal; terminal %= tokens.value | tokens.variable; if(!tokens.parenthesis.empty()) { parenthesised %= tokens.parenthesis.front().first >> expression >> tokens.parenthesis.front().second; std::for_each(tokens.parenthesis.cbegin() + 1, tokens.parenthesis.cend(), [&](typename Tokens::parenthesis_token_pair_type const& token_pair) { parenthesised %= parenthesised.copy() | (token_pair.first >> expression >> token_pair.second); } ); } } private: qi::rule start; qi::rule expression; qi::rule sum_operand; qi::rule sum_operator; qi::rule fac_operand; qi::rule fac_operator; qi::rule terminal; qi::rule parenthesised; }; int main() { typedef lex::lexertl::token<std::string::const_iterator, boost::mpl::vector> token_type; typedef expression_lexer<lex::lexertl::actor_lexer> expression_lexer_type; typedef expression_lexer_type::iterator_type expression_lexer_iterator_type; typedef expression_grammar expression_grammar_type; expression_lexer_type lexer; expression_grammar_type grammar(lexer); while(std::cin) { std::string line; std::getline(std::cin, line); std::string::const_iterator first = line.begin(); std::string::const_iterator const last = line.end(); bool const result = lex::tokenize_and_parse(first, last, lexer, grammar); if(!result) std::cout <" << std::string(first, last) << "<" << std::endl; else { if(first != last) std::cout <" << std::string(first, last) << "<" << std::endl; else std::cout << "Parsing succeeded!" << std::endl; } } } 

Это простой синтаксический анализатор для арифметических выражений со значениями и переменными. Он создается с помощью expression_lexer для извлечения токенов, а затем с помощью expression_grammar для анализа токенов.

Использование lexer для такого маленького случая может показаться излишним и, вероятно, одним. Но это стоимость упрощенного примера. Также обратите внимание, что использование lexer позволяет легко определять маркеры с регулярным выражением, в то время как это позволяет легко определить их внешним кодом (и, в частности, предоставленной пользователем конфигурацией). В приведенном примере не было бы вообще никаких проблем читать определение токенов из внешнего файла конфигурации и, например, разрешать пользователю изменять переменные от %name до $name .

Код работает нормально (проверено на Visual Studio 2013 с Boost 1.61).

У expression_lexer есть атрибуты, прикрепленные к токенам. Я думаю, они работают, так как они компилируются. Но я не знаю, как проверить.

В конечном счете, я хотел бы, чтобы грамматика построила мне std::vector с реверсивным польский обозначением выражения. (Где каждый элемент будет boost::variant по любому operator::type или double или std::string .)

Однако проблема заключается в том, что я не использовал атрибуты токена в моем expression_grammar . Например, если вы попытаетесь изменить sum_operator следующим образом:

 qi::rule sum_operator; 

вы получите ошибку компиляции. Я ожидал, что это сработает с момента operation::type является атрибутом для operator_add и operator_sub а также для их альтернативы. И все же он не компилируется. Судя по ошибке в assign_to_attribute_from_iterators кажется, что парсер пытается построить значение атрибута непосредственно из диапазона входных streamов. Это означает, что он игнорирует [lex::_val = operation::add] указанный мной в моем лексере.

Изменяя это на

 qi::rule sum_operator; 

тоже не помогло.

Также я попытался изменить определение

 sum_operator %= (tokens.operator_add | tokens.operator_sub) [qi::_val = qi::_1]; 

тоже не помогло.

Как обойти это? Я знаю, что могу использовать symbols из Ци. Но я хочу, чтобы лексер упрощал настройку регулярных выражений для токенов. Я мог бы также расширить assign_to_attribute_from_iterators как описано в документации, но этот вид двойной работы. Я думаю, я мог бы также пропустить атрибуты на lexer и просто иметь их на грамматике. Но это снова не очень хорошо работает с гибкостью в токенах variable (в моем фактическом случае там немного больше логики, так что она настраивается также, какая часть токена формирует фактическое имя переменной – в то время как здесь фиксируется просто пропустить первый символ). Что-нибудь еще?


Также побочный вопрос – может быть, кто-нибудь знает. Есть ли способ захватить группы регулярного выражения токена из действия токенов? Чтобы вместо

 variable [lex::_val = phoenix::construct(lex::_start + 1, lex::_end)] 

вместо этого я мог бы сделать строку из группы захвата и так легко обрабатывать форматы, как $var$ .


Под редакцией! Я улучшил пробелы, пропуская по выводам шкипера Whitespace при использовании Boost.Spirit Qi и Lex . Это упрощение, которое не затрагивает вопросы, заданные здесь.

Хорошо, вот мой подход к требованию RPN. Я сильно одобряю естественное (автоматическое) распространение атрибутов над семантическими действиями (см. Boost Spirit: «Семантические действия злы»? )

Я рассматриваю другие варианты (uglifying) оптимизации. Вы можете сделать это, если вы довольны общим дизайном и не возражаете, что это будет сложнее поддерживать 🙂

Live On Coliru

Помимо образца из моего комментария, который вы уже изучили, я добавил, что шаг преобразования RPN:

 namespace RPN { using cell = boost::variant; using rpn_stack = std::vector; struct transform : boost::static_visitor<> { void operator()(rpn_stack& stack, AST::expression const& e) const { boost::apply_visitor(boost::bind(*this, boost::ref(stack), ::_1), e); } void operator()(rpn_stack& stack, AST::bin_expr const& e) const { (*this)(stack, e.lhs); (*this)(stack, e.rhs); stack.push_back(e.op); } void operator()(rpn_stack& stack, AST::value const& v) const { stack.push_back(v); } void operator()(rpn_stack& stack, AST::variable const& v) const { stack.push_back(v); } }; } 

Это все! Используйте его так, например:

 RPN::transform compiler; RPN::rpn_stack program; compiler(program, expr); for (auto& instr : program) { std::cout << instr << " "; } 

Что делает вывод:

 Parsing success: (3 + (8 * 9)) 3 8 9 * + 

Полный список

Live On Coliru

 //#define BOOST_SPIRIT_DEBUG #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  namespace lex = boost::spirit::lex; namespace qi = boost::spirit::qi; namespace phoenix = boost::phoenix; struct operation { enum type { add, sub, mul, div }; friend std::ostream& operator<<(std::ostream& os, type op) { switch (op) { case type::add: return os << "+"; case type::sub: return os << "-"; case type::mul: return os << "*"; case type::div: return os << "/"; } return os << "<" << static_cast(op) << ">"; } }; template class expression_lexer : public lex::lexer { public: //typedef lex::token_def operator_token_type; typedef lex::token_def operator_token_type; typedef lex::token_def value_token_type; typedef lex::token_def variable_token_type; typedef lex::token_def parenthesis_token_type; typedef std::pair parenthesis_token_pair_type; typedef lex::token_def whitespace_token_type; expression_lexer() : operator_add('+'), operator_sub('-'), operator_mul("[x*]"), operator_div("[:/]"), value("\\d+(\\.\\d+)?"), variable("%(\\w+)"), parenthesis({ std::make_pair(parenthesis_token_type('('), parenthesis_token_type(')')), std::make_pair(parenthesis_token_type('['), parenthesis_token_type(']')) }), whitespace("[ \\t]+") { this->self += operator_add [lex::_val = operation::add] | operator_sub [lex::_val = operation::sub] | operator_mul [lex::_val = operation::mul] | operator_div [lex::_val = operation::div] | value | variable [lex::_val = phoenix::construct(lex::_start + 1, lex::_end)] | whitespace [lex::_pass = lex::pass_flags::pass_ignore] ; std::for_each(parenthesis.cbegin(), parenthesis.cend(), [&](parenthesis_token_pair_type const& token_pair) { this->self += token_pair.first | token_pair.second; } ); } operator_token_type operator_add; operator_token_type operator_sub; operator_token_type operator_mul; operator_token_type operator_div; value_token_type value; variable_token_type variable; std::vector parenthesis; whitespace_token_type whitespace; }; namespace AST { using operation = operation::type; using value = double; using variable = std::string; struct bin_expr; using expression = boost::variant >; struct bin_expr { expression lhs, rhs; operation op; friend std::ostream& operator<<(std::ostream& os, bin_expr const& be) { return os << "(" << be.lhs << " " << be.op << " " << be.rhs << ")"; } }; } BOOST_FUSION_ADAPT_STRUCT(AST::bin_expr, lhs, op, rhs) template class expression_grammar : public qi::grammar { public: template explicit expression_grammar(Tokens const& tokens) : expression_grammar::base_type(start) { start = expression >> qi::eoi; bin_sum_expr = sum_operand >> sum_operator >> expression; bin_fac_expr = fac_operand >> fac_operator >> sum_operand; expression = bin_sum_expr | sum_operand; sum_operand = bin_fac_expr | fac_operand; sum_operator = tokens.operator_add >> qi::attr(AST::operation::add) | tokens.operator_sub >> qi::attr(AST::operation::sub); fac_operator = tokens.operator_mul >> qi::attr(AST::operation::mul) | tokens.operator_div >> qi::attr(AST::operation::div); if(tokens.parenthesis.empty()) { fac_operand = terminal; } else { fac_operand = parenthesised | terminal; parenthesised = tokens.parenthesis.front().first >> expression >> tokens.parenthesis.front().second; std::for_each(tokens.parenthesis.cbegin() + 1, tokens.parenthesis.cend(), [&](typename Tokens::parenthesis_token_pair_type const& token_pair) { parenthesised = parenthesised.copy() | (token_pair.first >> expression >> token_pair.second); }); } terminal = tokens.value | tokens.variable; BOOST_SPIRIT_DEBUG_NODES( (start) (expression) (bin_sum_expr) (bin_fac_expr) (fac_operand) (terminal) (parenthesised) (sum_operand) (sum_operator) (fac_operator) ); } private: qi::rule start; qi::rule expression; qi::rule sum_operand; qi::rule fac_operand; qi::rule terminal; qi::rule parenthesised; qi::rule sum_operator; qi::rule fac_operator; // extra rules to help with AST creation qi::rule bin_sum_expr; qi::rule bin_fac_expr; }; namespace RPN { using cell = boost::variant; using rpn_stack = std::vector; struct transform : boost::static_visitor<> { void operator()(rpn_stack& stack, AST::expression const& e) const { boost::apply_visitor(boost::bind(*this, boost::ref(stack), ::_1), e); } void operator()(rpn_stack& stack, AST::bin_expr const& e) const { (*this)(stack, e.lhs); (*this)(stack, e.rhs); stack.push_back(e.op); } void operator()(rpn_stack& stack, AST::value const& v) const { stack.push_back(v); } void operator()(rpn_stack& stack, AST::variable const& v) const { stack.push_back(v); } }; } int main() { typedef lex::lexertl::token> token_type; typedef expression_lexer> expression_lexer_type; typedef expression_lexer_type::iterator_type expression_lexer_iterator_type; typedef expression_grammar expression_grammar_type; expression_lexer_type lexer; expression_grammar_type grammar(lexer); RPN::transform compiler; std::string line; while(std::getline(std::cin, line) && !line.empty()) { std::string::const_iterator first = line.begin(); std::string::const_iterator const last = line.end(); AST::expression expr; bool const result = lex::tokenize_and_parse(first, last, lexer, grammar, expr); if(!result) std::cout << "Parsing failed!\n"; else { std::cout << "Parsing success: " << expr << "\n"; RPN::rpn_stack program; compiler(program, expr); for (auto& instr : program) { std::cout << instr << " "; } } if(first != last) std::cout << "Remainder: >" << std::string(first, last) << "<\n"; } } к //#define BOOST_SPIRIT_DEBUG #include  #include  #include  #include  #include  #include  #include  #include  #include  #include  namespace lex = boost::spirit::lex; namespace qi = boost::spirit::qi; namespace phoenix = boost::phoenix; struct operation { enum type { add, sub, mul, div }; friend std::ostream& operator<<(std::ostream& os, type op) { switch (op) { case type::add: return os << "+"; case type::sub: return os << "-"; case type::mul: return os << "*"; case type::div: return os << "/"; } return os << "<" << static_cast(op) << ">"; } }; template class expression_lexer : public lex::lexer { public: //typedef lex::token_def operator_token_type; typedef lex::token_def operator_token_type; typedef lex::token_def value_token_type; typedef lex::token_def variable_token_type; typedef lex::token_def parenthesis_token_type; typedef std::pair parenthesis_token_pair_type; typedef lex::token_def whitespace_token_type; expression_lexer() : operator_add('+'), operator_sub('-'), operator_mul("[x*]"), operator_div("[:/]"), value("\\d+(\\.\\d+)?"), variable("%(\\w+)"), parenthesis({ std::make_pair(parenthesis_token_type('('), parenthesis_token_type(')')), std::make_pair(parenthesis_token_type('['), parenthesis_token_type(']')) }), whitespace("[ \\t]+") { this->self += operator_add [lex::_val = operation::add] | operator_sub [lex::_val = operation::sub] | operator_mul [lex::_val = operation::mul] | operator_div [lex::_val = operation::div] | value | variable [lex::_val = phoenix::construct(lex::_start + 1, lex::_end)] | whitespace [lex::_pass = lex::pass_flags::pass_ignore] ; std::for_each(parenthesis.cbegin(), parenthesis.cend(), [&](parenthesis_token_pair_type const& token_pair) { this->self += token_pair.first | token_pair.second; } ); } operator_token_type operator_add; operator_token_type operator_sub; operator_token_type operator_mul; operator_token_type operator_div; value_token_type value; variable_token_type variable; std::vector parenthesis; whitespace_token_type whitespace; }; namespace AST { using operation = operation::type; using value = double; using variable = std::string; struct bin_expr; using expression = boost::variant >; struct bin_expr { expression lhs, rhs; operation op; friend std::ostream& operator<<(std::ostream& os, bin_expr const& be) { return os << "(" << be.lhs << " " << be.op << " " << be.rhs << ")"; } }; } BOOST_FUSION_ADAPT_STRUCT(AST::bin_expr, lhs, op, rhs) template class expression_grammar : public qi::grammar { public: template explicit expression_grammar(Tokens const& tokens) : expression_grammar::base_type(start) { start = expression >> qi::eoi; bin_sum_expr = sum_operand >> sum_operator >> expression; bin_fac_expr = fac_operand >> fac_operator >> sum_operand; expression = bin_sum_expr | sum_operand; sum_operand = bin_fac_expr | fac_operand; sum_operator = tokens.operator_add >> qi::attr(AST::operation::add) | tokens.operator_sub >> qi::attr(AST::operation::sub); fac_operator = tokens.operator_mul >> qi::attr(AST::operation::mul) | tokens.operator_div >> qi::attr(AST::operation::div); if(tokens.parenthesis.empty()) { fac_operand = terminal; } else { fac_operand = parenthesised | terminal; parenthesised = tokens.parenthesis.front().first >> expression >> tokens.parenthesis.front().second; std::for_each(tokens.parenthesis.cbegin() + 1, tokens.parenthesis.cend(), [&](typename Tokens::parenthesis_token_pair_type const& token_pair) { parenthesised = parenthesised.copy() | (token_pair.first >> expression >> token_pair.second); }); } terminal = tokens.value | tokens.variable; BOOST_SPIRIT_DEBUG_NODES( (start) (expression) (bin_sum_expr) (bin_fac_expr) (fac_operand) (terminal) (parenthesised) (sum_operand) (sum_operator) (fac_operator) ); } private: qi::rule start; qi::rule expression; qi::rule sum_operand; qi::rule fac_operand; qi::rule terminal; qi::rule parenthesised; qi::rule sum_operator; qi::rule fac_operator; // extra rules to help with AST creation qi::rule bin_sum_expr; qi::rule bin_fac_expr; }; namespace RPN { using cell = boost::variant; using rpn_stack = std::vector; struct transform : boost::static_visitor<> { void operator()(rpn_stack& stack, AST::expression const& e) const { boost::apply_visitor(boost::bind(*this, boost::ref(stack), ::_1), e); } void operator()(rpn_stack& stack, AST::bin_expr const& e) const { (*this)(stack, e.lhs); (*this)(stack, e.rhs); stack.push_back(e.op); } void operator()(rpn_stack& stack, AST::value const& v) const { stack.push_back(v); } void operator()(rpn_stack& stack, AST::variable const& v) const { stack.push_back(v); } }; } int main() { typedef lex::lexertl::token> token_type; typedef expression_lexer> expression_lexer_type; typedef expression_lexer_type::iterator_type expression_lexer_iterator_type; typedef expression_grammar expression_grammar_type; expression_lexer_type lexer; expression_grammar_type grammar(lexer); RPN::transform compiler; std::string line; while(std::getline(std::cin, line) && !line.empty()) { std::string::const_iterator first = line.begin(); std::string::const_iterator const last = line.end(); AST::expression expr; bool const result = lex::tokenize_and_parse(first, last, lexer, grammar, expr); if(!result) std::cout << "Parsing failed!\n"; else { std::cout << "Parsing success: " << expr << "\n"; RPN::rpn_stack program; compiler(program, expr); for (auto& instr : program) { std::cout << instr << " "; } } if(first != last) std::cout << "Remainder: >" << std::string(first, last) << "<\n"; } }