y.cpp

#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);
}