Wie kann ich boolesche Ausdrücke in C mithilfe der Boost Spirit-Bibliothek analysieren?

Boolescher Ausdrucksparser in C

Einführung

Das Parsen boolescher Ausdrücke ist eine grundlegende Aufgabe in der Informatik. Dabei geht es darum, einen für Menschen lesbaren Ausdruck in eine Datenstruktur umzuwandeln, die ein Computer interpretieren kann.

Parsen mit Boost Spirit

Ein beliebter Ansatz zum Parsen boolescher Ausdrücke ist die Verwendung der Boost Spirit-Bibliothek. Spirit bietet ein leistungsstarkes und flexibles Framework zum Definieren und Parsen von Grammatiken.

Hier ist eine C-Implementierung basierend auf 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_;
};

Verwendung

So verwenden Sie den Parser:

1. Erstellen Sie eine Instanz der Parser-Klasse.
2. Übergeben Sie die boolescher Ausdruck für die Parse-Funktion zusammen mit den entsprechenden Iterator- und Skipper-Typen.
3. Das Ergebnis ist ein boost::variant, der den analysierten Ausdruck enthält.

Beispiel

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;

Ausgabe

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

Fazit

Dies Die Implementierung nutzt den rekursiven Descent-Parser-Generator von Boost Spirit, um einen Syntaxbaum zu erstellen, der den analysierten Ausdruck darstellt. Es verarbeitet Vorrangregeln korrekt, was zu einem Baum führt, der die logische Struktur des Ausdrucks genau erfasst.

Das obige ist der detaillierte Inhalt vonWie kann ich boolesche Ausdrücke in C mithilfe der Boost Spirit-Bibliothek analysieren?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!