Анализатор логических выражений (грамматика) в C++
Я хочу разобрать логическое выражение (в C++). Форма ввода:
a and b xor (c and d or a and b);
Я просто хочу разобрать это выражение в дереве, зная правило приоритета (не, и, или не, или). Поэтому приведенное выше выражение должно выглядеть примерно так:
(a and b) xor ((c and d) or (a and b));
парсеру.
И дерево будет иметь форму:
a
and
b
or
c
and
d
xor
a
and
b
Ввод будет либо через командную строку, либо в форме строки. Мне просто нужен парсер.
Есть ли источники, которые могут помочь мне сделать это?
5 ответов
Вот реализация, основанная на Boost Spirit.
Поскольку Boost Spirit генерирует парсеры рекурсивного спуска на основе шаблонов выражений, соблюдение "уникальных" (sic) правил приоритета (как уже упоминалось другими) довольно утомительно. Поэтому грамматике не хватает определенной элегантности.
Абстрактный тип данных
Я определил древовидную структуру данных, используя поддержку рекурсивного варианта Boost Variant, обратите внимание на определение 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;
(полный источник ниже)
Грамматические правила
Ниже приведено (немного утомительное) определение грамматики, как уже упоминалось.
Хотя я не считаю эту грамматику оптимальной, она вполне читаема, и у нас есть статически скомпилированный синтаксический анализатор со строго типизированным типом данных AST в примерно 50 строках кода. Все могло быть значительно хуже.
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_;
};
Работа с синтаксическим деревом
Очевидно, вы хотели бы оценить выражения. Сейчас я решил остановиться только на печати, поэтому мне не нужно искать таблицу для именованных переменных:)
Сначала обход рекурсивного варианта может показаться загадочным, но 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; }
Тестовый вывод:
Для тестовых случаев в коде выводится следующее, демонстрирующее правильную обработку правил приоритета путем добавления (избыточных) скобок:
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))
Полный код:
#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;
}
Бонус:
Для получения бонусных баллов, чтобы получить дерево в точности как показано в ОП:
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;
}
результат:
a
and
b
or
c
and
d
xor
a
and
b
Либо используйте генератор парсера, как уже упоминал Оли Чарльзуорт (yacc, bison, antlr; последний, по моему опыту, лучше подходит для C++, чем два других, хотя я какое-то время смотрел на них), либо создайте простой рекурсивный спуск синтаксический анализатор: для такого простого языка, как ваш, это может быть проще.
Смотрите мой SO ответ о том, как кодировать простые парсеры рекурсивного спуска.
Этот подход очень удобен для простых языков, таких как логические выражения. И концепции в значительной степени не зависят от вашего языка программирования.
Если, как и я, вы обнаружите, что накладные расходы и особенности разбора библиотек слишком велики для такой маленькой работы, вы можете очень легко написать собственный анализатор для простого сценария, подобного тому, который вы представляете. Смотрите здесь парсер, который я написал на C# для разбора простых выражений C# в соответствии с вашими требованиями.
Я столкнулся с огромным снижением производительности, когда попытался расширить набор двоичных операторов в примере @sehe. Я добавил следующие операторы:
eq_ = (neq_ >> "eq" >> eq_ ) [ _val = phx::construct<binop<op_eq>>(_1, _2) ] | neq_ [ _val = _1 ];
neq_ = (gt_ >> "neq" >> neq_ ) [ _val = phx::construct<binop<op_neq>>(_1, _2) ] | gt_ [ _val = _1 ];
gt_ = (lt_ >> "gt" >> gt_ ) [ _val = phx::construct<binop<op_gt>>(_1, _2) ] | lt_ [ _val = _1 ];
lt_ = (gte_ >> "lt" >> lt_ ) [ _val = phx::construct<binop<op_lt>>(_1, _2) ] | gte_ [ _val = _1 ];
gte_ = (lte_ >> "gte" >> gte_ ) [ _val = phx::construct<binop<op_gte>>(_1, _2) ] | lte_ [ _val = _1 ];
lte_ = (or_ >> "lte" >> lte_ ) [ _val = phx::construct<binop<op_lte>>(_1, _2) ] | or_ [ _val = _1 ];
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 ];
Анализ кода выше выполняется очень медленно, он зависает на несколько минут. Я попытался переписать эквивалентный код выше;
/*...*/
parser() : parser::base_type(expr_){
/*...*/
expr_ =
(
( ("not" > simple_ [_val = phx::construct<unop<op_not>>(_1)] ))
|
simple_ [_val = phx::construct<expr>(_1)])
>> *(
("and" >> simple_ [_val = phx::construct<binop<op_and>>(_val, _1)] )
|
("or" >> simple_ [_val = phx::construct<binop<op_or>>(_val, _1)] )
|
("xor" >> simple_ [_val = phx::construct<binop<op_xor>>(_val, _1)] )
|
("not" > simple_ [_val = phx::construct<unop<op_not>>(_val)] )
|
("gt" >> simple_ [_val = phx::construct<binop<op_gt>>(_val, _1)] )
|
("gte" >> simple_ [_val = phx::construct<binop<op_gte>>(_val, _1)] )
|
("lt" >> simple_ [_val = phx::construct<binop<op_lt>>(_val, _1)] )
|
("lte" >> simple_ [_val = phx::construct<binop<op_lte>>(_val, _1)] )
|
("eq" >> simple_ [_val = phx::construct<binop<op_eq>>(_val, _1)] )
|
("neq" >> simple_ [_val = phx::construct<binop<op_neq>>(_val, _1)] )
);
simple_ = (('(' > expr_ > ')') | var_);
var_ = qi::lexeme[ +alpha ];
}
/*...*/
qi::rule<It, var() , Skipper> var_;
qi::rule<It, expr(), Skipper> expr_, simple_;
};
Приведенный выше код мгновенно анализирует ввод, предоставленный op. Я не знаю, что вызывает снижение производительности, но вторая реализация как-то это решает. Странно.
Посмотрите на пример кода Mini C https://github.com/boostorg/spirit/tree/master/example/qi/compiler_tutorial/mini_c.
Особенно взгляните на expression.cpp, expression.hpp, expression_def.hpp и ast.hpp. Это хороший пример того, как анализировать выражения в AST.