c++ - online - simplificacion de expresiones booleanas ejercicios resueltos

Analizador de expresión booleana(gramática) en c++

Question

Quiero analizar una expresión booleana (en C ++). Forma de entrada:

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

Solo quiero analizar esta expresión en un árbol, conociendo la regla de precedencia (no, y, xor, o). Entonces, la expresión anterior debería verse más o menos así:

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

para el analizador.

Y el árbol sería de forma:

                        a
                   and
                        b
               or
                        c
                   and
                        d
        xor
                   a
              and
                   b

La entrada será a través de línea de comando o en forma de cadena. Solo necesito el analizador.

¿Hay alguna fuente que pueda ayudarme a hacer esto?

Answer 1

Aquí hay una implementación basada en Boost Spirit.

Debido a que Boost Spirit genera analizadores de descenso recursivos basados ​​en plantillas de expresión , respetar las reglas de precedencia "idiosincráticas" (sic) (como lo mencionaron otros) es bastante tedioso. Por lo tanto, la gramática carece de cierta elegancia.

Tipo de datos abstractos

Definí una estructura de datos de árbol usando el soporte de variante recursiva de Boost Variant, observe la definición de 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;

(fuente completa a continuación)

Reglas gramaticales

La siguiente es la definición de gramática (un poco tediosa), como se mencionó.

Aunque no considero óptima esta gramática, es bastante legible, y tenemos un analizador compilado estáticamente con un tipo de datos AST fuertemente tipado en aproximadamente 50 líneas de código. Las cosas podrían ser considerablemente peores.

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

Operando en el árbol de sintaxis

Obviamente, querrías evaluar las expresiones. Por ahora, decidí dejar de imprimir solo, así que no tengo que hacer la tabla de búsqueda para las variables con nombre :)

Atravesar una variante recursiva puede parecer críptico al principio, pero el boost::static_visitor<> es sorprendentemente simple una vez que lo boost::static_visitor<> :

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

Prueba de salida:

Para los casos de prueba en el código, se muestra lo siguiente, demostrando el manejo correcto de las reglas de precedencia agregando paréntesis (redundantes):

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

Código completo:

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

Prima:

Para puntos de bonificación, para obtener un árbol exactamente como se muestra en el PO:

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

resultado:

            a
        and 
            b
    or  
            c
        and 
            d
xor 
        a
    and 
        b

Answer 2

Eche un vistazo al código de ejemplo Mini C https://github.com/boostorg/spirit/tree/master/example/qi/compiler_tutorial/mini_c .

Especialmente eche un vistazo a expression.cpp, expression.hpp, expression_def.hpp y ast.hpp. Da un gran ejemplo sobre cómo analizar expresiones en un AST.

Answer 3

O use un generador de analizadores como ya mencionó Oli Charlesworth (yacc, bison, antlr; este último es en mi experiencia más adecuado para C ++ que los otros dos, aunque hace tiempo miro a alguno de ellos) o crea un descenso recursivo simple analizador: para un lenguaje tan simple como el suyo, este puede ser el enfoque más fácil.

Answer 4

Si, como a mí, le resulta demasiado caro e idiosincrasia de las bibliotecas de análisis para un trabajo tan pequeño, puede escribir fácilmente su propio analizador para un escenario simple como el que presenta. Vea here un analizador que escribí en C # para analizar expresiones C # simples en líneas similares a sus requisitos.

Answer 5

Vea mi respuesta SO sobre cómo codificar analizadores sintácticos de descenso recursivos simples .

Este enfoque es muy conveniente para lenguajes simples como expresiones booleanas. Y los conceptos son bastante independientes de su lenguaje de programación.