fork(3) download
copy 
  1. // TransformAST.cpp : Defines the entry point for the console application.
  2. //
  3.  
  4. #include <boost/spirit/include/qi.hpp>
  5. #include <boost/fusion/include/adapt_struct.hpp>
  6.  
  7. #include <boost/variant/recursive_wrapper.hpp>
  8.  
  9. namespace qi = boost::spirit::qi;
  10.  
  11.  
  12.  
  13. // Abstract data type
  14.  
  15. struct op_or {};
  16. struct op_and {};
  17. struct op_imp {};
  18. struct op_iff {};
  19. struct op_not {};
  20.  
  21. namespace ast
  22. {
  23. 	typedef std::string var;
  24. 	template <typename tag> struct binop;
  25. 	template <typename tag> struct unop;
  26.  
  27. 	enum class expr_type { var = 0, not_, and_, or_, imp, iff };
  28. 	typedef boost::variant<var,
  29. 		boost::recursive_wrapper<unop <op_not> >,
  30. 		boost::recursive_wrapper<binop<op_and> >,
  31. 		boost::recursive_wrapper<binop<op_or> >,
  32. 		boost::recursive_wrapper<binop<op_imp> >,
  33. 		boost::recursive_wrapper<binop<op_iff> >
  34. 	> expr;
  35.  
  36. 	expr_type get_expr_type(const expr& expression)
  37. 	{
  38. 		return static_cast<expr_type>(expression.which());
  39. 	}
  40.  
  41. 	template <typename tag> struct binop
  42. 	{
  43. 		expr oper1, oper2;
  44. 	};
  45.  
  46. 	template <typename tag> struct unop
  47. 	{
  48. 		expr oper1;
  49. 	};
  50.  
  51. 	struct printer : boost::static_visitor<void>
  52. 	{
  53. 		printer(std::ostream& os) : _os(os) {}
  54. 		std::ostream& _os;
  55. 		mutable bool first{ true };
  56.  
  57. 		//
  58. 		void operator()(const ast::var& v) const { _os << v; }
  59.  
  60.  
  61. 		void operator()(const ast::binop<op_and>& b) const 
  62. 		{ 
  63. 			print(" and ", b.oper1, b.oper2,static_cast<int>(expr_type::and_)); 
  64. 		}
  65. 		void operator()(const ast::binop<op_or>& b) const 
  66. 		{ 
  67. 			print(" or ", b.oper1, b.oper2, static_cast<int>(expr_type::or_));
  68. 		}
  69. 		void operator()(const ast::binop<op_imp>& b) const
  70. 		{
  71. 			print(" imp ", b.oper1, b.oper2, static_cast<int>(expr_type::imp));
  72. 		}
  73. 		void operator()(const ast::binop<op_iff>& b) const 
  74. 		{ 
  75. 			print(" iff ", b.oper1, b.oper2, static_cast<int>(expr_type::iff));
  76. 		}
  77.  
  78. 		void print_parens(const ast::expr& expression, int priority) const
  79. 		{
  80. 			int expr_priority = expression.which();
  81. 			if (priority < expr_priority)
  82. 			{
  83. 				_os << "( ";
  84. 			}
  85. 			boost::apply_visitor(*this, expression);
  86. 			if (priority < expr_priority)
  87. 			{
  88. 				_os << " )";
  89. 			}
  90. 		}
  91.  
  92. 		void print(const std::string& op, const ast::expr& l, const ast::expr& r,int priority) const
  93. 		{
  94. 			print_parens(l, priority);
  95. 			_os << op;
  96. 			print_parens(r, priority);
  97. 		}
  98.  
  99. 		void operator()(const ast::unop<op_not>& u) const
  100. 		{
  101. 			_os << "not ";
  102. 			print_parens(u.oper1, static_cast<int>(expr_type::not_));
  103. 		}
  104. 	};
  105.  
  106. 	std::ostream& operator<<(std::ostream& os, const expr& e)
  107. 	{
  108. 		boost::apply_visitor(printer(os), e); return os;
  109. 	}
  110.  
  111. 	expr operator!(const expr& e)
  112. 	{
  113. 		return unop<op_not>{e};
  114. 	}
  115.  
  116. 	expr operator||(const expr& l, const expr& r)
  117. 	{
  118. 		return binop<op_or>{l, r};
  119. 	}
  120.  
  121. 	expr operator&&(const expr& l, const expr& r)
  122. 	{
  123. 		return binop<op_and>{l, r};
  124. 	}
  125.  
  126. }
  127.  
  128. BOOST_FUSION_ADAPT_TPL_STRUCT(
  129. 	(Tag),
  130. 	(ast::binop) (Tag),
  131. 	(ast::expr, oper1)
  132. 	(ast::expr, oper2)
  133. )
  134.  
  135. BOOST_FUSION_ADAPT_TPL_STRUCT(
  136. 	(Tag),
  137. 	(ast::unop) (Tag),
  138. 	(ast::expr, oper1)
  139. )
  140.  
  141.  
  142. // Grammar rules
  143.  
  144. template <typename It, typename Skipper = qi::space_type>
  145. struct parser : qi::grammar<It, ast::expr(), Skipper>
  146. {
  147. 	parser() : parser::base_type(expr_)
  148. 	{
  149. 		using namespace qi;
  150. 		const as<ast::binop<op_iff> > as_iff = {};
  151. 		const as<ast::binop<op_imp> > as_imp = {};
  152. 		const as<ast::binop<op_or> > as_or = {};
  153. 		const as<ast::binop<op_and> > as_and = {};
  154. 		const as<ast::unop<op_not> > as_not = {};
  155.  
  156. 		expr_ = iff_.alias();
  157.  
  158. 		iff_ = as_iff[imp_ >> "iff" >> iff_] | imp_;
  159. 		imp_ = as_imp[or_ >> "imp" >> imp_] | or_;
  160. 		or_ = as_or[and_ >> "or" >> or_] | and_;
  161. 		and_ = as_and[not_ >> "and" >> and_] | not_;
  162. 		not_ = as_not["not" > simple] | simple;
  163.  
  164. 		simple = (('(' > expr_ > ')') | var_);
  165. 		var_ = qi::lexeme[+alpha];
  166.  
  167. 		BOOST_SPIRIT_DEBUG_NODE(expr_);
  168. 		BOOST_SPIRIT_DEBUG_NODE(iff_);
  169. 		BOOST_SPIRIT_DEBUG_NODE(imp_);
  170. 		BOOST_SPIRIT_DEBUG_NODE(or_);
  171. 		BOOST_SPIRIT_DEBUG_NODE(and_);
  172. 		BOOST_SPIRIT_DEBUG_NODE(not_);
  173. 		BOOST_SPIRIT_DEBUG_NODE(simple);
  174. 		BOOST_SPIRIT_DEBUG_NODE(var_);
  175. 	}
  176.  
  177. private:
  178. 	qi::rule<It, ast::var(), Skipper> var_;
  179. 	qi::rule<It, ast::expr(), Skipper> not_, and_, or_, imp_, iff_, simple, expr_;
  180. };
  181.  
  182. template <typename Transform>
  183. struct ast_helper : boost::static_visitor<ast::expr>
  184. {
  185.  
  186. 	template <typename Tag>
  187. 	ast::expr pass_through(const ast::binop<Tag>& op) const
  188. 	{
  189. 		return ast::binop<Tag>{recurse(op.oper1), recurse(op.oper2)};
  190. 	}
  191.  
  192. 	template <typename Tag>
  193. 	ast::expr pass_through(const ast::unop<Tag>& op) const
  194. 	{
  195. 		return ast::unop<Tag>{recurse(op.oper1)};
  196. 	}
  197.  
  198. 	ast::expr pass_through(const ast::var& variable) const
  199. 	{
  200. 		return variable;
  201. 	}
  202.  
  203. 	ast::expr recurse(const ast::expr& expression) const
  204. 	{
  205. 		return boost::apply_visitor(Transform{}, expression);
  206. 	}
  207.  
  208. 	struct left_getter:boost::static_visitor<ast::expr>
  209. 	{
  210. 		template< template<class> class Op,typename Tag>
  211. 		ast::expr operator()(const Op<Tag>& op) const
  212. 		{
  213. 			return op.oper1;
  214. 		}
  215.  
  216. 		ast::expr operator()(const ast::var&) const
  217. 		{
  218. 			return{};//throw something?
  219. 		}
  220. 	};
  221.  
  222.  
  223. 	ast::expr left(const ast::expr& expression) const
  224. 	{
  225. 		return boost::apply_visitor(left_getter{}, expression);
  226. 	}
  227.  
  228. 	ast::expr child0(const ast::expr& expression) const
  229. 	{
  230. 		return left(expression);
  231. 	}
  232.  
  233. 	struct right_getter :boost::static_visitor<ast::expr>
  234. 	{
  235. 		template<typename Tag>
  236. 		ast::expr operator()(const ast::binop<Tag>& op) const
  237. 		{
  238. 			return op.oper2;
  239. 		}
  240.  
  241. 		template<typename Expr>
  242. 		ast::expr operator()(const Expr&) const
  243. 		{
  244. 			return{};//throw something?
  245. 		}
  246. 	};
  247.  
  248. 	ast::expr right(const ast::expr& expression) const
  249. 	{
  250. 		return boost::apply_visitor(right_getter{}, expression);
  251. 	}
  252.  
  253. };
  254.  
  255. struct eliminate_imp : ast_helper<eliminate_imp>
  256. {
  257. 	template <typename Op>
  258. 	ast::expr operator()(const Op& op) const
  259. 	{
  260. 		return pass_through(op);
  261. 	}
  262.  
  263. 	ast::expr operator()(const ast::binop<op_imp>& imp) const
  264. 	{
  265. 		return !recurse(imp.oper1) || recurse(imp.oper2);
  266. 	}
  267.  
  268. 	ast::expr operator()(const ast::expr& expression) const
  269. 	{
  270. 		return recurse(expression);
  271. 	}
  272. };
  273.  
  274. struct eliminate_iff : ast_helper<eliminate_iff>
  275. {
  276. 	template <typename Op>
  277. 	ast::expr operator()(const Op& op) const
  278. 	{
  279. 		return pass_through(op);
  280. 	}
  281.  
  282. 	ast::expr operator()(const ast::binop<op_iff>& imp) const
  283. 	{
  284. 		return (recurse(imp.oper1) || !recurse(imp.oper2)) && (!recurse(imp.oper1) || recurse(imp.oper2));
  285. 	}
  286.  
  287. 	ast::expr operator()(const ast::expr& expression) const
  288. 	{
  289. 		return recurse(expression);
  290. 	}
  291. };
  292.  
  293. struct distribute_nots : ast_helper<distribute_nots>
  294. {
  295. 	template <typename Op>
  296. 	ast::expr operator()(const Op& op) const
  297. 	{
  298. 		return pass_through(op);
  299. 	}
  300.  
  301. 	ast::expr operator()(const ast::unop<op_not>& not_) const
  302. 	{
  303. 		switch (ast::get_expr_type(not_.oper1)) //There is probably a better solution
  304. 		{
  305. 		case ast::expr_type::and_:
  306. 			return recurse(!recurse(left(not_.oper1))) || recurse(!recurse(right(not_.oper1)));
  307.  
  308. 		case ast::expr_type::or_:
  309. 			return recurse(!recurse(left(not_.oper1))) && recurse(!recurse(right(not_.oper1)));
  310.  
  311. 		case ast::expr_type::not_:
  312. 			return recurse(child0(not_.oper1));
  313. 		default:
  314. 			return pass_through(not_);
  315. 		}
  316. 	}
  317.  
  318. 	ast::expr operator()(const ast::expr& expression) const
  319. 	{
  320. 		return recurse(expression);
  321. 	}
  322. };
  323.  
  324. struct any_and_inside : boost::static_visitor<bool>
  325. {
  326. 	any_and_inside(const ast::expr& expression) :expression(expression) {}
  327. 	const ast::expr& expression;
  328.  
  329. 	bool operator()(const ast::var&) const
  330. 	{
  331. 		return false;
  332. 	}
  333.  
  334. 	template <typename Tag>
  335. 	bool operator()(const ast::binop<Tag>& op) const
  336. 	{
  337. 		return boost::apply_visitor(*this, op.oper1) || boost::apply_visitor(*this, op.oper2);
  338. 	}
  339.  
  340. 	bool operator()(const ast::binop<op_and>&) const
  341. 	{
  342. 		return true;
  343. 	}
  344.  
  345. 	template<typename Tag>
  346. 	bool operator()(const ast::unop<Tag>& op) const
  347. 	{
  348. 		return boost::apply_visitor(*this, op.oper1);
  349. 	}
  350.  
  351.  
  352. 	explicit operator bool() const
  353. 	{
  354. 		return boost::apply_visitor(*this, expression);
  355. 	}
  356.  
  357. };
  358.  
  359. struct distribute_ors : ast_helper<distribute_ors>
  360. {
  361. 	template <typename Op>
  362. 	ast::expr operator()(const Op& op) const
  363. 	{
  364. 		return pass_through(op);
  365. 	}
  366.  
  367. 	ast::expr operator()(const ast::binop<op_or>& or_) const
  368. 	{
  369. 		if (ast::get_expr_type(or_.oper1) == ast::expr_type::and_)
  370. 		{
  371. 			return recurse(recurse(left(or_.oper1)) || recurse(or_.oper2)) 
  372. 				&& recurse(recurse(right(or_.oper1)) || recurse(or_.oper2));
  373. 		}
  374. 		else if (ast::get_expr_type(or_.oper2) == ast::expr_type::and_)
  375. 		{
  376. 			return recurse(recurse(or_.oper1) || recurse(left(or_.oper2)))
  377. 				&& recurse(recurse(or_.oper1) || recurse(right(or_.oper2)));
  378. 		}
  379. 		else if (any_and_inside( or_ ))
  380. 		{
  381. 			return recurse(pass_through(or_));
  382. 		}
  383. 		else
  384. 		{
  385. 			return pass_through(or_);
  386. 		}
  387. 	}
  388.  
  389. 	ast::expr operator()(const ast::expr& expression) const
  390. 	{
  391. 		return recurse(expression);
  392. 	}
  393.  
  394. };
  395.  
  396. ast::expr to_CNF(const ast::expr& expression)
  397. {
  398. 	return distribute_ors()(distribute_nots()(eliminate_iff()(eliminate_imp()(expression))));
  399. }
  400.  
  401.  
  402.  
  403.  
  404. // Test some examples in main and check the order of precedence
  405.  
  406. int main()
  407. {
  408. 	for (auto& input : std::list<std::string>{
  409.  
  410. 		// Test the order of precedence
  411. 		"(a and b) imp ((c and d) or (a and b));",
  412. 		"a and b iff (c and d or a and b);",
  413. 		"a and b imp (c and d or a and b);",
  414. 		"not a or not b;",
  415. 		"a or b;",
  416. 		"not a and b;",
  417. 		"not (a and b);",
  418. 		"a or b or c;",
  419. 		"aaa imp bbb iff ccc;",
  420. 		"aaa iff bbb imp ccc;",
  421.  
  422.  
  423. 		// Test elimination of equivalences
  424. 		"a iff b;",
  425. 		"a iff b or c;",
  426. 		"a or b iff b;",
  427. 		"a iff b iff c;",
  428.  
  429. 		// Test elimination of implications
  430. 		"p imp q;",
  431. 		"p imp not q;",
  432. 		"not p imp not q;",
  433. 		"p imp q and r;",
  434. 		"p imp q imp r;"
  435. 	})
  436. 	{
  437. 		auto f(std::begin(input)), l(std::end(input));
  438. 		parser<decltype(f)> p;
  439.  
  440. 		try
  441. 		{
  442. 			ast::expr result;
  443. 			bool ok = qi::phrase_parse(f, l, p > ';', qi::space, result);
  444.  
  445. 			if (!ok)
  446. 				std::cerr << "invalid input\n";
  447. 			else
  448. 			{
  449. 				std::cout << "original: " << input << "\n";
  450. 				std::cout << "parsed: " << result << "\n";
  451. 				std::cout << "CNF: " << to_CNF(result) << "\n";
  452. 			}
  453.  
  454. 		}
  455. 		catch (const qi::expectation_failure<decltype(f)>& e)
  456. 		{
  457. 			std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
  458. 		}
  459.  
  460. 		if (f != l) std::cerr << "unparsed: '" << std::string(f, l) << "'\n";
  461. 	}
  462.  
  463. 	return 0;
  464. }
  465.  
  466.  
  467.  
Success #stdin #stdout 0.01s 3560KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
original: (a and b) imp ((c and d) or (a and b));
parsed: a and b imp c and d or a and b
CNF: ( not a or not b or c or a ) and ( not a or not b or c or b ) and ( not a or not b or d or a ) and ( not a or not b or d or b )
original: a and b iff (c and d or a and b);
parsed: a and b iff c and d or a and b
CNF: ( a or not c or not d ) and ( a or not a or not b ) and ( b or not c or not d ) and ( b or not a or not b ) and ( not a or not b or c or a ) and ( not a or not b or c or b ) and ( not a or not b or d or a ) and ( not a or not b or d or b )
original: a and b imp (c and d or a and b);
parsed: a and b imp c and d or a and b
CNF: ( not a or not b or c or a ) and ( not a or not b or c or b ) and ( not a or not b or d or a ) and ( not a or not b or d or b )
original: not a or not b;
parsed: not a or not b
CNF: not a or not b
original: a or b;
parsed: a or b
CNF: a or b
original: not a and b;
parsed: not a and b
CNF: not a and b
original: not (a and b);
parsed: not ( a and b )
CNF: not a or not b
original: a or b or c;
parsed: a or b or c
CNF: a or b or c
original: aaa imp bbb iff ccc;
parsed: aaa imp bbb iff ccc
CNF: ( not aaa or bbb or not ccc ) and ( aaa or ccc ) and ( not bbb or ccc )
original: aaa iff bbb imp ccc;
parsed: aaa iff bbb imp ccc
CNF: ( aaa or bbb ) and ( aaa or not ccc ) and ( not aaa or not bbb or ccc )
original: a iff b;
parsed: a iff b
CNF: ( a or not b ) and ( not a or b )
original: a iff b or c;
parsed: a iff b or c
CNF: ( a or not b ) and ( a or not c ) and ( not a or b or c )
original: a or b iff b;
parsed: a or b iff b
CNF: ( a or b or not b ) and ( not a or b ) and ( not b or b )
original: a iff b iff c;
parsed: a iff b iff c
CNF: ( a or not b or b ) and ( a or not b or not c ) and ( a or c or b ) and ( a or c or not c ) and ( not a or b or not c ) and ( not a or not b or c )
original: p imp q;
parsed: p imp q
CNF: not p or q
original: p imp not q;
parsed: p imp not q
CNF: not p or not q
original: not p imp not q;
parsed: not p imp not q
CNF: p or not q
original: p imp q and r;
parsed: p imp q and r
CNF: ( not p or q ) and ( not p or r )
original: p imp q imp r;
parsed: p imp q imp r
CNF: not p or not q or r
https://ideone.com/mY7QSf
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!