Вторая, по существу, представляет собой обычный бесконечный цикл:

10 asgn С С + 1 goto 15

15 asgn С С - 1 goto 20

20 if 10 = 10 goto 10 else 30

30 end

При возникновении любой нештатной ситуации (переполнение, сиетакси-ческая ошибка, переход по недопустимому номеру строки) работа программы немедленно завершается.

Итак, для любой заданной программы на языке Tiny Power требуется определить, завершит ли она когда-нибудь свою работу или будет крутиться в бесконечном цикле.

Подсказка

Обратите внимание, что запись, содержащая текущие значения всех переменных программы и номер выполняемой строки, однозначно описывает состояние программы в данный момент времени. Если при выполнении алгоритма некоторое состояние возникает во второй раз, это означает бесконечный цикл.

Решение

Решение состоит из двух логически не связанных между собою шагов: вспомогательного - реализации интерпретатора языка Tiny Power - и собственно решения задачи останова.

Начнём с интерпретатора Tiny Power.

В большинстве программ на языке TinyPower используются переменные. Их удобно хранить в ассоциативном массиве, сопоставляющем символическому имени переменной её значение:

map<string, int> Variables;

Почти столь же фундаментальной для интерпретатора является функция ReadValue (), возвращающая числовое значение переменной или записанной в виде строки константы:

константа нуль

int ReadValue(const strings str) (

if(str == O ) return 0;

if(atoi(str.c str()) != 0) другая числовая константа

return atoi(str.c str());

пьютерных программ решаема за конечное (хотя и, возможно, невероятно долгое) время.

Задание заключается в решении задачи останова для произвольной программы, записанной на простейшем языке программирования Tiny Power.

В языке предусмотрены лишь две алгоритмические конструкции - присваивание и ветвление:

НомерСтроки asgn X Y goto НомерЦелевойСтроки НомерСтроки asgn X Y + Z goto НомерЦелевойСтроки НомерСтроки asgn X Y - Z goto НомерЦелевойСтроки

НомерСтроки if X if-операция Y goto НомерСтроки1 else НомерСтроки2

Операция присваивания имеет три разновидности. Первая соответствует простому присваиванию вида X = Y, где X - переменная, а Y - переменная, либо число. Переменные описывать в явном виде не требуется. Любая переменная считается целой со знаком, имеющей размер 16 разрядов (диапазон допустимых значений, таким образом, равен -32768...+32767). Начальное значение переменной равно нулю.

Вторая и третья разновидности позволяют присвоить переменной X значение выражения У + Z или У - Z, где У и Z - целые числа или переменные.

После выполнения операции компьютер переходит к строке, номер которой следует за словом goto. Ниже приведены примеры присваиваний:

10 asgn X 10 goto 20 15 asgn X 5 + К goto 30 20 asgn A Z - 10 goto 5

Инструкция if переходит к строке НомерСтрокиХ либо к строке НомерСтроки2 в зависимости от результата вычисления выражения X if-операция Y.

В качестве if-оПераций допускаются операции =, <>, <, <=, > и >=. X и У - целые переменные или константы. Пример:

10 if X > 40 goto 20 else 50

Специальная инструкция end заканчивает работу программы.

В качестве примеров можно привести две программы. Первая вычисляет сумму чисел от 1 до 5 (результат записывается в переменную S):

10 asgn i i + 1 goto 20

20 asgn S S + i goto 3 0

30 if i < 5 goto 10 else 40

40 end

return Variables[str];

имя переменной

Назначение этой функции проще всего понять на примере. Рассмотрим инструкцию

10 asgn X 5 goto 20

Предположим, что синтаксический анализатор (пока ещё не написанный) разбил её на шесть подстрок - 10 , asgn , X , 5 , goto и 20 . Как мы увидим в дальнейшем, уже знания самого количества подстрок достаточно, чтобы однозначно определить тип инструкции (в данном слзае - простейший вариант присваивания).

Третья подстрока ( Х ) указывает имя переменной, которой присваивается значение, а четвёртая ( 5 ) - само значение. Но значение, в свою очередь, может представлять собой как числовую константу, так и имя персмс1шой. Функция ReadValue () умеет обрабатывать оба случая. Отдельно рассмат-риваетсг строка, содержащая число О, поскольку функция atoi () возвращает нуль при ошибке преобразования (таким образом, с помощью atoi () нельзя отличить константу О от имени переменной, но в нашей ситуации эта проблема решается легко).

Обратите внимание, что при первом вызове инструкции return Variables[str];

когда переменной str ещё не существует, в ассоциативный массив записывается (согласно определению operator [ ] () ) пара (str, int () ). В свою очередь, значение int () равно нулю.

Программа на языке TinyPower состоит из инструкций. Поэтому нам потребуется новый тип данных инструкция :

class Statement {

public:

virtual void Perform() =0; выполнить инструкцию

Текст программы - это ассоциативный массив, сопоставляющий номерам строк те или иные инструкции:

map<int, Statement*> Program;

Отдельная переменная служит для хранения номера текущей строки: int CurrentLine;

Для каждой разновидности инструкции языка потребуется собственный подкласс, переопределяющий чистую виртуальную функцию-член

PerformO:

простое присваивание asgn X Y goto TargetLine

class SimpleAsgn : public Statement

private:

string* X, Y; int TargetLine;

public:

SimpleAsgn(const strings X, const stringb Y, int targetLine) : X( X), Y( Y), TargetLine( targetLine) {}

virtual void PerformO {

int V = ReadValue(Y); определить значение Y

if(v < -32768 11 V > 32767) проверить выход за

пределы допустимого диапазона

throw overflow error( *); Variables[X] = v; выполнить присваивание

CurrentLine - TargetLine;

присваивание с операцией asgn X Y op Z goto TargetLine

class OpAsgn : public Statement

private:

string X, Y/ Z, op; int TargetLine;

public:

OpAsgn(const stringfic X, const string& Y, const string& op,

const strings Z, int targetLine) : X( X), Y( Y), Z( Z), op( op), TargetLine( targetLine) {}

virtual void PerformO (

int sign = (op == * + ? 1 : -1); знак операции ( +

и - )

int V = ReadValue(Y) + sign * ReadValue(Z); значение Y op Z проверить выход за пределы допустимого диапазона if(v < -32768 1-1 V > 32767) проверить выход за

пределы допустимого диапазона

throw overflow error() ; Variables[X] = v; выполнить присваивание

CurrentLine = TargetLine;

CurrentLine (result ? TargetLinel : TargetLine2) ;

инструкция end

class EndStatement : public Statement {

public:

EndStatement() {}

virtual void Perform() { throw exception!); } выход из

программы

Преобразованием строковой записи инструкции в объект типа Statement занимается функция ParseLine ():

void ParseLine(const strings line) {

vector<string> cur s; istringstream is(line); string templine;

while(lis.eof()) {

разбить строковую запись инструкции на разделённые пробелами подстроки

is templine;

cur s.push back(templine);

int CurLine = atoi(cur s[0).c str()); номер строки тип инструкции определяется по количеству подстрок switch(cur s.size()) {

case 2: Program[CurLine] = new EndStatement(); break;

case 6: Program[CurLine] = new SimpleAsgn(cur s[2], cur s[3],

atoi(cur s[5] .c str() )) ;

break;

case 8: Program[CurLine] - new OpAsgn(cur s[2], cur s[3J,

cur s[4], cur s[5], atoi(cur s[7].c str()));

break;

case 9: Program[CurLine] - new IfStatement(cur s[2], cur s[3], cur s[4], atoi(cur s[6].c str0), atoi(cur s[8].c str ())); break;

Выполнение программы теперь сводится к вызову в бесконечном цикле функции

Program[CurrentLine]->Perform();

Генерация исключения типа exception будет означать нормальное завершение работы (конечно, сопоставлять исключение наил)пш1ему сценарию выполнения последовательности инструкций с точки зрения стиля не очень хорошо, но в данном случае это заметно упрощает код). Вторая проблема - выход значения переменной за границы допустимого диапазона - обнаруживается с помощью исключения типа overflow error.

Теперь займёмся выявлением бесконечных циклов. Как уже было сказано, отловить бесконечный цикл можно, если запоминать все уже встречавшиеся ранее состояния выполняемой программы. Повторное возникновение любого состояния означает зависание .

Состояние программы хранится в объекте типа ProgramState:

class ProgramState {

private:

map<string, int> Vars; значения переменных int CurLine; текущая строка

public:

инициализация глобальными значени5зми Variables и CurrentLine

ветвление if X ifop Y goto TargetLinel else TargetLine2

class IfStatement : public Statement

private:

string X, Y, ifop;

int TargetLinel, TargetLine2;

public:

IfStatement(const string& X, const strings ifop, const strings Y, int tlinel, int tline2) : X( X), Y( Y), ifop( ifop), TargetLinel( tlinel),

TargetLine2( tline2) {}

virtual void Perform{) {

найти значения X и Y

int vl ReadValue(X), v2 = ReadValue(Y); результат X ifop Y

bool result - (ifop == = && vl === v2) II (ifop == <> && vl != v2) II (ifop && vl < v2) II

(ifop = <= && vl <= v2) II (ifop == > && vl > v2) I I (ifop >= && vl >= v2);