1 /*=============================================================================
2 Copyright (c) 2001-2011 Joel de Guzman
3
4 Distributed under the Boost Software License, Version 1.0. (See accompanying
5 file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 =============================================================================*/
7 ///////////////////////////////////////////////////////////////////////////////
8 //
9 // Same as Calc4, this time, we'll incorporate debugging support,
10 // plus error handling and reporting.
11 //
12 // [ JDG April 28, 2008 ] For BoostCon 2008
13 // [ JDG February 18, 2011 ] Pure attributes. No semantic actions.
14 //
15 ///////////////////////////////////////////////////////////////////////////////
16
17 ///////////////////////////////////////////////////////////////////////////////
18 // Spirit v2.5 allows you to suppress automatic generation
19 // of predefined terminals to speed up complation. With
20 // BOOST_SPIRIT_NO_PREDEFINED_TERMINALS defined, you are
21 // responsible in creating instances of the terminals that
22 // you need (e.g. see qi::uint_type uint_ below).
23 #define BOOST_SPIRIT_NO_PREDEFINED_TERMINALS
24 ///////////////////////////////////////////////////////////////////////////////
25
26 ///////////////////////////////////////////////////////////////////////////////
27 // Define this to enable debugging
28 #define BOOST_SPIRIT_QI_DEBUG
29
30 ///////////////////////////////////////////////////////////////////////////////
31 // Uncomment this if you want to enable debugging
32 //#define BOOST_SPIRIT_QI_DEBUG
33 ///////////////////////////////////////////////////////////////////////////////
34
35 #if defined(_MSC_VER)
36 # pragma warning(disable: 4345)
37 #endif
38
39 #include <boost/config/warning_disable.hpp>
40 #include <boost/spirit/include/qi.hpp>
41 #include <boost/variant/recursive_variant.hpp>
42 #include <boost/variant/apply_visitor.hpp>
43 #include <boost/fusion/include/adapt_struct.hpp>
44 #include <boost/spirit/include/phoenix_function.hpp>
45 #include <boost/foreach.hpp>
46
47 #include <iostream>
48 #include <string>
49
50 namespace client { namespace ast
51 {
52 ///////////////////////////////////////////////////////////////////////////
53 // The AST
54 ///////////////////////////////////////////////////////////////////////////
55 struct nil {};
56 struct signed_;
57 struct program;
58
59 typedef boost::variant<
60 nil
61 , unsigned int
62 , boost::recursive_wrapper<signed_>
63 , boost::recursive_wrapper<program>
64 >
65 operand;
66
67 struct signed_
68 {
69 char sign;
70 operand operand_;
71 };
72
73 struct operation
74 {
75 char operator_;
76 operand operand_;
77 };
78
79 struct program
80 {
81 operand first;
82 std::list<operation> rest;
83 };
84
85 // print function for debugging
operator <<(std::ostream & out,nil)86 inline std::ostream& operator<<(std::ostream& out, nil) { out << "nil"; return out; }
87 }}
88
89 BOOST_FUSION_ADAPT_STRUCT(
90 client::ast::signed_,
91 (char, sign)
92 (client::ast::operand, operand_)
93 )
94
95 BOOST_FUSION_ADAPT_STRUCT(
96 client::ast::operation,
97 (char, operator_)
98 (client::ast::operand, operand_)
99 )
100
101 BOOST_FUSION_ADAPT_STRUCT(
102 client::ast::program,
103 (client::ast::operand, first)
104 (std::list<client::ast::operation>, rest)
105 )
106
107 namespace client { namespace ast
108 {
109 ///////////////////////////////////////////////////////////////////////////
110 // The AST Printer
111 ///////////////////////////////////////////////////////////////////////////
112 struct printer
113 {
114 typedef void result_type;
115
operator ()client::ast::printer116 void operator()(nil) const {}
operator ()client::ast::printer117 void operator()(unsigned int n) const { std::cout << n; }
118
operator ()client::ast::printer119 void operator()(operation const& x) const
120 {
121 boost::apply_visitor(*this, x.operand_);
122 switch (x.operator_)
123 {
124 case '+': std::cout << " add"; break;
125 case '-': std::cout << " subt"; break;
126 case '*': std::cout << " mult"; break;
127 case '/': std::cout << " div"; break;
128 }
129 }
130
operator ()client::ast::printer131 void operator()(signed_ const& x) const
132 {
133 boost::apply_visitor(*this, x.operand_);
134 switch (x.sign)
135 {
136 case '-': std::cout << " neg"; break;
137 case '+': std::cout << " pos"; break;
138 }
139 }
140
operator ()client::ast::printer141 void operator()(program const& x) const
142 {
143 boost::apply_visitor(*this, x.first);
144 BOOST_FOREACH(operation const& oper, x.rest)
145 {
146 std::cout << ' ';
147 (*this)(oper);
148 }
149 }
150 };
151
152 ///////////////////////////////////////////////////////////////////////////
153 // The AST evaluator
154 ///////////////////////////////////////////////////////////////////////////
155 struct eval
156 {
157 typedef int result_type;
158
operator ()client::ast::eval159 int operator()(nil) const { BOOST_ASSERT(0); return 0; }
operator ()client::ast::eval160 int operator()(unsigned int n) const { return n; }
161
operator ()client::ast::eval162 int operator()(operation const& x, int lhs) const
163 {
164 int rhs = boost::apply_visitor(*this, x.operand_);
165 switch (x.operator_)
166 {
167 case '+': return lhs + rhs;
168 case '-': return lhs - rhs;
169 case '*': return lhs * rhs;
170 case '/': return lhs / rhs;
171 }
172 BOOST_ASSERT(0);
173 return 0;
174 }
175
operator ()client::ast::eval176 int operator()(signed_ const& x) const
177 {
178 int rhs = boost::apply_visitor(*this, x.operand_);
179 switch (x.sign)
180 {
181 case '-': return -rhs;
182 case '+': return +rhs;
183 }
184 BOOST_ASSERT(0);
185 return 0;
186 }
187
operator ()client::ast::eval188 int operator()(program const& x) const
189 {
190 int state = boost::apply_visitor(*this, x.first);
191 BOOST_FOREACH(operation const& oper, x.rest)
192 {
193 state = (*this)(oper, state);
194 }
195 return state;
196 }
197 };
198 }}
199
200 namespace client
201 {
202 namespace qi = boost::spirit::qi;
203 namespace ascii = boost::spirit::ascii;
204 using boost::phoenix::function;
205
206 ///////////////////////////////////////////////////////////////////////////////
207 // Our error handler
208 ///////////////////////////////////////////////////////////////////////////////
209 struct error_handler_
210 {
211 template <typename, typename, typename>
212 struct result { typedef void type; };
213
214 template <typename Iterator>
operator ()client::error_handler_215 void operator()(
216 qi::info const& what
217 , Iterator err_pos, Iterator last) const
218 {
219 std::cout
220 << "Error! Expecting "
221 << what // what failed?
222 << " here: \""
223 << std::string(err_pos, last) // iterators to error-pos, end
224 << "\""
225 << std::endl
226 ;
227 }
228 };
229
230 function<error_handler_> const error_handler = error_handler_();
231
232 ///////////////////////////////////////////////////////////////////////////////
233 // Our calculator grammar
234 ///////////////////////////////////////////////////////////////////////////////
235 template <typename Iterator>
236 struct calculator : qi::grammar<Iterator, ast::program(), ascii::space_type>
237 {
calculatorclient::calculator238 calculator() : calculator::base_type(expression)
239 {
240 qi::char_type char_;
241 qi::uint_type uint_;
242 qi::_2_type _2;
243 qi::_3_type _3;
244 qi::_4_type _4;
245
246 using qi::on_error;
247 using qi::fail;
248
249 expression =
250 term
251 >> *( (char_('+') > term)
252 | (char_('-') > term)
253 )
254 ;
255
256 term =
257 factor
258 >> *( (char_('*') > factor)
259 | (char_('/') > factor)
260 )
261 ;
262
263 factor =
264 uint_
265 | '(' > expression > ')'
266 | (char_('-') > factor)
267 | (char_('+') > factor)
268 ;
269
270 // Debugging and error handling and reporting support.
271 BOOST_SPIRIT_DEBUG_NODE(expression);
272 BOOST_SPIRIT_DEBUG_NODE(term);
273 BOOST_SPIRIT_DEBUG_NODE(factor);
274
275 // Error handling
276 on_error<fail>(expression, error_handler(_4, _3, _2));
277 }
278
279 qi::rule<Iterator, ast::program(), ascii::space_type> expression;
280 qi::rule<Iterator, ast::program(), ascii::space_type> term;
281 qi::rule<Iterator, ast::operand(), ascii::space_type> factor;
282 };
283 }
284
285 ///////////////////////////////////////////////////////////////////////////////
286 // Main program
287 ///////////////////////////////////////////////////////////////////////////////
288 int
main()289 main()
290 {
291 std::cout << "/////////////////////////////////////////////////////////\n\n";
292 std::cout << "Expression parser...\n\n";
293 std::cout << "/////////////////////////////////////////////////////////\n\n";
294 std::cout << "Type an expression...or [q or Q] to quit\n\n";
295
296 typedef std::string::const_iterator iterator_type;
297 typedef client::calculator<iterator_type> calculator;
298 typedef client::ast::program ast_program;
299 typedef client::ast::printer ast_print;
300 typedef client::ast::eval ast_eval;
301
302 std::string str;
303 while (std::getline(std::cin, str))
304 {
305 if (str.empty() || str[0] == 'q' || str[0] == 'Q')
306 break;
307
308 calculator calc; // Our grammar
309 ast_program program; // Our program (AST)
310 ast_print print; // Prints the program
311 ast_eval eval; // Evaluates the program
312
313 std::string::const_iterator iter = str.begin();
314 std::string::const_iterator end = str.end();
315 boost::spirit::ascii::space_type space;
316 bool r = phrase_parse(iter, end, calc, space, program);
317
318 if (r && iter == end)
319 {
320 std::cout << "-------------------------\n";
321 std::cout << "Parsing succeeded\n";
322 print(program);
323 std::cout << "\nResult: " << eval(program) << std::endl;
324 std::cout << "-------------------------\n";
325 }
326 else
327 {
328 std::string rest(iter, end);
329 std::cout << "-------------------------\n";
330 std::cout << "Parsing failed\n";
331 std::cout << "-------------------------\n";
332 }
333 }
334
335 std::cout << "Bye... :-) \n\n";
336 return 0;
337 }
338
339
340