Comment puis-je analyser des expressions booléennes en C à l'aide de la bibliothèque Boost Spirit ?

Analyseur d'expressions booléennes en C

Introduction

L'analyse des expressions booléennes est une tâche fondamentale en informatique. Cela implique de convertir une expression lisible par l'homme en une structure de données qu'un ordinateur peut interpréter.

Analyse à l'aide de Boost Spirit

Une approche populaire pour analyser les expressions booléennes consiste à utiliser la bibliothèque Boost Spirit. Spirit fournit un cadre puissant et flexible pour définir et analyser les grammaires.

Voici une implémentation C basée sur Spirit :

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

using namespace boost::spirit;
using namespace boost::spirit::qi;

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

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&amp; l, const expr&amp; r) : oper1(l), oper2(r) { }
    expr oper1, oper2; 
};

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

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

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

Utilisation

Pour utiliser l'analyseur :

1. Créer une instance de l'analyseur class.
2. Passez l'expression booléenne à la fonction d'analyse avec les types d'itérateur et de skipper appropriés.
3. Le résultat sera un boost::variant qui contient la classe analysée. expression.

Exemple

auto expr = "a and b xor (c and d or a and b);";
expr parsed_expr;
qi::parse(expr.begin(), expr.end(), parser<std::string::const_iterator>(), parsed_expr);
std::cout << "Parsed expression: " << parsed_expr << std::endl;

Sortie

Parsed expression: ((a and b) xor ((c and d) or (a and b)))

Conclusion

Cette implémentation utilise le générateur d'analyseur de descente récursive de Boost Spirit pour créer un arbre syntaxique représentant l’expression analysée. Il gère correctement les règles de préséance, ce qui donne un arbre qui capture avec précision la structure logique de l'expression.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!