Wie analysiert man boolesche Ausdrücke und erstellt Syntaxbäume in C mit Boost Spirit?

Boolescher Ausdrucksgrammatik-Parser in C

Problem:

Parsen Sie einen booleschen Ausdruck, der als gegeben ist eine Zeichenfolge und erstellen Sie einen Baum, der den Syntaxbaum des Ausdrucks darstellt. Der Baum sollte den Prioritätsregeln folgen (NICHT, UND, XOR, ODER).

Antwort:

Verwendung von Boost Spirit:

1. Definieren Sie eine Aufzählung mit Tags, die die Operatoren darstellen (NOT, AND, XOR, ODER).

2. Definieren Sie einen rekursiven Variantentyp (expr), um die Baumknoten darzustellen:

   • var: Variablenname
   • unop: Unärer Operator
   • binop: Binärer Operator
3. Definieren Sie a Grammatik mit Boost Spirit Qi zum Parsen des booleschen Ausdrucks.
4. Erstellen Sie eine Besucherklasse, um den analysierten Ausdruck zu durchlaufen und ihn als Baum auszugeben.

Beispiel Verwendung:

using namespace qi;
using namespace phoenix;

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;

struct parser : grammar<It, expr(), Skipper> {
    parser() : parser::base_type(expr_) {
        not_ = ...
        or_  = ...
        xor_ = ...
        and_ = ...

        simple = '(' > expr_ > ')' | var_;
        var_ = lexeme[+alpha];
    }
    qi::rule<It, var(), Skipper> var_;
    qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};

int main() {
    std::string input = "(a and b) xor ((c and d) or (a and b));";
    const char *f = input.c_str(), *l = f + input.size();

    expr result;
    bool ok = phrase_parse(f, l, parser() > ';', qi::space, result);
    if (ok) {
        std::cout << result << '\n';
    }
}

Ergebnis:

((a and b) xor ((c and d) or (a and b)))

Das obige ist der detaillierte Inhalt vonWie analysiert man boolesche Ausdrücke und erstellt Syntaxbäume in C mit Boost Spirit?. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!