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

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?

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  struct binop; template  struct unop; typedef boost::variant >, boost::recursive_wrapper >, boost::recursive_wrapper >, boost::recursive_wrapper > > expr; 

(fuente completa a continuación)

Reglas gtwigticales

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 comstackdo 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  struct parser : qi::grammar { parser() : parser::base_type(expr_) { using namespace qi; expr_ = or_.alias(); or_ = (xor_ >> "or" >> xor_) [ _val = phx::construct>(_1, _2) ] | xor_ [ _val = _1 ]; xor_ = (and_ >> "xor" >> and_) [ _val = phx::construct>(_1, _2) ] | and_ [ _val = _1 ]; and_ = (not_ >> "and" >> not_) [ _val = phx::construct>(_1, _2) ] | not_ [ _val = _1 ]; not_ = ("not" > simple ) [ _val = phx::construct>(_1) ] | simple [ _val = _1 ]; simple = (('(' > expr_ > ')') | var_); var_ = qi::lexeme[ +alpha ]; } private: qi::rule var_; qi::rule not_, and_, xor_, or_, simple, expr_; }; 

Operando en el árbol de syntax

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 { printer(std::ostream& os) : _os(os) {} std::ostream& _os; // void operator()(const var& v) const { _os << v; } void operator()(const binop& b) const { print(" & ", b.oper1, b.oper2); } void operator()(const binop& b) const { print(" | ", b.oper1, b.oper2); } void operator()(const binop& 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& 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  #include  #include  #include  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  struct binop; template  struct unop; typedef boost::variant >, boost::recursive_wrapper >, boost::recursive_wrapper >, boost::recursive_wrapper > > expr; template  struct binop { explicit binop(const expr& l, const expr& r) : oper1(l), oper2(r) { } expr oper1, oper2; }; template  struct unop { explicit unop(const expr& o) : oper1(o) { } expr oper1; }; struct printer : boost::static_visitor { printer(std::ostream& os) : _os(os) {} std::ostream& _os; // void operator()(const var& v) const { _os << v; } void operator()(const binop& b) const { print(" & ", b.oper1, b.oper2); } void operator()(const binop& b) const { print(" | ", b.oper1, b.oper2); } void operator()(const binop& 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& 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  struct parser : qi::grammar { parser() : parser::base_type(expr_) { using namespace qi; expr_ = or_.alias(); or_ = (xor_ >> "or" >> or_ ) [ _val = phx::construct>(_1, _2) ] | xor_ [ _val = _1 ]; xor_ = (and_ >> "xor" >> xor_) [ _val = phx::construct>(_1, _2) ] | and_ [ _val = _1 ]; and_ = (not_ >> "and" >> and_) [ _val = phx::construct>(_1, _2) ] | not_ [ _val = _1 ]; not_ = ("not" > simple ) [ _val = phx::construct>(_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 var_; qi::rule not_, and_, xor_, or_, simple, expr_; }; int main() { for (auto& input : std::list { // 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 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& 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 { 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& b) const { print("and ", b.oper1, b.oper2); } void operator()(const binop& b) const { print("or ", b.oper2, b.oper1); } void operator()(const binop& 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& 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 

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.

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 progtwigción.

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 aquí un analizador que escribí en C # para analizar expresiones C # simples en líneas similares a sus requisitos.

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.