Skip to content

Instantly share code, notes, and snippets.

@cwvh
Created Jan 5, 2014
Embed
What would you like to do?
#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
#include <boost/spirit/include/qi.hpp>
namespace ast
{
struct Left
{
typedef size_t value_type;
int end() { return 0; }
void insert(int, char) { count++; }
Left() : count{0} {}
size_t count;
};
std::ostream& operator<<(std::ostream& os, const Left& rhs)
{
os << "Left[" << rhs.count << ']';
return os;
}
struct Right
{
typedef size_t value_type;
int end() { return 0; }
void insert(int, char) { count++; }
Right() : count{0} {}
size_t count;
};
std::ostream& operator<<(std::ostream& os, const Right& rhs)
{
os << "Right[" << rhs.count << ']';
return os;
}
struct Incr
{
typedef size_t value_type;
int end() { return 0; }
void insert(int, char c) { if (c == '+') count++; }
Incr() : count{0} {}
size_t count;
};
std::ostream& operator<<(std::ostream& os, const Incr& rhs)
{
os << "Incr[" << rhs.count << ']';
return os;
}
struct Decr
{
typedef size_t value_type;
int end() { return 0; }
void insert(int, char c) { if (c == '-') count++; }
Decr() : count{0} {}
size_t count;
};
std::ostream& operator<<(std::ostream& os, const Decr& rhs)
{
os << "Decr[" << rhs.count << ']';
return os;
}
struct Output
{
Output() {}
Output(char) {}
};
std::ostream& operator<<(std::ostream& os, const Output& rhs)
{
os << "Output";
return os;
}
struct Input
{
Input() {}
Input(char) {}
};
std::ostream& operator<<(std::ostream& os, const Input& rhs)
{
os << "Input";
return os;
}
typedef boost::variant<Left, Right, Incr, Decr, Output, Input> Primitive;
struct Loop;
typedef boost::variant<Primitive, Loop> Command;
typedef std::vector<Command> Commands;
typedef boost::shared_ptr<Commands> Commands_ptr;
struct Loop
{
typedef std::vector<Command> value_type;
void insert(Commands::iterator i, const Commands& cmds)
{
commands->insert(i, cmds.begin(), cmds.end());
}
Commands::iterator end()
{
return commands->end();
}
Commands::const_iterator end() const
{
return commands->end();
}
Loop() : commands{new Commands} {}
Commands_ptr commands;
};
std::ostream& operator<<(std::ostream& os, const Loop& rhs)
{
os << "Branch[";
for (auto i = rhs.commands->begin(); i != rhs.commands->end(); ++i) {
if (i != rhs.commands->begin())
os << ',';
os << *i;
}
os << ']';
return os;
}
typedef Commands Program;
std::ostream& operator<<(std::ostream& os, const Program& rhs)
{
os << "Program[";
for (auto i = rhs.begin(); i != rhs.end(); ++i) {
if (i != rhs.begin())
os << ',';
os << *i;
}
os << ']';
return os;
}
} // namespace ast;
namespace parser
{
namespace sp = boost::spirit;
namespace qi = boost::spirit::qi;
template<typename Iterator>
struct skipper : qi::grammar<Iterator>
{
skipper() : skipper::base_type{start}
{
using sp::ascii::char_;
using sp::no_skip;
using sp::lexeme;
start = char_ - char_("<>+-.,[]");
;
}
qi::rule<Iterator> start;
};
template<typename Iterator>
struct parser : qi::grammar<Iterator, ast::Program(), skipper<Iterator>>
{
parser() : parser::base_type{program}
{
using sp::ascii::char_;
program = +command >> sp::eoi
;
loop = '[' >> *command >> ']'
;
command = loop | primitive
;
primitive =
left
| right
| incr
| decr
| output
| input
;
left = +char_('<')
;
right = +char_('>')
;
incr = +char_('+')
;
decr = +char_('-')
;
output = char_('.')
;
input = char_(',')
;
}
bool parse(Iterator first, Iterator last, ast::Program& prog)
{
return qi::phrase_parse(first, last, *this,
skipper<Iterator>(), prog);
}
qi::rule<Iterator, ast::Program(), skipper<Iterator>> program;
qi::rule<Iterator, ast::Command(), skipper<Iterator>> command;
qi::rule<Iterator, ast::Loop(), skipper<Iterator>> loop;
qi::rule<Iterator, ast::Primitive(), skipper<Iterator>> primitive;
qi::rule<Iterator, ast::Left(), skipper<Iterator>> left;
qi::rule<Iterator, ast::Right(), skipper<Iterator>> right;
qi::rule<Iterator, ast::Incr(), skipper<Iterator>> incr;
qi::rule<Iterator, ast::Decr(), skipper<Iterator>> decr;
qi::rule<Iterator, ast::Output(), skipper<Iterator>> output;
qi::rule<Iterator, ast::Input(), skipper<Iterator>> input;
}; // parser
template<typename Iterator>
bool parse(Iterator first, Iterator last, ast::Program& prog)
{
parser<Iterator> parser;
return parser.parse(first, last, prog);
}
} // namespace parser
namespace codegen
{
struct interp_visitor : public boost::static_visitor<void>
{
int tape[30000] = {0};
int sp = 0;
template<typename T>
void operator()(const T& rhs)
{
interp(rhs);
}
void interp(const ast::Command& rhs)
{
boost::apply_visitor(*this, rhs);
}
void interp(const ast::Commands& rhs)
{
for (auto& cmd : rhs)
interp(cmd);
}
void interp(const ast::Primitive& rhs)
{
boost::apply_visitor(*this, rhs);
}
void interp(const ast::Loop& rhs)
{
while (tape[sp] != 0)
for (auto& cmd : *rhs.commands)
interp(cmd);
}
void interp(const ast::Left& rhs)
{
sp -= rhs.count;
}
void interp(const ast::Right& rhs)
{
sp += rhs.count;
}
void interp(const ast::Incr& rhs)
{
tape[sp] += rhs.count;
}
void interp(const ast::Decr& rhs)
{
tape[sp] -= rhs.count;
}
void interp(const ast::Output& rhs)
{
fputc(tape[sp], stdout);
}
void interp(const ast::Input& rhs)
{
tape[sp] = fgetc(stdin);
}
};
} // namespace codegen
void eval(ast::Program& program)
{
codegen::interp_visitor eval;
eval(program);
}
int main(int argc, char** argv)
{
std::string s{std::istreambuf_iterator<char>(std::cin),
std::istreambuf_iterator<char>()};
ast::Program program;
bool r = parser::parse(s.begin(), s.end(), program);
if (!r) {
std::cerr << "syntax error" << std::endl;
exit(1);
}
//std::cout << program << std::endl;
eval(program);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment