calc2_ast_vm.cpp

/*=============================================================================
    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;
}