Building a Custom Expression Tree in Spirit:Qi (Without Utree or Boost::Variant)

boost-spirit boost-spirit-qi c++ expression-trees parsing

Question

First off, if using Boost Variant or Utree makes things significantly simpler, I'll stick with them and attempt to resolve my concerns with them in an other thread. But I really want to be able to construct trees like the one I've shown here.

If you want to skip the background information and get to the point, say so: I'd want to be able to create an expression tree that parses data similar to

"({a} == 0) && ({b} > 5)"

or a common mathematical formula

"(2 * a) + b"

Before evaluating my tree, I will then describe what a and b are, something like this:

a = 10;
double val = myExpression->Evaluate();

My problem arises when I attempt to create the expression tree to parse the string. I'm using an abstract class called "Expression" from which "Variable," "Constant," and "Binary" expressions are derived (unary is also supported, but it shouldn't affect my issue). I'm obviously doing something incorrectly since I constantly running into issues while trying to add to the tree using my rules. I'm finding it difficult to comprehend the qualities.

My tree (Tree.h) looks like this:

class BinaryExpression;
typedef double (*func)(double, double);

class Expression
{
public:
    virtual double Evaluate() = 0;
};

class BinaryExpression : public Expression
{
private:
    Expression* lhs;
    Expression* rhs;
    func method;

    double Evaluate();

public:
    BinaryExpression(void);
    BinaryExpression(char op, Expression* lhs, Expression* rhs);
    BinaryExpression(char op);
    void operator()(Expression* lhs, Expression* rhs);
};

class ConstantExpression : public Expression
{
private:
    double value;
public:
    ConstantExpression(void);
    ConstantExpression(char op);
    ConstantExpression(double val);

    double Evaluate();
};

// Require as many types as there are fields in expression?
static double a;
static double b;
class VariableExpression : public Expression
{
private:
    char op;

public:
    VariableExpression(char op);

    double Evaluate();
};

BOOST_FUSION_ADAPT_STRUCT(
    BinaryExpression,
    (Expression*, lhs)
    (Expression*, rhs)
    (func, method)
)

BOOST_FUSION_ADAPT_STRUCT(
    VariableExpression,
    (char, op)
)

BOOST_FUSION_ADAPT_STRUCT(
    ConstantExpression,
    (double, op)
)

Tree.cpp

typedef double (*func)(double, double);

/////////////////////////////////////////////////////////////////////////////
// BINARY EXPRESSION
////////////////////////////////////////////////////////////////////////////

BinaryExpression::BinaryExpression(void) {}

BinaryExpression::BinaryExpression(char op, Expression* lhs, Expression* rhs)
{
    this->lhs = lhs;
    this->rhs = rhs;

    // Example, methods are held in another header
    if (op == '+')
        method = Add;
    else if (op == '-')
        method = Subtract;

}

double BinaryExpression::Evaluate()
{
    return method(lhs->Evaluate(), rhs->Evaluate());
}

BinaryExpression::BinaryExpression(char op)
{
    if (op == '+')
        method = Add;
    else if (op == '-')
        method = Subtract;
}

void BinaryExpression::operator()(Expression* lhs, Expression* rhs)
{
    this->lhs = lhs;
    this->rhs = rhs;
}

/////////////////////////////////////////////////////////////////////////////
// CONSTANT EXPRESSION
////////////////////////////////////////////////////////////////////////////

ConstantExpression::ConstantExpression() {}

ConstantExpression::ConstantExpression(char op)
{
    this->value = op - 48;
}
ConstantExpression::ConstantExpression(double val)
{
    value = val;
}

double ConstantExpression::Evaluate()
{
    return value;
}

/////////////////////////////////////////////////////////////////////////////
// VARIABLE EXPRESSION
////////////////////////////////////////////////////////////////////////////

VariableExpression::VariableExpression(char op)
{
    this->op = op;
}

double VariableExpression::Evaluate()
{
    // a and b are defined in the header, and are used to fill in the variables we     want to evaluate
    if (op == 'a')
        return a;
    if (op == 'b')
        return b;
    return 0;
}

I don't believe there is a problem with the way it is constructed since everything works properly if I manually create the tree at this point.

This is Grammar.h. (I could delete the several comments from where I tried different things, but I think it's important to note what I did and where I want to go with it.)

#include "Tree.h"

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix_function.hpp>

namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;

qi::_1_type _1;
qi::_2_type _2;

// Pass functions to boost
boost::phoenix::function<BinaryExpression> plus = BinaryExpression('+');
boost::phoenix::function<BinaryExpression> minus = BinaryExpression('-');

template <typename Iterator>
struct ExpressionParser : qi::grammar<Iterator, BinaryExpression(), ascii::space_type>
{
    ExpressionParser() : ExpressionParser::base_type(expression)
    {
        qi::_3_type _3;
        qi::_4_type _4;

        qi::char_type char_;
        qi::uint_type uint_;
        qi::_val_type _val;
        qi::raw_type raw;
        qi::lexeme_type lexeme;
        qi::alpha_type alpha;
        qi::alnum_type alnum;
        qi::bool_type bool_;
        qi::double_type double_;


        expression = //?
            additive_expr                       [_val = _1]
            ;

        //equality_expr = 
        //      relational_expr >> 
        //      *(lit("==") > relational_expr)      [/*Semantice action to add to tree*/]
        //      ;

        additive_expr =
            primary_expr >>
            ( '+' > primary_expr)               [plus(_val, _1)]   
            | ( '-' > primary_expr)             [minus(_val, _1)]
            ;
        // Also tried "_val = plus(_1, _2)"

        primary_expr =
            constant                                [_val = _1]
            | variable                          [_val = _1]
            //| '(' > expression > ')'          [_val = _1]
            ;

        string %=
            '{' >> *(char_ - '}') >> '}'
            ;

        // Returns ConstantExpression
        constant =
            double_                                 [_val = _1];

        // Returns VariableExpression
        variable =
            char_                                   [_val = _1]
            ;
    }

    // constant expression = double
    // variable expression = string
    qi::rule<Iterator, BinaryExpression(), ascii::space_type>
        expression;

    qi::rule<Iterator, BinaryExpression(), ascii::space_type>
        // eventually will deal with all these rules
        equality_expr,
        relational_expr,        
        logical_expr,
        additive_expr,
        multiplicative_expr,
        primary_expr
            ;

    qi::rule<Iterator, ConstantExpression(), ascii::space_type>
        constant
        ;

    qi::rule<Iterator, VariableExpression(), ascii::space_type>
        variable
        ;

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

Therefore, this is seriously disassembled, but perhaps it will demonstrate what I'm attempting to do. Any suggestions or counsel would be much appreciated. Is there an instance when a tree like this has been constructed without the use of variant or utree.

I apologize if I violated any formatting rules; I tried to make it as legible as I could.

1
7
10/24/2012 9:46:59 PM

Accepted Answer

I'm not sure why you object to (recursive) versions, but here is one that fits with your desire to employ "traditional" tree construction with dynamically allocated nodes:

I purposely avoided addressing the problem with operator priority in your grammar because

Recall how I

  • Using shared ptr (you may use the Boost one if you don't have a TR1 library) eliminated pervasive memory leaks
  • As a Phoenix actor is slack, I eliminated the careless reuse of a particular BinaryExpression instance. Instead, I created a regionalmakebinary actor nowadays.
  • Note the new support for chains of operators (1+2+5+6–10):

    additive_expr =
        primary_expr                         [ _val = _1 ]
        >> *(char_("-+*/") >> primary_expr)  [ _val = makebinary(_1, _val, _2)]
        ;
    
  • I tacked{var} , / , * and (expr) support

  • serialization was added for display (Print virtual technique,operator<< For ease of presentation, BinaryExpression keeps theoperator in place of the outcomemethod now)

  • Consequently, you may now utilize BOOST SPIRIT DEBUG (uncomment first line)
  • I changed the nameExpression to AbstractExpression (and created the destructor protected)
  • I changed the namePrimaryExpression to Expression This is your primary phrasing datatype at this time.
  • I demonstrate how to simply store variables in astatic map
  • uses adapting fusion structures much less (just forvariable now)
  • makes it very simple to generate an expression from several parsed types by using the templated constructor trick:

    struct Expression : AbstractExpression {
        template <typename E>
        Expression(E const& e) : _e(make_from(e)) { } // cloning the expression
        // ...
    };
    

    sufficient to support efficiently, for instance

    primary_expr =
          ( '(' > expression > ')' )         [ _val = _1 ]
        | constant                           [ _val = _1 ]
        | variable                           [ _val = _1 ]
        ;
    
  • I've included a couple additional test cases for fun:

    Input:                3*8 + 6
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(3) * ConstantExpression(8)) + ConstantExpression(6)))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    30
    ----------------------------------------
    Input:                3*(8+6)
    Expression:           Expression(BinaryExpression(ConstantExpression(3) * BinaryExpression(ConstantExpression(8) + ConstantExpression(6))))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    42
    ----------------------------------------
    Input:                0x1b
    Expression:           Expression(ConstantExpression(27))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    27
    ----------------------------------------
    Input:                1/3
    Expression:           Expression(BinaryExpression(ConstantExpression(1) / ConstantExpression(3)))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    0.333333
    ----------------------------------------
    Input:                .3333 * 8e12
    Expression:           Expression(BinaryExpression(ConstantExpression(0.3333) * ConstantExpression(8e+12)))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    2.6664e+12
    ----------------------------------------
    Input:                (2 * a) + b
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(2) * VariableExpression('a')) + VariableExpression('b')))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               10, 7
    Evaluation result:    27
    ----------------------------------------
    Input:                (2 * a) + b
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(2) * VariableExpression('a')) + VariableExpression('b')))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               -10, 800
    Evaluation result:    780
    ----------------------------------------
    Input:                (2 * {a}) + b
    Expression:           Expression(BinaryExpression(BinaryExpression(ConstantExpression(2) * VariableExpression('a')) + VariableExpression('b')))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               -10, 800
    Evaluation result:    780
    ----------------------------------------
    Input:                {names with spaces}
    Expression:           Expression(VariableExpression('names with spaces'))
    Parse success:        true
    Remaining unparsed:  ''
    (a, b):               0, 0
    Evaluation result:    0
    ----------------------------------------
    

Total Code

// #define BOOST_SPIRIT_DEBUG
// #define BOOST_RESULT_OF_USE_DECLTYPE
// #define BOOST_SPIRIT_USE_PHOENIX_V3

#include <cassert>
#include <memory>
#include <iostream>
#include <map>

struct AbstractExpression;
typedef std::shared_ptr<AbstractExpression> Ptr;

struct AbstractExpression {
    virtual ~AbstractExpression() {}
    virtual double Evaluate() const = 0;
    virtual std::ostream& Print(std::ostream& os) const = 0;

    friend std::ostream& operator<<(std::ostream& os, AbstractExpression const& e)
        { return e.Print(os); }

    protected: AbstractExpression() {}
};

template <typename Expr> // general purpose, static Expression cloner
    static Ptr make_from(Expr const& t) { return std::make_shared<Expr>(t); }

struct BinaryExpression : AbstractExpression 
{
    BinaryExpression() {}

    template<typename L, typename R>
    BinaryExpression(char op, L const& l, R const& r) 
        : _op(op), _lhs(make_from(l)), _rhs(make_from(r)) 
    {}

    double Evaluate() const {
        func f = Method(_op);
        assert(f && _lhs && _rhs);
        return f(_lhs->Evaluate(), _rhs->Evaluate());
    }

  private:
    char _op;
    Ptr _lhs, _rhs;

    typedef double(*func)(double, double);

    static double Add(double a, double b)      { return a+b; }
    static double Subtract(double a, double b) { return a-b; }
    static double Multuply(double a, double b) { return a*b; }
    static double Divide(double a, double b)   { return a/b; }

    static BinaryExpression::func Method(char op)
    {
        switch(op) {
            case '+': return Add;
            case '-': return Subtract;
            case '*': return Multuply;
            case '/': return Divide;
            default:  return nullptr;
        }
    }
    std::ostream& Print(std::ostream& os) const
        { return os << "BinaryExpression(" << *_lhs << " " << _op << " " << *_rhs << ")"; }
};

struct ConstantExpression : AbstractExpression {
    double value;
    ConstantExpression(double v = 0) : value(v) {}

    double Evaluate() const { return value; }

    virtual std::ostream& Print(std::ostream& os) const
        { return os << "ConstantExpression(" << value << ")"; }
};

struct VariableExpression : AbstractExpression {
    std::string _name;

    static double& get(std::string const& name) {
        static std::map<std::string, double> _symbols;
        return _symbols[name];
        /*switch(name) {
         *    case 'a': static double a; return a;
         *    case 'b': static double b; return b;
         *    default:  throw "undefined variable";
         *}
         */
    }

    double Evaluate() const { return get(_name); }

    virtual std::ostream& Print(std::ostream& os) const
        { return os << "VariableExpression('" << _name << "')"; }
};

struct Expression : AbstractExpression
{
    Expression() { }

    template <typename E>
    Expression(E const& e) : _e(make_from(e)) { } // cloning the expression

    double Evaluate() const { assert(_e); return _e->Evaluate(); }

    // special purpose overload to avoid unnecessary wrapping
    friend Ptr make_from(Expression const& t) { return t._e; }
  private:
    Ptr _e;
    virtual std::ostream& Print(std::ostream& os) const
        { return os << "Expression(" << *_e << ")"; }
};

//Tree.cpp

/////////////////////////////////////////////////////////////////////////////
// BINARY EXPRESSION
////////////////////////////////////////////////////////////////////////////

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

BOOST_FUSION_ADAPT_STRUCT(VariableExpression, (std::string, _name))

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

// Pass functions to boost
template <typename Iterator>
struct ExpressionParser : qi::grammar<Iterator, Expression(), ascii::space_type> 
{
    struct MakeBinaryExpression {
        template<typename,typename,typename> struct result { typedef BinaryExpression type; };

        template<typename C, typename L, typename R>
            BinaryExpression operator()(C op, L const& lhs, R const& rhs) const 
            { return BinaryExpression(op, lhs, rhs); }
    };

    phx::function<MakeBinaryExpression> makebinary;

    ExpressionParser() : ExpressionParser::base_type(expression) 
    {
        using namespace qi;
        expression =
            additive_expr                        [ _val = _1]
            ;

        additive_expr =
            primary_expr                         [ _val = _1 ]
            >> *(char_("-+*/") >> primary_expr)  [ _val = makebinary(_1, _val, _2)]
            ;

        primary_expr =
              ( '(' > expression > ')' )         [ _val = _1 ]
            | constant                           [ _val = _1 ]
            | variable                           [ _val = _1 ]
            ;

        constant = lexeme ["0x" >> hex] | double_ | int_;
        string   = '{' >> lexeme [ *~char_("}") ] > '}';
        variable = string | as_string [ alpha ];

        BOOST_SPIRIT_DEBUG_NODE(expression);
        BOOST_SPIRIT_DEBUG_NODE(additive_expr);

        BOOST_SPIRIT_DEBUG_NODE(primary_expr);
        BOOST_SPIRIT_DEBUG_NODE(constant);
        BOOST_SPIRIT_DEBUG_NODE(variable);
        BOOST_SPIRIT_DEBUG_NODE(string);
    }

    qi::rule<Iterator, Expression()        , ascii::space_type> expression;
    qi::rule<Iterator, Expression()        , ascii::space_type> additive_expr;

    qi::rule<Iterator, Expression()        , ascii::space_type> primary_expr;
    qi::rule<Iterator, ConstantExpression(), ascii::space_type> constant;
    qi::rule<Iterator, VariableExpression(), ascii::space_type> variable;
    qi::rule<Iterator, std::string()       , ascii::space_type> string;
};

void test(const std::string input, double a=0, double b=0)
{
    typedef std::string::const_iterator It;
    ExpressionParser<It> p;

    Expression e;
    It f(input.begin()), l(input.end());
    bool ok = qi::phrase_parse(f,l,p,ascii::space,e);

    std::cout << "Input:                "  << input            << "\n";
    std::cout << "Expression:           "  << e                << "\n";
    std::cout << "Parse success:        "  << std::boolalpha   << ok << "\n";
    std::cout << "Remaining unparsed:  '"  << std::string(f,l) << "'\n";

    std::cout << "(a, b):               "  << a << ", " << b   << "\n";

    VariableExpression::get("a") = a;
    VariableExpression::get("b") = b;
    std::cout << "Evaluation result:    "  << e.Evaluate()     << "\n";
    std::cout << "----------------------------------------\n";
}

int main() 
{
    test("3*8 + 6"); 
    test("3*(8+6)"); 
    test("0x1b"); 
    test("1/3"); 
    test(".3333 * 8e12");
    test("(2 * a) + b",    10,   7);
    test("(2 * a) + b",   -10, 800);
    test("(2 * {a}) + b", -10, 800);
    test("{names with spaces}");
}
10
5/23/2017 12:15:30 PM


Related Questions





Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow
Licensed under: CC-BY-SA with attribution
Not affiliated with Stack Overflow