fork download 
  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, bool right = false) const
  79. 		{
  80. 			int expr_priority = expression.which();
  81. 			if (priority < expr_priority || right && priority == expr_priority)
  82. 			{
  83. 				_os << "( ";
  84. 			}
  85. 			boost::apply_visitor(*this, expression);
  86. 			if (priority < expr_priority || right && 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, true);
  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.  
  107. 	std::ostream& operator<<(std::ostream& os, const expr& e)
  108. 	{
  109. 		boost::apply_visitor(printer(os), e); return os;
  110. 	}
  111.  
  112. 	expr operator!(const expr& e)
  113. 	{
  114. 		return unop<op_not>{e};
  115. 	}
  116.  
  117. 	expr operator||(const expr& l, const expr& r)
  118. 	{
  119. 		return binop<op_or>{l, r};
  120. 	}
  121.  
  122. 	expr operator&&(const expr& l, const expr& r)
  123. 	{
  124. 		return binop<op_and>{l, r};
  125. 	}
  126.  
  127. }
  128.  
  129. BOOST_FUSION_ADAPT_TPL_STRUCT(
  130. 	(Tag),
  131. 	(ast::binop) (Tag),
  132. 	(ast::expr, oper1)
  133. 	(ast::expr, oper2)
  134. 	)
  135.  
  136. 	BOOST_FUSION_ADAPT_TPL_STRUCT(
  137. 		(Tag),
  138. 		(ast::unop) (Tag),
  139. 		(ast::expr, oper1)
  140. 		)
  141.  
  142.  
  143. 	// Grammar rules
  144.  
  145. 	template <typename It, typename Skipper = qi::space_type>
  146. struct parser : qi::grammar<It, ast::expr(), Skipper>
  147. {
  148. 	parser() : parser::base_type(expr_)
  149. 	{
  150. 		using namespace qi;
  151. 		const as<ast::binop<op_iff> > as_iff = {};
  152. 		const as<ast::binop<op_imp> > as_imp = {};
  153. 		const as<ast::binop<op_or> > as_or = {};
  154. 		const as<ast::binop<op_and> > as_and = {};
  155. 		const as<ast::unop<op_not> > as_not = {};
  156.  
  157. 		expr_ = iff_.alias();
  158.  
  159. 		iff_ = as_iff[imp_ >> "iff" >> iff_] | imp_;
  160. 		imp_ = as_imp[or_ >> "imp" >> imp_] | or_;
  161. 		or_ = as_or[and_ >> "or" >> or_] | and_;
  162. 		and_ = as_and[not_ >> "and" >> and_] | not_;
  163. 		not_ = as_not["not" > simple] | simple;
  164.  
  165. 		simple = (('(' > expr_ > ')') | var_);
  166. 		var_ = qi::lexeme[+alpha];
  167.  
  168. 		BOOST_SPIRIT_DEBUG_NODE(expr_);
  169. 		BOOST_SPIRIT_DEBUG_NODE(iff_);
  170. 		BOOST_SPIRIT_DEBUG_NODE(imp_);
  171. 		BOOST_SPIRIT_DEBUG_NODE(or_);
  172. 		BOOST_SPIRIT_DEBUG_NODE(and_);
  173. 		BOOST_SPIRIT_DEBUG_NODE(not_);
  174. 		BOOST_SPIRIT_DEBUG_NODE(simple);
  175. 		BOOST_SPIRIT_DEBUG_NODE(var_);
  176. 	}
  177.  
  178. private:
  179. 	qi::rule<It, ast::var(), Skipper> var_;
  180. 	qi::rule<It, ast::expr(), Skipper> not_, and_, or_, imp_, iff_, simple, expr_;
  181. };
  182.  
  183. template <typename Transform>
  184. struct ast_helper : boost::static_visitor<ast::expr>
  185. {
  186.  
  187. 	template <typename Tag>
  188. 	ast::expr pass_through(const ast::binop<Tag>& op) const
  189. 	{
  190. 		return ast::binop<Tag>{recurse(op.oper1), recurse(op.oper2)};
  191. 	}
  192.  
  193. 	template <typename Tag>
  194. 	ast::expr pass_through(const ast::unop<Tag>& op) const
  195. 	{
  196. 		return ast::unop<Tag>{recurse(op.oper1)};
  197. 	}
  198.  
  199. 	ast::expr pass_through(const ast::var& variable) const
  200. 	{
  201. 		return variable;
  202. 	}
  203.  
  204. 	ast::expr recurse(const ast::expr& expression) const
  205. 	{
  206. 		return boost::apply_visitor(Transform{}, expression);
  207. 	}
  208.  
  209. 	struct left_getter :boost::static_visitor<ast::expr>
  210. 	{
  211. 		template< template<class> class Op, typename Tag>
  212. 		ast::expr operator()(const Op<Tag>& op) const
  213. 		{
  214. 			return op.oper1;
  215. 		}
  216.  
  217. 		ast::expr operator()(const ast::var&) const
  218. 		{
  219. 			return{};//throw something?
  220. 		}
  221. 	};
  222.  
  223.  
  224. 	ast::expr left(const ast::expr& expression) const
  225. 	{
  226. 		return boost::apply_visitor(left_getter{}, expression);
  227. 	}
  228.  
  229. 	ast::expr child0(const ast::expr& expression) const
  230. 	{
  231. 		return left(expression);
  232. 	}
  233.  
  234. 	struct right_getter :boost::static_visitor<ast::expr>
  235. 	{
  236. 		template<typename Tag>
  237. 		ast::expr operator()(const ast::binop<Tag>& op) const
  238. 		{
  239. 			return op.oper2;
  240. 		}
  241.  
  242. 		template<typename Expr>
  243. 		ast::expr operator()(const Expr&) const
  244. 		{
  245. 			return{};//throw something?
  246. 		}
  247. 	};
  248.  
  249. 	ast::expr right(const ast::expr& expression) const
  250. 	{
  251. 		return boost::apply_visitor(right_getter{}, expression);
  252. 	}
  253.  
  254. };
  255.  
  256. struct eliminate_imp : ast_helper<eliminate_imp>
  257. {
  258. 	template <typename Op>
  259. 	ast::expr operator()(const Op& op) const
  260. 	{
  261. 		return pass_through(op);
  262. 	}
  263.  
  264. 	ast::expr operator()(const ast::binop<op_imp>& imp) const
  265. 	{
  266. 		return !recurse(imp.oper1) || recurse(imp.oper2);
  267. 	}
  268.  
  269. 	ast::expr operator()(const ast::expr& expression) const
  270. 	{
  271. 		return recurse(expression);
  272. 	}
  273. };
  274.  
  275. struct eliminate_iff : ast_helper<eliminate_iff>
  276. {
  277. 	template <typename Op>
  278. 	ast::expr operator()(const Op& op) const
  279. 	{
  280. 		return pass_through(op);
  281. 	}
  282.  
  283. 	ast::expr operator()(const ast::binop<op_iff>& imp) const
  284. 	{
  285. 		return (recurse(imp.oper1) || !recurse(imp.oper2)) && (!recurse(imp.oper1) || recurse(imp.oper2));
  286. 	}
  287.  
  288. 	ast::expr operator()(const ast::expr& expression) const
  289. 	{
  290. 		return recurse(expression);
  291. 	}
  292. };
  293.  
  294. struct distribute_nots : ast_helper<distribute_nots>
  295. {
  296. 	template <typename Op>
  297. 	ast::expr operator()(const Op& op) const
  298. 	{
  299. 		return pass_through(op);
  300. 	}
  301.  
  302. 	ast::expr operator()(const ast::unop<op_not>& not_) const
  303. 	{
  304. 		switch (ast::get_expr_type(not_.oper1)) //There is probably a better solution
  305. 		{
  306. 		case ast::expr_type::and_:
  307. 			return recurse(!recurse(left(not_.oper1))) || recurse(!recurse(right(not_.oper1)));
  308.  
  309. 		case ast::expr_type::or_:
  310. 			return recurse(!recurse(left(not_.oper1))) && recurse(!recurse(right(not_.oper1)));
  311.  
  312. 		case ast::expr_type::not_:
  313. 			return recurse(child0(not_.oper1));
  314. 		default:
  315. 			return pass_through(not_);
  316. 		}
  317. 	}
  318.  
  319. 	ast::expr operator()(const ast::expr& expression) const
  320. 	{
  321. 		return recurse(expression);
  322. 	}
  323. };
  324.  
  325. struct any_and_inside : boost::static_visitor<bool>
  326. {
  327. 	any_and_inside(const ast::expr& expression) :expression(expression) {}
  328. 	const ast::expr& expression;
  329.  
  330. 	bool operator()(const ast::var&) const
  331. 	{
  332. 		return false;
  333. 	}
  334.  
  335. 	template <typename Tag>
  336. 	bool operator()(const ast::binop<Tag>& op) const
  337. 	{
  338. 		return boost::apply_visitor(*this, op.oper1) || boost::apply_visitor(*this, op.oper2);
  339. 	}
  340.  
  341. 	bool operator()(const ast::binop<op_and>&) const
  342. 	{
  343. 		return true;
  344. 	}
  345.  
  346. 	template<typename Tag>
  347. 	bool operator()(const ast::unop<Tag>& op) const
  348. 	{
  349. 		return boost::apply_visitor(*this, op.oper1);
  350. 	}
  351.  
  352.  
  353. 	explicit operator bool() const
  354. 	{
  355. 		return boost::apply_visitor(*this, expression);
  356. 	}
  357.  
  358. };
  359.  
  360. struct distribute_ors : ast_helper<distribute_ors>
  361. {
  362. 	template <typename Op>
  363. 	ast::expr operator()(const Op& op) const
  364. 	{
  365. 		return pass_through(op);
  366. 	}
  367.  
  368. 	ast::expr operator()(const ast::binop<op_or>& or_) const
  369. 	{
  370. 		if (ast::get_expr_type(or_.oper1) == ast::expr_type::and_)
  371. 		{
  372. 			return recurse(recurse(left(or_.oper1)) || recurse(or_.oper2))
  373. 				&& recurse(recurse(right(or_.oper1)) || recurse(or_.oper2));
  374. 		}
  375. 		else if (ast::get_expr_type(or_.oper2) == ast::expr_type::and_)
  376. 		{
  377. 			return recurse(recurse(or_.oper1) || recurse(left(or_.oper2)))
  378. 				&& recurse(recurse(or_.oper1) || recurse(right(or_.oper2)));
  379. 		}
  380. 		else if (any_and_inside(or_))
  381. 		{
  382. 			return recurse(pass_through(or_));
  383. 		}
  384. 		else
  385. 		{
  386. 			return pass_through(or_);
  387. 		}
  388. 	}
  389.  
  390. 	ast::expr operator()(const ast::expr& expression) const
  391. 	{
  392. 		return recurse(expression);
  393. 	}
  394.  
  395. };
  396.  
  397.  
  398. ast::expr fix(const ast::expr& expression);
  399.  
  400.  
  401. template <typename Tag>
  402. struct tag_folder : boost::static_visitor<void>
  403. {
  404. 	boost::optional<ast::expr> folded_expression{};
  405.  
  406. 	template <typename Whatever>
  407. 	void operator()(const Whatever& whatever) 
  408. 	{
  409. 		fold(fix(whatever));
  410. 	}
  411.  
  412. 	void operator()(const ast::binop<Tag>& op) 
  413. 	{
  414. 		boost::apply_visitor(*this, op.oper1);
  415. 		boost::apply_visitor(*this, op.oper2);
  416. 	}
  417.  
  418. 	ast::expr operator()(const ast::expr& expression) 
  419. 	{
  420. 		boost::apply_visitor(*this, expression);
  421. 		return *folded_expression;
  422. 	}
  423.  
  424. 	void fold(const ast::expr& expression)
  425. 	{
  426. 		if (folded_expression)
  427. 		{
  428. 			folded_expression = ast::binop<Tag>{ *folded_expression,expression };
  429. 		}
  430. 		else
  431. 		{
  432. 			folded_expression = expression;
  433. 		}
  434. 	}
  435. };
  436.  
  437.  
  438. struct fix_associativity : boost::static_visitor<ast::expr>
  439. {
  440. 	template <typename Whatever>
  441. 	ast::expr operator()(const Whatever& whatever) const
  442. 	{
  443. 		return whatever;
  444. 	}
  445.  
  446.  
  447. 	template <typename Tag>
  448. 	ast::expr operator()(const ast::binop<Tag>& op) const
  449. 	{
  450. 		tag_folder<Tag> folder;
  451. 		return folder(static_cast<ast::expr>(op));
  452. 	}
  453. };
  454.  
  455. ast::expr fix(const ast::expr& expression)
  456. {
  457. 	return boost::apply_visitor(fix_associativity(), expression);
  458. }
  459.  
  460. ast::expr to_CNF(const ast::expr& expression)
  461. {
  462. 	return distribute_ors()(distribute_nots()(eliminate_iff()(eliminate_imp()(expression))));
  463. }
  464.  
  465.  
  466.  
  467.  
  468. // Test some examples in main and check the order of precedence
  469.  
  470. int main()
  471. {
  472. 	for (auto& input : std::list<std::string>{
  473.  
  474. 		// Test the order of precedence
  475. 		"(a and b) imp ((c and d) or (a and b));",
  476. 		"a and b iff (c and d or a and b);",
  477. 		"a and b imp (c and d or a and b);",
  478. 		"not a or not b;",
  479. 		"a or b;",
  480. 		"not a and b;",
  481. 		"not (a and b);",
  482. 		"a or b or c;",
  483. 		"aaa imp bbb iff ccc;",
  484. 		"aaa iff bbb imp ccc;",
  485.  
  486.  
  487. 		// Test elimination of equivalences
  488. 		"a iff b;",
  489. 		"a iff b or c;",
  490. 		"a or b iff b;",
  491. 		"a iff b iff c;",
  492.  
  493. 		// Test elimination of implications
  494. 		"p imp q;",
  495. 		"p imp not q;",
  496. 		"not p imp not q;",
  497. 		"p imp q and r;",
  498. 		"p imp q imp r;",
  499. 	})
  500. 	{
  501. 		auto f(std::begin(input)), l(std::end(input));
  502. 		parser<decltype(f)> p;
  503.  
  504. 		try
  505. 		{
  506. 			ast::expr result;
  507. 			bool ok = qi::phrase_parse(f, l, p > ';', qi::space, result);
  508.  
  509. 			if (!ok)
  510. 				std::cerr << "invalid input\n";
  511. 			else
  512. 			{
  513. 				std::cout << "original: " << input << "\n";
  514. 				std::cout << "parsed: " << result << "\n";
  515. 				std::cout << "fixed?: " << fix(result) << "\n";
  516. 				std::cout << "CNF: " << to_CNF(fix(result)) << "\n";
  517. 				std::cout << "CNF fixed?: " << fix(to_CNF(fix(result))) << "\n";
  518. 			}
  519.  
  520. 		}
  521. 		catch (const qi::expectation_failure<decltype(f)>& e)
  522. 		{
  523. 			std::cerr << "expectation_failure at '" << std::string(e.first, e.last) << "'\n";
  524. 		}
  525.  
  526. 		if (f != l) std::cerr << "unparsed: '" << std::string(f, l) << "'\n";
  527. 	}
  528.  
  529. 	return 0;
  530. }
  531.  
  532.  
  533.  
Success #stdin #stdout 0s 3584KB
comments (?)
stdin 
Standard input is empty
stdout 
original: (a and b) imp ((c and d) or (a and b));
parsed: a and b imp c and d or a and b
fixed?: 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 ) ) )
CNF fixed?: ( 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
fixed?: 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 ) ) ) )
CNF fixed?: ( 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
fixed?: 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 ) ) )
CNF fixed?: ( 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
fixed?: not a or not b
CNF: not a or not b
CNF fixed?: not a or not b
original: a or b;
parsed: a or b
fixed?: a or b
CNF: a or b
CNF fixed?: a or b
original: not a and b;
parsed: not a and b
fixed?: not a and b
CNF: not a and b
CNF fixed?: not a and b
original: not (a and b);
parsed: not ( a and b )
fixed?: not ( a and b )
CNF: not a or not b
CNF fixed?: not a or not b
original: a or b or c;
parsed: a or ( b or c )
fixed?: a or b or c
CNF: a or b or c
CNF fixed?: a or b or c
original: aaa imp bbb iff ccc;
parsed: aaa imp bbb iff ccc
fixed?: aaa imp bbb iff ccc
CNF: ( not aaa or bbb or not ccc ) and ( ( aaa or ccc ) and ( not bbb or ccc ) )
CNF fixed?: ( 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
fixed?: aaa iff bbb imp ccc
CNF: ( aaa or bbb ) and ( aaa or not ccc ) and ( not aaa or ( not bbb or ccc ) )
CNF fixed?: ( aaa or bbb ) and ( aaa or not ccc ) and ( not aaa or not bbb or ccc )
original: a iff b;
parsed: a iff b
fixed?: a iff b
CNF: ( a or not b ) and ( not a or b )
CNF fixed?: ( a or not b ) and ( not a or b )
original: a iff b or c;
parsed: a iff b or c
fixed?: a iff b or c
CNF: ( a or not b ) and ( a or not c ) and ( not a or ( b or c ) )
CNF fixed?: ( 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
fixed?: a or b iff b
CNF: ( a or b or not b ) and ( ( not a or b ) and ( not b or b ) )
CNF fixed?: ( 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 )
fixed?: a iff b iff c
CNF: ( a or not b or not c ) and ( not a or b or not c ) and ( ( not a or a or c ) and ( not a or not b or c ) and ( ( b or a or c ) and ( b or not b or c ) ) )
CNF fixed?: ( a or not b or not c ) and ( not a or b or not c ) and ( not a or a or c ) and ( not a or not b or c ) and ( b or a or c ) and ( b or not b or c )
original: p imp q;
parsed: p imp q
fixed?: p imp q
CNF: not p or q
CNF fixed?: not p or q
original: p imp not q;
parsed: p imp not q
fixed?: p imp not q
CNF: not p or not q
CNF fixed?: not p or not q
original: not p imp not q;
parsed: not p imp not q
fixed?: not p imp not q
CNF: p or not q
CNF fixed?: p or not q
original: p imp q and r;
parsed: p imp q and r
fixed?: p imp q and r
CNF: ( not p or q ) and ( not p or r )
CNF fixed?: ( not p or q ) and ( not p or r )
original: p imp q imp r;
parsed: p imp ( q imp r )
fixed?: p imp q imp r
CNF: ( p or r ) and ( not q or r )
CNF fixed?: ( p or r ) and ( not q or r )
https://ideone.com/nL0zte
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!