/*
* File: main.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 15:21
*/
#include <iostream>
#include <valarray>
#include <string>
#include <locale>
#include "Machine.h"
/*
*
*/
// Печатает состояние машины на каждом шаге
void printState(const State& state);
int main(int argc, char** argv)
{
// Программа взятая с википедии для вычитания двух чисел
std::string prg_str[] = {
"1 x",
"2 >",
"3 ? 4,5",
"4 !",
"5 <",
"6 ? 5,7",
"7 x",
"8 >",
"9 ? 8,1"
};
std::valarray<std::string> prg(prg_str,sizeof(prg_str)/sizeof(prg_str[0]));
try
{
std::locale::global(std::locale(""));
// Создание машины и запуск
Machine(prg, "00111110111000", 8).Run(printState);
}
catch (std::exception& ex)
{
std::cout << ex.what() << std::endl;
}
system("pause");
return 0;
}
void printState(const State& state)
{
std::cout << state << std::endl;
}
/*
* File: SyntaxMachineException.h
* Author:
*
* Created on 12 Июнь 2013 г., 7:50
*/
#ifndef SYNTAXMACHINEEXCEPTION_H
#define SYNTAXMACHINEEXCEPTION_H
#include "MachineException.h"
// Исключение при синтаксической ошибке программы
class SyntaxMachineException : public MachineException {
public:
SyntaxMachineException(const std::string& msg);
virtual ~SyntaxMachineException() throw();
private:
};
#endif /* SYNTAXMACHINEEXCEPTION_H */
/*
* File: SyntaxMachineException.cpp
* Author:
*
* Created on 12 Июнь 2013 г., 7:50
*/
#include "SyntaxMachineException.h"
SyntaxMachineException::SyntaxMachineException(const std::string& msg)
: MachineException(msg)
{
}
SyntaxMachineException::~SyntaxMachineException() throw()
{
}
/*
* File: StopMachine.h
* Author:
*
* Created on 11 Июнь 2013 г., 23:39
*/
#ifndef STOPMACHINE_H
#define STOPMACHINE_H
#include "MachineException.h"
// Исключение при нормальном завершении программы
class StopMachineException : public MachineException {
public:
StopMachineException();
virtual ~StopMachineException() throw();
private:
};
#endif /* STOPMACHINE_H */
/*
* File: StopMachine.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 23:39
*/
#include "StopMachineException.h"
StopMachineException::StopMachineException()
: MachineException("Останов программы")
{
}
StopMachineException::~StopMachineException() throw()
{
}
/*
* File: ExitCommand.h
* Author:
*
* Created on 11 Июнь 2013 г., 23:20
*/
#ifndef EXITCOMMAND_H
#define EXITCOMMAND_H
#include "Command.h"
// Комманда останов программы
class StopCommand : public Command {
public:
StopCommand(size_t line);
virtual ~StopCommand();
virtual void execute(State& state) const;
virtual std::string toString() const;
private:
};
#endif /* EXITCOMMAND_H */
/*
* File: ExitCommand.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 23:20
*/
#include <sstream>
#include "StopCommand.h"
#include "StopMachineException.h"
StopCommand::StopCommand(size_t cur)
: Command(cur, STOP)
{
}
StopCommand::~StopCommand()
{
}
void StopCommand::execute(State& state) const
{
state.last = state.line;
throw StopMachineException();
}
std::string StopCommand::toString() const
{
std::stringstream sstr;
sstr << _line << ' ' << static_cast<char> (_op);
return sstr.str();
}
/*
* File: State.h
* Author:
*
* Created on 12 Июнь 2013 г., 0:09
*/
#ifndef STATE_H
#define STATE_H
#include <cstddef>
#include <deque>
#include <string>
#include <iostream>
#include "MachineException.h"
typedef std::deque<bool> tape_t;
class Program;
// Состояние машины
struct State {
State(tape_t::size_type pos, const tape_t& data, size_t line, Program* program = 0);
// Можно задать данные ввиде строки, состоящей из '0' и '1'
State(tape_t::size_type pos, const std::string& data, size_t line, Program* program = 0);
// "Бесконечная" лента
tape_t tape;
// Позиция указателя
tape_t::size_type pos;
// Текущая инструкция и предыдущая
size_t line, last;
// Номер шага
size_t step;
// Указатель на программу, если нужна
Program * program;
};
std::ostream& operator<<(std::ostream& out, const State& state);
#endif /* STATE_H */
#include "State.h"
#include "Program.h"
State::State(tape_t::size_type pos, const tape_t& data, size_t line, Program* program)
: pos(pos)
, tape(data)
, line(line)
, last(0)
, step(0)
, program(program)
{
};
State::State(tape_t::size_type pos, const std::string& data, size_t line, Program* program)
: pos(pos)
, line(line)
, last(0)
, step(0)
, program(program)
{
for (std::string::size_type i = 0, end = data.length(); i < end; ++i)
{
switch (data[i])
{
case '0':
tape.push_back(false);
break;
case '1':
tape.push_back(true);
break;
default:
throw MachineException("Входные данные должны состоять из нулей и единиц");
}
}
}
std::ostream& operator<<(std::ostream& out, const State& state)
{
out << "Шаг: " << state.step << std::endl;
out << std::string(state.pos, ' ') << 'V' << std::endl;
for (tape_t::size_type i = 0, end = state.tape.size(); i < end; ++i)
{
out << state.tape[i];
}
if (state.program)
{
out << " | " << (*state.program)[state.line]->toString() << std::endl;
}
return out;
}
/*
* File: MoveCommand.h
* Author:
*
* Created on 11 Июнь 2013 г., 22:55
*/
#ifndef MOVECOMMAND_H
#define MOVECOMMAND_H
#include "Command.h"
// Комманды типа a op b
class SimpleCommand : public Command {
public:
SimpleCommand(size_t line, commands op, size_t to);
virtual ~SimpleCommand();
virtual void execute(State& state) const;
virtual std::string toString() const;
// Инструкция, на которую переходит выполнение после комманды
size_t to() const;
protected:
size_t _to;
};
#endif /* MOVECOMMAND_H */
/*
* File: MoveCommand.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 22:55
*/
#include <sstream>
#include "SimpleCommand.h"
SimpleCommand::SimpleCommand(size_t cur, commands op, size_t to)
: Command(cur, op)
, _to(to)
{
}
SimpleCommand::~SimpleCommand()
{
}
size_t SimpleCommand::to() const
{
return _to;
}
void SimpleCommand::execute(State& state) const
{
state.last = state.line;
state.line = this->_to;
}
std::string SimpleCommand::toString() const
{
std::stringstream sstr;
sstr << _line << ' ' << static_cast<char> (_op) << ' ' << _to;
return sstr.str();
}
/*
* File: SetCommand.h
* Author:
*
* Created on 11 Июнь 2013 г., 23:09
*/
#ifndef SETCOMMAND_H
#define SETCOMMAND_H
#include "SimpleCommand.h"
// Комманда установки метки
class SetCommand : public SimpleCommand {
public:
SetCommand(size_t line, size_t to);
virtual ~SetCommand();
virtual void execute(State& state) const;
private:
};
#endif /* SETCOMMAND_H */
/*
* File: SetCommand.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 23:09
*/
#include "SetCommand.h"
#include "RuntimeMachineException.h"
SetCommand::SetCommand(size_t cur, size_t to)
: SimpleCommand(cur, SET, to)
{
}
SetCommand::~SetCommand()
{
}
void SetCommand::execute(State& state) const
{
if (state.tape[state.pos])
{
throw RuntimeMachineException("Нельзя записать в помеченное поле", state);
}
state.tape[state.pos] = true;
SimpleCommand::execute(state);
}
/*
* File: RuntimeMachineException.h
* Author:
*
* Created on 12 Июнь 2013 г., 7:50
*/
#ifndef RUNTIMEMACHINEEXCEPTION_H
#define RUNTIMEMACHINEEXCEPTION_H
#include "MachineException.h"
#include "State.h"
// Исключение времени выполнения для машины
class RuntimeMachineException : public MachineException {
public:
RuntimeMachineException(const std::string& msg, const State& state);
virtual ~RuntimeMachineException() throw();
// Возвращает состояние машины
State state() const;
private:
State _state;
};
#endif /* RUNTIMEMACHINEEXCEPTION_H */
/*
* File: RuntimeMachineException.cpp
* Author:
*
* Created on 12 Июнь 2013 г., 7:50
*/
#include "RuntimeMachineException.h"
RuntimeMachineException::RuntimeMachineException(const std::string& msg, const State& state)
: MachineException(msg)
, _state(state)
{
}
RuntimeMachineException::~RuntimeMachineException() throw()
{
}
State RuntimeMachineException::state() const
{
return _state;
}
/*
* File: program.h
* Author:
*
* Created on 11 Июнь 2013 г., 16:39
*/
#ifndef PROGRAM_H
#define PROGRAM_H
#include <valarray>
#include <memory>
#include "Command.h"
// Программа. Содержит список инструкций. Где каждая комманда представлена своим класом
class Program {
public:
// Конструктор. принимает массив строк программы
Program(const std::valarray<std::string>& prog);
virtual ~Program();
// Возвращает указатель на комманду по номеру строки
const Command* operator [](size_t line) const;
private:
Program(const Program& orig);
Command* createCommand(const std::string& cmd) const;
template<class T> T convert(const std::string& str) const;
std::valarray<std::shared_ptr<Command > > _commands;
};
#endif /* PROGRAM_H */
/*
* File: program.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 16:39
*/
#include <sstream>
#include <typeinfo>
#include <regex>
#include "MachineException.h"
#include "SyntaxMachineException.h"
#include "MoveLeftCommand.h"
#include "MoveRightCommand.h"
#include "IfCommand.h"
#include "SetCommand.h"
#include "ClearCommand.h"
#include "StopCommand.h"
#include "Program.h"
Program::Program(const std::valarray<std::string>& prog_str)
: _commands(prog_str.size())
{
for (size_t i = 0, end = prog_str.size(); i < end; ++i)
{
auto ptr = std::shared_ptr<Command>(createCommand(prog_str[i]));
if (ptr->line() != i + 1)
{
throw SyntaxMachineException(std::string("Неверный номер строки программы(нумерация не по порядку): ") + prog_str[i]);
}
_commands[i] = ptr;
}
}
Program::~Program()
{
}
const Command* Program::operator [](size_t line) const
{
if (line < 1 || line > _commands.size())
{
std::stringstream sstr;
sstr<<line;
throw MachineException(std::string("Неверный номер строки: ") + sstr.str());
}
return _commands[line - 1].get();
}
Command* Program::createCommand(const std::string& cmd) const
{
// Регулярные выражения для проверки синтаксиса
static const std::regex simpleCommand("^\\s*(\\d{1,5})\\s*([VvXx<>])\\s*(\\d{1,5}){0,1}\\s*$");
static const std::regex ifCommand("^\\s*(\\d{1,5})\\s+(\\?)\\s+(\\d{1,5})\\s*,\\s*(\\d{1,5})\\s*$");
static const std::regex stopCommand("^\\s*(\\d{1,5})\\s*!\\s*$");
std::smatch m;
if (std::regex_match(cmd, m, simpleCommand))
{
std::string currentStr = m[1],
commandStr = m[2],
toStr = m[3];
unsigned int current = convert<unsigned int>(currentStr),
to = toStr.empty()?current+1:convert<unsigned int>(toStr);
switch (commandStr[0])
{
case 'V':
case 'v':
return new SetCommand(current, to);
case 'X':
case 'x':
return new ClearCommand(current, to);
case '<':
return new MoveLeftCommand(current, to);
case '>':
return new MoveRightCommand(current, to);
break;
}
}
else if (std::regex_match(cmd, m, ifCommand))
{
std::string currentStr = m[1],
commandStr = m[2],
falseNoStr = m[3],
trueNoStr = m[4];
size_t current = convert<size_t>(currentStr),
falseLine = convert<size_t>(falseNoStr),
trueLine = convert<size_t>(trueNoStr);
return new IfCommand(current, falseLine, trueLine);
}
else if (std::regex_match(cmd, m, stopCommand))
{
std::string currentStr = m[1];
size_t current = convert<size_t>(currentStr);
return new StopCommand(current);
}
else
{
throw SyntaxMachineException(std::string("Неверная комманда: '") + cmd + "'");
}
return 0;
}
template<class T> T Program::convert(const std::string& str) const
{
std::istringstream sstr(str);
T result;
sstr >> result;
if (sstr.fail())
{
throw MachineException(std::string("Ошибка конвертации('") + str + "' в " + typeid (T).name() + ")");
}
return result;
}
/*
* File: MoveRightCommand.h
* Author:
*
* Created on 11 Июнь 2013 г., 23:05
*/
#ifndef MOVERIGHTCOMMAND_H
#define MOVERIGHTCOMMAND_H
#include "SimpleCommand.h"
// Класс-комманда сдвига вправо
class MoveRightCommand : public SimpleCommand {
public:
MoveRightCommand(size_t line, size_t to);
virtual ~MoveRightCommand();
virtual void execute(State& state) const;
private:
};
#endif /* MOVERIGHTCOMMAND_H */
/*
* File: MoveRightCommand.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 23:05
*/
#include "MoveRightCommand.h"
MoveRightCommand::MoveRightCommand(size_t cur, size_t to)
: SimpleCommand(cur, RIGHT, to)
{
}
MoveRightCommand::~MoveRightCommand()
{
}
void MoveRightCommand::execute(State& state) const
{
if (++state.pos == state.tape.size())
{
state.tape.push_back(false);
}
SimpleCommand::execute(state);
}
/*
* File: MoveLeftCommand.h
* Author:
*
* Created on 11 Июнь 2013 г., 22:15
*/
#ifndef MOVELEFTCOMMAND_H
#define MOVELEFTCOMMAND_H
#include "SimpleCommand.h"
// Класс-комманда сдвига влево
class MoveLeftCommand : public SimpleCommand {
public:
MoveLeftCommand(size_t line, size_t to);
virtual ~MoveLeftCommand();
virtual void execute(State& state) const;
private:
};
#endif /* MOVELEFTCOMMAND_H */
/*
* File: MoveLeftCommand.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 22:15
*/
#include "MoveLeftCommand.h"
#include "RuntimeMachineException.h"
MoveLeftCommand::MoveLeftCommand(size_t cur, size_t to)
: SimpleCommand(cur, LEFT, to)
{
}
MoveLeftCommand::~MoveLeftCommand()
{
}
void MoveLeftCommand::execute(State& state) const
{
if (!state.pos)
{
state.tape.push_front(false);
}
else
{
--state.pos;
}
SimpleCommand::execute(state);
}
/*
* File: machine_error.h
* Author:
*
* Created on 11 Июнь 2013 г., 15:28
*/
#ifndef MACHINE_ERROR_H
#define MACHINE_ERROR_H
#include <exception>
#include <string>
// Базовый класс-исключение для работы машины
class MachineException : public std::exception {
public:
MachineException(const std::string& msg);
virtual ~MachineException() throw();
virtual const char* what() const throw();
private:
std::string message;
};
#endif /* MACHINE_ERROR_H */
/*
* File: machine_error.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 15:28
*/
#include "MachineException.h"
MachineException::MachineException(const std::string& msg)
:message(msg)
{
}
MachineException::~MachineException() throw()
{
}
const char* MachineException::what() const throw()
{
return message.c_str();
}
/*
* File: machine.h
* Author:
*
* Created on 11 Июнь 2013 г., 16:11
*/
#ifndef MACHINE_H
#define MACHINE_H
#include <valarray>
#include <string>
#include "State.h"
#include "Program.h"
// Машина
class Machine {
public:
// Тип для функции обратного вызова
typedef void (*callback)(const State& state);
Machine(const std::valarray<std::string>& program, const std::string& data, std::string::size_type pos);
virtual ~Machine();
// Запускает машину на выполнение. Если в качестве аргумента передана функция то вызывает ее на каждом шаге
State Run(callback func = 0);
private:
// Состояние машины
State _state;
// Программа
Program _program;
};
#endif /* MACHINE_H */
/*
* File: machine.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 16:11
*/
#include "StopMachineException.h"
#include "RuntimeMachineException.h"
#include "Machine.h"
Machine::Machine(const std::valarray<std::string>& program, const std::string& data, std::string::size_type pos)
: _program(program)
, _state(pos, data, 1, &_program)
{
}
Machine::~Machine()
{
}
State Machine::Run(callback func)
{
try
{
if (func)
{
func(_state);
}
// Цикл выполнения. Выход по исключению
while (true)
{
_program[_state.line]->execute(_state);
++_state.step;
if (func)
{
func(_state);
}
}
}
catch (StopMachineException&)
{
// В случае нормального завершения программы
}
catch (MachineException& ex)
{
throw RuntimeMachineException(ex.what(), _state);
}
catch (...)
{
throw;
}
return _state;
}
/*
* File: IfCommand.h
* Author:
*
* Created on 11 Июнь 2013 г., 23:16
*/
#ifndef IFCOMMAND_H
#define IFCOMMAND_H
#include "Command.h"
// Класс-комманда условного перехода
class IfCommand : public Command {
public:
IfCommand(size_t cur, size_t falseLine, size_t trueLine);
virtual ~IfCommand();
// Строка перехода если нет метки
size_t falseLine() const;
// Строка перехода если есть метка
size_t trueLine() const;
virtual void execute(State& state) const;
virtual std::string toString() const;
private:
size_t _falseLine, _trueLine;
};
#endif /* IFCOMMAND_H */
/*
* File: IfCommand.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 23:16
*/
#include <sstream>
#include "IfCommand.h"
IfCommand::IfCommand(size_t cur, size_t falseLine, size_t trueLine)
: Command(cur, IF)
, _falseLine(falseLine)
, _trueLine(trueLine)
{
}
IfCommand::~IfCommand()
{
}
void IfCommand::execute(State& state) const
{
state.last = state.line;
if (state.tape[state.pos])
{
state.line = _trueLine;
}
else
{
state.line = _falseLine;
}
}
std::string IfCommand::toString() const
{
std::stringstream sstr;
sstr << _line << ' ' << static_cast<char> (_op) << ' ' << _falseLine << ',' << _trueLine;
return sstr.str();
}
/*
* File: command.h
* Author:
*
* Created on 11 Июнь 2013 г., 15:24
*/
#ifndef COMMAND_H
#define COMMAND_H
#include "State.h"
// Базовый абстрактный класс для комманд
class Command {
public:
// Типы комманд
enum commands {
STOP = '!',
SET = 'V',
CLEAR = 'X',
LEFT = '<',
RIGHT = '>',
IF = '?'
};
Command(size_t line, commands op);
virtual ~Command();
// Выполняет комманду
virtual void execute(State& state) const = 0;
// Строковое представление комманды
virtual std::string toString() const = 0;
// Номер строки
size_t line() const;
// Комманда
commands command() const;
protected:
size_t _line;
commands _op;
};
#endif /* COMMAND_H */
/*
* File: command.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 15:24
*/
#include <iostream>
#include "Command.h"
Command::Command(size_t line, commands op)
: _line(line)
, _op(op)
{
}
Command::~Command()
{
}
size_t Command::line() const
{
return _line;
}
Command::commands Command::command() const
{
return _op;
}
/*
* File: ClearCommand.h
* Author:
*
* Created on 11 Июнь 2013 г., 23:13
*/
#ifndef CLEARCOMMAND_H
#define CLEARCOMMAND_H
#include "SimpleCommand.h"
// Класс-комманда для останова машины
class ClearCommand : public SimpleCommand {
public:
ClearCommand(size_t line, size_t to);
virtual ~ClearCommand();
virtual void execute(State& state) const;
private:
};
#endif /* CLEARCOMMAND_H */
/*
* File: ClearCommand.cpp
* Author:
*
* Created on 11 Июнь 2013 г., 23:13
*/
#include "ClearCommand.h"
#include "RuntimeMachineException.h"
ClearCommand::ClearCommand(size_t cur, size_t to)
: SimpleCommand(cur, CLEAR, to)
{
}
ClearCommand::~ClearCommand()
{
}
void ClearCommand::execute(State& state) const
{
if (!state.tape[state.pos])
{
throw RuntimeMachineException("Нельзя стереть пустое поле", state);
}
state.tape[state.pos] = false;
SimpleCommand::execute(state);
}
Шаг: 0
V
00111110111000 | 1 X 2
Шаг: 1
V
00111110011000 | 2 > 3
Шаг: 2
V
00111110011000 | 3 ? 4,5
Шаг: 3
V
00111110011000 | 5 < 6
Шаг: 4
V
00111110011000 | 6 ? 5,7
Шаг: 5
V
00111110011000 | 5 < 6
Шаг: 6
V
00111110011000 | 6 ? 5,7
Шаг: 7
V
00111110011000 | 5 < 6
Шаг: 8
V
00111110011000 | 6 ? 5,7
Шаг: 9
V
00111110011000 | 7 X 8
Шаг: 10
V
00111100011000 | 8 > 9
Шаг: 11
V
00111100011000 | 9 ? 8,1
Шаг: 12
V
00111100011000 | 8 > 9
Шаг: 13
V
00111100011000 | 9 ? 8,1
Шаг: 14
V
00111100011000 | 8 > 9
Шаг: 15
V
00111100011000 | 9 ? 8,1
Шаг: 16
V
00111100011000 | 1 X 2
Шаг: 17
V
00111100001000 | 2 > 3
Шаг: 18
V
00111100001000 | 3 ? 4,5
Шаг: 19
V
00111100001000 | 5 < 6
Шаг: 20
V
00111100001000 | 6 ? 5,7
Шаг: 21
V
00111100001000 | 5 < 6
Шаг: 22
V
00111100001000 | 6 ? 5,7
Шаг: 23
V
00111100001000 | 5 < 6
Шаг: 24
V
00111100001000 | 6 ? 5,7
Шаг: 25
V
00111100001000 | 5 < 6
Шаг: 26
V
00111100001000 | 6 ? 5,7
Шаг: 27
V
00111100001000 | 5 < 6
Шаг: 28
V
00111100001000 | 6 ? 5,7
Шаг: 29
V
00111100001000 | 7 X 8
Шаг: 30
V
00111000001000 | 8 > 9
Шаг: 31
V
00111000001000 | 9 ? 8,1
Шаг: 32
V
00111000001000 | 8 > 9
Шаг: 33
V
00111000001000 | 9 ? 8,1
Шаг: 34
V
00111000001000 | 8 > 9
Шаг: 35
V
00111000001000 | 9 ? 8,1
Шаг: 36
V
00111000001000 | 8 > 9
Шаг: 37
V
00111000001000 | 9 ? 8,1
Шаг: 38
V
00111000001000 | 8 > 9
Шаг: 39
V
00111000001000 | 9 ? 8,1
Шаг: 40
V
00111000001000 | 1 X 2
Шаг: 41
V
00111000000000 | 2 > 3
Шаг: 42
V
00111000000000 | 3 ? 4,5
Шаг: 43
V
00111000000000 | 4 !
Если Вы уже зарегистрированы на Портале - войдите в систему, если Вы еще не регистрировались - пройдите простую процедуру регистрации.