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