Skip to content

Instantly share code, notes, and snippets.

@sehe

sehe/Makefile

Created November 2, 2015 21:23
Show Gist options
  • Save sehe/5bb9891590a4cac3ee27 to your computer and use it in GitHub Desktop.
Save sehe/5bb9891590a4cac3ee27 to your computer and use it in GitHub Desktop.
Download ZIP
mini_c question
Raw
annotation.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_ANNOTATION_HPP)
#define BOOST_SPIRIT_MINIC_ANNOTATION_HPP
#include <map>
#include <boost/variant/apply_visitor.hpp>
#include <boost/type_traits/is_base_of.hpp>
#include <boost/mpl/bool.hpp>
#include "ast.hpp"
namespace client
{
///////////////////////////////////////////////////////////////////////////////
// The annotation handler links the AST to a map of iterator positions
// for the purpose of subsequent semantic error handling when the
// program is being compiled.
///////////////////////////////////////////////////////////////////////////////
template <typename Iterator>
struct annotation
{
template <typename, typename>
struct result { typedef void type; };
std::vector<Iterator>& iters;
annotation(std::vector<Iterator>& iters)
: iters(iters) {}
struct set_id
{
typedef void result_type;
int id;
set_id(int id) : id(id) {}
void operator()(ast::function_call& x) const
{
x.function_name.id = id;
}
void operator()(ast::identifier& x) const
{
x.id = id;
}
template <typename T>
void operator()(T& x) const
{
// no-op
}
};
void operator()(ast::operand& ast, Iterator pos) const
{
int id = iters.size();
iters.push_back(pos);
boost::apply_visitor(set_id(id), ast);
}
void operator()(ast::variable_declaration& ast, Iterator pos) const
{
int id = iters.size();
iters.push_back(pos);
ast.lhs.id = id;
}
void operator()(ast::assignment& ast, Iterator pos) const
{
int id = iters.size();
iters.push_back(pos);
ast.lhs.id = id;
}
void operator()(ast::return_statement& ast, Iterator pos) const
{
int id = iters.size();
iters.push_back(pos);
ast.id = id;
}
void operator()(ast::identifier& ast, Iterator pos) const
{
int id = iters.size();
iters.push_back(pos);
ast.id = id;
}
};
}
#endif
Raw
ast.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_AST_HPP)
#define BOOST_SPIRIT_MINIC_AST_HPP
#include <boost/config/warning_disable.hpp>
#include <boost/variant/recursive_variant.hpp>
#include <boost/fusion/include/adapt_struct.hpp>
#include <boost/fusion/include/io.hpp>
#include <boost/optional.hpp>
#include <list>
namespace client { namespace ast
{
///////////////////////////////////////////////////////////////////////////
// The AST
///////////////////////////////////////////////////////////////////////////
struct tagged
{
int id; // Used to annotate the AST with the iterator position.
// This id is used as a key to a map<int, Iterator>
// (not really part of the AST.)
};
struct nil {};
struct unary;
struct function_call;
struct expression;
struct identifier : tagged
{
identifier(std::string const& name = "") : name(name) {}
std::string name;
};
typedef boost::variant<
nil
, bool
, unsigned int
, identifier
, boost::recursive_wrapper<unary>
, boost::recursive_wrapper<function_call>
, boost::recursive_wrapper<expression>
>
operand;
enum optoken
{
op_plus,
op_minus,
op_times,
op_divide,
op_positive,
op_negative,
op_not,
op_equal,
op_not_equal,
op_less,
op_less_equal,
op_greater,
op_greater_equal,
op_and,
op_or
};
struct unary
{
optoken operator_;
operand operand_;
};
struct operation
{
optoken operator_;
operand operand_;
};
struct function_call
{
identifier function_name;
std::list<expression> args;
};
struct expression
{
operand first;
std::list<operation> rest;
};
struct assignment
{
identifier lhs;
expression rhs;
};
struct variable_declaration
{
identifier lhs;
boost::optional<expression> rhs;
};
struct if_statement;
struct while_statement;
struct statement_list;
struct return_statement;
typedef boost::variant<
variable_declaration
, assignment
, boost::recursive_wrapper<if_statement>
, boost::recursive_wrapper<while_statement>
, boost::recursive_wrapper<return_statement>
, boost::recursive_wrapper<statement_list>
>
statement;
struct statement_list : std::list<statement> {};
struct if_statement
{
expression condition;
statement then;
boost::optional<statement> else_;
};
struct while_statement
{
expression condition;
statement body;
};
struct return_statement : tagged
{
boost::optional<expression> expr;
};
struct function
{
std::string return_type;
identifier function_name;
std::list<identifier> args;
statement_list body;
};
typedef std::list<function> function_list;
// print functions for debugging
inline std::ostream& operator<<(std::ostream& out, nil)
{
out << "nil"; return out;
}
inline std::ostream& operator<<(std::ostream& out, identifier const& id)
{
out << id.name; return out;
}
}}
BOOST_FUSION_ADAPT_STRUCT(
client::ast::unary,
(client::ast::optoken, operator_)
(client::ast::operand, operand_)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::operation,
(client::ast::optoken, operator_)
(client::ast::operand, operand_)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::function_call,
(client::ast::identifier, function_name)
(std::list<client::ast::expression>, args)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::expression,
(client::ast::operand, first)
(std::list<client::ast::operation>, rest)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::variable_declaration,
(client::ast::identifier, lhs)
(boost::optional<client::ast::expression>, rhs)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::assignment,
(client::ast::identifier, lhs)
(client::ast::expression, rhs)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::if_statement,
(client::ast::expression, condition)
(client::ast::statement, then)
(boost::optional<client::ast::statement>, else_)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::while_statement,
(client::ast::expression, condition)
(client::ast::statement, body)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::return_statement,
(boost::optional<client::ast::expression>, expr)
)
BOOST_FUSION_ADAPT_STRUCT(
client::ast::function,
(std::string, return_type)
(client::ast::identifier, function_name)
(std::list<client::ast::identifier>, args)
(client::ast::statement_list, body)
)
#endif
Raw
compiler.cpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#include "compiler.hpp"
#include "vm.hpp"
#include <boost/foreach.hpp>
#include <boost/variant/apply_visitor.hpp>
#include <boost/assert.hpp>
#include <boost/lexical_cast.hpp>
#include <set>
namespace client { namespace code_gen
{
void function::op(int a)
{
code.push_back(a);
size_ += 1;
}
void function::op(int a, int b)
{
code.push_back(a);
code.push_back(b);
size_ += 2;
}
void function::op(int a, int b, int c)
{
code.push_back(a);
code.push_back(b);
code.push_back(c);
size_ += 3;
}
int const* function::find_var(std::string const& name) const
{
std::map<std::string, int>::const_iterator i = variables.find(name);
if (i == variables.end())
return 0;
return &i->second;
}
void function::add_var(std::string const& name)
{
std::size_t n = variables.size();
variables[name] = n;
}
void function::link_to(std::string const& name, std::size_t address)
{
function_calls[address] = name;
}
void function::print_assembler() const
{
std::vector<int>::const_iterator pc = code.begin() + address;
std::vector<std::string> locals(variables.size());
typedef std::pair<std::string, int> pair;
BOOST_FOREACH(pair const& p, variables)
{
locals[p.second] = p.first;
std::cout << " local "
<< p.first << ", @" << p.second << std::endl;
}
std::map<std::size_t, std::string> lines;
std::set<std::size_t> jumps;
while (pc != (code.begin() + address + size_))
{
std::string line;
std::size_t address = pc - code.begin();
switch (*pc++)
{
case op_neg:
line += " op_neg";
break;
case op_not:
line += " op_not";
break;
case op_add:
line += " op_add";
break;
case op_sub:
line += " op_sub";
break;
case op_mul:
line += " op_mul";
break;
case op_div:
line += " op_div";
break;
case op_eq:
line += " op_eq";
break;
case op_neq:
line += " op_neq";
break;
case op_lt:
line += " op_lt";
break;
case op_lte:
line += " op_lte";
break;
case op_gt:
line += " op_gt";
break;
case op_gte:
line += " op_gte";
break;
case op_and:
line += " op_and";
break;
case op_or:
line += " op_or";
break;
case op_load:
line += " op_load ";
line += boost::lexical_cast<std::string>(locals[*pc++]);
break;
case op_store:
line += " op_store ";
line += boost::lexical_cast<std::string>(locals[*pc++]);
break;
case op_int:
line += " op_int ";
line += boost::lexical_cast<std::string>(*pc++);
break;
case op_true:
line += " op_true";
break;
case op_false:
line += " op_false";
break;
case op_jump:
{
line += " op_jump ";
std::size_t pos = (pc - code.begin()) + *pc++;
if (pos == code.size())
line += "end";
else
line += boost::lexical_cast<std::string>(pos);
jumps.insert(pos);
}
break;
case op_jump_if:
{
line += " op_jump_if ";
std::size_t pos = (pc - code.begin()) + *pc++;
if (pos == code.size())
line += "end";
else
line += boost::lexical_cast<std::string>(pos);
jumps.insert(pos);
}
break;
case op_call:
{
line += " op_call ";
int nargs = *pc++;
std::size_t jump = *pc++;
line += boost::lexical_cast<std::string>(nargs) + ", ";
BOOST_ASSERT(function_calls.find(jump) != function_calls.end());
line += function_calls.find(jump)->second;
}
break;
case op_stk_adj:
line += " op_stk_adj ";
line += boost::lexical_cast<std::string>(*pc++);
break;
case op_return:
line += " op_return";
break;
}
lines[address] = line;
}
std::cout << "start:" << std::endl;
typedef std::pair<std::size_t, std::string> line_info;
BOOST_FOREACH(line_info const& l, lines)
{
std::size_t pos = l.first;
if (jumps.find(pos) != jumps.end())
std::cout << pos << ':' << std::endl;
std::cout << l.second << std::endl;
}
std::cout << "end:" << std::endl << std::endl;
}
bool compiler::operator()(unsigned int x)
{
BOOST_ASSERT(current != 0);
current->op(op_int, x);
return true;
}
bool compiler::operator()(bool x)
{
BOOST_ASSERT(current != 0);
current->op(x ? op_true : op_false);
return true;
}
bool compiler::operator()(ast::identifier const& x)
{
BOOST_ASSERT(current != 0);
int const* p = current->find_var(x.name);
if (p == 0)
{
error_handler(x.id, "Undeclared variable: " + x.name);
return false;
}
current->op(op_load, *p);
return true;
}
bool compiler::operator()(ast::operation const& x)
{
BOOST_ASSERT(current != 0);
if (!boost::apply_visitor(*this, x.operand_))
return false;
switch (x.operator_)
{
case ast::op_plus: current->op(op_add); break;
case ast::op_minus: current->op(op_sub); break;
case ast::op_times: current->op(op_mul); break;
case ast::op_divide: current->op(op_div); break;
case ast::op_equal: current->op(op_eq); break;
case ast::op_not_equal: current->op(op_neq); break;
case ast::op_less: current->op(op_lt); break;
case ast::op_less_equal: current->op(op_lte); break;
case ast::op_greater: current->op(op_gt); break;
case ast::op_greater_equal: current->op(op_gte); break;
case ast::op_and: current->op(op_and); break;
case ast::op_or: current->op(op_or); break;
default: BOOST_ASSERT(0); return false;
}
return true;
}
bool compiler::operator()(ast::unary const& x)
{
BOOST_ASSERT(current != 0);
if (!boost::apply_visitor(*this, x.operand_))
return false;
switch (x.operator_)
{
case ast::op_negative: current->op(op_neg); break;
case ast::op_not: current->op(op_not); break;
case ast::op_positive: break;
default: BOOST_ASSERT(0); return false;
}
return true;
}
bool compiler::operator()(ast::function_call const& x)
{
BOOST_ASSERT(current != 0);
if (functions.find(x.function_name.name) == functions.end())
{
error_handler(x.function_name.id, "Function not found: " + x.function_name.name);
return false;
}
boost::shared_ptr<code_gen::function> p = functions[x.function_name.name];
if (p->nargs() != x.args.size())
{
error_handler(x.function_name.id, "Wrong number of arguments: " + x.function_name.name);
return false;
}
BOOST_FOREACH(ast::expression const& expr, x.args)
{
if (!(*this)(expr))
return false;
}
current->op(
op_call,
p->nargs(),
p->get_address());
current->link_to(x.function_name.name, p->get_address());
return true;
}
bool compiler::operator()(ast::expression const& x)
{
BOOST_ASSERT(current != 0);
if (!boost::apply_visitor(*this, x.first))
return false;
BOOST_FOREACH(ast::operation const& oper, x.rest)
{
if (!(*this)(oper))
return false;
}
return true;
}
bool compiler::operator()(ast::assignment const& x)
{
BOOST_ASSERT(current != 0);
if (!(*this)(x.rhs))
return false;
int const* p = current->find_var(x.lhs.name);
if (p == 0)
{
error_handler(x.lhs.id, "Undeclared variable: " + x.lhs.name);
return false;
}
current->op(op_store, *p);
return true;
}
bool compiler::operator()(ast::variable_declaration const& x)
{
BOOST_ASSERT(current != 0);
int const* p = current->find_var(x.lhs.name);
if (p != 0)
{
error_handler(x.lhs.id, "Duplicate variable: " + x.lhs.name);
return false;
}
if (x.rhs) // if there's an RHS initializer
{
bool r = (*this)(*x.rhs);
if (r) // don't add the variable if the RHS fails
{
current->add_var(x.lhs.name);
current->op(op_store, *current->find_var(x.lhs.name));
}
return r;
}
else
{
current->add_var(x.lhs.name);
}
return true;
}
bool compiler::operator()(ast::statement const& x)
{
BOOST_ASSERT(current != 0);
return boost::apply_visitor(*this, x);
}
bool compiler::operator()(ast::statement_list const& x)
{
BOOST_ASSERT(current != 0);
BOOST_FOREACH(ast::statement const& s, x)
{
if (!(*this)(s))
return false;
}
return true;
}
bool compiler::operator()(ast::if_statement const& x)
{
BOOST_ASSERT(current != 0);
if (!(*this)(x.condition))
return false;
current->op(op_jump_if, 0); // we shall fill this (0) in later
std::size_t skip = current->size()-1; // mark its position
if (!(*this)(x.then))
return false;
(*current)[skip] = current->size()-skip; // now we know where to jump to (after the if branch)
if (x.else_) // We got an alse
{
(*current)[skip] += 2; // adjust for the "else" jump
current->op(op_jump, 0); // we shall fill this (0) in later
std::size_t exit = current->size()-1; // mark its position
if (!(*this)(*x.else_))
return false;
(*current)[exit] = current->size()-exit;// now we know where to jump to (after the else branch)
}
return true;
}
bool compiler::operator()(ast::while_statement const& x)
{
BOOST_ASSERT(current != 0);
std::size_t loop = current->size(); // mark our position
if (!(*this)(x.condition))
return false;
current->op(op_jump_if, 0); // we shall fill this (0) in later
std::size_t exit = current->size()-1; // mark its position
if (!(*this)(x.body))
return false;
current->op(op_jump,
int(loop-1) - int(current->size())); // loop back
(*current)[exit] = current->size()-exit; // now we know where to jump to (to exit the loop)
return true;
}
bool compiler::operator()(ast::return_statement const& x)
{
if (void_return)
{
if (x.expr)
{
error_handler(x.id, "'void' function returning a value: ");
return false;
}
}
else
{
if (!x.expr)
{
error_handler(x.id, current_function_name + " function must return a value: ");
return false;
}
}
if (x.expr)
{
if (!(*this)(*x.expr))
return false;
}
current->op(op_return);
return true;
}
bool compiler::operator()(ast::function const& x)
{
void_return = x.return_type == "void";
if (functions.find(x.function_name.name) != functions.end())
{
error_handler(x.function_name.id, "Duplicate function: " + x.function_name.name);
return false;
}
boost::shared_ptr<code_gen::function>& p = functions[x.function_name.name];
p.reset(new code_gen::function(code, x.args.size()));
current = p.get();
current_function_name = x.function_name.name;
// op_stk_adj 0 for now. we'll know how many variables
// we'll have later and add them
current->op(op_stk_adj, 0);
BOOST_FOREACH(ast::identifier const& arg, x.args)
{
current->add_var(arg.name);
}
if (!(*this)(x.body))
return false;
(*current)[1] = current->nvars(); // now store the actual number of variables
// this includes the arguments
return true;
}
bool compiler::operator()(ast::function_list const& x)
{
// Jump to the main function
code.push_back(op_jump);
code.push_back(0); // we will fill this in later when we finish compiling
// and we know where the main function is
BOOST_FOREACH(ast::function const& f, x)
{
if (!(*this)(f))
{
code.clear();
return false;
}
}
// find the main function
boost::shared_ptr<code_gen::function> p =
find_function("main");
if (!p) // main function not found
{
std::cerr << "Error: main function not defined" << std::endl;
return false;
}
code[1] = p->get_address()-1; // jump to this (main function) address
return true;
}
void compiler::print_assembler() const
{
typedef std::pair<std::string, boost::shared_ptr<code_gen::function> > pair;
BOOST_FOREACH(pair const& p, functions)
{
std::cout << ";;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;" << std::endl;
std::cout << p.second->get_address() << ": function " << p.first << std::endl;
p.second->print_assembler();
}
}
boost::shared_ptr<code_gen::function>
compiler::find_function(std::string const& name) const
{
function_table::const_iterator i = functions.find(name);
if (i == functions.end())
return boost::shared_ptr<code_gen::function>();
else
return i->second;
}
}}
Raw
compiler.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_COMPILER_HPP)
#define BOOST_SPIRIT_MINIC_COMPILER_HPP
#include "ast.hpp"
#include "error_handler.hpp"
#include <vector>
#include <map>
#include <boost/function.hpp>
#include <boost/shared_ptr.hpp>
#include <boost/spirit/include/phoenix_core.hpp>
#include <boost/spirit/include/phoenix_function.hpp>
#include <boost/spirit/include/phoenix_operator.hpp>
namespace client { namespace code_gen
{
///////////////////////////////////////////////////////////////////////////
// The Function
///////////////////////////////////////////////////////////////////////////
struct function
{
function(std::vector<int>& code, int nargs)
: code(code), address(code.size()), size_(0), nargs_(nargs) {}
void op(int a);
void op(int a, int b);
void op(int a, int b, int c);
int& operator[](std::size_t i) { return code[address+i]; }
int const& operator[](std::size_t i) const { return code[address+i]; }
std::size_t size() const { return size_; }
std::size_t get_address() const { return address; }
size_t nargs() const { return nargs_; }
size_t nvars() const { return variables.size(); }
int const* find_var(std::string const& name) const;
void add_var(std::string const& name);
void link_to(std::string const& name, std::size_t address);
void print_assembler() const;
private:
std::map<std::string, int> variables;
std::map<std::size_t, std::string> function_calls;
std::vector<int>& code;
std::size_t address;
std::size_t size_;
std::size_t nargs_;
};
///////////////////////////////////////////////////////////////////////////
// The Compiler
///////////////////////////////////////////////////////////////////////////
struct compiler
{
typedef bool result_type;
template <typename ErrorHandler>
compiler(ErrorHandler& error_handler_)
: current(0)
{
using namespace boost::phoenix::arg_names;
namespace phx = boost::phoenix;
using boost::phoenix::function;
error_handler = function<ErrorHandler>(error_handler_)(
"Error! ", _2, phx::cref(error_handler_.iters)[_1]);
}
bool operator()(ast::nil) { BOOST_ASSERT(0); return false; }
bool operator()(unsigned int x);
bool operator()(bool x);
bool operator()(ast::identifier const& x);
bool operator()(ast::operation const& x);
bool operator()(ast::unary const& x);
bool operator()(ast::function_call const& x);
bool operator()(ast::expression const& x);
bool operator()(ast::assignment const& x);
bool operator()(ast::variable_declaration const& x);
bool operator()(ast::statement_list const& x);
bool operator()(ast::statement const& x);
bool operator()(ast::if_statement const& x);
bool operator()(ast::while_statement const& x);
bool operator()(ast::return_statement const& x);
bool operator()(ast::function const& x);
bool operator()(ast::function_list const& x);
void print_assembler() const;
boost::shared_ptr<code_gen::function>
find_function(std::string const& name) const;
std::vector<int>& get_code() { return code; }
std::vector<int> const& get_code() const { return code; }
private:
typedef std::map<std::string, boost::shared_ptr<code_gen::function> > function_table;
std::vector<int> code;
code_gen::function* current;
std::string current_function_name;
function_table functions;
bool void_return;
boost::function<
void(int tag, std::string const& what)>
error_handler;
};
}}
#endif
Raw
error_handler.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_ERROR_HANDLER_HPP)
#define BOOST_SPIRIT_MINIC_ERROR_HANDLER_HPP
#include <iostream>
#include <string>
#include <vector>
namespace client
{
///////////////////////////////////////////////////////////////////////////////
// The error handler
///////////////////////////////////////////////////////////////////////////////
template <typename Iterator>
struct error_handler
{
template <typename, typename, typename>
struct result { typedef void type; };
error_handler(Iterator first, Iterator last)
: first(first), last(last) {}
template <typename Message, typename What>
void operator()(
Message const& message,
What const& what,
Iterator err_pos) const
{
int line;
Iterator line_start = get_pos(err_pos, line);
if (err_pos != last)
{
std::cout << message << what << " line " << line << ':' << std::endl;
std::cout << get_line(line_start) << std::endl;
for (; line_start != err_pos; ++line_start)
std::cout << ' ';
std::cout << '^' << std::endl;
}
else
{
std::cout << "Unexpected end of file. ";
std::cout << message << what << " line " << line << std::endl;
}
}
Iterator get_pos(Iterator err_pos, int& line) const
{
line = 1;
Iterator i = first;
Iterator line_start = first;
while (i != err_pos)
{
bool eol = false;
if (i != err_pos && *i == '\r') // CR
{
eol = true;
line_start = ++i;
}
if (i != err_pos && *i == '\n') // LF
{
eol = true;
line_start = ++i;
}
if (eol)
++line;
else
++i;
}
return line_start;
}
std::string get_line(Iterator err_pos) const
{
Iterator i = err_pos;
// position i to the next EOL
while (i != last && (*i != '\r' && *i != '\n'))
++i;
return std::string(err_pos, i);
}
Iterator first;
Iterator last;
std::vector<Iterator> iters;
};
}
#endif
Raw
expression.cpp
/*=============================================================================
Copyright (c) 2001-2010 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)
=============================================================================*/
#if defined(_MSC_VER)
# pragma warning(disable: 4345)
#endif
#include "expression_def.hpp"
typedef std::string::const_iterator iterator_type;
template struct client::parser::expression<iterator_type>;
Raw
expression.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_EXPRESSION_HPP)
#define BOOST_SPIRIT_MINIC_EXPRESSION_HPP
///////////////////////////////////////////////////////////////////////////////
// Spirit v2.5 allows you to suppress automatic generation
// of predefined terminals to speed up complation. With
// BOOST_SPIRIT_NO_PREDEFINED_TERMINALS defined, you are
// responsible in creating instances of the terminals that
// you need (e.g. see qi::uint_type uint_ below).
#define BOOST_SPIRIT_NO_PREDEFINED_TERMINALS
///////////////////////////////////////////////////////////////////////////////
///////////////////////////////////////////////////////////////////////////////
// Uncomment this if you want to enable debugging
// #define BOOST_SPIRIT_QI_DEBUG
///////////////////////////////////////////////////////////////////////////////
#include <boost/spirit/include/qi.hpp>
#include "ast.hpp"
#include "error_handler.hpp"
#include "skipper.hpp"
#include <vector>
namespace client { namespace parser
{
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
///////////////////////////////////////////////////////////////////////////////
// The expression grammar
///////////////////////////////////////////////////////////////////////////////
template <typename Iterator>
struct expression : qi::grammar<Iterator, ast::expression(), skipper<Iterator> >
{
expression(error_handler<Iterator>& error_handler);
qi::rule<Iterator, ast::expression(), skipper<Iterator> >
expr, equality_expr, relational_expr,
logical_or_expr, logical_and_expr,
additive_expr, multiplicative_expr
;
qi::rule<Iterator, ast::operand(), skipper<Iterator> >
unary_expr, primary_expr
;
qi::rule<Iterator, ast::function_call(), skipper<Iterator> >
function_call
;
qi::rule<Iterator, std::list<ast::expression>(), skipper<Iterator> >
argument_list
;
qi::rule<Iterator, std::string(), skipper<Iterator> >
identifier
;
qi::symbols<char, ast::optoken>
logical_or_op, logical_and_op,
equality_op, relational_op,
additive_op, multiplicative_op, unary_op
;
qi::symbols<char>
keywords
;
};
}}
#endif
Raw
expression_def.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#include "expression.hpp"
#include "error_handler.hpp"
#include "annotation.hpp"
#include <boost/spirit/include/phoenix_function.hpp>
namespace client { namespace parser
{
template <typename Iterator>
expression<Iterator>::expression(error_handler<Iterator>& error_handler)
: expression::base_type(expr)
{
qi::_1_type _1;
//qi::_2_type _2;
qi::_3_type _3;
qi::_4_type _4;
qi::char_type char_;
qi::uint_type uint_;
qi::_val_type _val;
qi::raw_type raw;
qi::lexeme_type lexeme;
qi::alpha_type alpha;
qi::alnum_type alnum;
qi::bool_type bool_;
using qi::on_error;
using qi::on_success;
using qi::fail;
using boost::phoenix::function;
typedef function<client::error_handler<Iterator> > error_handler_function;
typedef function<client::annotation<Iterator> > annotation_function;
///////////////////////////////////////////////////////////////////////
// Tokens
logical_or_op.add
("||", ast::op_or)
;
logical_and_op.add
("&&", ast::op_and)
;
equality_op.add
("==", ast::op_equal)
("!=", ast::op_not_equal)
;
relational_op.add
("<", ast::op_less)
("<=", ast::op_less_equal)
(">", ast::op_greater)
(">=", ast::op_greater_equal)
;
additive_op.add
("+", ast::op_plus)
("-", ast::op_minus)
;
multiplicative_op.add
("*", ast::op_times)
("/", ast::op_divide)
;
unary_op.add
("+", ast::op_positive)
("-", ast::op_negative)
("!", ast::op_not)
;
keywords.add
("true")
("false")
("if")
("else")
("while")
("int")
("void")
("return")
;
///////////////////////////////////////////////////////////////////////
// Main expression grammar
expr =
logical_or_expr.alias()
;
logical_or_expr =
logical_and_expr
>> *(logical_or_op > logical_and_expr)
;
logical_and_expr =
equality_expr
>> *(logical_and_op > equality_expr)
;
equality_expr =
relational_expr
>> *(equality_op > relational_expr)
;
relational_expr =
additive_expr
>> *(relational_op > additive_expr)
;
additive_expr =
multiplicative_expr
>> *(additive_op > multiplicative_expr)
;
multiplicative_expr =
unary_expr
>> *(multiplicative_op > unary_expr)
;
unary_expr =
primary_expr
| (unary_op > unary_expr)
;
primary_expr =
uint_
| function_call
| identifier
| bool_
| ('(' > expr > ')')
;
function_call =
(identifier >> '(')
> argument_list
> ')'
;
argument_list = -(expr % ',');
identifier =
!lexeme[keywords >> !(alnum | '_')]
>> raw[lexeme[(alpha | '_') >> *(alnum | '_')]]
;
///////////////////////////////////////////////////////////////////////
// Debugging and error handling and reporting support.
BOOST_SPIRIT_DEBUG_NODES(
(expr)
(logical_or_expr)
(logical_and_expr)
(equality_expr)
(relational_expr)
(additive_expr)
(multiplicative_expr)
(unary_expr)
(primary_expr)
(function_call)
(argument_list)
(identifier)
);
///////////////////////////////////////////////////////////////////////
// Error handling: on error in expr, call error_handler.
on_error<fail>(expr,
error_handler_function(error_handler)(
"Error! Expecting ", _4, _3));
///////////////////////////////////////////////////////////////////////
// Annotation: on success in primary_expr, call annotation.
on_success(primary_expr,
annotation_function(error_handler.iters)(_val, _1));
}
}}
Raw
function.cpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if defined(_MSC_VER)
# pragma warning(disable: 4345)
#endif
#include "function_def.hpp"
typedef std::string::const_iterator iterator_type;
template struct client::parser::function<iterator_type>;
Raw
function.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_FUNCTION_HPP)
#define BOOST_SPIRIT_MINIC_FUNCTION_HPP
#include "statement.hpp"
namespace client { namespace parser
{
///////////////////////////////////////////////////////////////////////////////
// The function grammar
///////////////////////////////////////////////////////////////////////////////
template <typename Iterator>
struct function : qi::grammar<Iterator, ast::function(), skipper<Iterator> >
{
function(error_handler<Iterator>& error_handler);
statement<Iterator> body;
qi::rule<Iterator, std::string(), skipper<Iterator> > name;
qi::rule<Iterator, ast::identifier(), skipper<Iterator> > identifier;
qi::rule<Iterator, std::list<ast::identifier>(), skipper<Iterator> > argument_list;
qi::rule<Iterator, ast::function(), skipper<Iterator> > start;
};
}}
#endif
Raw
function_def.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#include "function.hpp"
#include "error_handler.hpp"
#include "annotation.hpp"
namespace client { namespace parser
{
template <typename Iterator>
function<Iterator>::function(error_handler<Iterator>& error_handler)
: function::base_type(start), body(error_handler)
{
qi::_1_type _1;
//qi::_2_type _2;
qi::_3_type _3;
qi::_4_type _4;
qi::_val_type _val;
qi::raw_type raw;
qi::lexeme_type lexeme;
qi::alpha_type alpha;
qi::alnum_type alnum;
qi::string_type string;
using qi::on_error;
using qi::on_success;
using qi::fail;
using boost::phoenix::function;
typedef function<client::error_handler<Iterator> > error_handler_function;
typedef function<client::annotation<Iterator> > annotation_function;
name =
!body.expr.keywords
>> raw[lexeme[(alpha | '_') >> *(alnum | '_')]]
;
identifier = name;
argument_list = -(identifier % ',');
start =
lexeme[(string("void") | string("int"))
>> !(alnum | '_')] // make sure we have whole words
> identifier
> '(' > argument_list > ')'
> '{' > body > '}'
;
// Debugging and error handling and reporting support.
BOOST_SPIRIT_DEBUG_NODES(
(identifier)
(argument_list)
(start)
);
// Error handling: on error in start, call error_handler.
on_error<fail>(start,
error_handler_function(error_handler)(
"Error! Expecting ", _4, _3));
// Annotation: on success in start, call annotation.
on_success(identifier,
annotation_function(error_handler.iters)(_val, _1));
}
}}
Raw
main.cpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
///////////////////////////////////////////////////////////////////////////////
//
// Not a calculator anymore, right? :-)
//
// [ JDG April 10, 2007 ] spirit2
// [ JDG February 18, 2011 ] Pure attributes. No semantic actions.
//
///////////////////////////////////////////////////////////////////////////////
#include "function.hpp"
#include "skipper.hpp"
#include "vm.hpp"
#include "compiler.hpp"
#include <boost/lexical_cast.hpp>
#include <fstream>
///////////////////////////////////////////////////////////////////////////////
// Main program
///////////////////////////////////////////////////////////////////////////////
int main(int argc, char **argv)
{
char const* filename;
if (argc > 1)
{
filename = argv[1];
}
else
{
std::cerr << "Error: No input file provided." << std::endl;
return 1;
}
std::ifstream in(filename, std::ios_base::in);
if (!in)
{
std::cerr << "Error: Could not open input file: "
<< filename << std::endl;
return 1;
}
std::string source_code; // We will read the contents here.
in.unsetf(std::ios::skipws); // No white space skipping!
std::copy(
std::istream_iterator<char>(in),
std::istream_iterator<char>(),
std::back_inserter(source_code));
typedef std::string::const_iterator iterator_type;
iterator_type iter = source_code.begin();
iterator_type end = source_code.end();
client::vmachine vm; // Our virtual machine
client::ast::function_list ast; // Our AST
client::error_handler<iterator_type>
error_handler(iter, end); // Our error handler
client::parser::function<iterator_type>
function(error_handler); // Our parser
client::parser::skipper<iterator_type>
skipper; // Our skipper
client::code_gen::compiler
compiler(error_handler); // Our compiler
bool success = phrase_parse(iter, end, +function, skipper, ast);
std::cout << "-------------------------\n";
if (success && iter == end)
{
if (compiler(ast))
{
boost::shared_ptr<client::code_gen::function>
p = compiler.find_function("main");
if (!p)
return 1;
size_t nargs = argc-2;
if (p->nargs() != nargs)
{
std::cerr << "Error: main function requires " << p->nargs() << " arguments." << std::endl;
std::cerr << nargs << "supplied." << std::endl;
return 1;
}
std::cout << "Success\n";
std::cout << "-------------------------\n";
std::cout << "Assembler----------------\n\n";
compiler.print_assembler();
// Push the arguments into our stack
for (size_t i = 0; i < nargs; ++i)
vm.get_stack()[i] = boost::lexical_cast<int>(argv[i+2]);
// Call the interpreter
int r = vm.execute(compiler.get_code());
std::cout << "-------------------------\n";
std::cout << "Result: " << r << std::endl;
std::cout << "-------------------------\n\n";
}
else
{
std::cout << "Compile failure\n";
}
}
else
{
std::cout << "Parse failure\n";
}
return 0;
}
Raw
Makefile
all:mini_c
CPPFLAGS+=-std=c++11 -Wall -pedantic
CPPFLAGS+=-g -O2
CPPFLAGS+=-pthread
%.o:%.cpp
$(CXX) $(CPPFLAGS) $< -c -o $@
mini_c: $(patsubst %.cpp,%.o,$(wildcard *.cpp))
$(CXX) $(CPPFLAGS) $^ -o $@ $(LDFLAGS)
-include .depends
.depends: $(wildcard *.cpp)
$(CXX) $(CPPFLAGS) -M $^ > $@
Raw
skipper.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_SKIPPER_HPP)
#define BOOST_SPIRIT_MINIC_SKIPPER_HPP
#include <boost/spirit/include/qi.hpp>
namespace client { namespace parser
{
namespace qi = boost::spirit::qi;
namespace ascii = boost::spirit::ascii;
///////////////////////////////////////////////////////////////////////////////
// The skipper grammar
///////////////////////////////////////////////////////////////////////////////
template <typename Iterator>
struct skipper : qi::grammar<Iterator>
{
skipper() : skipper::base_type(start)
{
qi::char_type char_;
ascii::space_type space;
start =
space // tab/space/cr/lf
| "/*" >> *(char_ - "*/") >> "*/" // C-style comments
;
}
qi::rule<Iterator> start;
};
}}
#endif
Raw
statement.cpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if defined(_MSC_VER)
# pragma warning(disable: 4345)
#endif
#include "statement_def.hpp"
typedef std::string::const_iterator iterator_type;
template struct client::parser::statement<iterator_type>;
Raw
statement.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_STATEMENT_HPP)
#define BOOST_SPIRIT_MINIC_STATEMENT_HPP
#include "expression.hpp"
namespace client { namespace parser
{
///////////////////////////////////////////////////////////////////////////////
// The statement grammar
///////////////////////////////////////////////////////////////////////////////
template <typename Iterator>
struct statement : qi::grammar<Iterator, ast::statement_list(), skipper<Iterator> >
{
statement(error_handler<Iterator>& error_handler);
expression<Iterator> expr;
qi::rule<Iterator, ast::statement_list(), skipper<Iterator> >
statement_list, compound_statement;
qi::rule<Iterator, ast::statement(), skipper<Iterator> > statement_;
qi::rule<Iterator, ast::variable_declaration(), skipper<Iterator> > variable_declaration;
qi::rule<Iterator, ast::assignment(), skipper<Iterator> > assignment;
qi::rule<Iterator, ast::if_statement(), skipper<Iterator> > if_statement;
qi::rule<Iterator, ast::while_statement(), skipper<Iterator> > while_statement;
qi::rule<Iterator, ast::return_statement(), skipper<Iterator> > return_statement;
qi::rule<Iterator, std::string(), skipper<Iterator> > identifier;
};
}}
#endif
Raw
statement_def.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#include "statement.hpp"
#include "error_handler.hpp"
#include "annotation.hpp"
namespace client { namespace parser
{
void print_this_declaration() { std::cout << "output here: \n"; }
template <typename Iterator>
statement<Iterator>::statement(error_handler<Iterator>& error_handler)
: statement::base_type(statement_list), expr(error_handler)
{
qi::_1_type _1;
//qi::_2_type _2;
qi::_3_type _3;
qi::_4_type _4;
qi::_val_type _val;
qi::raw_type raw;
qi::lexeme_type lexeme;
qi::alpha_type alpha;
qi::alnum_type alnum;
qi::lit_type lit;
using qi::on_error;
using qi::on_success;
using qi::fail;
using boost::phoenix::function;
typedef function<client::error_handler<Iterator> > error_handler_function;
typedef function<client::annotation<Iterator> > annotation_function;
statement_list =
+statement_
;
statement_ =
variable_declaration [print_this_declaration]
| assignment
| compound_statement
| if_statement
| while_statement
| return_statement
;
identifier =
!expr.keywords
>> raw[lexeme[(alpha | '_') >> *(alnum | '_')]]
;
variable_declaration =
lexeme["int" >> !(alnum | '_')] // make sure we have whole words
> identifier
> -('=' > expr)
> ';'
;
assignment =
identifier
> '='
> expr
> ';'
;
if_statement =
lit("if")
> '('
> expr
> ')'
> statement_
>
-(
lexeme["else" >> !(alnum | '_')] // make sure we have whole words
> statement_
)
;
while_statement =
lit("while")
> '('
> expr
> ')'
> statement_
;
compound_statement =
'{' >> -statement_list >> '}'
;
return_statement =
lexeme["return" >> !(alnum | '_')] // make sure we have whole words
> -expr
> ';'
;
// Debugging and error handling and reporting support.
BOOST_SPIRIT_DEBUG_NODES(
(statement_list)
(identifier)
(variable_declaration)
(assignment)
);
// Error handling: on error in statement_list, call error_handler.
on_error<fail>(statement_list,
error_handler_function(error_handler)(
"Error! Expecting ", _4, _3));
// Annotation: on success in variable_declaration,
// assignment and return_statement, call annotation.
on_success(variable_declaration,
annotation_function(error_handler.iters)(_val, _1));
on_success(assignment,
annotation_function(error_handler.iters)(_val, _1));
on_success(return_statement,
annotation_function(error_handler.iters)(_val, _1));
}
}}
Raw
vm.cpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#include "vm.hpp"
#if defined(_MSC_VER)
# pragma warning(disable: 4800) // forcing value to bool 'true' or 'false'
// (performance warning)
#endif
namespace client
{
int vmachine::execute(
std::vector<int> const& code
, std::vector<int>::const_iterator pc
, std::vector<int>::iterator frame_ptr
)
{
std::vector<int>::iterator stack_ptr = frame_ptr;
while (true)
{
switch (*pc++)
{
case op_neg:
stack_ptr[-1] = -stack_ptr[-1];
break;
case op_not:
stack_ptr[-1] = !bool(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_eq:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1] == stack_ptr[0]);
break;
case op_neq:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1] != stack_ptr[0]);
break;
case op_lt:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1] < stack_ptr[0]);
break;
case op_lte:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1] <= stack_ptr[0]);
break;
case op_gt:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1] > stack_ptr[0]);
break;
case op_gte:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1] >= stack_ptr[0]);
break;
case op_and:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1]) && bool(stack_ptr[0]);
break;
case op_or:
--stack_ptr;
stack_ptr[-1] = bool(stack_ptr[-1]) || bool(stack_ptr[0]);
break;
case op_load:
*stack_ptr++ = frame_ptr[*pc++];
break;
case op_store:
--stack_ptr;
frame_ptr[*pc++] = stack_ptr[0];
break;
case op_int:
*stack_ptr++ = *pc++;
break;
case op_true:
*stack_ptr++ = true;
break;
case op_false:
*stack_ptr++ = false;
break;
case op_jump:
pc += *pc;
break;
case op_jump_if:
if (!bool(stack_ptr[-1]))
pc += *pc;
else
++pc;
--stack_ptr;
break;
case op_stk_adj:
stack_ptr += *pc++;
break;
case op_call:
{
int nargs = *pc++;
int jump = *pc++;
// a function call is a recursive call to execute
int r = execute(
code
, code.begin() + jump
, stack_ptr - nargs
);
// cleanup after return from function
stack_ptr[-nargs] = r; // get return value
stack_ptr -= (nargs - 1); // the stack will now contain
// the return value
}
break;
case op_return:
return stack_ptr[-1];
}
}
}
}
Raw
vm.hpp
/*=============================================================================
Copyright (c) 2001-2011 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)
=============================================================================*/
#if !defined(BOOST_SPIRIT_MINIC_VM_HPP)
#define BOOST_SPIRIT_MINIC_VM_HPP
#include <vector>
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_not, // boolean negate the top stack entry
op_eq, // compare the top two stack entries for ==
op_neq, // compare the top two stack entries for !=
op_lt, // compare the top two stack entries for <
op_lte, // compare the top two stack entries for <=
op_gt, // compare the top two stack entries for >
op_gte, // compare the top two stack entries for >=
op_and, // logical and top two stack entries
op_or, // logical or top two stack entries
op_load, // load a variable
op_store, // store a variable
op_int, // push constant integer into the stack
op_true, // push constant 0 into the stack
op_false, // push constant 1 into the stack
op_jump_if, // jump to a relative position in the code if top stack
// evaluates to false
op_jump, // jump to a relative position in the code
op_stk_adj, // adjust the stack (for args and locals)
op_call, // function call
op_return // return from function
};
class vmachine
{
public:
vmachine(unsigned stackSize = 4096)
: stack(stackSize)
{
}
int execute(std::vector<int> const& code)
{
return execute(code, code.begin(), stack.begin());
}
std::vector<int> const& get_stack() const { return stack; };
std::vector<int>& get_stack() { return stack; };
private:
int execute(
std::vector<int> const& code // the program code
, std::vector<int>::const_iterator pc // program counter
, std::vector<int>::iterator frame_ptr // start of arguments and locals
);
std::vector<int> stack;
};
}
#endif
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment