ceph/src/boost/libs/spirit/example/qi/compiler_tutorial/calc6.cpp

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