рекурсия — преобразование логической формулы в конъюнктивную нормальную форму в переполнении стека

Вдохновленный тем, что я мало знаю о Boost.Proto, я попытался изменить ваш код, чтобы сделать возможными независимые преобразования. Этот подход использует 4 прохода (устранение_ффайса, устранение_импульса, распространение_ответов и распространение_ордина) и в каждом из них он перестраивает ast. Может быть способ сделать то же самое за один проход, возможно, с лучшей производительностью, но я думаю, что такой подход будет (даже) сложнее понять.

Объяснение изменений:

Первое изменение немного безвозмездно, но я действительно думаю, что все phx::construct...делает грамматику труднее читать. Я использую грамматику:

    iff_ = as_iff[imp_ >> "iff" >> iff_] | imp_;
imp_ = as_imp[or_ >> "imp" >> imp_] | or_;
or_ = as_or[and_ >> "or" >> or_] | and_;
and_ = as_and[not_ >> "and" >> and_] | not_;
not_ = as_not["not" > simple] | simple;

Для того, чтобы использовать это, вам нужно адаптировать unop а также binop с помощью BOOST_FUSION_ADAPT_TPL_STRUCT и объявить as_xxx как:

const as<binop<op_xxx>> as_xxx={};

Если вам не нравится это изменение, ваша оригинальная грамматика также должна работать (если вы добавляете using namespace ast;).

Я положил все, что связано с АСТ внутри namespace ast и сделал несколько дополнений:

• enum class expr_type: порядок его перечислителей должен быть синхронизирован с параметрами в варианте. Он используется для проверки того, имеет ли один из потомков узла определенный тип.
• get_expr_type: просто возвращает тип выражения.
• printer: теперь он просто печатает переданное выражение, без каких-либо преобразований. Может быть, это может быть изменено, чтобы быть умнее в размещении скобок.
• операторы !, && а также ||: они используются для облегчения восстановления AST.

И наконец преобразования. Каждое преобразование использует ast_helper<Transformation> в качестве своей базы. Эта структура имеет несколько повторно используемых функций-членов:

• pass_through: создает узел того же типа, который имеет в качестве членов, результат преобразования исходных элементов.
• recurse: применяет преобразование к текущему узлу.
• left: получает первый член узла независимо от типа узла. Используется в более сложных преобразованиях, чтобы немного помочь с удобочитаемостью.
• child0: точно так же, как left, но имя имеет больше смысла в унарных узлах.
• right: получает второго члена узла.

eliminate_imp :
Это действительно легко:

• Если вы получите binop<op_imp> вернуть !p || q, куда p а также q являются результатом применения преобразования к первому и второму операндам соответственно.
• Если вы получили что-то еще, верните узел того же типа, применяя преобразование к его операндам (pass_through).

eliminate_iff :
Это в основном то же самое, меняя binop<op_iff> с (p || !q)&&(!p || q),

distribute_nots :

• Если вы получаете что-то, что не является unop<op_not> просто pass_through.

• Если вы получите unop<op_not>Сначала проверьте тип своего операнда:

  • Если это и, заменить !p || !q,
  • Если это или, заменить !p && !q,
  • Если это не так, заменить p,

distribute_ors :

• Если это что-то, кроме или, pass_through.
• Если это или:
  • Проверьте, является ли его первый операнд and, Если это распространять ors и применить преобразование снова в случае, если другое or->and есть.
  • Проверьте, является ли его второй операнд and, Сделайте аналогичную работу.
  • Если ни один прямой ребенок не является andпроверить рекурсивно, если есть and в поддереве, начиная с этого узла. Если это произойдет, то все закончится плавающим наверху, поэтому нам нужно вернуться к pass_through.
  • Если нет and в поддереве это уже в CNF и просто pass_through.

Бег на Идеоне

Полный код:

#include <boost/spirit/include/qi.hpp>
#include <boost/fusion/include/adapt_struct.hpp>

#include <boost/variant/recursive_wrapper.hpp>

namespace qi = boost::spirit::qi;// Abstract data type

struct op_or {};
struct op_and {};
struct op_imp {};
struct op_iff {};
struct op_not {};

namespace ast
{
typedef std::string var;
template <typename tag> struct binop;
template <typename tag> struct unop;

enum class expr_type { var = 0, not_, and_, or_, imp, iff };
typedef boost::variant<var,
boost::recursive_wrapper<unop <op_not> >,
boost::recursive_wrapper<binop<op_and> >,
boost::recursive_wrapper<binop<op_or> >,
boost::recursive_wrapper<binop<op_imp> >,
boost::recursive_wrapper<binop<op_iff> >
> expr;

expr_type get_expr_type(const expr& expression)
{
return static_cast<expr_type>(expression.which());
}

template <typename tag> struct binop
{
expr oper1, oper2;
};

template <typename tag> struct unop
{
expr oper1;
};

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

//
void operator()(const ast::var& v) const { _os << v; }void operator()(const ast::binop<op_and>& b) const { print(" and ", b.oper1, b.oper2); }
void operator()(const ast::binop<op_or>& b) const { print(" or ", b.oper1, b.oper2); }
void operator()(const ast::binop<op_iff>& b) const { print(" iff ", b.oper1, b.oper2); }
void operator()(const ast::binop<op_imp>& b) const { print(" imp ", b.oper1, b.oper2); }

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

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

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

expr operator!(const expr& e)
{
return unop<op_not>{e};
}

expr operator||(const expr& l, const expr& r)
{
return binop<op_or>{l, r};
}

expr operator&&(const expr& l, const expr& r)
{
return binop<op_and>{l, r};
}

}

BOOST_FUSION_ADAPT_TPL_STRUCT(
(Tag),
(ast::binop) (Tag),
(ast::expr, oper1)
(ast::expr, oper2)
)

BOOST_FUSION_ADAPT_TPL_STRUCT(
(Tag),
(ast::unop) (Tag),
(ast::expr, oper1)
)// Grammar rules

template <typename It, typename Skipper = qi::space_type>
struct parser : qi::grammar<It, ast::expr(), Skipper>
{
parser() : parser::base_type(expr_)
{
using namespace qi;
const as<ast::binop<op_iff> > as_iff = {};
const as<ast::binop<op_imp> > as_imp = {};
const as<ast::binop<op_or> > as_or = {};
const as<ast::binop<op_and> > as_and = {};
const as<ast::unop<op_not> > as_not = {};

expr_ = iff_.alias();

iff_ = as_iff[imp_ >> "iff" >> iff_] | imp_;
imp_ = as_imp[or_ >> "imp" >> imp_] | or_;
or_ = as_or[and_ >> "or" >> or_] | and_;
and_ = as_and[not_ >> "and" >> and_] | not_;
not_ = as_not["not" > simple] | simple;

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

BOOST_SPIRIT_DEBUG_NODE(expr_);
BOOST_SPIRIT_DEBUG_NODE(iff_);
BOOST_SPIRIT_DEBUG_NODE(imp_);
BOOST_SPIRIT_DEBUG_NODE(or_);
BOOST_SPIRIT_DEBUG_NODE(and_);
BOOST_SPIRIT_DEBUG_NODE(not_);
BOOST_SPIRIT_DEBUG_NODE(simple);
BOOST_SPIRIT_DEBUG_NODE(var_);
}

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

template <typename Transform>
struct ast_helper : boost::static_visitor<ast::expr>
{

template <typename Tag>
ast::expr pass_through(const ast::binop<Tag>& op) const
{
return ast::binop<Tag>{recurse(op.oper1), recurse(op.oper2)};
}

template <typename Tag>
ast::expr pass_through(const ast::unop<Tag>& op) const
{
return ast::unop<Tag>{recurse(op.oper1)};
}

ast::expr pass_through(const ast::var& variable) const
{
return variable;
}

ast::expr recurse(const ast::expr& expression) const
{
return boost::apply_visitor(Transform{}, expression);
}

struct left_getter:boost::static_visitor<ast::expr>
{
template< template<class> class Op,typename Tag>
ast::expr operator()(const Op<Tag>& op) const
{
return op.oper1;
}

ast::expr operator()(const ast::var&) const
{
return{};//throw something?
}
};ast::expr left(const ast::expr& expression) const
{
return boost::apply_visitor(left_getter{}, expression);
}

ast::expr child0(const ast::expr& expression) const
{
return left(expression);
}

struct right_getter :boost::static_visitor<ast::expr>
{
template<typename Tag>
ast::expr operator()(const ast::binop<Tag>& op) const
{
return op.oper2;
}

template<typename Expr>
ast::expr operator()(const Expr&) const
{
return{};//throw something?
}
};

ast::expr right(const ast::expr& expression) const
{
return boost::apply_visitor(right_getter{}, expression);
}

};

struct eliminate_imp : ast_helper<eliminate_imp>
{
template <typename Op>
ast::expr operator()(const Op& op) const
{
return pass_through(op);
}

ast::expr operator()(const ast::binop<op_imp>& imp) const
{
return !recurse(imp.oper1) || recurse(imp.oper2);
}

ast::expr operator()(const ast::expr& expression) const
{
return recurse(expression);
}
};

struct eliminate_iff : ast_helper<eliminate_iff>
{
template <typename Op>
ast::expr operator()(const Op& op) const
{
return pass_through(op);
}

ast::expr operator()(const ast::binop<op_iff>& imp) const
{
return (recurse(imp.oper1) || !recurse(imp.oper2)) && (!recurse(imp.oper1) || recurse(imp.oper2));
}

ast::expr operator()(const ast::expr& expression) const
{
return recurse(expression);
}
};

struct distribute_nots : ast_helper<distribute_nots>
{
template <typename Op>
ast::expr operator()(const Op& op) const
{
return pass_through(op);
}

ast::expr operator()(const ast::unop<op_not>& not_) const
{
switch (ast::get_expr_type(not_.oper1)) //There is probably a better solution
{
case ast::expr_type::and_:
return recurse(!recurse(left(not_.oper1))) || recurse(!recurse(right(not_.oper1)));

case ast::expr_type::or_:
return recurse(!recurse(left(not_.oper1))) && recurse(!recurse(right(not_.oper1)));

case ast::expr_type::not_:
return recurse(child0(not_.oper1));
default:
return pass_through(not_);
}
}

ast::expr operator()(const ast::expr& expression) const
{
return recurse(expression);
}
};

struct any_and_inside : boost::static_visitor<bool>
{
any_and_inside(const ast::expr& expression) :expression(expression) {}
const ast::expr& expression;

bool operator()(const ast::var&) const
{
return false;
}

template <typename Tag>
bool operator()(const ast::binop<Tag>& op) const
{
return boost::apply_visitor(*this, op.oper1) || boost::apply_visitor(*this, op.oper2);
}

bool operator()(const ast::binop<op_and>&) const
{
return true;
}

template<typename Tag>
bool operator()(const ast::unop<Tag>& op) const
{
return boost::apply_visitor(*this, op.oper1);
}explicit operator bool() const
{
return boost::apply_visitor(*this, expression);
}

};

struct distribute_ors : ast_helper<distribute_ors>
{
template <typename Op>
ast::expr operator()(const Op& op) const
{
return pass_through(op);
}

ast::expr operator()(const ast::binop<op_or>& or_) const
{
if (ast::get_expr_type(or_.oper1) == ast::expr_type::and_)
{
return recurse(recurse(left(or_.oper1)) || recurse(or_.oper2))
&& recurse(recurse(right(or_.oper1)) || recurse(or_.oper2));
}
else if (ast::get_expr_type(or_.oper2) == ast::expr_type::and_)
{
return recurse(recurse(or_.oper1) || recurse(left(or_.oper2)))
&& recurse(recurse(or_.oper1) || recurse(right(or_.oper2)));
}
else if (any_and_inside( or_ ))
{
return recurse(recurse(or_.oper1) || recurse(or_.oper2));
}
else
{
return pass_through(or_);
}
}

ast::expr operator()(const ast::expr& expression) const
{
return recurse(expression);
}

};

ast::expr to_CNF(const ast::expr& expression)
{
return distribute_ors()(distribute_nots()(eliminate_iff()(eliminate_imp()(expression))));
}// Test some examples in main and check the order of precedence

int main()
{
for (auto& input : std::list<std::string>{

// Test the order of precedence
"(a and b) imp ((c and d) or (a and b));",
"a and b iff (c and d or a and b);",
"a and b imp (c and d or a and b);",
"not a or not b;",
"a or b;",
"not a and b;",
"not (a and b);",
"a or b or c;",
"aaa imp bbb iff ccc;",
"aaa iff bbb imp ccc;",// Test elimination of equivalences
"a iff b;",
"a iff b or c;",
"a or b iff b;",
"a iff b iff c;",

// Test elimination of implications
"p imp q;",
"p imp not q;",
"not p imp not q;",
"p imp q and r;",
"p imp q imp r;"})
{
auto f(std::begin(input)), l(std::end(input));
parser<decltype(f)> p;

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

if (!ok)
std::cerr << "invalid input\n";
else
{
std::cout << "original: " << result << "\n";
std::cout << "CNF: " << to_CNF(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;
}