1

I have a parser, which parses boolean expressions. How I should modify it to support "implied-And" e.g "A1 A2" which must be parsed as A1 and A2? I've tried to change the "and_" rule to support it, but it started to treat "xor" as a variable even if it was used as an operation. Excluding of "xor" from the rule of var with (!(" xor ") >>) still fails for simple expressions.

The source code :

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

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

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

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;

template <typename tag> struct binop
{
    explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
    expr oper1, oper2;
};

template <typename tag> struct unop
{
    explicit unop(const expr& o) : oper1(o) { }
    expr oper1;
};

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


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

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

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

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

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

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();

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

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

    BOOST_SPIRIT_DEBUG_NODE(expr_);
    BOOST_SPIRIT_DEBUG_NODE(or_);
    BOOST_SPIRIT_DEBUG_NODE(xor_);
    BOOST_SPIRIT_DEBUG_NODE(and_);
    BOOST_SPIRIT_DEBUG_NODE(not_);
    BOOST_SPIRIT_DEBUG_NODE(simple);
    BOOST_SPIRIT_DEBUG_NODE(var_);
}

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

int main()
{
for (auto& input : std::list<std::string> {
        "(a and b) xor ((c and d) or (a and b));",
        "a and b xor c and d or a and b;",

        /// Simpler tests:
        "a and b;",
        "a or b;",
        "xor_in1 xor xor_in2;",
        "xorin1 xor xorin2;",
        "and1 xor xor;",
        "not a;",
        "not a and b;",
        "not (a and b);",
        "a or b or c;",
        })
{
    auto f(std::begin(input)), l(std::end(input));
    parser<decltype(f)> p;

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

        if (!ok)
            std::cerr << "invalid input\n";
        else
            std::cout << "result: " << result << "\n";

    } catch (const qi::expectation_failure<decltype(f)>& e)
    {
        std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
    }

    if (f!=l) std::cerr << "unparsed: '" << std::string(f,l) << "'\n";
    }
    return 0;
}
Grigor Aghanyan
  • 53
  • 5
  • Next time just link to [the source](http://stackoverflow.com/questions/8706356/boolean-expression-grammar-parser-in-c/8707598#8707598). In this case the question is more of a comment to that answer, in fact. – sehe May 21 '15 at 11:18
  • The most of code is the same (btw thank you for nice example of QI usage), but I've modified it to correct the precedence of operations. – Grigor Aghanyan May 21 '15 at 11:36

1 Answers1

1

First of I restored the parser rules with the original ones from Boolean expression (grammar) parser in c++ that you obviously started with:

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 ];
not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];

Now the failing cases like "xorin1 xor xorin2;" don't have anything todo with the things you ask about (implicit and). In fact you just found out that you need to do something to correctly parse keywords distinctly:

Here's the fix using the distinct directive from the Spirit Repository:

or_  = (xor_ >> qr::distinct(alnum|'_')[ "or" ]  >> or_ ) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
xor_ = (and_ >> qr::distinct(alnum|'_')[ "xor" ] >> xor_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
and_ = (not_ >> qr::distinct(alnum|'_')[ "and" ] >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
not_ = (qr::distinct(alnum|'_')[ "not" ] > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];

Next up, and also unrelated, you apparently wish to treat "xor_in1" etc. as valid identifiers. Change the rule accordingly:

var_ = qi::lexeme[ alpha >> *(alnum | char_("_")) ];

Now all cases pass:

Live On Coliru

result: ((a & b) ^ ((c & d) | (a & b)))
result: (((a & b) ^ (c & d)) | (a & b))
result: (a & b)
result: (a | b)
result: (xor_in1 ^ xor_in2)
result: (xorin1 ^ xorin2)
result: (and1 ^ xor)
result: (!a)
result: ((!a) & b)
result: (!(a & b))
result: (a | (b | c))

BONUS

You mentioned something about implicit and?

and_ = (not_ >> -qr::distinct(alnum|'_')[ "and" ] >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];

Some nice test cases:

Live On Coliru

//#define BOOST_SPIRIT_DEBUG
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/include/phoenix.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
#include <boost/spirit/repository/include/qi_distinct.hpp>
#include <boost/variant/recursive_wrapper.hpp>

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

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

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;

template <typename tag> struct binop
{
    explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { }
    expr oper1, oper2;
};

template <typename tag> struct unop
{
    explicit unop(const expr& o) : oper1(o) { }
    expr oper1;
};

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


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

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

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

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

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

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();

        or_  = (xor_ >>  qr::distinct(alnum|'_')[ "or" ]  >> or_ ) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
        xor_ = (and_ >>  qr::distinct(alnum|'_')[ "xor" ] >> xor_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
        and_ = (not_ >> -qr::distinct(alnum|'_')[ "and" ] >> and_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
        not_ = (qr::distinct(alnum|'_')[ "not" ] > simple       )  [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];

        simple = (('(' > expr_ > ')') | var_);
        var_   = 
            !qr::distinct(alnum|'_') [ lit("or")|"xor"|"and"|"not" ] >>
            qr::distinct(alnum|'_') [ alpha >> *(alnum | char_("_")) ]
            ;

        BOOST_SPIRIT_DEBUG_NODES((expr_) (or_) (xor_) (and_) (not_) (simple) (var_))
    }

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

int main()
{
    for (auto& input : std::list<std::string> {
#if 0
            "a or b or c;",
            "(a and b);",
            "a xor b;",
            "a or b;",
            "(a) or (b);",
            "((c and d) or (a and b));",
#endif
            "(a and b) xor ((c and d) or (a and b));",
            "(a b) xor ((c d) or (a b));",

            "a and b xor c and d or a and b;",
            "a b xor c d or a b;",

            /// Simpler tests:
            "a and b;",
            "a b;",
            "not a and b;",
            "not a b;",

            "not (a and b);",
            "not (a b);",
            })
    {
        auto f(std::begin(input)), l(std::end(input));
        parser<decltype(f)> p;

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

            std::cout << "\n======= input '" << input << "'\n";

            if (!ok)
                std::cerr << "invalid input\n";
            else
                std::cout << "result: " << result << "\n";

        } catch (const qi::expectation_failure<decltype(f)>& e)
        {
            std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
        }

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

Prints

======= input '(a and b) xor ((c and d) or (a and b));'
result: ((a & b) ^ ((c & d) | (a & b)))

======= input '(a b) xor ((c d) or (a b));'
result: ((a & b) ^ ((c & d) | (a & b)))

======= input 'a and b xor c and d or a and b;'
result: (((a & b) ^ (c & d)) | (a & b))

======= input 'a b xor c d or a b;'
result: (((a & b) ^ (c & d)) | (a & b))

======= input 'a and b;'
result: (a & b)

======= input 'a b;'
result: (a & b)

======= input 'not a and b;'
result: ((!a) & b)

======= input 'not a b;'
result: ((!a) & b)

======= input 'not (a and b);'
result: (!(a & b))

======= input 'not (a b);'
result: (!(a & b))
Community
  • 1
  • 1
sehe
  • 374,641
  • 47
  • 450
  • 633
  • Thank you for your response. The problem with the grammar http://stackoverflow.com/questions/8706356/boolean-expression-grammar-parser-in-c/8707598#8707598 is that it parses with wrong precedence e.g. a or b or c is (a | (b | c)), but the correct one is ((a | b) | c). The other problem is that your example fails to parse "ab cd or ef;". – Grigor Aghanyan May 21 '15 at 11:34
  • The output of the parser isn't the one I expec. E.g. for '(a and b) xor ((c and d) or (a and b));' the output is wrong as operations ("or") are considered as variables. – Grigor Aghanyan May 21 '15 at 12:09
  • I've edited my comment. I meant another issue with implicit and. It breaks the parsing of other boolean operations e.g. "or". – Grigor Aghanyan May 21 '15 at 12:14
  • Good spot. It's the precedence really. Just fix that, and it will be gone (AFAICT). Or you can wait until I get back to it – sehe May 21 '15 at 12:21
  • On the `(a | (b | c))` vs. `((a | b) | c)`; that's not precedence, it's associativity. And it doesn't matter because the binary operators are all commutative here. Also, the implicit `and` does break operator parsing so you need to update the `var` rule: **[Live On Coliru](http://coliru.stacked-crooked.com/a/6b45892a80cbda0f)** – sehe May 21 '15 at 15:31