The parser parses the expression which involves binary operators (+,-,*,/) in the right precedence. However I can't get it to work with the logical expressions (&&,||).
For example, the result for the following expression should be 1 (true) (currently its 0):
1 || 0 && 0
The rule I wrote currently parses from left to right with no && precedence:
expression = (uint_[_val = _1] | '(' >> expression[_val = _1] >> ')') * (("&&" >> (uint_[_val = (_val && _1)] | expression[_val = (_val && _1)])) | ("||" >> (uint_[_val = (_val || _1)] | expression[_val = (_val || _1)])));
Moreover, the rule currently does not do short-circuiting.
If you want heterogeneous evaluations (not just boolean predicates), unary operators, precedence, associativity, look at some examples I made on this site.
Usually they separate the evaluation stage from the parsing stage:
As long as you conflate parsing with evaluation, there can NEVER be any useful sense of "short-cutting" since the parsing can not be skipped regardless.
Seeing the example from Boolean expression (grammar) parser in c++ and Support implied AND operation in boost spirit boolean expression parser, you can use nested rules to impose precedence:
or_ = (xor_ >> qr::distinct(alnum | '_')["||"] >> or_) //
[_val = phx::construct<binop<op_or>>(_1, _2)] |
xor_[_val = _1];
xor_ = (and_ >> qr::distinct(alnum | '_')["^"] >> xor_) //
[_val = phx::construct<binop<op_xor>>(_1, _2)] |
and_[_val = _1];
and_ = (not_ >> -qr::distinct(alnum | '_')["&&"] >> and_) //
[_val = phx::construct<binop<op_and>>(_1, _2)] |
not_[_val = _1];
not_ = (qr::distinct(alnum | '_')["!"] > simple) //
[_val = phx::construct<unop<op_not>>(_1)] |
simple[_val = _1];
Now this creates an AST that can be re-evaluated later. Because parsing ISN'T conflated with evaluation, shortcut simplification can be done.
Here's a demo adapted towards your question:
// #define BOOST_SPIRIT_DEBUG
#include <boost/phoenix.hpp>
#include <boost/spirit/include/qi.hpp>
#include <boost/spirit/repository/include/qi_distinct.hpp>
namespace qi = boost::spirit::qi;
namespace qr = boost::spirit::repository::qi;
namespace phx = boost::phoenix;
using var = std::string;
template <typename> struct binop;
template <typename> struct unop;
typedef boost::variant<var, //
bool, //
boost::recursive_wrapper<unop<struct op_not>>, //
boost::recursive_wrapper<binop<struct op_and>>, //
boost::recursive_wrapper<binop<struct op_xor>>, //
boost::recursive_wrapper<binop<struct op_or>> //
>
expr;
template <typename> struct binop {
expr oper1, oper2;
auto operator<=>(binop const&) const = default;
};
template <typename> struct unop {
expr oper1;
auto operator<=>(unop const&) const = default;
};
struct print_f {
std::ostream& _os;
void operator()(expr const& e) const { boost::apply_visitor(*this, e); }
void operator()(bool const& b) const { _os << (b?1:0); }
void operator()(var const& v) const { _os << v; }
void operator()(binop<op_and> const& b) const { print(" && ", b.oper1, b.oper2); }
void operator()(binop<op_or> const& b) const { print(" || ", b.oper1, b.oper2); }
void operator()(binop<op_xor> const& b) const { print(" ^ ", b.oper1, b.oper2); }
void print(std::string const& op, expr const& l, expr const& r) const {
_os << "("; operator()(l); _os << op; operator()(r); _os << ")";
}
void operator()(unop<op_not> const& u) const {
_os << "("; _os << "!"; operator()(u.oper1); _os << ")";
}
};
struct simplify_f {
expr operator()(expr const& e) const {
auto simplified = boost::apply_visitor(*this, e);
if (simplified != e)
std::cout << " - simplified: " << e << " -> " << simplified << "\n";
return simplified;
}
expr operator()(auto const& v) const { return v; }
expr operator()(binop<op_and> const& b) const {
auto lhs = operator()(b.oper1);
auto rhs = operator()(b.oper2);
if (static_false(lhs)) return rhs;
if (static_false(rhs)) return lhs;
if (lhs == rhs) return lhs; // a && a == a
return binop<op_and>{lhs, rhs};
}
expr operator()(binop<op_or> const& b) const {
auto lhs = operator()(b.oper1);
auto rhs = operator()(b.oper2);
if (static_true(lhs) || static_true(rhs)) return true;
if (static_false(lhs)) return rhs;
if (static_false(rhs)) return lhs;
if (lhs == rhs) return lhs; // a || a == a
return binop<op_or>{lhs, rhs};
}
expr operator()(binop<op_xor> const& b) const {
auto lhs = operator()(b.oper1);
auto rhs = operator()(b.oper2);
if (static_true(lhs)) return operator()(unop<op_not>(rhs));
if (static_true(rhs)) return operator()(unop<op_not>(lhs));
if (static_false(lhs)) return rhs;
if (static_false(rhs)) return lhs;
if (lhs == rhs) return false; // a ^ a == false
if (lhs == expr{unop<op_not>(rhs)}) return true; // a ^ !a == true
if (rhs == expr{unop<op_not>(lhs)}) return true; // !a ^ a == true
return binop<op_xor>{lhs, rhs};
}
expr operator()(unop<op_not> const& u) const {
auto lhs = operator()(u.oper1);
if (static_true(lhs)) return false;
if (static_false(lhs)) return true;
return unop<op_not>{lhs};
}
private:
static bool static_true(expr const& e) { return e == expr{true}; }
static bool static_false(expr const& e) { return e == expr{false}; }
};
enum Trace { verbose, silent };
template <typename Map> struct eval_f {
Map& map_;
Trace trace_ = verbose;
bool operator()(expr const& e) const {
auto val = boost::apply_visitor(*this, e);
if (trace_ == verbose && (e != expr{val}))
std::cout << " - trace eval: " << e << " -> " << val << "\n";
return val;
}
bool operator()(bool const& b) const { return b; }
bool operator()(var const& v) const { return map_[v]; }
bool operator()(binop<op_and> const& b) const { return operator()(b.oper1) && operator()(b.oper2); }
bool operator()(binop<op_or> const& b) const { return operator()(b.oper1) || operator()(b.oper2); }
bool operator()(binop<op_xor> const& b) const { return operator()(b.oper1) != operator()(b.oper2); }
bool operator()(unop<op_not> const& u) const { return !operator()(u.oper1); }
};
std::ostream& operator<<(std::ostream& os, expr const& e) {
boost::apply_visitor(print_f(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_) //
[_val = phx::construct<binop<op_or>>(_1, _2)] | xor_[_val = _1];
xor_ = (and_ >> qr::distinct(alnum | '_')["^"] >> xor_) //
[_val = phx::construct<binop<op_xor>>(_1, _2)] | and_[_val = _1];
and_ = (not_ >> qr::distinct(alnum | '_')["&&"] >> and_) //
[_val = phx::construct<binop<op_and>>(_1, _2)] | not_[_val = _1];
not_ = (qr::distinct(alnum | '_')["!"] > simple) //
[_val = phx::construct<unop<op_not>>(_1)] | simple[_val = _1];
simple = (('(' > expr_ > ')') | lit_ | var_);
lit_ = qi::uint_parser<bool, 2, 1, 1>{} | qi::bool_;
var_ = qr::distinct(alnum | '_')[alpha >> *(alnum | char_("_"))];
BOOST_SPIRIT_DEBUG_NODES((expr_)(or_)(xor_)(and_)(not_)(simple)(var_)(lit_));
}
private:
qi::rule<It, var()> var_;
qi::rule<It, bool()> lit_;
qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};
int main() {
std::cout << std::boolalpha;
static parser<std::string::const_iterator> const p;
static simplify_f const simplify;
for (auto const& input : std::list<std::string>{
"1 || 0 && 0",
"(a && b) ^ ((c && d) || (a && b))",
"a && b ^ c && d || a && b",
/// Simpler tests:
"a && b",
"! a && b",
"! (a && b)",
"a || b || c",
"(a && b)",
"a ^ b",
"a || b",
"(a) || (b)",
"((c && d) || (a && b))",
}) {
auto f(std::begin(input)), l(std::end(input));
try {
expr parsed;
bool ok = qi::phrase_parse(f, l, p, qi::space, parsed);
std::cout << "\n======= input '" << input << "'\n";
if (!ok)
std::cerr << "invalid input\n";
else {
std::cout << "result: " << parsed << "\n";
auto simplified = simplify(parsed);
if (simplified != parsed)
std::cout << "simplified: " << simplified << "\n";
std::map<std::string, bool> vars {{"a", true}, {"b", true}, {"c", true}, {"d", false}};
auto value = eval_f{vars}(simplified);
std::cout << "evaluated: " << value << "\n";
auto original = eval_f{vars, silent}(parsed);
assert(original == value); // simplify should not change the result
}
} catch (qi::expectation_failure<decltype(f)> const& e) {
std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
}
if (f != l)
std::cerr << "unparsed: '" << std::string(f, l) << "'\n";
}
}
Printing
======= input '1 || 0 && 0'
result: (1 || (0 && 0))
- simplified: (0 && 0) -> false
- simplified: (1 || (0 && 0)) -> true
simplified: 1
evaluated: true
======= input '(a && b) ^ ((c && d) || (a && b))'
result: ((a && b) ^ ((c && d) || (a && b)))
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a && b) -> true
- trace eval: c -> true
- trace eval: d -> false
- trace eval: (c && d) -> false
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a && b) -> true
- trace eval: ((c && d) || (a && b)) -> true
- trace eval: ((a && b) ^ ((c && d) || (a && b))) -> false
evaluated: false
======= input 'a && b ^ c && d || a && b'
result: (((a && b) ^ (c && d)) || (a && b))
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a && b) -> true
- trace eval: c -> true
- trace eval: d -> false
- trace eval: (c && d) -> false
- trace eval: ((a && b) ^ (c && d)) -> true
- trace eval: (((a && b) ^ (c && d)) || (a && b)) -> true
evaluated: true
======= input 'a && b'
result: (a && b)
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a && b) -> true
evaluated: true
======= input '! a && b'
result: ((!a) && b)
- trace eval: a -> true
- trace eval: (!a) -> false
- trace eval: ((!a) && b) -> false
evaluated: false
======= input '! (a && b)'
result: (!(a && b))
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a && b) -> true
- trace eval: (!(a && b)) -> false
evaluated: false
======= input 'a || b || c'
result: (a || (b || c))
- trace eval: a -> true
- trace eval: (a || (b || c)) -> true
evaluated: true
======= input '(a && b)'
result: (a && b)
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a && b) -> true
evaluated: true
======= input 'a ^ b'
result: (a ^ b)
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a ^ b) -> false
evaluated: false
======= input 'a || b'
result: (a || b)
- trace eval: a -> true
- trace eval: (a || b) -> true
evaluated: true
======= input '(a) || (b)'
result: (a || b)
- trace eval: a -> true
- trace eval: (a || b) -> true
evaluated: true
======= input '((c && d) || (a && b))'
result: ((c && d) || (a && b))
- trace eval: c -> true
- trace eval: d -> false
- trace eval: (c && d) -> false
- trace eval: a -> true
- trace eval: b -> true
- trace eval: (a && b) -> true
- trace eval: ((c && d) || (a && b)) -> true
evaluated: true