我如何从本例中更改语法以解析"AND((OR(a b c))(NOT(d))) [英] How do i change the grammar from this example to parse "AND ( (OR (a b c)) (NOT (d)))

问题描述

C ++中的布尔表达式(语法)解析器

我正在尝试根据"sehe"提供的上述示例修改语法，以解析以下表达式."AND((OR(a b c))(NOt(d)))".

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)))".

有三个运算符AND/OR/NOT，NOT是一元运算符，但是AND和OR可以作用于多个操作数.

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

谢谢

推荐答案

更改后的语法实际上要简单得多，因为它避开了运算符优先级的问题.这是语法的'lisp'方法:)

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_;
};

如果您也想评估:

//////////////////////////////////////////////////
// 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); 
}

您可以使用

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

输出:

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).

奖励材料:

您可能已经注意到语法在角落变得非常对称.这恰恰是因为优先权问题已消失.因此，可能有必要进一步简化语法: simplified.cpp

---

完整代码示例

也在 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";
}

这篇关于我如何从本例中更改语法以解析"AND((OR(a b c))(NOT(d)))的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！