123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248 |
- /*=============================================================================
- Copyright (c) 2001-2010 Joel de Guzman
- Copyright (c) 2001-2010 Hartmut Kaiser
- 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)
- =============================================================================*/
- ///////////////////////////////////////////////////////////////////////////////
- //
- // A Calculator example demonstrating generation of AST from which we generate
- // a simple byte code representation being interpreted by a similar virtual
- // machine.
- //
- // [ JDG April 28, 2008 ]
- // [ HK May 05, 2008 ]
- //
- ///////////////////////////////////////////////////////////////////////////////
- #include <boost/config/warning_disable.hpp>
- #include <iostream>
- #include <vector>
- #include <string>
- #include "calc2_ast_vm.hpp"
- #include <boost/spirit/include/qi.hpp>
- #include <boost/spirit/include/karma.hpp>
- #include <boost/fusion/include/adapt_struct.hpp>
- using namespace boost::spirit;
- using namespace boost::spirit::ascii;
- ///////////////////////////////////////////////////////////////////////////////
- // Our calculator parser grammar
- ///////////////////////////////////////////////////////////////////////////////
- template <typename Iterator>
- struct calculator
- : qi::grammar<Iterator, expression_ast(), space_type>
- {
- calculator() : calculator::base_type(expression)
- {
- expression =
- term [_val = _1]
- >> *( ('+' >> term [_val += _1])
- | ('-' >> term [_val -= _1])
- )
- ;
- term =
- factor [_val = _1]
- >> *( ('*' >> factor [_val *= _1])
- | ('/' >> factor [_val /= _1])
- )
- ;
- factor =
- uint_ [_val = _1]
- | '(' >> expression [_val = _1] >> ')'
- | ('-' >> factor [_val = neg(_1)])
- | ('+' >> factor [_val = pos(_1)])
- ;
- }
- qi::rule<Iterator, expression_ast(), space_type> expression, term, factor;
- };
- ///////////////////////////////////////////////////////////////////////////////
- // The Virtual Machine
- ///////////////////////////////////////////////////////////////////////////////
- class vmachine
- {
- public:
- union element {
- int code;
- char bytes[sizeof(int)];
- };
- vmachine(unsigned stackSize = 4096)
- : stack(stackSize)
- , stack_ptr(stack.begin())
- {
- }
- int top() const { return stack_ptr[-1]; };
- void execute(std::vector<element> const& code);
- private:
- std::vector<int> stack;
- std::vector<int>::iterator stack_ptr;
- };
- void vmachine::execute(std::vector<element> const& code)
- {
- std::vector<element>::const_iterator pc = code.begin();
- stack_ptr = stack.begin();
- while ((*pc).code && pc != code.end())
- {
- switch ((*pc++).code)
- {
- 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++).code;
- break;
- }
- }
- }
- // We need to tell fusion about our binary_op and unary_op structs
- // to make them a first-class fusion citizen
- //
- // Note: we register the members exactly in the same sequence as we need them
- // in the grammar
- BOOST_FUSION_ADAPT_STRUCT(
- binary_op,
- (expression_ast, left)
- (expression_ast, right)
- (int, op)
- )
- BOOST_FUSION_ADAPT_STRUCT(
- unary_op,
- (expression_ast, right)
- (int, op)
- )
- ///////////////////////////////////////////////////////////////////////////////
- // Our AST grammar for the generator, this just dumps the AST as a expression
- ///////////////////////////////////////////////////////////////////////////////
- template <typename OuputIterator, typename Delimiter>
- struct generate_byte_code
- : karma::grammar<OuputIterator, expression_ast(), Delimiter>
- {
- generate_byte_code() : generate_byte_code::base_type(ast_node)
- {
- ast_node %= int_node | binary_node | unary_node;
- int_node %= dword(op_int) << dword;
- binary_node %= ast_node << ast_node << byte_;
- unary_node %= ast_node << byte_;
- }
- karma::rule<OuputIterator, expression_ast(), Delimiter> ast_node;
- karma::rule<OuputIterator, int(), Delimiter> int_node;
- karma::rule<OuputIterator, binary_op(), Delimiter> binary_node;
- karma::rule<OuputIterator, unary_op(), Delimiter> unary_node;
- };
- ///////////////////////////////////////////////////////////////////////////////
- // helper function helping to deduce the delimiter type
- template <typename Delimiter>
- bool generate_vm_code(expression_ast const& ast,
- std::vector<vmachine::element>& code, Delimiter const& d)
- {
- // Our generator grammar definitions
- typedef char* output_iterator_type;
- typedef generate_byte_code<output_iterator_type, Delimiter> generate_byte_code;
- char* outbuffer = (*code.begin()).bytes;
- generate_byte_code gen_vm;
- return karma::generate_delimited(outbuffer, gen_vm, d, ast);
- }
- ///////////////////////////////////////////////////////////////////////////////
- // Main program
- ///////////////////////////////////////////////////////////////////////////////
- int
- main()
- {
- std::cout << "/////////////////////////////////////////////////////////\n\n";
- std::cout << "Compile simple expressions to bytecode...\n\n";
- std::cout << "/////////////////////////////////////////////////////////\n\n";
- std::cout << "Type an expression...or [q or Q] to quit\n\n";
- // Our parser grammar definitions
- typedef std::string::const_iterator iterator_type;
- typedef calculator<iterator_type> calculator;
- calculator calc;
- std::string str;
- while (std::getline(std::cin, str))
- {
- if (str.empty() || str[0] == 'q' || str[0] == 'Q')
- break;
- expression_ast ast;
- std::string::const_iterator iter = str.begin();
- std::string::const_iterator end = str.end();
- bool r = qi::phrase_parse(iter, end, calc, space, ast);
- if (r && iter == end)
- {
- // we assume a vm code size of 4096 is sufficient
- std::vector<vmachine::element> code (4096);
- r = generate_vm_code(ast, code, pad(4));
- if (r)
- {
- vmachine vm;
- vm.execute(code);
- std::cout << "\nresult = " << vm.top() << std::endl;
- std::cout << "-------------------------\n";
- }
- else
- {
- std::cout << "-------------------------\n";
- std::cout << "Generating failed\n";
- std::cout << "-------------------------\n";
- }
- }
- else
- {
- std::string rest(iter, end);
- std::cout << "-------------------------\n";
- std::cout << "Parsing failed\n";
- std::cout << "stopped at: \": " << rest << "\"\n";
- std::cout << "-------------------------\n";
- }
- }
- std::cout << "Bye... :-) \n\n";
- return 0;
- }
|