Comment Boost Spirit peut-il être utilisé pour analyser des expressions booléennes avec priorité aux opérateurs ?-C++-php.cn

Comment Boost Spirit peut-il être utilisé pour analyser des expressions booléennes avec priorité aux opérateurs ?

Linda Hamilton

Libérer： 2024-12-21 22:33:40

original

835 Les gens l'ont consulté

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

Analyse d'expressions booléennes

Étant donné une expression booléenne sous la forme : "a et b xor (c et d ou a et b);", le but est de analysez-le dans un arbre, en respectant les règles de préséance (pas, et, xor, ou).

Boost Spirit Implémentation

Boost Spirit peut être utilisé pour créer un analyseur de descente récursif basé sur des modèles d'expression. Voici l'implémentation :

Type de données abstrait

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;

Copier après la connexion

Règles de grammaire

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

Copier après la connexion

Fonctionnement sur l'arbre syntaxique

Pour parcourir et imprimer la syntaxe arbre :

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

Copier après la connexion

Test de sortie

Le l'analyseur gère correctement les règles de préséance et les sorties :

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

Copier après la connexion