Лекция 11

Команды SPL

Программа, реализующая интерпретатор, должна осуществить перевод текста программы на языке SPL в последовательность некоторых команд, занесенных в таблицу команд TCD. Затем эта последовательность команд выполняется. Какие это промежуточные команды и сколько их - это решает программист. В рассматриваемом интерпретаторе используется 10 команд. Каждая из них представлена целым положительным числом. Для удобства все они описаны в виде перечня целых констант. Это позволяет промежуточную команду в программе-интерпретаторе описать в виде сокращенного слова на английском языке. При этом каждому такому сокращению соответствует целое число. Итак, имеется глобальное описание перечисленных констант.

enum{OPR,LIT,LDE,LDI,STE,STI,CAL,INI,JMC, JMP};

Напомним, что по умолчанию OPR соответствует целое число ноль. Соответственно

LIT -единица, LDE - два и т. д.

В команде с кодом OPR есть десять операций.

1) OPR 1 -ввести в вершину стека число из файла stdin (с клавиатуры).

OPR 2 - число из вершины стека выводится на экран дисплея (в файл stdout).

OPR 3, OPR 4, OPR 5, OPR 6, OPR 7 - выполняют соответственно операции +, -,*, /, % над двумя верхними числами в стеке. При этом первый операнд находится в t-1, а второй - в вершине стека t. Результат всегда будет в вершине стека.

OPR 8 - изменение знака на противоположный у числа в вершине стека.

OPR 9 - возвращение из функции (return). Возвращается число, находящееся в вершине стека. При возвращении из main(), если счетчик команд p=-1, печатается результат. О счетчике команд р более подробно будет рассказано позже.

OPR 10 – остановка.

2) LIT а - загрузка константы а в вершину стека t.

3) LDE а - загрузка значения глобальной переменной в вершину стека. а - смещение этой переменной в стеке.

4) LDI а - загрузка значения локальной переменной со смещением а в вершину стека.

5) STE а - число из вершины стека заносится в качестве глобальной переменной, имеющей смещение а. Иными словами, глобальной переменной, которая находится в st [a], присваивается значение из вершины стека.

6) STI а - число из вершины стека заносится в качестве локальной переменной, у которой сдвиг в стеке равен а. Осуществляется занесение из вершины стека в st[sp+a], где sp- адрес в стеке, с которого заносятся локальные переменные.

7) CAL а - вызов функции с точкой входа а в таблице команд TCD.

8) INI а – увеличение адреса вершины стека на а (выделение памяти).

9) JMC а - безусловный переход на команду с номером а в таблице команд TCD.

10) JMP а - условный переход на команду с номером а.

Если число в вершине стека меньше или равно нулю, то переход осуществляется. Иначе- нет. Важно помнить, что после проверки условия содержание вершины стека пропадает.

Создание SPL –программы

Выше уже говорилось о том, что во время синтаксического анализа с помощью расширенных функций для нетерминальных символов заполняются таблицы ТОВ, TFN, TCD.

Таблица идентификаторов TNM заполняется при лексическом анализе.

При заполнении таблицы команд TCD выражения переводятся в обратный польский вид, когда а+b выглядит как < а><b>+.

Константа или число со значением val переводится в команду {LIT val}. Локальная или глобальная переменная d со смещением в стеке а переводится соответственно в {LDE a} или в {LDI a}. Эти команды соответствуют вызову глобальной или локальной переменных, то есть занесение их значений в вершину стека t.

Вызов функции f(e1,e2,…en)с точкой входа а в TCD переводится в последовательность команд <e₁><e₂>…<e_n> {LIT n } {CAL a}, где <e_i> - результат перевода выражения e_i. {LIT n } заносит в стек количество параметров. Изменение знака у выражения переводится в <e>{OPR 8}.

Выполнение одной из арифметических операций для двух операндов e₁ и e₂ переводится в последовательность < e₁>< e₂>{OPR }, где =3,4,5,6,7 соответственно для +,-, *, /, %. То есть сначала в вершину стека заносится e₁. Затем - e₂. При этом e₁ перемещается в t -1. Затем следует одна из операций над этими операндами {OPR }.

Если в программе на языке SPL встречается присвоение глобальной переменной d значение e, где d имеет смещение в стеке, равное а, то оно будет заменено на последовательность <e>{STE a}. Присвоение для локальной переменной со смещением а выглядит как <e>{STI a}.

Оператор ввода read d заменяется на {OPR 1}{STE a }для глобальной переменной d и на {OPR 1}{STI a} – для локальной. Здесь а- смещение в стеке.

Операторы print e, return e переводятся соответственно в d <e>{OPR 2},<e>{OPR 9 }. То есть число e, находящееся в вершине стека t, выводится на экран или возвращается из функции.

Оператор условной передачи управления if e then s end проверяет значение e в вершине стека. Если это число больше нуля, то выполняется последовательность s команд, находящаяся между then и end. Затем выполняется следующий за if оператор. Если е≤0, то управление сразу передается этому оператору. Это реализуется с помощью следующей последовательности команд в TCD <e>{JMC l} <s> l, где l- номер первой команды после последовательности команд s в TCD.

Оператор цикла while e do s end переводится в последовательность промежуточных команд lb:<e>{JMC l}<s>{JMP lb} l. Здесь lb - номер команды в TCD, по которой было получено результат е в вершине стека. l - номер команд в TCD, следующий за командой {JMP lb}. В начале проверяется число е в вершине стека. Если оно больше нуля, то выполняется последовательность s команд, стоящих между do и end. Затем выполняется безусловная передача управления команде с номером lb в TCD. Вновь проверяется е и т.д. Если е≤0, происходит переход на команду номер l в TCD (выход из цикла.)

Рассмотрим, как выглядит описание функции. На языке SPL оно имеет вид

f(параметры)

begin

описание локальных переменных и констант;

операторы

end

Это описание переводится в последовательность команд a:{ INI m} <s> {OPR 10}

Здесь a - точка входа в функцию (номер первой команды в TCD для этой функции);

m - количество локальных переменных.

s - последовательность команд, соответствующих операторам между begin и and.

Пример. Имеется программа на языке SPL

main(x,y)

begin

int c;

read c;

c=x-y/c;

if c then return c

end

Рассмотрим, в какую последовательность промежуточных команд будет переведен этот текст.

У функции main() имеются два параметра x и y и одна локальная переменная с.

Смещение для параметров определяется в соответствии с ранее приведенным правилом через их количество n.

Смещение для x равно –(n+2)=-4. Соответственно сдвиг для y равен -3. Для локальной переменной с сдвиг равен 1.

Таким образом, переменные x,y, c находятся в стеке по адресам st[sp-4], st[sp-3], st[sp+1].

После перевода текста программы в таблице команд появится последовательность промежуточных команд, приведенных в таблице.

Номер в TCD	Команда	Пояснение
	INI 1	Выделение места под локальную переменную с
	OPR 1	Занесение числа из файла stdin в вершину стека (stdin→t)
	STI 1	c=t. Число из вершины стека присваивается переменной с
	LDI -4	Занесение значения x в вершину стека
	LDL -3	Занесение y в t. x «проваливается» в t -1
	LDI 1	Занесение c в t, x переносится в t -2, а y - в t -1
	OPR 6	Деление y на c, результат в t
	OPR 4	x-y/c. Результат в вершине стека t
	STI 1	Число из t присваивается переменной с
	LDI 1	Выполняется c=x-y/c. Значение c загружается в вершину стека. Это нужно потому, что после каждой операции адрес вершины стека изменяется. Изменяется и её содержимое
	JMC 13	Если содержание вершины стека ≤0, то переход к команде 13. Иначе- к следующей, т.е. 11
	LDI 1	Загружается значение с в вершину стека, т.к. после предыдущей проверки оно из t исчезло
	OPR 9	return. Выход из функции main(). Результат - в вершине t стека
	OPR 10	Останов

Напомним, что таблица TCD представляет собой массив структур cmd TCD [300].

В каждой структуре описана команда (что делать) и операнд (над чем производить операцию). Таким образом, содержимое TCD в виде кодов имеет следующий вид.

i	TCD[i].cod	TCD[i].opd
		-4
		-3

Таким образом, в таблице команд находится последовательность промежуточных команд, полученных в результате перевода программы с алгоритмического языка SPL.

Дата добавления: 2015-06-27