[Boost-commit] svn:boost r45184 - trunk/libs/spirit/example/karma

From: hartmut.kaiser_at_[hidden]
Date: 2008-05-06 19:58:57

Author: hkaiser
Date: 2008-05-06 19:58:57 EDT (Tue, 06 May 2008)
New Revision: 45184
URL: http://svn.boost.org/trac/boost/changeset/45184

Log:
Spirit.Karma: Added calc2_ast_vm example
Added:
   trunk/libs/spirit/example/karma/calc2_ast_vm.cpp   (contents, props changed)
   trunk/libs/spirit/example/karma/calc2_ast_vm.hpp   (contents, props changed)
Text files modified: 
   trunk/libs/spirit/example/karma/Jamfile |     1 +                                       
   1 files changed, 1 insertions(+), 0 deletions(-)

Modified: trunk/libs/spirit/example/karma/Jamfile
==============================================================================
--- trunk/libs/spirit/example/karma/Jamfile	(original)
+++ trunk/libs/spirit/example/karma/Jamfile	2008-05-06 19:58:57 EDT (Tue, 06 May 2008)
@@ -13,4 +13,5 @@
 exe functor_facilities : functor_facilities.cpp ;
 exe calc2_ast_dump     : calc2_ast_dump.cpp ;
 exe calc2_ast_rpn      : calc2_ast_rpn.cpp ;
+exe calc2_ast_vm       : calc2_ast_vm.cpp ;
 

Added: trunk/libs/spirit/example/karma/calc2_ast_vm.cpp
==============================================================================
--- (empty file)
+++ trunk/libs/spirit/example/karma/calc2_ast_vm.cpp	2008-05-06 19:58:57 EDT (Tue, 06 May 2008)
@@ -0,0 +1,246 @@
+/*=============================================================================
+    Copyright (c) 2001-2008 Joel de Guzman
+    Copyright (c) 2001-2008 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 <boost/spirit/include/qi.hpp>
+#include <boost/spirit/include/karma.hpp>
+#include <boost/spirit/home/karma/binary.hpp>
+
+#include <iostream>
+#include <vector>
+#include <string>
+
+#include "calc2_ast_vm.hpp"
+
+using namespace boost::spirit;
+using namespace boost::spirit::ascii;
+using namespace boost::spirit::arg_names;
+
+///////////////////////////////////////////////////////////////////////////////
+//  Our calculator parser grammar
+///////////////////////////////////////////////////////////////////////////////
+template <typename Iterator>
+struct calculator : qi::grammar_def<Iterator, expression_ast(), space_type>
+{
+    calculator()
+    {
+        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;
+        }
+    }
+}
+
+///////////////////////////////////////////////////////////////////////////////
+//  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_def<OuputIterator, expression_ast(), Delimiter>
+{
+    generate_byte_code()
+    {
+        ast_node %= 
+                (dword(op_int) << dword) [_1 = _int(_val)]
+            |   binary_node              [_1 = _bin_op(_val)]
+            |   unary_node               [_1 = _unary_op(_val)]
+            ;
+            
+        binary_node = 
+                (ast_node << ast_node << byte)
+                [ 
+                    _1 = _left(_val), _2 = _right(_val), _3 = _op(_val)
+                ]
+            ;
+
+        unary_node =
+                (ast_node << byte)
+                [
+                    _1 = _right(_val), _2 = _op(_val)
+                ]
+            ;
+    }
+
+    karma::rule<OuputIterator, expression_ast(), Delimiter> ast_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;
+    
+    generate_byte_code generate_byte_code_def;
+    karma::grammar<generate_byte_code> gen_vm(
+        generate_byte_code_def, generate_byte_code_def.ast_node); 
+
+    return karma::generate_delimited((*code.begin()).bytes, gen_vm, ast, d);
+}
+
+///////////////////////////////////////////////////////////////////////////////
+//  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 def; 
+    qi::grammar<calculator> calc(def, def.expression);
+
+    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, ast, space);
+
+        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;
+}
+
+

Added: trunk/libs/spirit/example/karma/calc2_ast_vm.hpp
==============================================================================
--- (empty file)
+++ trunk/libs/spirit/example/karma/calc2_ast_vm.hpp	2008-05-06 19:58:57 EDT (Tue, 06 May 2008)
@@ -0,0 +1,224 @@
+/*=============================================================================
+    Copyright (c) 2001-2008 Joel de Guzman
+    Copyright (c) 2001-2008 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 which gets dumped into
+//  a human readable format afterwards.
+//
+//  [ JDG April 28, 2008 ]
+//  [ HK April 28, 2008 ]
+//
+///////////////////////////////////////////////////////////////////////////////
+
+#if !defined(SPIRIT_EXAMPLE_CALC2_AST_APR_30_2008_1011AM)
+#define SPIRIT_EXAMPLE_CALC2_AST_APR_30_2008_1011AM
+
+#include <boost/variant/recursive_variant.hpp>
+#include <boost/spirit/include/phoenix_operator.hpp>
+#include <boost/spirit/include/phoenix_function.hpp>
+#include <boost/spirit/include/phoenix_statement.hpp>
+
+///////////////////////////////////////////////////////////////////////////////
+//  Our AST
+///////////////////////////////////////////////////////////////////////////////
+struct binary_op;
+struct unary_op;
+struct nil {};
+
+struct expression_ast
+{
+    typedef
+        boost::variant<
+            nil // can't happen!
+          , int
+          , boost::recursive_wrapper<binary_op>
+          , boost::recursive_wrapper<unary_op>
+        >
+    type;
+
+    // expose variant types 
+    typedef type::types types;
+    
+    // expose variant functionality
+    int which() const { return expr.which(); }
+    
+    // constructors
+    expression_ast()
+      : expr(nil()) {}
+
+    expression_ast(unary_op const& expr)
+      : expr(expr) {}
+
+    expression_ast(binary_op const& expr)
+      : expr(expr) {}
+
+    expression_ast(unsigned int expr)
+      : expr(expr) {}
+      
+    expression_ast(type const& expr)
+      : expr(expr) {}
+      
+    expression_ast& operator+=(expression_ast const& rhs);
+    expression_ast& operator-=(expression_ast const& rhs);
+    expression_ast& operator*=(expression_ast const& rhs);
+    expression_ast& operator/=(expression_ast const& rhs);
+
+    type expr;
+};
+
+// expose variant functionality
+template <typename T>
+inline T get(expression_ast const& expr)
+{
+    return boost::get<T>(expr.expr);
+}
+
+enum byte_code
+{
+    op_neg = 1,     //  negate the top stack entry
+    op_pos,         //  essentially a no-op (unary plus)
+    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
+};
+
+///////////////////////////////////////////////////////////////////////////////
+struct binary_op
+{
+    binary_op() {}
+    
+    binary_op(
+        int op
+      , expression_ast const& left
+      , expression_ast const& right)
+      : op(op), left(left), right(right) {}
+
+    int op;
+    expression_ast left;
+    expression_ast right;
+};
+
+struct unary_op
+{
+    unary_op(
+        int op
+      , expression_ast const& right)
+    : op(op), right(right) {}
+
+    int op;
+    expression_ast right;
+};
+
+inline expression_ast& expression_ast::operator+=(expression_ast const& rhs)
+{
+    expr = binary_op(op_add, expr, rhs);
+    return *this;
+}
+
+inline expression_ast& expression_ast::operator-=(expression_ast const& rhs)
+{
+    expr = binary_op(op_sub, expr, rhs);
+    return *this;
+}
+
+inline expression_ast& expression_ast::operator*=(expression_ast const& rhs)
+{
+    expr = binary_op(op_mul, expr, rhs);
+    return *this;
+}
+
+inline expression_ast& expression_ast::operator/=(expression_ast const& rhs)
+{
+    expr = binary_op(op_div, expr, rhs);
+    return *this;
+}
+
+// We should be using expression_ast::operator-. There's a bug
+// in phoenix type deduction mechanism that prevents us from
+// doing so. Phoenix will be switching to BOOST_TYPEOF. In the
+// meantime, we will use a phoenix::function below:
+template <char Op>
+struct unary_expr
+{
+    template <typename T>
+    struct result { typedef T type; };
+
+    expression_ast operator()(expression_ast const& expr) const
+    {
+        return unary_op(Op, expr);
+    }
+};
+
+boost::phoenix::function<unary_expr<op_pos> > pos;
+boost::phoenix::function<unary_expr<op_neg> > neg;
+
+///////////////////////////////////////////////////////////////////////////////
+//  A couple of phoenix functions helping to access the elements of the 
+//  generated AST
+///////////////////////////////////////////////////////////////////////////////
+template <typename T>
+struct get_element
+{
+    template <typename T1>
+    struct result { typedef T const& type; };
+
+    T const& operator()(expression_ast const& expr) const
+    {
+        return boost::get<T>(expr.expr);
+    }
+};
+
+boost::phoenix::function<get_element<int> > _int;
+boost::phoenix::function<get_element<binary_op> > _bin_op;
+boost::phoenix::function<get_element<unary_op> > _unary_op;
+
+///////////////////////////////////////////////////////////////////////////////
+struct get_left
+{
+    template <typename T1>
+    struct result { typedef expression_ast const& type; };
+
+    expression_ast const& operator()(binary_op const& bin_op) const
+    {
+        return bin_op.left;
+    }
+};
+
+boost::phoenix::function<get_left> _left;
+
+struct get_right
+{
+    template <typename T1>
+    struct result { typedef expression_ast const& type; };
+
+    template <typename Node>
+    expression_ast const& operator()(Node const& op) const
+    {
+        return op.right;
+    }
+};
+
+boost::phoenix::function<get_right> _right;
+
+struct get_op
+{
+    template <typename T1>
+    struct result { typedef int type; };
+
+    template <typename Node>
+    int operator()(Node const& bin_op) const
+    {
+        return bin_op.op;
+    }
+};
+
+boost::phoenix::function<get_op> _op;
+
+#endif