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 // Yet another calculator example! This time, we will compile to a simple
10 // virtual machine. This is actually one of the very first Spirit example
11 // circa 2000. Now, it's ported to Spirit2.
12 //
13 // [ JDG Sometime 2000 ] pre-boost
14 // [ JDG September 18, 2002 ] spirit1
15 // [ JDG April 8, 2007 ] spirit2
16 // [ JDG February 18, 2011 ] Pure attributes. No semantic actions.
17 //
18 ///////////////////////////////////////////////////////////////////////////////
19
20 ///////////////////////////////////////////////////////////////////////////////
21 // Spirit v2.5 allows you to suppress automatic generation
22 // of predefined terminals to speed up complation. With
23 // BOOST_SPIRIT_NO_PREDEFINED_TERMINALS defined, you are
24 // responsible in creating instances of the terminals that
25 // you need (e.g. see qi::uint_type uint_ below).
26 #define BOOST_SPIRIT_NO_PREDEFINED_TERMINALS
27 ///////////////////////////////////////////////////////////////////////////////
28
29 ///////////////////////////////////////////////////////////////////////////////
30 // Define this to enable debugging
31 //#define BOOST_SPIRIT_QI_DEBUG
32
33 ///////////////////////////////////////////////////////////////////////////////
34 // Uncomment this if you want to enable debugging
35 //#define BOOST_SPIRIT_QI_DEBUG
36 ///////////////////////////////////////////////////////////////////////////////
37
38 #if defined(_MSC_VER)
39 # pragma warning(disable: 4345)
40 #endif
41
42 #include <boost/config/warning_disable.hpp>
43 #include <boost/spirit/include/qi.hpp>
44 #include <boost/variant/recursive_variant.hpp>
45 #include <boost/variant/apply_visitor.hpp>
46 #include <boost/fusion/include/adapt_struct.hpp>
47 #include <boost/spirit/include/phoenix_function.hpp>
48 #include <boost/foreach.hpp>
49
50 #include <iostream>
51 #include <string>
52
53 namespace client { namespace ast
54 {
55 ///////////////////////////////////////////////////////////////////////////
56 // The AST
57 ///////////////////////////////////////////////////////////////////////////
58 struct nil {};
59 struct signed_;
60 struct expression;
61
62 typedef boost::variant<
63 nil
64 , unsigned int
65 , boost::recursive_wrapper<signed_>
66 , boost::recursive_wrapper<expression>
67 >
68 operand;
69
70 struct signed_
71 {
72 char sign;
73 operand operand_;
74 };
75
76 struct operation
77 {
78 char operator_;
79 operand operand_;
80 };
81
82 struct expression
83 {
84 operand first;
85 std::list<operation> rest;
86 };
87
88 // print function for debugging
operator <<(std::ostream & out,nil)89 inline std::ostream& operator<<(std::ostream& out, nil) { out << "nil"; return out; }
90 }}
91
92 BOOST_FUSION_ADAPT_STRUCT(
93 client::ast::signed_,
94 (char, sign)
95 (client::ast::operand, operand_)
96 )
97
98 BOOST_FUSION_ADAPT_STRUCT(
99 client::ast::operation,
100 (char, operator_)
101 (client::ast::operand, operand_)
102 )
103
104 BOOST_FUSION_ADAPT_STRUCT(
105 client::ast::expression,
106 (client::ast::operand, first)
107 (std::list<client::ast::operation>, rest)
108 )
109
110 namespace client
111 {
112 ///////////////////////////////////////////////////////////////////////////
113 // The Virtual Machine
114 ///////////////////////////////////////////////////////////////////////////
115 enum byte_code
116 {
117 op_neg, // negate the top stack entry
118 op_add, // add top two stack entries
119 op_sub, // subtract top two stack entries
120 op_mul, // multiply top two stack entries
121 op_div, // divide top two stack entries
122 op_int, // push constant integer into the stack
123 };
124
125 class vmachine
126 {
127 public:
128
vmachine(unsigned stackSize=4096)129 vmachine(unsigned stackSize = 4096)
130 : stack(stackSize)
131 , stack_ptr(stack.begin())
132 {
133 }
134
top() const135 int top() const { return stack_ptr[-1]; };
136 void execute(std::vector<int> const& code);
137
138 private:
139
140 std::vector<int> stack;
141 std::vector<int>::iterator stack_ptr;
142 };
143
execute(std::vector<int> const & code)144 void vmachine::execute(std::vector<int> const& code)
145 {
146 std::vector<int>::const_iterator pc = code.begin();
147 stack_ptr = stack.begin();
148
149 while (pc != code.end())
150 {
151 switch (*pc++)
152 {
153 case op_neg:
154 stack_ptr[-1] = -stack_ptr[-1];
155 break;
156
157 case op_add:
158 --stack_ptr;
159 stack_ptr[-1] += stack_ptr[0];
160 break;
161
162 case op_sub:
163 --stack_ptr;
164 stack_ptr[-1] -= stack_ptr[0];
165 break;
166
167 case op_mul:
168 --stack_ptr;
169 stack_ptr[-1] *= stack_ptr[0];
170 break;
171
172 case op_div:
173 --stack_ptr;
174 stack_ptr[-1] /= stack_ptr[0];
175 break;
176
177 case op_int:
178 *stack_ptr++ = *pc++;
179 break;
180 }
181 }
182 }
183
184 ///////////////////////////////////////////////////////////////////////////
185 // The Compiler
186 ///////////////////////////////////////////////////////////////////////////
187 struct compiler
188 {
189 typedef void result_type;
190
191 std::vector<int>& code;
compilerclient::compiler192 compiler(std::vector<int>& code)
193 : code(code) {}
194
operator ()client::compiler195 void operator()(ast::nil) const { BOOST_ASSERT(0); }
operator ()client::compiler196 void operator()(unsigned int n) const
197 {
198 code.push_back(op_int);
199 code.push_back(n);
200 }
201
operator ()client::compiler202 void operator()(ast::operation const& x) const
203 {
204 boost::apply_visitor(*this, x.operand_);
205 switch (x.operator_)
206 {
207 case '+': code.push_back(op_add); break;
208 case '-': code.push_back(op_sub); break;
209 case '*': code.push_back(op_mul); break;
210 case '/': code.push_back(op_div); break;
211 default: BOOST_ASSERT(0); break;
212 }
213 }
214
operator ()client::compiler215 void operator()(ast::signed_ const& x) const
216 {
217 boost::apply_visitor(*this, x.operand_);
218 switch (x.sign)
219 {
220 case '-': code.push_back(op_neg); break;
221 case '+': break;
222 default: BOOST_ASSERT(0); break;
223 }
224 }
225
operator ()client::compiler226 void operator()(ast::expression const& x) const
227 {
228 boost::apply_visitor(*this, x.first);
229 BOOST_FOREACH(ast::operation const& oper, x.rest)
230 {
231 (*this)(oper);
232 }
233 }
234 };
235
236 namespace qi = boost::spirit::qi;
237 namespace ascii = boost::spirit::ascii;
238 using boost::phoenix::function;
239
240 ///////////////////////////////////////////////////////////////////////////////
241 // The error handler
242 ///////////////////////////////////////////////////////////////////////////////
243 struct error_handler_
244 {
245 template <typename, typename, typename>
246 struct result { typedef void type; };
247
248 template <typename Iterator>
operator ()client::error_handler_249 void operator()(
250 qi::info const& what
251 , Iterator err_pos, Iterator last) const
252 {
253 std::cout
254 << "Error! Expecting "
255 << what // what failed?
256 << " here: \""
257 << std::string(err_pos, last) // iterators to error-pos, end
258 << "\""
259 << std::endl
260 ;
261 }
262 };
263
264 function<error_handler_> const error_handler = error_handler_();
265
266 ///////////////////////////////////////////////////////////////////////////////
267 // The calculator grammar
268 ///////////////////////////////////////////////////////////////////////////////
269 template <typename Iterator>
270 struct calculator : qi::grammar<Iterator, ast::expression(), ascii::space_type>
271 {
calculatorclient::calculator272 calculator() : calculator::base_type(expression)
273 {
274 qi::char_type char_;
275 qi::uint_type uint_;
276 qi::_2_type _2;
277 qi::_3_type _3;
278 qi::_4_type _4;
279
280 using qi::on_error;
281 using qi::fail;
282
283 expression =
284 term
285 >> *( (char_('+') > term)
286 | (char_('-') > term)
287 )
288 ;
289
290 term =
291 factor
292 >> *( (char_('*') > factor)
293 | (char_('/') > factor)
294 )
295 ;
296
297 factor =
298 uint_
299 | '(' > expression > ')'
300 | (char_('-') > factor)
301 | (char_('+') > factor)
302 ;
303
304 // Debugging and error handling and reporting support.
305 BOOST_SPIRIT_DEBUG_NODES(
306 (expression)(term)(factor));
307
308 // Error handling
309 on_error<fail>(expression, error_handler(_4, _3, _2));
310 }
311
312 qi::rule<Iterator, ast::expression(), ascii::space_type> expression;
313 qi::rule<Iterator, ast::expression(), ascii::space_type> term;
314 qi::rule<Iterator, ast::operand(), ascii::space_type> factor;
315 };
316 }
317
318 ///////////////////////////////////////////////////////////////////////////////
319 // Main program
320 ///////////////////////////////////////////////////////////////////////////////
321 int
main()322 main()
323 {
324 std::cout << "/////////////////////////////////////////////////////////\n\n";
325 std::cout << "Expression parser...\n\n";
326 std::cout << "/////////////////////////////////////////////////////////\n\n";
327 std::cout << "Type an expression...or [q or Q] to quit\n\n";
328
329 typedef std::string::const_iterator iterator_type;
330 typedef client::calculator<iterator_type> calculator;
331 typedef client::ast::expression ast_expression;
332 typedef client::compiler compiler;
333
334 std::string str;
335 while (std::getline(std::cin, str))
336 {
337 if (str.empty() || str[0] == 'q' || str[0] == 'Q')
338 break;
339
340 client::vmachine mach; // Our virtual machine
341 std::vector<int> code; // Our VM code
342 calculator calc; // Our grammar
343 ast_expression expression; // Our program (AST)
344 compiler compile(code); // Compiles the program
345
346 std::string::const_iterator iter = str.begin();
347 std::string::const_iterator end = str.end();
348 boost::spirit::ascii::space_type space;
349 bool r = phrase_parse(iter, end, calc, space, expression);
350
351 if (r && iter == end)
352 {
353 std::cout << "-------------------------\n";
354 std::cout << "Parsing succeeded\n";
355 compile(expression);
356 mach.execute(code);
357 std::cout << "\nResult: " << mach.top() << std::endl;
358 std::cout << "-------------------------\n";
359 }
360 else
361 {
362 std::string rest(iter, end);
363 std::cout << "-------------------------\n";
364 std::cout << "Parsing failed\n";
365 std::cout << "-------------------------\n";
366 }
367 }
368
369 std::cout << "Bye... :-) \n\n";
370 return 0;
371 }
372
373
374