Wie kann Boost Spirit verwendet werden, um boolesche Ausdrücke mit Operatorpriorität zu analysieren?

Boolesche Ausdrucksanalyse

Bei einem gegebenen booleschen Ausdruck in der Form: „a und b xor (c und d oder a und b);“ besteht das Ziel darin Parse es in einen Baum und befolge dabei die Prioritätsregeln (nicht, und, xor, oder).

Boost Spirit Implementierung

Boost Spirit kann verwendet werden, um einen rekursiven Abstiegsparser basierend auf Ausdrucksvorlagen zu erstellen. Hier ist die Implementierung:

Abstrakter Datentyp

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;

Grammatikregeln

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

Arbeiten am Syntaxbaum

Zum Durchlaufen und Drucken der Syntax Baum:

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 Ausgabe

Der Parser verarbeitet Prioritätsregeln korrekt und gibt Folgendes aus:

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)

Vollständiger Code und Live-Beispiel (Coliru)

[Klicken Sie hier, um den vollständigen Code anzuzeigen Coliru](https://coliru.stacked-crooked.com/a/a795dea9a310e79bb12db3fe86fa61cf)

Das obige ist der detaillierte Inhalt vonWie kann Boost Spirit verwendet werden, um boolesche Ausdrücke mit Operatorpriorität zu analysieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!