1 /*=============================================================================
2 Copyright (c) 2001-2014 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 (and X3).
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 // [ JDG April 9, 2014 ] Spirit X3 (from qi calc6)
18 //
19 ///////////////////////////////////////////////////////////////////////////////
20
21 ///////////////////////////////////////////////////////////////////////////////
22 // Uncomment this if you want to enable debugging
23 //#define BOOST_SPIRIT_X3_DEBUG
24
25 #if defined(_MSC_VER)
26 # pragma warning(disable: 4345)
27 #endif
28
29 #include <boost/config/warning_disable.hpp>
30 #include <boost/spirit/home/x3.hpp>
31 #include <boost/spirit/home/x3/support/ast/variant.hpp>
32 #include <boost/fusion/include/adapt_struct.hpp>
33
34 #include <iostream>
35 #include <string>
36 #include <list>
37 #include <numeric>
38
39 namespace x3 = boost::spirit::x3;
40
41 namespace client { namespace ast
42 {
43 ///////////////////////////////////////////////////////////////////////////
44 // The AST
45 ///////////////////////////////////////////////////////////////////////////
46 struct nil {};
47 struct signed_;
48 struct expression;
49
50 struct operand : x3::variant<
51 nil
52 , unsigned int
53 , x3::forward_ast<signed_>
54 , x3::forward_ast<expression>
55 >
56 {
57 using base_type::base_type;
58 using base_type::operator=;
59 };
60
61 struct signed_
62 {
63 char sign;
64 operand operand_;
65 };
66
67 struct operation
68 {
69 char operator_;
70 operand operand_;
71 };
72
73 struct expression
74 {
75 operand first;
76 std::list<operation> rest;
77 };
78
79 // print function for debugging
operator <<(std::ostream & out,nil)80 inline std::ostream& operator<<(std::ostream& out, nil) { out << "nil"; return out; }
81 }}
82
83 BOOST_FUSION_ADAPT_STRUCT(client::ast::signed_,
84 sign, operand_
85 )
86
87 BOOST_FUSION_ADAPT_STRUCT(client::ast::operation,
88 operator_, operand_
89 )
90
91 BOOST_FUSION_ADAPT_STRUCT(client::ast::expression,
92 first, rest
93 )
94
95 namespace client
96 {
97 ///////////////////////////////////////////////////////////////////////////
98 // The Virtual Machine
99 ///////////////////////////////////////////////////////////////////////////
100 enum byte_code
101 {
102 op_neg, // negate the top stack entry
103 op_add, // add top two stack entries
104 op_sub, // subtract top two stack entries
105 op_mul, // multiply top two stack entries
106 op_div, // divide top two stack entries
107 op_int, // push constant integer into the stack
108 };
109
110 class vmachine
111 {
112 public:
113
vmachine(unsigned stackSize=4096)114 vmachine(unsigned stackSize = 4096)
115 : stack(stackSize)
116 , stack_ptr(stack.begin())
117 {
118 }
119
top() const120 int top() const { return stack_ptr[-1]; };
121 void execute(std::vector<int> const& code);
122
123 private:
124
125 std::vector<int> stack;
126 std::vector<int>::iterator stack_ptr;
127 };
128
execute(std::vector<int> const & code)129 void vmachine::execute(std::vector<int> const& code)
130 {
131 std::vector<int>::const_iterator pc = code.begin();
132 stack_ptr = stack.begin();
133
134 while (pc != code.end())
135 {
136 switch (*pc++)
137 {
138 case op_neg:
139 stack_ptr[-1] = -stack_ptr[-1];
140 break;
141
142 case op_add:
143 --stack_ptr;
144 stack_ptr[-1] += stack_ptr[0];
145 break;
146
147 case op_sub:
148 --stack_ptr;
149 stack_ptr[-1] -= stack_ptr[0];
150 break;
151
152 case op_mul:
153 --stack_ptr;
154 stack_ptr[-1] *= stack_ptr[0];
155 break;
156
157 case op_div:
158 --stack_ptr;
159 stack_ptr[-1] /= stack_ptr[0];
160 break;
161
162 case op_int:
163 *stack_ptr++ = *pc++;
164 break;
165 }
166 }
167 }
168
169 ///////////////////////////////////////////////////////////////////////////
170 // The Compiler
171 ///////////////////////////////////////////////////////////////////////////
172 struct compiler
173 {
174 typedef void result_type;
175
176 std::vector<int>& code;
compilerclient::compiler177 compiler(std::vector<int>& code)
178 : code(code) {}
179
operator ()client::compiler180 void operator()(ast::nil) const { BOOST_ASSERT(0); }
operator ()client::compiler181 void operator()(unsigned int n) const
182 {
183 code.push_back(op_int);
184 code.push_back(n);
185 }
186
operator ()client::compiler187 void operator()(ast::operation const& x) const
188 {
189 boost::apply_visitor(*this, x.operand_);
190 switch (x.operator_)
191 {
192 case '+': code.push_back(op_add); break;
193 case '-': code.push_back(op_sub); break;
194 case '*': code.push_back(op_mul); break;
195 case '/': code.push_back(op_div); break;
196 default: BOOST_ASSERT(0); break;
197 }
198 }
199
operator ()client::compiler200 void operator()(ast::signed_ const& x) const
201 {
202 boost::apply_visitor(*this, x.operand_);
203 switch (x.sign)
204 {
205 case '-': code.push_back(op_neg); break;
206 case '+': break;
207 default: BOOST_ASSERT(0); break;
208 }
209 }
210
operator ()client::compiler211 void operator()(ast::expression const& x) const
212 {
213 boost::apply_visitor(*this, x.first);
214 for (ast::operation const& oper : x.rest)
215 {
216 (*this)(oper);
217 }
218 }
219 };
220
221 ///////////////////////////////////////////////////////////////////////////////
222 // The calculator grammar
223 ///////////////////////////////////////////////////////////////////////////////
224 namespace calculator_grammar
225 {
226 using x3::uint_;
227 using x3::char_;
228
229 struct expression_class;
230 struct term_class;
231 struct factor_class;
232
233 x3::rule<expression_class, ast::expression> const expression("expression");
234 x3::rule<term_class, ast::expression> const term("term");
235 x3::rule<factor_class, ast::operand> const factor("factor");
236
237 auto const expression_def =
238 term
239 >> *( (char_('+') > term)
240 | (char_('-') > term)
241 )
242 ;
243
244 auto const term_def =
245 factor
246 >> *( (char_('*') > factor)
247 | (char_('/') > factor)
248 )
249 ;
250
251 auto const factor_def =
252 uint_
253 | '(' > expression > ')'
254 | (char_('-') > factor)
255 | (char_('+') > factor)
256 ;
257
258 BOOST_SPIRIT_DEFINE(
259 expression
260 , term
261 , factor
262 );
263
264 struct expression_class
265 {
266 // Our error handler
267 template <typename Iterator, typename Exception, typename Context>
268 x3::error_handler_result
on_errorclient::calculator_grammar::expression_class269 on_error(Iterator&, Iterator const& last, Exception const& x, Context const& context)
270 {
271 std::cout
272 << "Error! Expecting: "
273 << x.which()
274 << " here: \""
275 << std::string(x.where(), last)
276 << "\""
277 << std::endl
278 ;
279 return x3::error_handler_result::fail;
280 }
281 };
282
283 auto calculator = expression;
284 }
285
286 using calculator_grammar::calculator;
287 }
288
289 ///////////////////////////////////////////////////////////////////////////////
290 // Main program
291 ///////////////////////////////////////////////////////////////////////////////
292 int
main()293 main()
294 {
295 std::cout << "/////////////////////////////////////////////////////////\n\n";
296 std::cout << "Expression parser...\n\n";
297 std::cout << "/////////////////////////////////////////////////////////\n\n";
298 std::cout << "Type an expression...or [q or Q] to quit\n\n";
299
300 typedef std::string::const_iterator iterator_type;
301 typedef client::ast::expression ast_expression;
302 typedef client::compiler compiler;
303
304 std::string str;
305 while (std::getline(std::cin, str))
306 {
307 if (str.empty() || str[0] == 'q' || str[0] == 'Q')
308 break;
309
310 client::vmachine mach; // Our virtual machine
311 std::vector<int> code; // Our VM code
312 auto& calc = client::calculator; // Our grammar
313 ast_expression expression; // Our program (AST)
314 compiler compile(code); // Compiles the program
315
316 iterator_type iter = str.begin();
317 iterator_type const end = str.end();
318 boost::spirit::x3::ascii::space_type space;
319 bool r = phrase_parse(iter, end, calc, space, expression);
320
321 if (r && iter == end)
322 {
323 std::cout << "-------------------------\n";
324 std::cout << "Parsing succeeded\n";
325 compile(expression);
326 mach.execute(code);
327 std::cout << "\nResult: " << mach.top() << std::endl;
328 std::cout << "-------------------------\n";
329 }
330 else
331 {
332 std::string rest(iter, end);
333 std::cout << "-------------------------\n";
334 std::cout << "Parsing failed\n";
335 std::cout << "-------------------------\n";
336 }
337 }
338
339 std::cout << "Bye... :-) \n\n";
340 return 0;
341 }
342