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

source code of boost/libs/spirit/example/x3/calc/calc6.cpp