-
Notifications
You must be signed in to change notification settings - Fork 1
/
task.txt
170 lines (107 loc) · 10.1 KB
/
task.txt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
Задача 1
Трансляция и интерпретация программ, содержащих строки с оператором
присваивания и оператором print, т.е. вида:
<левая часть> = <арифметическое_выражение>
и
print <арифметическое_выражение_1>, <арифметическое_выражение_2>, ...
где:
<левая часть> ::= <идентификатор> | <индексное выражение>
<индексное выражение> ::= <идентификатор> [ <список индексов> ]
<список индексов> ::= <арифметическое выражение> | , <список индексов>
Каждый оператор начинается с новой строки.
Типы идентификаторов: целые и вещественные.
Первое вхождение идентификатора есть его описание. Правило типов (из Ф77):
идентификаторы, начинающиеся с букв i, j, k, l, m, n - целые, остальные -
вещественные.
Выходным кодом будет код гипотетической стековой машины, в которой в момент
исполнения есть фрейм текущей активации процедуры с относительными адресами
0, 1, 2, ... . При распределении памяти нужно учитывать, что целые занимают
1 элемент памяти, а вещественные - 2.
Начальная инициализация переменных и массивов по умолчанию равна 0.
Размер массивов по каждой из размерностей всегда равен 100 элементам
(в терминах его формата), а размерность не больше 2.
В реализации можно ввести теги для всех данных, хранящихся в памяти, и
часть работы (по контролю, по приведению типов) выполнять динамически,
в момент интерпретации. При этом память во фрейме можно отводить элементами
одинаковой длины (по максимуму). Тегами должны быть охвачены также и адресные
типы данных, хотя в данной редакции СК они пояавляются только оперативно,
в верхушке стека, и не записываются в память.
Операции гипотетической машины:
1. Отведение памяти в стеке (продвижение регистра STP -- Stack Pointer).
Этой командой отводится память (фрейм) на столько переменных, сколько
было обнаружено в момент трансляции.
2. Загрузка в верхушку стека константы из командного потока ("непосред-
ственная" загрузка: ldci <целая-константа>, ldcd <реальная-константа>)
3. Загрузка верхушки стека: ldi <shift>, ldd <shift>. <shift> -- отно-
сительный адрес обьекта внутри фрейма процедуры.
4. Вычисление адреса по стеку: lda <shift>. Формируется "указатель"
на обьект, расположенный со смещением <shift> во фрейме.
5. Чтение по адресу, находящемуся в верхушке стека: ldsi, ldsd. Этот
адрес вырабатывается с помощью предыдущей команды.
6. Запись по адресу, находящемуся в верхушке стека: sti, std. Запись
происходит с сохранением значения в верхушке стека.
7. Вычеркивание значения из верхушки стека: scr.
8. Формирование адреса элемента массива: index.
В верхушке стека находятся два операнда: адрес начала массива (выра-
ботанный командой lda) и индекс элемента. При интерпретации данной
команды выполняется контроль за выходом за границу массива.
9. Арифметические операции над верхушкой стека (+,-,*,/,%). Результат
снова помещается в верхушку (по правилам стековых архитектур).
10. Изменение знака операнда в верхушке стека (chs).
11. Изменение типа операнда в верхушке стека (fi2d -- из целого в плавающий,
fd2i -- из плавающего в целый)
12. Подготовка к входу в процедуру (MS). Формируется "маркер стека" (со
спец. тегом в случае теговой архитектуры), помечающий начало области
фактических параметров. Для нетеговой архитектуры для этого можно ввести
некоторый регистр.
13. Вход в экстракод "Печать" (экстракод для операции "print"). Распечатыва-
ет столько обьектов, сколько передано в качестве фактических параметров
(их количество определяется расстоянием от MS). Для теговой архитектуры
тип обьекта берется по тегу, для нетеговых -- нужен специальный допол-
нительный параметр, кодирующий каждый из обьектов:
<object_type>
<object>
<object_type>
<object>
...
14. Вход в системную функцию (sin, cos, tan, ctg, asin, acos). Для
каждой из функций можно иметь свой экстракод (код операции), а
можно в команде указывать индекс в таблицу внешних функций.
Для полноценной работы необходимо разработать и реализовать Ассемблер для
данной архитектуры.
Трудозатраты: 2 человека. Один делает компиляцию операторов входного языка
в Ассемблер. Другой -- перевод Ассемблерных конструкций в формат команд
машины и их интерпретацию.
Для всех компиляций (Язык-->Ассемблер и Ассемблер-->СК) можно для ускорения
программирования использовать средства YACC и LEX (Bizon) системы UNIX.
Язык реализации: С, С++, Джава -- по желанию.
Задача 2
Превратить код стековой машины из задачи #1 в параллельный код другой
псевдо-машины. В этой машине есть:
прямо-адресуемая память (0 - 2^16);
пул из 256 регистров ; в случае исчерпания регистров компактировка
прекращается;
4 независимых устройства (несимметричных), нумеруемых от 0 до 3-х;
они работают так:
а) устройства 0 и 1 осуществляют загрузку/выгрузку памяти на регистры,
т.е. кодманды ld, st:
ldc <индекс константы>, <регистр>
ld <адрес>, <регистр>
st <регистр>, <адрес>
lda <регистр дескриптора>, <регистр индекса>, <регистр назначения>
sta <регистр дескриптора>, <регистр индекса>, <регистр источника>
На этих же устройствах исполняются команды передачи управления:
be <адрес>
call <индекс в таблице имен>
б) устройства 2 и 3 выполняют всю арифметику (над регистрами) в
формате 2х/3х-адресной системы команд:
<OP> <#r1> <#r2>
<OP> <#r1> <#r2> <#r3>
<OP>::= add | sub | mul | div | rem | ! | chsgn | fd2i | fi2d
в) В каждом устройстве есть команда NOP.
Входная информация - ассемблерный код (или процедурный интерфейс) стековой
машины.
Выходная информация - распечатка ассемблерного кода (syllables) на АЦПУ.
Язык реализации: С, С++, Джава -- по желанию.
Трудозатраты: с интрепретатором параллельной машины -- 2 чел;
без интерпретатора -- 1 чел.