How do i change the grammar from this example to parse "AND ( (OR (a b c)) (NOT (d)))

Question

Boolean expression (grammar) parser in c++

I'm trying to modify the grammar from the above example provided by "sehe" to parse the following expression. "AND ( (OR (a b c)) (NOT (d)))".

There are three operators AND/OR/NOT, NOT is unary but AND and OR can act on multiple operands.

Thanks

2

What have you done so far? – djechlin Jun 07 '13 at 16:22

sehe · Answer 1 · 2013-06-10T22:21:00.167

The changed grammar is actually a lot simpler because it sidesteps the issue of operator precedence. This is the 'lisp' approach to grammars :)

Nevertheless, since you asked, I give you, the changed parser to parse your modified grammar:

struct op_or  {};
struct op_and {};
struct op_xor {};
struct op_not {};

typedef std::string var;
template <typename tag> struct combination_op;
template <typename tag> struct unop;

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<combination_op<op_and> >,
        boost::recursive_wrapper<combination_op<op_xor> >,
        boost::recursive_wrapper<combination_op<op_or> >
        > expr;

template <typename tag> struct combination_op 
{ 
    typedef std::vector<expr> operands_t;
    combination_op() = default;
    combination_op(operands_t const& operands) : operands(operands) { }
    operands_t operands;
};

template <typename tag> struct unop  
{ 
    unop() = default;
    unop(const expr& o) : operand(o) { }
    expr operand; 
};

//////////////////////////////////////////////////
// Parser grammar
template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
    parser() : parser::base_type(expr_)
    {
        using namespace qi;

        or_  = no_case [ "OR"  ] > '(' > expr_list > ')';
        xor_ = no_case [ "XOR" ] > '(' > expr_list > ')';
        and_ = no_case [ "AND" ] > '(' > expr_list > ')';
        not_ = no_case [ "NOT" ] > '(' > expr_     > ')';
        var_ = qi::lexeme[ +alpha ];

        expr_list = +expr_;
        expr_ = xor_ | and_ | or_ | not_ | var_;

        on_error<fail> ( expr_, std::cout
             << phx::val("Error! Expecting ") << _4 << phx::val(" here: \"")
             << phx::construct<std::string>(_3, _2) << phx::val("\"\n"));
    }

  private:
    template <typename Attr> using Rule = qi::rule<It, Attr(), Skipper>;
    Rule<var>                    var_;
    Rule<unop<op_not>>           not_;
    Rule<combination_op<op_and>> and_;
    Rule<combination_op<op_xor>> xor_;
    Rule<combination_op<op_or>>  or_;
    Rule<std::vector<expr>>      expr_list;
    Rule<expr>                   expr_;
};

If you wanted evaluation too:

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

    //
    bool operator()(const var& v) const 
    { 
        if (v=="T" || v=="t" || v=="true" || v=="True")
            return true;
        else if (v=="F" || v=="f" || v=="false" || v=="False")
            return false;
        return boost::lexical_cast<bool>(v); 
    }

    bool operator()(const combination_op<op_and>& b) const
    {
        return std::accumulate(begin(b.operands), end(b.operands), true, 
                [this](bool a, expr const& b) { return a && recurse(b); });
    }
    bool operator()(const combination_op<op_xor>& b) const
    {
        return std::accumulate(begin(b.operands), end(b.operands), false, 
                [this](bool a, expr const& b) { return a != recurse(b); });
    }
    bool operator()(const combination_op<op_or>& b) const
    {
        return std::accumulate(begin(b.operands), end(b.operands), false, 
                [this](bool a, expr const& b) { return a || recurse(b); });
    }
    bool operator()(const unop<op_not>& u) const
    {
        return !recurse(u.operand);
    } 

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

bool evaluate(const expr& e)
{ 
    return boost::apply_visitor(eval(), e); 
}

And you can print the evaluation results using

    std::cout << "eval: " << evaluate(result) << "\n";

Output:

tree: XOR (AND (true NOT (T)) OR (AND (T T) AND (F T)))
eval: 1

(Note: The tree is printed using the mirroring karma grammar, see "full code sample" below).

BONUS MATERIAL:

You may have noticed that the grammar has gotten very symmetrical around the corners. This is precisely because the precedence issue has vanished. Therefore, it might make sense to simplify the grammar further: simplified.cpp

Full Code Sample

Also on github: straight_forward.cpp

#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/karma.hpp>
#include <boost/variant/recursive_wrapper.hpp>
#include <boost/lexical_cast.hpp>

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

struct op_or  {};
struct op_and {};
struct op_xor {};
struct op_not {};

typedef std::string var;
template <typename tag> struct combination_op;
template <typename tag> struct unop;

typedef boost::variant<var, 
        boost::recursive_wrapper<unop <op_not> >, 
        boost::recursive_wrapper<combination_op<op_and> >,
        boost::recursive_wrapper<combination_op<op_xor> >,
        boost::recursive_wrapper<combination_op<op_or> >
        > expr;

template <typename tag> struct combination_op 
{ 
    typedef std::vector<expr> operands_t;
    combination_op() = default;
    combination_op(operands_t const& operands) : operands(operands) { }
    operands_t operands;
};

template <typename tag> struct unop  
{ 
    unop() = default;
    unop(const expr& o) : operand(o) { }
    expr operand; 
};

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

    //
    bool operator()(const var& v) const 
    { 
        if (v=="T" || v=="t" || v=="true" || v=="True")
            return true;
        else if (v=="F" || v=="f" || v=="false" || v=="False")
            return false;
        return boost::lexical_cast<bool>(v); 
    }

    bool operator()(const combination_op<op_and>& b) const
    {
        return std::accumulate(begin(b.operands), end(b.operands), true, 
                [this](bool a, expr const& b) { return a && recurse(b); });
    }
    bool operator()(const combination_op<op_xor>& b) const
    {
        return std::accumulate(begin(b.operands), end(b.operands), false, 
                [this](bool a, expr const& b) { return a != recurse(b); });
    }
    bool operator()(const combination_op<op_or>& b) const
    {
        return std::accumulate(begin(b.operands), end(b.operands), false, 
                [this](bool a, expr const& b) { return a || recurse(b); });
    }
    bool operator()(const unop<op_not>& u) const
    {
        return !recurse(u.operand);
    } 

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

bool evaluate(const expr& e)
{ 
    return boost::apply_visitor(eval(), e); 
}

//////////////////////////////////////////////////
// Parser grammar
template <typename It, typename Skipper = qi::space_type>
    struct parser : qi::grammar<It, expr(), Skipper>
{
    parser() : parser::base_type(expr_)
    {
        using namespace qi;

        or_  = no_case [ "OR"  ] > '(' > expr_list > ')';
        xor_ = no_case [ "XOR" ] > '(' > expr_list > ')';
        and_ = no_case [ "AND" ] > '(' > expr_list > ')';
        not_ = no_case [ "NOT" ] > '(' > expr_     > ')';
        var_ = qi::lexeme[ +alpha ];

        expr_list = +expr_;
        expr_ = xor_ | and_ | or_ | not_ | var_;

        on_error<fail> ( expr_, std::cout
             << phx::val("Error! Expecting ") << _4 << phx::val(" here: \"")
             << phx::construct<std::string>(_3, _2) << phx::val("\"\n"));
    }

  private:
    template <typename Attr> using Rule = qi::rule<It, Attr(), Skipper>;
    Rule<var>                    var_;
    Rule<unop<op_not>>           not_;
    Rule<combination_op<op_and>> and_;
    Rule<combination_op<op_xor>> xor_;
    Rule<combination_op<op_or>>  or_;
    Rule<std::vector<expr>>      expr_list;
    Rule<expr>                   expr_;
};

//////////////////////////////////////////////////
// Output generator
template <typename It>
    struct generator : karma::grammar<It, expr()>
{
    generator() : generator::base_type(expr_)
    {
        using namespace karma;

        or_  = lit("OR ")  << '(' << expr_list[ _1 = phx::bind(&combination_op<op_or >::operands, _val) ] << ')';
        xor_ = lit("XOR ") << '(' << expr_list[ _1 = phx::bind(&combination_op<op_xor>::operands, _val) ] << ')';
        and_ = lit("AND ") << '(' << expr_list[ _1 = phx::bind(&combination_op<op_and>::operands, _val) ] << ')';
        not_ = lit("NOT ") << '(' << expr_    [ _1 = phx::bind(&unop<op_not>          ::operand,  _val) ] << ')';
        var_ = karma::string;

        expr_list = expr_ % ' ';
        expr_ = var_ | not_ | xor_ | and_ | or_ | not_;
    }

  private:
    template <typename Attr> using Rule = karma::rule<It, Attr()>;
    Rule<var>                    var_;
    Rule<unop<op_not>>           not_;
    Rule<combination_op<op_and>> and_;
    Rule<combination_op<op_xor>> xor_;
    Rule<combination_op<op_or>>  or_;
    Rule<std::vector<expr>>      expr_list;
    Rule<expr>                   expr_;
};

int main()
{
    const std::string input("xor (and (true not(T)) or (and (T T) and (F T)));");

    auto f(std::begin(input)), l(std::end(input));
    const static parser<decltype(f)> p;

    expr result;
    bool ok = qi::phrase_parse(f,l,p > ';',qi::space,result);

    if (!ok)
        std::cout << "invalid input\n";
    else
    {
        const static generator<boost::spirit::ostream_iterator> g;
        std::cout << "tree: " << karma::format(g, result) << "\n";
        std::cout << "eval: " << evaluate(result) << "\n";
    }

    if (f!=l) std::cout << "unparsed: '" << std::string(f,l) << "'\n";
}

added the [simplified](https://gist.github.com/sehe/5732243#file-simplified-cpp) version too, now; 20 fewer lines of code. — sehe, Jun 07 '13 at 21:11
Thanks "not-sehe" for the response. In my case the operands are columns from the database to be retrieved. BTW "NOT" is not working. — user2461517, Jun 10 '13 at 18:29
**[Fixed](http://stackoverflow.com/posts/16992549/revisions)** the NOT implementation (both [straight_forward.cpp](https://gist.github.com/sehe/5732243#file-straight_forward-cpp) and [simplified.cpp](https://gist.github.com/sehe/5732243#file-simplified-cpp)) — sehe, Jun 10 '13 at 22:22
With this grammar i'm trying to create a vector of operations using the Print function in one of your examples. This function has a problem for the following: AND($F4 OR($F1 $F2)) when an operand appears before an inner operator. How would i change spirit grammar to generate precedence based on brackets. — user2461517, Jul 08 '13 at 21:13
Here is the function [link] https://github.com/syash/Example/blob/master/CVec.cc Works fine for the following Input String: AND (OR ($flag1 $flag2) NOT($flag3)); OR -> $flag1 , $flag2 , NOT -> $flag3 , AND -> Input String: AND( $F1 OR($F1 $F2)); OR -> $F1 , $F1 , $F2 which is wrong. — user2461517, Jul 08 '13 at 21:37
Are you trying to generate RPN of the evaluation tree? Since, cramming a recursive datastructure into a single vector is a lossy operation. It's not at all clear what you want here. Consider posting a proper question? — sehe, Jul 08 '13 at 21:54
Yes. I'm trying to create a tree type data structure. For example AND (OR ($flag1 $flag2) NOT($flag3) i want to evaluate in the following order. 1.OR 2.NOT and then apply AND for the previous two operations. — user2461517, Jul 09 '13 at 04:20
@user2461517 **A:** I don't see the problem. The `eval` visitor from my answer already does exactly this? **B:** a tree is not reverse polish notation. **C:** Also, you cannot store a tree in `operVector`, because it is not a recursive data structure. — sehe, Jul 09 '13 at 06:33
sehe Thanks for your help. In my case i also need to store operator precedence. So I used your evaluate function as reference and created ConstructVector which stores operator, precedence and operands. This is a crude way of doing it... [link] https://github.com/syash/Example/edit/master/CVec.cc Input String: AND (OR (OR ($F1 $F2) $F3 $F4) $F7); Output: OR - 3 - ($F1 , $F2 ) OR - 2 - ($F3 , $F4 ) AND - 1 - ( $F7 ) Input String: AND(OR ($F1 $F2) NOT($F3)); Output: OR - 2 - ($F1 , $F2 ) NOT - 2 - ($F3 ) AND - 1 — user2461517, Jul 10 '13 at 21:34
@user2461517 I don't see why you want to cram a tree into a flat container. Seems overly complicated to me, but, hey, this looks like it could conceptually work :) _(oh and `s/edit/blob/` in that hyperlink)_ — sehe, Jul 10 '13 at 21:42

How do i change the grammar from this example to parse "AND ( (OR (a b c)) (NOT (d)))

1 Answers1

BONUS MATERIAL:

Full Code Sample

Linked