How can Boost Spirit be used to parse Boolean expressions with operator precedence?

Boolean Expression Parsing

Given a Boolean expression in the form: "a and b xor (c and d or a and b);", the goal is to parse it into a tree, adhering to the precedence rules (not, and, xor, or).

Boost Spirit Implementation

Boost Spirit can be used to create a recursive descent parser based on expression templates. Here's the implementation:

Abstract Data Type

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

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

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

Grammar Rules

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

        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];
#ifdef RIGHT_ASSOCIATIVE
        or_  = (xor_ >> "or"  >> or_ ) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
        xor_ = (and_ >> "xor" >> xor_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
        and_ = (not_ >> "and" >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
#else
        or_  = xor_ [ _val = _1 ] >> *("or"  >> xor_ [ _val = phx::construct<binop<op_or>> (_val, _1) ]);
        xor_ = and_ [ _val = _1 ] >> *("xor" >> and_ [ _val = phx::construct<binop<op_xor>>(_val, _1) ]);
        and_ = not_ [ _val = _1 ] >> *("and" >> not_ [ _val = phx::construct<binop<op_and>>(_val, _1) ]);
#endif

        simple = (('(' > expr_ > ')') | var_);
        var_ = qi::lexeme[ +alpha ];
    }

  private:
    qi::rule<It, var() , Skipper> var_;
    qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};

Operating on the Syntax Tree

To traverse and print the syntax tree:

struct printer : boost::static_visitor<void>
{
    printer(std::ostream&amp; os) : _os(os) {}
    std::ostream&amp; _os;

    //
    void operator()(const var&amp; v) const { _os << v; }

    void operator()(const binop<op_and>&amp; b) const { print(" &amp; ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >&amp; b) const { print(" | ", b.oper1, b.oper2); }
    void operator()(const binop<op_xor>&amp; b) const { print(" ^ ", b.oper1, b.oper2); }

    void print(const std::string&amp; op, const expr&amp; l, const expr&amp; r) const
    {
        _os << "(";
            boost::apply_visitor(*this, l);
            _os << op;
            boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>&amp; u) const
    {
        _os << "(";
            _os << "!";
            boost::apply_visitor(*this, u.oper1);
        _os << ")";
    }
};

std::ostream&amp; operator<<(std::ostream&amp; os, const expr&amp; e)
{ boost::apply_visitor(printer(os), e); return os; }

Test Output

The parser correctly handles precedence rules and outputs:

result: ((a & b) ^ ((c & d) | (a & b)))
result: ((a & b) ^ ((c & d) | (a & b)))
result: (a & b)
result: (a | b)
result: (a ^ b)
result: (!a)
result: ((!a) & b)
result: (!(a & b))
result: ((a | b) | c)

Full Code and Live Example (Coliru)

[Click here to try and view the full code on Coliru](https://coliru.stacked-crooked.com/a/a795dea9a310e79bb12db3fe86fa61cf)

The above is the detailed content of How can Boost Spirit be used to parse Boolean expressions with operator precedence?. For more information, please follow other related articles on the PHP Chinese website!