How to verify algebraic statements using boost::spirit?

Question

I'm trying to extend the calculator example so that instead of parsing and evaluating an algebraic expression, the parser will determine if an algebraic statement is true or not. By this I mean statements like 1 + 5 * 5 - 10 = 19 - 3 (desired parser result is true) and 3 - 1 = 9 (desired parser result is false).

I've got to admit I'm new to boost::spirit and it's all kind of overwhelming at the moment. However, I do feel I understand the calculator example good enough to at least make some headway.

Using the provided example as a starting point, the grammar looks like this:

calculator() : calculator::base_type(expression)
{
    using qi::uint_;
    using qi::_val;
    using qi::_1;

    expression =
        term                    [_val = _1]
            >> *( ('+' >> term  [_val = _val + _1])
                | ('-' >> term  [_val = _val - _1])
                );

        term =
            factor                [_val = _1]
            >> *( ('*' >> factor  [_val = _val * _1])
                | ('/' >> factor  [_val = _val / _1])
                );

        factor =
            uint_                 [_val = _1]
            |   '(' >> expression [_val = _1] >> ')'
            |   ('-' >> factor    [_val = -_1])
            |   ('+' >> factor    [_val = _1]);
}

where I've dropped the debug macros for brevity.

To limit the scope of the problem, I've decided to allow only a single equality sign per statement. As it is meaningless (at least in a regular sense) to have equality signs appear inside a closed pair of parentheses, I've decided not to allow parentheses either. This simplifies the factor-parser by permitting the removal of the optional '(' >> expression [_val = _1] >> ')'.

At this point I'm a little stuck. First of all, I need the parser to accept a single equality sign. Secondly, I need the semantic actions to evaluate the left hand side (LHS) and the right hand side (RHS) of the statement individually, before finally performing a comparison (or so this is what I think needs to be done).

I am wondering if the easiest approach would be to construct two separate parsers, one LHS and one RHS, separated by a third parser matching the equality sign. The two parsers LHS and RHS should be identical, except for the semantic action which, clearly, need to separate the input into two different categories in order for these to finally be compared.

Before trying to write two separate parsers LHS and RHS, I wanted to learn how to modify the original parser so that it stored the evaluated expressions in a local variable. (I'm not even sure that would be a viable path to anywhere, but it seems like a step in the right direction.)

This is what I tried:

int result;

expression =
    term                            [result = _1]
    >> *(   ('+' >> term            [result = result + _1])
        |   ('-' >> term            [result = result - _1])
        );

but this makes my compiler (Apple LLVM compiler 4.2, Xcode 4.6) go nuts, yelling at me that

Assigning to 'int' from incompatible type 'const _1_type' (aka 'const actor< argument < 0 > >')

In hindsight, this makes sense of course, since _val was never bound to int in the first place (after all, the parsers are AFAIU supposed to be generic). In other words, I need to figure out how to define the type to use for temporary storing the evaluated parsed expression.

The question is: can anyone give me a nudge in the right direction? Does the split in LHS and RHS seem like the way to go?

Any suggestion is greatly appreciated!

Answer 1

The simplest thing that could work, if you ask me would be http://liveworkspace.org/code/1fvc8x$0

equation = (expression >> "=" >> expression) [ _val = _1 == _2 ];

This will parse two expressions, and the returned attribute is a bool that indicates whether both expressions evaluated to the same value.

The demonstration program

int main()
{
    doParse("1 + 2 * 3 = 7");
    doParse("1 + 2 * 3 = 8");
}

prints

parse success
result: true
parse success
result: false

Sample program

#include <boost/fusion/adapted.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>

namespace qi    = boost::spirit::qi;
namespace phx   = boost::phoenix;

typedef unsigned attr_t;

template <typename It, typename Skipper = qi::space_type>
    struct calculator : qi::grammar<It, bool(), Skipper>
{
    calculator() : calculator::base_type(equation)
    {
        using qi::uint_;
        using qi::_val;
        using qi::_1;
        using qi::_2;

        equation = (expression >> "=" >> expression) [ _val = _1 == _2 ];

        expression =
            term                    [_val = _1]
                >> *( ('+' >> term  [_val = _val + _1])
                    | ('-' >> term  [_val = _val - _1])
                    );

            term =
                factor                [_val = _1]
                >> *( ('*' >> factor  [_val = _val * _1])
                    | ('/' >> factor  [_val = _val / _1])
                    );

            factor =
                uint_                 [_val = _1]
                |   '(' >> expression [_val = _1] >> ')'
                |   ('-' >> factor    [_val = -_1])
                |   ('+' >> factor    [_val = _1]);
    }

  private:
    qi::rule<It, unsigned(), Skipper> expression, term, factor;
    qi::rule<It, bool(), Skipper> equation;
};

bool doParse(const std::string& input)
{
    typedef std::string::const_iterator It;
    auto f(begin(input)), l(end(input));

    calculator<It, qi::space_type> p;
    bool result;

    try
    {
        bool ok = qi::phrase_parse(f,l,p,qi::space,result);
        if (ok)   
        {
            std::cout << "parse success\n";
            std::cout << "result: " << std::boolalpha << result << "\n";
        }
        else      std::cerr << "parse failed: '" << std::string(f,l) << "'\n";

        if (f!=l) std::cerr << "trailing unparsed: '" << std::string(f,l) << "'\n";
        return ok;
    } catch(const qi::expectation_failure<It>& e)
    {
        std::string frag(e.first, e.last);
        std::cerr << e.what() << "'" << frag << "'\n";
    }

    return false;
}

int main()
{
    doParse("1 + 2 * 3 = 7");
    doParse("1 + 2 * 3 = 8");
}