fork download
copy 
  1. /* Copyright (c) 2011, Ronald Landheer-Cieslak <rlc at vlinder dot ca>
  2.  * All rights reserved.
  3.  * 
  4.  * Redistribution and use in source and binary forms, with or without
  5.  * modification, are permitted provided that the following conditions are met:
  6.  *     * Redistributions of source code must retain the above copyright
  7.  *       notice, this list of conditions and the following disclaimer.
  8.  *     * Redistributions in binary form must reproduce the above copyright
  9.  *       notice, this list of conditions and the following disclaimer in the
  10.  *       documentation and/or other materials provided with the distribution.
  11.  *     * Neither the name of the Vlinder Software nor the name of Ronald 
  12.  *       Landheer-Cieslak names of its contributors may be used to endorse or 
  13.  *       promote products derived from this software without specific prior 
  14.  *       written permission.
  15.  * 
  16.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
  17.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18.  * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19.  * DISCLAIMED. IN NO EVENT SHALL RONALD LANDHEER-CIESLAK BE LIABLE FOR ANY
  20.  * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21.  * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23.  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24.  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25.  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE
  26.  */
  27. #include <boost/spirit/include/qi.hpp>
  28. #include <boost/spirit/include/phoenix_core.hpp>
  29. #include <boost/spirit/include/phoenix_operator.hpp>
  30. #include <boost/spirit/include/phoenix_stl.hpp>
  31. #include <boost/fusion/include/adapt_struct.hpp>
  32. #include <boost/fusion/include/io.hpp>
  33. #include <boost/lexical_cast.hpp>
  34. #include <boost/algorithm/string/erase.hpp>
  35.  
  36. namespace qi = boost::spirit::qi;
  37. namespace ascii = boost::spirit::ascii;
  38. using namespace std;
  39. using namespace boost;
  40.  
  41. enum Operator {
  42. 	plus__,
  43. 	minus__,
  44. 	multiply__,
  45. 	divide__,
  46. 	operator_count__
  47. };
  48.  
  49. enum ListItemType {
  50. 	int__,
  51. 	double__,
  52. 	string__,
  53. 	expression__,
  54. 	list_item_type_count__
  55. };
  56.  
  57. struct Expression;
  58. typedef variant< int, double, string, Expression > ListItem;
  59. typedef vector< ListItem > List;
  60. struct Expression
  61. {
  62. 	Operator operator_;
  63. 	List list_;
  64. };
  65. BOOST_FUSION_ADAPT_STRUCT(
  66.     Expression,
  67. 	(Operator, operator_)
  68. 	(List, list_)
  69. )
  70.  
  71. template < ListItemType target_list_item_type__ >
  72. struct get_cast_target_type;
  73. template <>
  74. struct get_cast_target_type< int__ >
  75. {
  76. 	typedef int type;
  77. };
  78. template <>
  79. struct get_cast_target_type< double__ >
  80. {
  81. 	typedef double type;
  82. };
  83. template <>
  84. struct get_cast_target_type< string__ >
  85. {
  86. 	typedef string type;
  87. };
  88.  
  89. template < ListItemType target_list_item_type__ >
  90. /*unspecified*/typename get_cast_target_type< target_list_item_type__ >::type cast(const ListItem & list_item);
  91. template < >
  92. int cast< int__ >(const ListItem & list_item)
  93. {
  94. 	assert(list_item.which() == int__);
  95. 	return get< int >(list_item);
  96. }
  97. template < >
  98. double cast< double__ >(const ListItem & list_item)
  99. {
  100. 	assert((list_item.which() == int__) || (list_item.which() == double__));
  101. 	if (list_item.which() == double__)
  102. 	{
  103. 		return get< double >(list_item);
  104. 	}
  105. 	else
  106. 	{
  107. 		return static_cast< double >(get< int >(list_item));
  108. 	}
  109. }
  110. template < >
  111. string cast< string__ >(const ListItem & list_item)
  112. {
  113. 	assert(list_item.which() != expression__);
  114. 	if (list_item.which() == string__)
  115. 	{
  116. 		return get< string >(list_item);
  117. 	}
  118. 	else if (list_item.which() == int__)
  119. 	{
  120. 		return lexical_cast< string >(get< int >(list_item));
  121. 	}
  122. 	else
  123. 	{
  124. 		assert(list_item.which() == double__);
  125. 		return lexical_cast< string >(get< double >(list_item));
  126. 	}
  127. }
  128.  
  129. template < Operator operator__, ListItemType return_type__ >
  130. struct Operator_;
  131.  
  132. template <>
  133. struct Operator_< plus__, int__ >
  134. {
  135. 	static ListItem apply(ListItem lhs, ListItem rhs)
  136. 	{
  137. 		assert(lhs.which() == int__);
  138. 		assert(rhs.which() == int__);
  139. 		get< int >(lhs) += get< int >(rhs);
  140. 		return lhs;
  141. 	}
  142. };
  143.  
  144. template <>
  145. struct Operator_< plus__, double__ >
  146. {
  147. 	static ListItem apply(ListItem lhs, ListItem rhs)
  148. 	{
  149. 		get< double >(lhs) += cast< double__ >(rhs);
  150. 		return lhs;
  151. 	}
  152. };
  153.  
  154. template <>
  155. struct Operator_< plus__, string__ >
  156. {
  157. 	static ListItem apply(ListItem lhs, ListItem rhs)
  158. 	{
  159. 		string r = cast< string__ >(rhs);
  160. 		string &l = get< string >(lhs);
  161. 		l.insert(l.end(), r.begin(), r.end());
  162. 		return lhs;
  163. 	}
  164. };
  165.  
  166. template <>
  167. struct Operator_< minus__, int__ >
  168. {
  169. 	static ListItem apply(ListItem lhs, ListItem rhs)
  170. 	{
  171. 		assert(lhs.which() == int__);
  172. 		assert(rhs.which() == int__);
  173. 		get< int >(lhs) -= get< int >(rhs);
  174. 		return lhs;
  175. 	}
  176. };
  177.  
  178. template <>
  179. struct Operator_< minus__, double__ >
  180. {
  181. 	static ListItem apply(ListItem lhs, ListItem rhs)
  182. 	{
  183. 		get< double >(lhs) -= get< double >(rhs);
  184. 		return lhs;
  185. 	}
  186. };
  187.  
  188. template <>
  189. struct Operator_< minus__, string__ >
  190. {
  191. 	static ListItem apply(ListItem lhs, ListItem rhs)
  192. 	{
  193. 		using boost::algorithm::erase_first;
  194.  
  195. 		string r = cast< string__ >(rhs);
  196. 		string &l = get< string >(lhs);
  197. 		erase_first(l, r);
  198. 		return lhs;
  199. 	}
  200. };
  201.  
  202. template <>
  203. struct Operator_< divide__, int__ >
  204. {
  205. 	static ListItem apply(ListItem lhs, ListItem rhs)
  206. 	{
  207. 		assert(lhs.which() == int__);
  208. 		assert(rhs.which() == int__);
  209. 		get< int >(lhs) /= get< int >(rhs);
  210. 		return lhs;
  211. 	}
  212. };
  213.  
  214. template <>
  215. struct Operator_< divide__, double__ >
  216. {
  217. 	static ListItem apply(ListItem lhs, ListItem rhs)
  218. 	{
  219. 		get< double >(lhs) /= cast< double__ >(rhs);
  220. 		return lhs;
  221. 	}
  222. };
  223.  
  224. template <>
  225. struct Operator_< multiply__, int__ >
  226. {
  227. 	static ListItem apply(ListItem lhs, ListItem rhs)
  228. 	{
  229. 		assert(lhs.which() == int__);
  230. 		assert(rhs.which() == int__);
  231. 		get< int >(lhs) *= get< int >(rhs);
  232. 		return lhs;
  233. 	}
  234. };
  235.  
  236. template <>
  237. struct Operator_< multiply__, double__ >
  238. {
  239. 	static ListItem apply(ListItem lhs, ListItem rhs)
  240. 	{
  241. 		get< double >(lhs) *= cast< double__ >(rhs);
  242. 		return lhs;
  243. 	}
  244. };
  245.  
  246. struct Accumulator
  247. {
  248. 	virtual ~Accumulator()
  249. 	{}
  250.  
  251. 	virtual Accumulator* create(ListItem &result) const = 0;
  252.  
  253. 	const Accumulator& operator()(const ListItem &list_item) const
  254. 	{
  255. 		call_(list_item);
  256. 		return *this;
  257. 	}
  258.  
  259. 	ListItem operator*() const
  260. 	{
  261. 		return *result_;
  262. 	}
  263.  
  264. protected :
  265. 	virtual void call_(const ListItem &list_item) const = 0;
  266.  
  267. 	Accumulator()
  268. 		: result_(0)
  269. 		, first_(true)
  270. 	{ /* no-op */ }
  271.  
  272.  
  273. 	Accumulator(ListItem &result)
  274. 		: result_(&result)
  275. 		, first_(true)
  276. 	{ /* no-op */ }
  277.  
  278. 	ListItem *result_;
  279. 	mutable bool first_;
  280. };
  281.  
  282. template < Operator operator_type__, ListItemType return_type__ >
  283. struct Accumulator_ : Accumulator
  284. {
  285. private :
  286. 	Accumulator_()
  287. 	{ /* no-op */ }
  288.  
  289. 	Accumulator_(ListItem &result)
  290. 		: Accumulator(result)
  291. 	{ /* no-op */ }
  292.  
  293. 	Accumulator_* create(ListItem &result) const
  294. 	{
  295. 		return new Accumulator_(result);
  296. 	}
  297.  
  298. protected :
  299. 	/*virtual */void call_(const ListItem &list_item) const/* = 0*/
  300. 	{
  301. 		if (first_)
  302. 		{
  303. 			switch (result_->which())
  304. 			{
  305. 			case int__ :
  306. 				*result_ = cast< int__ >(list_item);
  307. 				break;
  308. 			case double__ :
  309. 				*result_ = cast< double__ >(list_item);
  310. 				break;
  311. 			case string__ :
  312. 				*result_ = cast< string__ >(list_item);
  313. 				break;
  314. 			}
  315. 			first_ = false;
  316. 		}
  317. 		else
  318. 		{
  319. 			*result_ = Operator_< operator_type__, return_type__ >::apply(*result_, list_item);
  320. 		}
  321. 	}
  322.  
  323. 	friend boost::shared_ptr< Accumulator > getAccumulator(ListItem &result, Operator operator_type, ListItemType return_type);
  324. };
  325.  
  326. boost::shared_ptr< Accumulator > getAccumulator(ListItem &result, Operator operator_type, ListItemType return_type)
  327. {
  328. 	static Accumulator_< plus__, int__ >		pi_accumulator__;
  329. 	static Accumulator_< plus__, double__ >		pd_accumulator__;
  330. 	static Accumulator_< plus__, string__ >		ps_accumulator__;
  331. 	static Accumulator_< minus__, int__ >		mi_accumulator__;
  332. 	static Accumulator_< minus__, double__ >	md_accumulator__;
  333. 	static Accumulator_< minus__, string__ >	ms_accumulator__;
  334. 	static Accumulator_< multiply__, int__ >	ui_accumulator__;
  335. 	static Accumulator_< multiply__, double__ >	ud_accumulator__;
  336. 	static Accumulator_< divide__, int__ >		di_accumulator__;
  337. 	static Accumulator_< divide__, double__ >	dd_accumulator__;
  338. 	static Accumulator* accumulators__[operator_count__][list_item_type_count__] = {
  339. 		{ &pi_accumulator__, &pd_accumulator__, &ps_accumulator__, 0 },
  340. 		{ &mi_accumulator__, &md_accumulator__, &ms_accumulator__, 0 },
  341. 		{ &ui_accumulator__, &ud_accumulator__, 0, 0 },
  342. 		{ &di_accumulator__, &dd_accumulator__, 0, 0 }
  343. 	};
  344.  
  345. 	if (accumulators__[operator_type][return_type] != 0)
  346. 	{
  347. 		return boost::shared_ptr< Accumulator >(accumulators__[operator_type][return_type]->create(result));
  348. 	}
  349. 	else
  350. 	{
  351. 		if (operator_type == multiply__)
  352. 		{
  353. 			throw logic_error("Don't know how to multiply a string");
  354. 		}
  355. 		else
  356. 		{
  357. 			throw logic_error("Don't know how to divide a string");
  358. 		}
  359. 	}
  360. }
  361.  
  362. void ping()
  363. {
  364. 	cout << "ping" << endl;
  365. }
  366.  
  367. template < typename Iterator >
  368. struct Grammar : qi::grammar< Iterator, Expression(), ascii::space_type >
  369. {
  370. 	Grammar()
  371. 		: Grammar::base_type(expression_)
  372. 	{
  373. 		using qi::_val;
  374. 		using qi::_1;
  375. 		using phoenix::push_back;
  376. 		using qi::lexeme;
  377.  
  378. 		expression_ = '(' >> operator_ >> list_ >> ')'
  379. 					;
  380. 		operator_.add
  381. 					("+", plus__)
  382. 					("-", minus__)
  383. 					("*", multiply__)
  384. 					("/", divide__)
  385. 					;
  386. 		list_		= +list_item_
  387. 					;
  388. 		list_item_	= expression_
  389. 					| qi::int_
  390. 					| qi::double_
  391. 					| string_
  392. 					;
  393. 		string_		= lexeme['"' >> *(unescape_char_ | ("\\x" >> qi::hex) | (qi::char_ - qi::char_('"'))) >> '"']
  394. 					;
  395. 		unescape_char_.add
  396. 					("\\a", '\a')("\\b", '\b')("\\f", '\f')("\\n", '\n')
  397. 					("\\r", '\r')("\\t", '\t')("\\v", '\v')("\\\\", '\\')
  398. 					("\\\'", '\'')("\\\"", '\"');
  399.  
  400. 	}
  401.  
  402. 	qi::rule< Iterator, Expression(), ascii::space_type > expression_;
  403. 	qi::rule< Iterator, List(), ascii::space_type > list_;
  404. 	qi::rule< Iterator, ListItem(), ascii::space_type > list_item_;
  405. 	qi::rule< Iterator, string(), ascii::space_type > string_;
  406. 	qi::symbols< char const, char const > unescape_char_;
  407. 	qi::symbols< char const, Operator > operator_;
  408. };
  409.  
  410. ListItem evaluate(Expression &expression)
  411. {
  412. 	ListItemType result_type(int__);
  413. 	ListItem retval;
  414. 	// first pass: evaluate any sub-expressions
  415. 	for (List::iterator iter(expression.list_.begin()); iter != expression.list_.end(); ++iter)
  416. 	{
  417. 		if (iter->which() == expression__)
  418. 		{
  419. 			*iter = evaluate(get< Expression >(*iter));
  420. 		}
  421. 		switch (iter->which())
  422. 		{
  423. 		case int__ :
  424. 			// this is the default type - it doesn't change anything
  425. 			break;
  426. 		case double__ :
  427. 			if (result_type == int__)
  428. 			{
  429. 				result_type = double__;
  430. 			}
  431. 			else
  432. 			{ /* either already a double, or it's a string */ }
  433. 			break;
  434. 		case string__ :
  435. 			result_type = string__;
  436. 			break;
  437. 		default :
  438. 			throw logic_error("unexpected operand type");
  439. 		}
  440. 	}
  441. 	switch (result_type)
  442. 	{
  443. 	case int__ :
  444. 		// nothing to do in this case: this is the default for the variant, and it will be zero-initialized
  445. 		break;
  446. 	case double__ :
  447. 		retval = 0.0;
  448. 		break;
  449. 	case string__ :
  450. 		retval = string();
  451. 		break;
  452. 	default :
  453. 		throw logic_error("Unexpected result type");
  454. 	}
  455. 	boost::shared_ptr< Accumulator > accumulator = getAccumulator(retval, expression.operator_, result_type);
  456. 	for (List::const_iterator iter(expression.list_.begin()); iter != expression.list_.end(); ++iter)
  457. 	{
  458. 			(*accumulator)(*iter);
  459. 	}
  460.  
  461. 	return retval;
  462. }	
  463.  
  464. int main()
  465. {
  466. 	using boost::spirit::ascii::space;
  467.  
  468. 	Expression expression;
  469. 	Grammar< string::const_iterator > grammar;
  470. 	string test("(+ 1 (+ 1 1.2))");
  471. 	string::const_iterator iter = test.begin();
  472. 	string::const_iterator end = test.end();
  473. 	if (qi::phrase_parse(iter, end, grammar, space, expression))
  474. 	{
  475. 		assert(expression.operator_ == plus__);
  476. 		ListItem result(evaluate(expression));
  477. 		assert(result.which() == double__);
  478. 		assert(get< double >(result) == 3.2);
  479. 	}
  480. 	else
  481. 	{
  482. 		assert(!"parse failed");
  483. 	}
  484. 	test = "(* 1 2)";
  485. 	iter = test.begin();
  486. 	end = test.end();
  487. 	expression.list_.clear();
  488. 	if (qi::phrase_parse(iter, end, grammar, space, expression))
  489. 	{
  490. 		assert(expression.operator_ == multiply__);
  491. 		ListItem result(evaluate(expression));
  492. 		assert(result.which() == int__);
  493. 		assert(get< int >(result) == 2);
  494. 	}
  495. 	else
  496. 	{
  497. 		assert(!"parse failed");
  498. 	}
  499. 	test = "(+ \"Hello, \" \"world!\")";
  500. 	iter = test.begin();
  501. 	end = test.end();
  502. 	expression.list_.clear();
  503. 	if (qi::phrase_parse(iter, end, grammar, space, expression))
  504. 	{
  505. 		assert(expression.operator_ == plus__);
  506. 		ListItem result(evaluate(expression));
  507. 		assert(result.which() == string__);
  508. 		assert(get< string >(result) == "Hello, world!");
  509. 	}
  510. 	else
  511. 	{
  512. 		assert(!"parse failed");
  513. 	}
  514. 	test = "(+ \"Goodbye\" (- \"Hello, world!\" \"Hello\"))";
  515. 	iter = test.begin();
  516. 	end = test.end();
  517. 	expression.list_.clear();
  518. 	if (qi::phrase_parse(iter, end, grammar, space, expression))
  519. 	{
  520. 		assert(expression.operator_ == plus__);
  521. 		ListItem result(evaluate(expression));
  522. 		assert(result.which() == string__);
  523. 		assert(get< string >(result) == "Goodbye, world!");
  524. 	}
  525. 	else
  526. 	{
  527. 		assert(!"parse failed");
  528. 	}
  529. }
  530.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/iJYEV
language:
C++14 (gcc 8.3)
created:
12 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!