Boolescher Ausdruck (Grammatik) Parser in C ++

Möchte ich analysieren, ein boolescher Ausdruck (in C++). Input form:

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

Ich will nur analysieren, diesen Ausdruck in einen Baum, wissend, dass die Vorrang-Regel (not,and,xor,or).
Also der obige Ausdruck soll so Aussehen:

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

den parser.

Und die Struktur der form:

                        a
                   and
                        b
               or
                        c
                   and
                        d
        xor
                   a
              and
                   b

Wird die Eingabe entweder über die Befehlszeile oder in der form einer Zeichenfolge.
Ich brauche nur den parser.

Gibt es irgendwelche Quellen, die mir helfen können, dies zu tun?

InformationsquelleAutor der Frage A Gore | 2012-01-02

  1. 85

    Hier ist eine Umsetzung basierend auf Boost Geist.

    Weil Boost Geist erzeugt rekursiven Abstieg Parser basiert auf expression templateszu Ehren der 'eigenwilligen' (sic) Vorrang (wie von anderen erwähnt) ist ziemlich langweilig. Deshalb ist die Grammatik fehlt eine gewisse Eleganz.

    Abstrakten Datentyp

    Definierte ich eine Baumstruktur mit Boost Variante der rekursiven Variante unterstützen, beachten Sie die definition von expr:

    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;

    (source unten)

    Grammatik-Regeln

    Im folgenden ist die (etwas mühsame) Grammatik definition, wie bereits erwähnt.

    Obwohl ich nicht betrachten dieser Grammatik optimal, es ist durchaus lesbar, und wir haben uns ein statisch kompiliert parser mit stark typisierten AST-Datentyp in etwa 50 Zeilen code. Dinge könnten wesentlich schlechter.

    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();

        or_  = (xor_ >> "or"  >> xor_) [ _val = phx::construct<binop<op_or >>(_1, _2) ] | xor_   [ _val = _1 ];
        xor_ = (and_ >> "xor" >> and_) [ _val = phx::construct<binop<op_xor>>(_1, _2) ] | and_   [ _val = _1 ];
        and_ = (not_ >> "and" >> not_) [ _val = phx::construct<binop<op_and>>(_1, _2) ] | not_   [ _val = _1 ];
        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _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_;
};

    Betriebssystem auf dem syntax-Baum

    Offensichtlich wollen Sie auswerten der Ausdrücke. Für jetzt, ich beschlossen, zu stoppen auf Druck, so dass ich nicht haben, um die lookup-Tabelle für die Variablen bezeichnet 🙂

    Durchqueren eine rekursive Variante sieht vielleicht kryptisch auf den ersten, aber die boost::static_visitor<> ist überraschend einfach, sobald Sie den Dreh raus:

    struct printer : boost::static_visitor<void>
{
    printer(std::ostream& os) : _os(os) {}
    std::ostream& _os;

    //
    void operator()(const var& v) const { _os << v; }

    void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
    void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        _os << "(";
            boost::apply_visitor(*this, l);
            _os << op;
            boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << "(";
            _os << "!";
            boost::apply_visitor(*this, u.oper1);
        _os << ")";
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }

    Test Ausgabe:

    Für die Testfälle im code folgende Ausgabe demonstriert richtige Umgang mit den Vorrang-Regeln durch hinzufügen von (unnötigen) Klammern:

    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ändige Code:

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

namespace qi    = boost::spirit::qi;
namespace phx   = boost::phoenix;

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

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

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

struct printer : boost::static_visitor<void>
{
    printer(std::ostream& os) : _os(os) {}
    std::ostream& _os;

    //
    void operator()(const var& v) const { _os << v; }

    void operator()(const binop<op_and>& b) const { print(" & ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print(" | ", b.oper1, b.oper2); }
    void operator()(const binop<op_xor>& b) const { print(" ^ ", b.oper1, b.oper2); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        _os << "(";
            boost::apply_visitor(*this, l);
            _os << op;
            boost::apply_visitor(*this, r);
        _os << ")";
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << "(";
            _os << "!";
            boost::apply_visitor(*this, u.oper1);
        _os << ")";
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ boost::apply_visitor(printer(os), e); return os; }

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();

        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 ];
        not_ = ("not" > simple       ) [ _val = phx::construct<unop <op_not>>(_1)     ] | simple [ _val = _1 ];

        simple = (('(' > expr_ > ')') | var_);
        var_ = qi::lexeme[ +alpha ];

        BOOST_SPIRIT_DEBUG_NODE(expr_);
        BOOST_SPIRIT_DEBUG_NODE(or_);
        BOOST_SPIRIT_DEBUG_NODE(xor_);
        BOOST_SPIRIT_DEBUG_NODE(and_);
        BOOST_SPIRIT_DEBUG_NODE(not_);
        BOOST_SPIRIT_DEBUG_NODE(simple);
        BOOST_SPIRIT_DEBUG_NODE(var_);
    }

  private:
    qi::rule<It, var() , Skipper> var_;
    qi::rule<It, expr(), Skipper> not_, and_, xor_, or_, simple, expr_;
};

int main()
{
    for (auto& input : std::list<std::string> {
            //From the OP:
            "(a and b) xor ((c and d) or (a and b));",
            "a and b xor (c and d or a and b);",

            ///Simpler tests:
            "a and b;",
            "a or b;",
            "a xor b;",
            "not a;",
            "not a and b;",
            "not (a and b);",
            "a or b or c;",
            })
    {
        auto f(std::begin(input)), l(std::end(input));
        parser<decltype(f)> p;

        try
        {
            expr result;
            bool ok = qi::phrase_parse(f,l,p > ';',qi::space,result);

            if (!ok)
                std::cerr << "invalid input\n";
            else
                std::cout << "result: " << result << "\n";

        } catch (const qi::expectation_failure<decltype(f)>& e)
        {
            std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
        }

        if (f!=l) std::cerr << "unparsed: '" << std::string(f,l) << "'\n";
    }

    return 0;
}

    Bonus:

    Für bonus-Punkte zu bekommen, ein Baum-genau wie im OP:

    static const char indentstep[] = "    ";

struct tree_print : boost::static_visitor<void>
{
    tree_print(std::ostream& os, const std::string& indent=indentstep) : _os(os), _indent(indent) {}
    std::ostream& _os;
    std::string _indent;

    void operator()(const var& v) const { _os << _indent << v << std::endl; }

    void operator()(const binop<op_and>& b) const { print("and ", b.oper1, b.oper2); }
    void operator()(const binop<op_or >& b) const { print("or  ", b.oper2, b.oper1); }
    void operator()(const binop<op_xor>& b) const { print("xor ", b.oper2, b.oper1); }

    void print(const std::string& op, const expr& l, const expr& r) const
    {
        boost::apply_visitor(tree_print(_os, _indent+indentstep), l);
        _os << _indent << op << std::endl;
        boost::apply_visitor(tree_print(_os, _indent+indentstep), r);
    }

    void operator()(const unop<op_not>& u) const
    {
        _os << _indent << "!";
        boost::apply_visitor(tree_print(_os, _indent+indentstep), u.oper1);
    }
};

std::ostream& operator<<(std::ostream& os, const expr& e)
{ 
    boost::apply_visitor(tree_print(os), e); return os; 
}

    Ergebnis:

                a
        and 
            b
    or  
            c
        and 
            d
xor 
        a
    and 
        b

    InformationsquelleAutor der Antwort sehe

  2. 5

    Entweder einen parser-generator wie Oli Charlesworth bereits erwähnt (yacc, bison, antlr; die letztere ist meiner Erfahrung nach besser geeignet, C++ als die beiden anderen ist es zwar eine Weile, ich sah jeden von Ihnen) oder erstellen eines einfachen recursive descent parsers: eine Sprache so einfach wie die Eure, kann dies der einfachere Ansatz.

    InformationsquelleAutor der Antwort Dietmar Kühl

  3. 2

    Sehen meine Antwort, wie man code einfach recursive-descent-Parser.

    Dieser Ansatz ist sehr praktisch für einfache Sprachen wie Boolesche Ausdrücke. Und die Konzepte sind so ziemlich unabhängig von der Programmiersprache.

    InformationsquelleAutor der Antwort Ira Baxter

  4. 1

    Wenn Sie, wie ich, finden die overhead-und die Eigenheiten der parsing-libraries zu viel für so einen kleinen job haben, können Sie sehr einfach schreiben Sie Ihre eigenen parser für ein einfaches Szenario, wie Sie Sie präsentieren. Sehen hier für einen parser schrieb ich in C# zu analysieren, einfache C# - Ausdrücke, die Analog zu Ihren Anforderungen.

    InformationsquelleAutor der Antwort Kent Boogaart

  5. 0

    Haben Sie einen Blick auf die Mini-C-Beispiel-code https://github.com/boostorg/spirit/tree/master/example/qi/compiler_tutorial/mini_c.

    Vor allem haben Sie einen Blick auf die expression.cpp Ausdruck.hpp, expression_def.hpp, und ast.hpp. Es gibt ein tolles Beispiel, wie das Parsen von Ausdrücken in eine AST.

    InformationsquelleAutor der Antwort gvd

Schreibe einen Kommentar