boost spirit how to access child nodes (leaves) from parent nodes

Question

I would like to evaluate boolean expression such as a=b & s<9 or simply a=b with only comparison operator (wihtout logical operator such as |, & and !). We can have the following AST:

or

               &
              / \  
             /   \
            =     <
           / \    /\
          /   \  /  \
          a    b s   9

The leaves nodes are values. The parent of leave nodes are always comparison operator such as =, !=, <,>, >=, <=. The parent of comparison nodes are logical operator |, &, and !. I would like to access to value nodes (leaves) from their parent node and then pass these values to another function (which will be implemented later). The parsing step is ok.

How to access values nodes (leaves) from their parent node. I am using examples at : How to calculate boolean expression in Spirit

and Boolean expression (grammar) parser in c++ This is an evaluation code taken from these links:


    struct eval : boost::static_visitor<bool>
{
    eval() {}

    //
    bool operator()(const var& v) const
    {
        std::cout<<"feuille:\n"<<v<<std::endl;
        return true;
    }

    bool operator()(const binop<op_and>& b) const
    {
        recurse(b.oper1) && recurse(b.oper2);
    }
    bool operator()(const binop<op_or>& b) const
    {
        recurse(b.oper1) || recurse(b.oper2);
    }
    bool operator()(const unop<op_not>& u) const
    {
        return !recurse(u.oper1);
    }

    //------------adding others operators----------------------------
    bool operator()(const binop<op_equal>& u) const
    {
        // will be implemented later
        return true;
    }

    bool operator()(const binop<op_not_equal>& u) const
    {
       // will be implemented later
        return true;
    }

    bool operator()(const binop<op_less>& u) const
    {
        // will be implemented later
        return true;
    }

    bool operator()(const binop<op_less_equal>& u) const
    {
        // will be implemented later
        return true;
    }

    bool operator()(const binop<op_greater>& u) const
    {
        // will be implemented later
        return true;
    }
    bool operator()(const binop<op_greater_equal>& u) const
    {
        // will be implemented later
        return true;
    }

Thank you. Any suggestion is welcome.

sehe sehe · Accepted Answer · 2013-10-18T12:32:01

Have you looked at the other evaluation overloads for the existing operators? Did you notice how they got the value of their operands (which may be sub-expressions, indeed)?

Let me take binary or as an example:

bool operator()(const binop<op_or>& b) const
{
    return recurse(b.oper1) || recurse(b.oper2);
}

As you can see, it just applies || to the value of both operands. That value is not found in the AST^[1]. So, we treat each operand as an expression, and just call the eval method on it, recursively.

Because the expression type is a variant, calling eval is actually applying a visitor to the variant, and I had already written the helpful wrapper that does this so it's easy to recurse:

private:
template<typename T>
    bool recurse(T const& v) const 
    { return boost::apply_visitor(*this, v); }

So, not knowing the rest of your grammar, but assuming you extended it in the same vein as the existing grammar:

bool operator()(const binop<op_equal>& u) const {
    return recurse(b.oper1) == recurse(b.oper2);
}

would be about right. Note that with a clever macro, you can be done very quickly:

struct eval : boost::static_visitor<value> {

    // terminal
    value operator()(const var& v) const {
        std::cout<<"feuille:\n"<<v<<std::endl;
        return true; // TODO get value from var
    }

    // unary operator
    value operator()(const unop<op_not>& u) const { return !recurse(u.oper1); }

    /*
     * binary operators
     */
#define EXPR_DEF_BINOP(tag, op) \
    value operator()(const binop<tag>& u) const { \
        return recurse(b.oper1) op recurse(b.oper2); \
    }

    EXPR_DEF_BINOP(op_and,           &&)
    EXPR_DEF_BINOP(op_equal,         ==)
    EXPR_DEF_BINOP(op_greater,       >)
    EXPR_DEF_BINOP(op_greater_equal, >=)
    EXPR_DEF_BINOP(op_less,          <)
    EXPR_DEF_BINOP(op_less_equal,    <=)
    EXPR_DEF_BINOP(op_not_equal,     !=)
    EXPR_DEF_BINOP(op_or,            ||)

#undef EXPR_DEF_BINOP

  private:
    template<typename T>
        value recurse(T const& v) const 
        { return boost::apply_visitor(*this, v); }
};

Some more notes:

I added a TODO to the leaf-node evaluation function
I changed the type to value (from bool). This is because your grammar supports non-boolean expressions, otherwise operators <= and >= wouldn't make sense.^[2], so you would have values of different types (too):
```
using value = variant<bool, int32_t>;
```
I'll leave the rest for you

^[1] Remember AST = Abstract Syntax Tree: it's a 1:1 representation of the source. (The "half-exception" would be literals, although you still need to tell the evaluator how to use the value of the literal.)

^[2] arguably

a<b could imply !a && b
a>b could imply !b && a
a!=b could imply a XOR b
a==b could imply !(a XOR b)

boost spirit how to access child nodes (leaves) from parent nodes

1 Answers