How to add support for the exponential operator to one of the boost::spirit calculators?

Question

I am trying to add the exponential operator to this boost::spirit calculator example, whose grammar is the one below. Note that expressions like "-2^2^3" must be parsed as "-(2^(2^3))" == -256.

    expr =
        equality_expr.alias()
        ;

    equality_expr =
            relational_expr
        >> *(equality_op > relational_expr)
        ;

    relational_expr =
            logical_expr
        >> *(relational_op > logical_expr)
        ;

    logical_expr =
            additive_expr
        >> *(logical_op > additive_expr)
        ;

    additive_expr =
            multiplicative_expr
        >> *(additive_op > multiplicative_expr)
        ;

    multiplicative_expr =
            unary_expr
        >> *(multiplicative_op > unary_expr)
        ;

    unary_expr =
            primary_expr
        |   (unary_op > primary_expr)
        ;

    primary_expr =
            uint_
        |   identifier
        |   bool_
        |   '(' > expr > ')'
        ;

    identifier =
            !keywords
        >>  raw[lexeme[(alpha | '_') >> *(alnum | '_')]]
        ;

After having read the documentation, my understanding is that I have to insert the following exponential_expr rule to the grammar for it to parse exponential operations with the proper right-to-left associativity:

    multiplicative_expr =
            exponential_expr
        >> *(multiplicative_op > exponential_expr)
        ;

    exponential_expr =
            unary_expr
        >> !(exponential_op >> exponential_expr)
        ;

Where the rules are:

    qi::rule<Iterator, ast::expression(), ascii::space_type>
    expr, equality_expr, relational_expr,
    logical_expr, additive_expr, multiplicative_expr, exponential_expr
    ;

    qi::rule<Iterator, ast::operand(), ascii::space_type>
    unary_expr, primary_expr
    ;

    qi::rule<Iterator, ast::function_call(), ascii::space_type >
    function_call
    ;

    qi::rule<Iterator, std::list<ast::expression>(), ascii::space_type >
    argument_list
    ;

    qi::rule<Iterator, std::string(), ascii::space_type>
    identifier
    ;

    qi::symbols<char, ast::optoken>
    equality_op, relational_op, logical_op,
    additive_op, multiplicative_op, unary_op, exponential_op
    ;

    qi::symbols<char>
    keywords
    ;

The problem I am having now is that the program fails to compile, as the AST (ast.hpp) must be also modified accordingly, but I don't exactly now how. Do you have any idea?

This is the compiler error:

calculator/ExpressionDef.hpp:114:9: required from 'calculator::parser::expression::expression(calculator::error_handler&) [with Iterator = __gnu_cxx::__normal_iterator >]' Expression.cpp:4:37: required from here /usr/include/boost/spirit/home/qi/detail/assign_to.hpp:152:13: error: no matching function for call to 'calculator::ast::expression::expression(const boost::variant, boost::recursive_wrapper, boost::recursive_wrapper >&)' /usr/include/boost/spirit/home/qi/detail/assign_to.hpp:152:13: note: candidates are: In file included from ./calculator/Expression.hpp:20:0, from calculator/ExpressionDef.hpp:1, from Expression.cpp:1: ./calculator/Ast.hpp:83:12: note: calculator::ast::expression::expression() ./calculator/Ast.hpp:83:12: note: candidate expects 0 arguments, 1 provided ./calculator/Ast.hpp:83:12: note: calculator::ast::expression::expression(const calculator::ast::expression&) ./calculator/Ast.hpp:83:12: note: no known conversion for argument 1 from 'const boost::variant, boost::recursive_wrapper, boost::recursive_wrapper >' to 'const calculator::ast::expression&' ./calculator/Ast.hpp:83:12: note: calculator::ast::expression::expression(calculator::ast::expression&&) ./calculator/Ast.hpp:83:12: note: no known conversion for argument 1 from 'const boost::variant, boost::recursive_wrapper, boost::recursive_wrapper >' to 'calculator::ast::expression&&'

cv_and_he cv_and_he · Accepted Answer · 2014-01-09T17:04:53

I haven't tested it thoroughly but I think that the following modifications provide the functionality you want. Keep in mind that this version of the calculator uses ints as its only type, and so you won't be able to work with negative exponents and the danger of overflow is present.

ast.hpp
You need to add a new element (op_exp) to the enum optoken:

...
op_times,
op_divides,
op_exp,    //ADDED //Line 55
op_positive,
...

expression.hpp
You need to add a declaration for exponential_expr, exponential_operand and exponential_op:

qi::rule<Iterator, ast::expression(), ascii::space_type>
    expr, equality_expr, relational_expr,
    logical_expr, additive_expr, multiplicative_expr, exponential_expr //MODIFIED
    ;

qi::rule<Iterator, ast::operand(), ascii::space_type>
    unary_expr, primary_expr, exponential_operand //MODIFIED
    ;
...
qi::symbols<char, ast::optoken>
    equality_op, relational_op, logical_op,
    additive_op, multiplicative_op, exponential_op, unary_op //MODIFIED
    ;

expression_def.hpp
You need to add the initialization of exponential_op, change the rules as follows, and add the new rules to the list of BOOST_SPIRIT_DEBUG_NODES:

...
multiplicative_op.add
    ("*", ast::op_times)
    ("/", ast::op_divide)
    ;       
exponential_op.add      //ADDED //Line 69
("^", ast::op_exp)
;
...
multiplicative_expr =       
        unary_expr
    >> *(multiplicative_op > unary_expr)
    ;

unary_expr =    //MODIFIED
        exponential_operand
    |   (unary_op > exponential_operand)
    ;

exponential_operand = exponential_expr; //ADDED

exponential_expr =          //ADDED
        primary_expr
    >> *(exponential_op > unary_expr)
    ;

primary_expr =
        uint_
    |   identifier
    |   bool_
    |   '(' > expr > ')'
    ;
...
(additive_expr)
(multiplicative_expr)
(exponential_expr)      //ADDED //Line 150
(exponential_operand)   //ADDED
(unary_expr)
...

compiler.cpp
You need to add a new case to the switches in program::print_assembler and compiler::operator():

...
case op_div:
    line += "      op_div";
    break;

case op_exp:        //ADDED //Line 105
    line += "      op_exp";
    break;

case op_eq:
    line += "      op_eq";
    break;
...
case ast::op_times: program.op(op_mul); break;
case ast::op_divide: program.op(op_div); break;
case ast::op_exp: program.op(op_exp); break;  //ADDED //Line 244

case ast::op_equal: program.op(op_eq); break;
...

vm.hpp
You need to add a new element (op_exp) to the enum byte_code:

...
op_mul,         //  multiply top two stack entries
op_div,         //  divide top two stack entries
op_exp,         //ADDED //Line 24

op_not,         //  boolean negate the top stack entry
...

vm.cpp
You need to add a new case to the switch in vmachine::execute (I've simply used std::pow, including cmath previously):

...
case op_div:
    --stack_ptr;
    stack_ptr[-1] /= stack_ptr[0];
    break;

case op_exp:    //ADDED //Line 60
    --stack_ptr;
    stack_ptr[-1] = std::pow(stack_ptr[-1],stack_ptr[0]);
    break;

case op_eq:
    --stack_ptr;
    stack_ptr[-1] = bool(stack_ptr[-1] == stack_ptr[0]);
    break;
...

How to add support for the exponential operator to one of the boost::spirit calculators?

1 Answers