Grammar of expressions using the exponentiation operator using Boost Spirit

Question

I would like to add an exponential operator to the grammar of the expression represented in the Boost spirit samples .

The BNF grammar is as follows: (see this answer, for example: "An explicit grammar for the exposure operation" )

E -> E + T | E - T | T T -> T * F | T / F | X X -> X ^ Y | Y Y -> i | (E) 

which I translated into Boost spirit as follows:

  template <typename Iterator> struct calculator : qi::grammar<Iterator, ascii::space_type> { calculator() : calculator::base_type(expression) { qi::uint_type uint_; expression = term >> *( ('+' >> term [&do_add]) | ('-' >> term [&do_subt]) ) ; term = factor >> *( ( '*' >> factor [&do_mult]) | ('x' >> factor [&do_mult]) | ('/' >> factor [&do_div]) ); factor= expo >> *( '^' >> expo [&do_power]); expo = uint_ [&do_int] | '(' >> expression >> ')' | ('-' >> expo[&do_neg]) | ('+' >> expo) ; } qi::rule<Iterator, ascii::space_type> expression, term, factor, expo; }; 

The problem is that the ^ operator in this case is left associative, i.e. 2 ^ 3 ^ 4 incorrectly parsed as (2 ^ 3) ^ 4 instead of 2^ (3 ^ 4) .

How can I rewrite the grammar so that ^ becomes the correct associative? Obviously, the Klein star that I used in the definition of factor is incorrect. What is the method for translating grammar into Spirit code? There seems to be a way to move from left-factorized grammar to the realization of the Spirit, but I can't see it right away.

In a more formal form, the Spirit code looks like this (before I tried to add an exponent):

 E = T ( +T | -T ) * T = F ( xF | /F ) * F = int | ( E ) | +F | -F 

and left-factorized grammar

 E = TE' E' = +TE' | -TE' | epsilon T = FT' T' = *FT' | /FT' | epsilon F = ( E ) | int | +F | -F 

Answer 1

I think you can use the correct recursion to get what you want:

 factor= expo >> -('^' >> factor [&do_power]); 

I am not sure of the desired evaluation order; you might want something like

 factor= expo [&do_power] >> -('^' >> factor); 

instead.

Here is a simple test program showing how it handles 2^(6/2)^4+1 :

Change Look at LIVE on Coliru

 Type an expression...or [q or Q] to quit 2^(6/2)^4+1 push 2 push 6 push 2 divide push 4 exp exp push 1 add ------------------------- Parsing succeeded 

Full code

 #define BOOST_SPIRIT_NO_PREDEFINED_TERMINALS #define BOOST_SPIRIT_DEBUG #include <boost/spirit/include/qi.hpp> namespace client { namespace qi = boost::spirit::qi; namespace ascii = boost::spirit::ascii; /////////////////////////////////////////////////////////////////////////////// // Semantic actions ////////////////////////////////////////////////////////1/////////////////////// namespace { void do_int(int n) { std::cout << "push " << n << std::endl; } void do_add() { std::cout << "add\n"; } void do_subt() { std::cout << "subtract\n"; } void do_mult() { std::cout << "mult\n"; } void do_div() { std::cout << "divide\n"; } void do_power() { std::cout << "exp\n"; } void do_neg() { std::cout << "negate\n"; } } /////////////////////////////////////////////////////////////////////////////// // Our calculator grammar /////////////////////////////////////////////////////////////////////////////// template <typename Iterator> struct calculator : qi::grammar<Iterator, ascii::space_type> { calculator() : calculator::base_type(expression) { qi::uint_type uint_; expression = term >> *( ('+' >> term [&do_add]) | ('-' >> term [&do_subt]) ) ; term = factor >> *( ( '*' >> factor [&do_mult]) | ('x' >> factor [&do_mult]) | ('/' >> factor [&do_div]) ); factor= expo >> -('^' >> factor [&do_power]); expo = uint_ [&do_int] | '(' >> expression >> ')' | ('-' >> expo[&do_neg]) | ('+' >> expo) ; BOOST_SPIRIT_DEBUG_NODES((expression)(term)(factor)(expo)); } private: qi::rule<Iterator, ascii::space_type> expression, term, factor, expo; }; } /////////////////////////////////////////////////////////////////////////////// // Main program /////////////////////////////////////////////////////////////////////////////// int main() { std::cout << "/////////////////////////////////////////////////////////\n\n"; std::cout << "Expression parser...\n\n"; std::cout << "/////////////////////////////////////////////////////////\n\n"; std::cout << "Type an expression...or [q or Q] to quit\n\n"; typedef std::string::const_iterator iterator_type; typedef client::calculator<iterator_type> calculator; boost::spirit::ascii::space_type space; // Our skipper calculator calc; // Our grammar std::string str; while (std::getline(std::cin, str)) { if (str.empty() || str[0] == 'q' || str[0] == 'Q') break; std::string::const_iterator iter = str.begin(); std::string::const_iterator end = str.end(); bool r = phrase_parse(iter, end, calc, space); if (r && iter == end) { std::cout << "-------------------------\n"; std::cout << "Parsing succeeded\n"; std::cout << "-------------------------\n"; } else { std::string rest(iter, end); std::cout << "-------------------------\n"; std::cout << "Parsing failed\n"; std::cout << "stopped at: \" " << rest << "\"\n"; std::cout << "-------------------------\n"; } } std::cout << "Bye... :-) \n\n"; return 0; }