• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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