Expressão booleana (gramática) parser em c ++

Eu quero analisar uma expressão booleana (em C ++). Formulário de input:

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

Eu só quero analisar essa expressão em uma tree, conhecendo a regra de precedência (não, e, xor, ou). Então a expressão acima deve ser algo como:

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

para o parser.

E a tree seria de forma:

  a and b or c and d xor a and b 

A input será através da linha de comando ou na forma de uma string. Eu só preciso do parser.

Há alguma fonte que possa me ajudar a fazer isso?

Aqui está uma implementação baseada no Boost Spirit.

Como o Boost Spirit gera analisadores de descendência recursivos com base em modelos de expressão , respeitar as regras de precedência “idiossincráticas” (sic) (como mencionado por outros) é bastante entediante. Portanto, a gramática não possui uma certa elegância.

Tipo de dados abstratos

Eu defini uma estrutura de dados em tree usando o suporte à variante recursiva do Boost Variant, observe a definição 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; 

(fonte completa abaixo)

Regras de gramática

A seguir está a definição da gramática (um tanto tediosa), conforme mencionado.

Embora eu não considere esta gramática ideal, ela é bastante legível, e nós temos um analisador estaticamente compilado com tipos de dados AST fortemente tipados em aproximadamente 50 linhas de código. As coisas poderiam ser consideravelmente piores.

 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 na tree de syntax

Obviamente, você gostaria de avaliar as expressões. Por enquanto, decidi parar apenas imprimindo, então não preciso fazer a tabela de pesquisa para variables ​​nomeadas 🙂

Atravessar uma variante recursiva pode parecer enigmático no início, mas o boost::static_visitor<> é surpreendentemente simples quando você pega o jeito:

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

Saída de teste:

Para os casos de teste no código, o seguinte é gerado, demonstrando o tratamento correto das regras de precedência, adicionando parênteses (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; } 

Bônus:

Para pontos de bônus, para obter uma tree exatamente como mostrado no OP:

 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 

Ou use um gerador de parser como Oli Charlesworth já mencionou (yacc, bison, antlr; o último é na minha experiência mais adequado para C ++ que os outros dois, embora seja um tempo que eu olhei para qualquer um deles) ou crie uma descida recursiva simples analisador: para uma linguagem tão simples quanto a sua, essa pode ser a abordagem mais fácil.

Veja minha resposta SO sobre como codificar parsers de descida recursiva simples .

Essa abordagem é muito conveniente para linguagens simples, como expressões booleanas. E os conceitos são praticamente independentes da sua linguagem de programação.

Se, como eu, você encontrar demais as sobrecargas e as idiossincrasias das bibliotecas de análise para um trabalho tão pequeno, será muito fácil escrever seu próprio analisador em um cenário simples como o que você apresenta. Veja aqui um analisador que escrevi em C # para analisar expressões C # simples em linhas semelhantes às suas necessidades.

Dê uma olhada no código de exemplo do Mini C https://github.com/boostorg/spirit/tree/master/example/qi/compiler_tutorial/mini_c .

Especialmente, dê uma olhada no expression.cpp, expression.hpp, expression_def.hpp e ast.hpp. Ele dá um ótimo exemplo de como analisar expressões em um AST.