How to parse a mathematical expression with boost::spirit and bind it to a function

Question

I would like to define a function taking 2 arguments

 double func(double t, double x); 

where the actual implementation is read from an external text file.
For example, specifying in the text file

function = x*t;    

the function should implement the multiplication between x and t, so that it could be called at a later stage. I'm trying to parse the function using boost::spirit. But I do not know how to actually achieve it.

Below, I created a simple function that implements the multiplication. I bind it to a boost function and I can use it. I also created a simple grammar, which parse the multiplication between two doubles.

#include <boost/config/warning_disable.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include "boost/function.hpp"
#include "boost/bind.hpp"
#include <boost/spirit/include/qi_symbols.hpp>
#include <iostream>
#include <string>

namespace qi = boost::spirit::qi;
namespace ascii=boost::spirit::ascii;
using boost::spirit::ascii::space;
using boost::spirit::qi::symbols;

template< typename Iterator >
struct MyGrammar : public virtual qi::grammar<  Iterator,  ascii::space_type >
{
    MyGrammar() : MyGrammar::base_type(expression)
    {
        using qi::double_;
        //The expression should take x and t as symbolic expressions
        expression = (double_ >> '*' >> double_)[std::cout << "Parse multiplication: " << (qi::_1 * qi::_2)];
     }

     qi::rule<Iterator, ascii::space_type> expression;
 };

double func(const double a, const double b)
{
    return a*b; //This is the operation to perform
}

int main()
{
    typedef std::string::const_iterator iterator_Type;
    typedef MyGrammar<iterator_Type> grammar_Type;

    grammar_Type calc; 

    std::string str = "1.*2."; // This should be changed to x*t

    iterator_Type iter = str.begin();
    iterator_Type end = str.end();
    bool r = phrase_parse(iter, end, calc, space);

    typedef boost::function < double ( const double t,
                                       const double x) > function_Type;

    function_Type multiplication = boost::bind(&func, _1, _2);

    std::cout << "\nResult: " << multiplication( 2.0, 3.0) << std::endl;

    return 0;
}

If I modify the above code setting

std::string str = "x*t";

how can I parse such an expression and bind it to the function multiplication such that, if I call multiplication(1.0, 2.0), it associates t to 1.0, x to 2.0 and it returns the result of the operation?

Marcasite

Basic idea: you list all operations you want to support in your source code as separate functions (note that the compiler can't generate them from a string during run time...). Then choose the correct function depending on the operator symbol which was parsed. – Yablon

@Yablon that's usually the breaking point yes. However, the OP is asking about something else – Liesa

@Liesa You're right... I read it too fast. Or it is too late. Excuses, excuses... ;) – Yablon

This question is about boost-spirit but if you want a library that already does this try looking into muparser. – Forland

@Forland I did just answer, but given the context, I'll +1 your comment. This seems the sane thing to do (except if the goal is indeed to learn Boost Spirit) – Liesa

Answer 1

You're going to learn Spirit. Great!

It seems you're biting off more than you can chew here, though.

Firstly, your grammar doesn't actually parse an expression yet. And it certainly doesn't result in a function that you can then bind.

1. In fact you're parsing the input using a grammar that is not producing any result. It only creates a side-effect (which is to print the result of the simple binary expression with immediate simple operands to the console). This /resembles/ interpreted languages, although it would soon break up when

   • you try to parse an expression like 2*8 + 9
   • you would have input that backtracks (oops, the side effect already fired)

2. Next up you're binding func (which is redundant by the way; you're not binding any arguments so you could just say function_Type multiplication(func); here), and calling it. While cool, this has literally nothing to do with the parsing input.

3. Finally, your question is about a third thing, that wasn't even touched upon anywhere in the above. This question is about symbol tables and identifier lookup.

   • This would imply you should parse the source for actual identifiers (x or t, e.g.)
   • you'd need to store these into a symbol table so they could be mapped to a value (and perhaps a scope/lifetime)

   • There is a gaping logic hole in the question where you don't define the source of the "formal parameter list" (you mention it in the text here: function = x*t; but the parser doesn't deal with it, neither did you hardcode any such metadata); so there is no way we could even start to map the x and t things to the formal argument list (because it doesn't exist).

     Let's assume for the moment that in fact arguments are positional (as they are, and you seem to want this as you call the bound function with positional arguments anyways. (So we don't have to worry about a name because no one will ever see a name.)

   • the caller should pass in a context to the functions, so that values can be looked up by identifier name during evaluation.

So, while I could try to sit you down and talk you through all the nuts and bolts that need to be created first before you can even dream of glueing it together in fantastic ways like you are asking for, let's not.

It would take me too much time and you would likely be overwhelmed.

Suggestions

I can only suggest to look at simpler resources. Start with the tutorials

• The calculator series of tutorials is nice. In this answer I list the calculator samples with short descriptions of what techniques they demonstrate: What is the most efficient way to recalculate attributes of a Boost Spirit parse with a different symbol table?
• The compiler tutorials actually do everything you're trying for, but they're a bit advanced

Ask freely if you have any questions along the way and you're at risk of getting stuck. But at least then we have a question that is answerable and answers that genuinely help you.

For now, look at some other answers of mine where I actually implemented grammars like this (somewhat ordered by increasing complexity):

• Nice for comparison: This answer to Boost::spirit how to parse and call c++ function-like expressions interprets the parsed expressions on-the-fly (this mimics the approach with [std::cout << "Parse multiplication: " << (qi::_1 * qi::_2)] in your own parser)

• The other answer there (Boost::spirit how to parse and call c++ function-like expressions) achieves the goal but using a dedicated AST representation, and a separate interpretation phase.

The benefits of each approach are described in these answers. These parsers do not have a symbol table nor a evaluation context.

More examples:

• a simple boolean expression grammar evaluator (which supports only literals, not variables)
• Building a Custom Expression Tree in Spirit:Qi (Without Utree or Boost::Variant)

Liesa