2015-08-21
677
Стековая машина определяется следующими структурами данных:
Integer D[0..2n1] память данных, стек
Integer C[0..2n2] память команд
Integer p_D номер последней занятой ячейки в D, указатель стека
Integer p_C номер текущей просматриваемой ячейки в С, счетчик команд
Boolean ERROR индикатор ошибки
Массив D может содержать произвольные целые числа из диапазона [-9999 9999]. В элементах массива C могут находиться либо числа из диапазона [–10013 –10000], представляющие код одной из принимаемых стековой машиной команд, либо числа из диапазона [-9999 9999], представляющие аргументы следующих далеее команд. Приняты следующие правила кодирования команд:
Таблица 1
| Числовой код команды | Мнемоническое обозначение |
| -10000 | Add |
| -10001 | Mult |
| -10002 | Minus |
| -10003 | Div |
| -10004 | If= |
| -10005 | If< |
| -10006 | Goto |
| -10007 | Load |
| -10008 | Free |
| -10009 | Store |
| -10010 | Count |
| -10011 | |
| -10012 | Read |
| -10013 | Stop |
Для каждой из принимаемых стековой машиной команд определено ее назначение в соответствии со следующими правилами:
Таблица 2
| Мнемоническое обозначение | Выполняемые действия | Возможная реализация команды на псевдокоде |
| Add | Взять с вершины стека два элемента, поместить на вершину стека сумму этих элементов | p_D=p_D-1; D[p_D]=D[p_D]+D[p_D+1]; p_C=p_C+1; |
| Mult | Взять с вершины стека два элемента, поместить поместить на вершину стека произведение этих элементов | p_D=p_D-1; D[p_D]=D[p_D]*D[p_D+1]; p_C=p_C+1 |
| Minus | Взять с вершины стека один элемент, поместить на вершину стека отрицание числа | D[p_D]=-D[p_D]; p_C=p_C+1 |
| Div | Взять с вершины стека два элемента, поместить на вершину стека результат целочисленного деления первого элемента на второй | p_D=p_D-1; D[p_D]=D[p_D]/D[p_D+1]; p_C=p_C+1 |
| If= | Взять с вершины стека три элемента Если первые два снятых элемента стека(вершина стека и элемент под ней) равны, то счетчик команд сделать равным третьему снятому элементу | IF D[p_D]=D[p_D-1] THEN p_C=D[p_D-2] ELSE p_C=p_C+1 FI p_D=p_D-3; |
| If< | Взять с вершины стека три элемента Если первый снятый элемент стека (вершина стека) меньше второго, то счетчик команд сделать равным третьему снятому элементу | IF D[p_D]<D[p_D-1] THEN p_C=D[p_D-2] ELSE p_C=p_C+1 FI p_D=p_D-3; |
| Goto | Взять с вершины стека один элемент и присвоить его значение счетчику команд | p_C=D[p_D]; p_D=p_D-1 |
| Load | Взять с вершины стека один элемент и поместить на вершину стека значение элемента стека, индексированного значением снятого элемента | D[p_D]=D[D[p_D]]; p_C=p_C+1 |
| Free | Удалить с вершины стека один элемент | p_D=p_D-1; p_C=p_C+1 |
| Store | Взять с вершины стека один элемент и используя его значение как индекс элемента в стеке, поместить значение следующего элемента стека в индексируемый элемент | D[D[p_D]]=D[p_D-1]; p_D=p_D-1; p_C=p_C-1 |
| Count | Поместить на вершину стека количество элементов в нем | p_D=p_D+1; D[p_D]=p_D; p_C=p_C+1 |
| Вывести на устройство вывода значение элемента на вершине стека. Содержимое стека не изменяется. | PRINT(D[p_D]); p_C=p_C+1 | |
| Read | Прочитать целое число с устройства ввода, поместить его на вершину стека | p_D=p_D+1; READ(D[p_D]); P_C=p_C+1 |
| Stop | Остановить работу машины |
В том случае, когда счетчик команд указывает на элемент, содержащий аргумент команды (число из диапазона [-9999 9999]), выполняется его загрузка в стек данных и перемещение счетчика команд на следующий элемент:
|
|
|
|
|
|
p_D=p_D+1;D[p_D]=C[p_C];p_C=p_C+1
