| /*============================================================================= |
| Copyright (c) 2001-2014 Joel de Guzman |
| |
| Distributed under the Boost Software License, Version 1.0. (See accompanying |
| file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| =============================================================================*/ |
| /////////////////////////////////////////////////////////////////////////////// |
| // |
| // Yet another calculator example! This time, we will compile to a simple |
| // virtual machine. This is actually one of the very first Spirit example |
| // circa 2000. Now, it's ported to Spirit2 (and X3). |
| // |
| // [ JDG Sometime 2000 ] pre-boost |
| // [ JDG September 18, 2002 ] spirit1 |
| // [ JDG April 8, 2007 ] spirit2 |
| // [ JDG February 18, 2011 ] Pure attributes. No semantic actions. |
| // [ JDG April 9, 2014 ] Spirit X3 (from qi calc6) |
| // |
| /////////////////////////////////////////////////////////////////////////////// |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // Uncomment this if you want to enable debugging |
| //#define BOOST_SPIRIT_X3_DEBUG |
| |
| #if defined(_MSC_VER) |
| # pragma warning(disable: 4345) |
| #endif |
| |
| #include <boost/config/warning_disable.hpp> |
| #include <boost/spirit/home/x3.hpp> |
| #include <boost/spirit/home/x3/support/ast/variant.hpp> |
| #include <boost/fusion/include/adapt_struct.hpp> |
| |
| #include <iostream> |
| #include <string> |
| #include <list> |
| #include <numeric> |
| |
| namespace x3 = boost::spirit::x3; |
| |
| namespace client { namespace ast |
| { |
| /////////////////////////////////////////////////////////////////////////// |
| // The AST |
| /////////////////////////////////////////////////////////////////////////// |
| struct nil {}; |
| struct signed_; |
| struct expression; |
| |
| struct operand : x3::variant< |
| nil |
| , unsigned int |
| , x3::forward_ast<signed_> |
| , x3::forward_ast<expression> |
| > |
| { |
| using base_type::base_type; |
| using base_type::operator=; |
| }; |
| |
| struct signed_ |
| { |
| char sign; |
| operand operand_; |
| }; |
| |
| struct operation |
| { |
| char operator_; |
| operand operand_; |
| }; |
| |
| struct expression |
| { |
| operand first; |
| std::list<operation> rest; |
| }; |
| |
| // print function for debugging |
| inline std::ostream& operator<<(std::ostream& out, nil) { out << "nil"; return out; } |
| }} |
| |
| BOOST_FUSION_ADAPT_STRUCT( |
| client::ast::signed_, |
| (char, sign) |
| (client::ast::operand, operand_) |
| ) |
| |
| BOOST_FUSION_ADAPT_STRUCT( |
| client::ast::operation, |
| (char, operator_) |
| (client::ast::operand, operand_) |
| ) |
| |
| BOOST_FUSION_ADAPT_STRUCT( |
| client::ast::expression, |
| (client::ast::operand, first) |
| (std::list<client::ast::operation>, rest) |
| ) |
| |
| namespace client |
| { |
| /////////////////////////////////////////////////////////////////////////// |
| // The Virtual Machine |
| /////////////////////////////////////////////////////////////////////////// |
| enum byte_code |
| { |
| op_neg, // negate the top stack entry |
| op_add, // add top two stack entries |
| op_sub, // subtract top two stack entries |
| op_mul, // multiply top two stack entries |
| op_div, // divide top two stack entries |
| op_int, // push constant integer into the stack |
| }; |
| |
| class vmachine |
| { |
| public: |
| |
| vmachine(unsigned stackSize = 4096) |
| : stack(stackSize) |
| , stack_ptr(stack.begin()) |
| { |
| } |
| |
| int top() const { return stack_ptr[-1]; }; |
| void execute(std::vector<int> const& code); |
| |
| private: |
| |
| std::vector<int> stack; |
| std::vector<int>::iterator stack_ptr; |
| }; |
| |
| void vmachine::execute(std::vector<int> const& code) |
| { |
| std::vector<int>::const_iterator pc = code.begin(); |
| stack_ptr = stack.begin(); |
| |
| while (pc != code.end()) |
| { |
| switch (*pc++) |
| { |
| case op_neg: |
| stack_ptr[-1] = -stack_ptr[-1]; |
| break; |
| |
| case op_add: |
| --stack_ptr; |
| stack_ptr[-1] += stack_ptr[0]; |
| break; |
| |
| case op_sub: |
| --stack_ptr; |
| stack_ptr[-1] -= stack_ptr[0]; |
| break; |
| |
| case op_mul: |
| --stack_ptr; |
| stack_ptr[-1] *= stack_ptr[0]; |
| break; |
| |
| case op_div: |
| --stack_ptr; |
| stack_ptr[-1] /= stack_ptr[0]; |
| break; |
| |
| case op_int: |
| *stack_ptr++ = *pc++; |
| break; |
| } |
| } |
| } |
| |
| /////////////////////////////////////////////////////////////////////////// |
| // The Compiler |
| /////////////////////////////////////////////////////////////////////////// |
| struct compiler |
| { |
| typedef void result_type; |
| |
| std::vector<int>& code; |
| compiler(std::vector<int>& code) |
| : code(code) {} |
| |
| void operator()(ast::nil) const { BOOST_ASSERT(0); } |
| void operator()(unsigned int n) const |
| { |
| code.push_back(op_int); |
| code.push_back(n); |
| } |
| |
| void operator()(ast::operation const& x) const |
| { |
| boost::apply_visitor(*this, x.operand_); |
| switch (x.operator_) |
| { |
| case '+': code.push_back(op_add); break; |
| case '-': code.push_back(op_sub); break; |
| case '*': code.push_back(op_mul); break; |
| case '/': code.push_back(op_div); break; |
| default: BOOST_ASSERT(0); break; |
| } |
| } |
| |
| void operator()(ast::signed_ const& x) const |
| { |
| boost::apply_visitor(*this, x.operand_); |
| switch (x.sign) |
| { |
| case '-': code.push_back(op_neg); break; |
| case '+': break; |
| default: BOOST_ASSERT(0); break; |
| } |
| } |
| |
| void operator()(ast::expression const& x) const |
| { |
| boost::apply_visitor(*this, x.first); |
| for (ast::operation const& oper : x.rest) |
| { |
| (*this)(oper); |
| } |
| } |
| }; |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // The calculator grammar |
| /////////////////////////////////////////////////////////////////////////////// |
| namespace calculator_grammar |
| { |
| using x3::uint_; |
| using x3::char_; |
| |
| struct expression_class; |
| struct term_class; |
| struct factor_class; |
| |
| x3::rule<expression_class, ast::expression> const expression("expression"); |
| x3::rule<term_class, ast::expression> const term("term"); |
| x3::rule<factor_class, ast::operand> const factor("factor"); |
| |
| auto const expression_def = |
| term |
| >> *( (char_('+') > term) |
| | (char_('-') > term) |
| ) |
| ; |
| |
| auto const term_def = |
| factor |
| >> *( (char_('*') > factor) |
| | (char_('/') > factor) |
| ) |
| ; |
| |
| auto const factor_def = |
| uint_ |
| | '(' > expression > ')' |
| | (char_('-') > factor) |
| | (char_('+') > factor) |
| ; |
| |
| BOOST_SPIRIT_DEFINE( |
| expression = expression_def |
| , term = term_def |
| , factor = factor_def |
| ); |
| |
| struct expression_class |
| { |
| // Our error handler |
| template <typename Iterator, typename Exception, typename Context> |
| x3::error_handler_result |
| on_error(Iterator&, Iterator const& last, Exception const& x, Context const& context) |
| { |
| std::cout |
| << "Error! Expecting: " |
| << x.which() |
| << " here: \"" |
| << std::string(x.where(), last) |
| << "\"" |
| << std::endl |
| ; |
| return x3::error_handler_result::fail; |
| } |
| }; |
| |
| auto calculator = expression; |
| } |
| |
| using calculator_grammar::calculator; |
| } |
| |
| /////////////////////////////////////////////////////////////////////////////// |
| // Main program |
| /////////////////////////////////////////////////////////////////////////////// |
| int |
| main() |
| { |
| std::cout << "/////////////////////////////////////////////////////////\n\n"; |
| std::cout << "Expression parser...\n\n"; |
| std::cout << "/////////////////////////////////////////////////////////\n\n"; |
| std::cout << "Type an expression...or [q or Q] to quit\n\n"; |
| |
| typedef std::string::const_iterator iterator_type; |
| typedef client::ast::expression ast_expression; |
| typedef client::compiler compiler; |
| |
| std::string str; |
| while (std::getline(std::cin, str)) |
| { |
| if (str.empty() || str[0] == 'q' || str[0] == 'Q') |
| break; |
| |
| client::vmachine mach; // Our virtual machine |
| std::vector<int> code; // Our VM code |
| auto& calc = client::calculator; // Our grammar |
| ast_expression expression; // Our program (AST) |
| compiler compile(code); // Compiles the program |
| |
| std::string::const_iterator iter = str.begin(); |
| std::string::const_iterator end = str.end(); |
| boost::spirit::x3::ascii::space_type space; |
| bool r = phrase_parse(iter, end, calc, space, expression); |
| |
| if (r && iter == end) |
| { |
| std::cout << "-------------------------\n"; |
| std::cout << "Parsing succeeded\n"; |
| compile(expression); |
| mach.execute(code); |
| std::cout << "\nResult: " << mach.top() << std::endl; |
| std::cout << "-------------------------\n"; |
| } |
| else |
| { |
| std::string rest(iter, end); |
| std::cout << "-------------------------\n"; |
| std::cout << "Parsing failed\n"; |
| std::cout << "-------------------------\n"; |
| } |
| } |
| |
| std::cout << "Bye... :-) \n\n"; |
| return 0; |
| } |