Разработка элементов учебной системы программирования

Минобрнауки России Санкт-Петербургский государственный технический университет Факультет технической кибернетики

Кафедра «Информационных и Управляющих Систем»

Санкт-Петербург

Разработка элементов учебной системы программирования

1. Разработка макета учебной системы программирования Построение компилятора с языка высокого уровня (ЯВУ), являющегося одним из элементов системы программирования, образующих в совокупности следующий технологический конвейер:

При этом предполагается то, что данная система программирования работает на технологической ЭВМ (IBM PC) и является по существу кросс-системой для объектной ЭВМ (ЕС ЭВМ). В этой системе:

· в качестве языка высокого уровня (ЯВУ) выбран язык, образованный из подмножества языковых конструкций ПЛ1, а исходная программа готовится в виде текстового файла технологической ЭВМ с расширением *.pli;

· язык АССЕМБЛЕРА сформирован из языковых конструкций АССЕМБЛЕРА ЕС ЭВМ, а ассемблеровский эквивалент исходной программы формируется в виде текстового файла технологической ЭВМ с расширением *.ass;

· объектный эквивалент исходной программы готовится в формате объектных файлов операционной системы ОС ЕС ЭВМ и хранится в виде двоичного файла технологической ЭВМ с расширением *.tex;

· загрузочный эквивалент исходной программы представляет собой машинный код ЕС ЭВМ, запоминаемый в области ОЗУ технологической ЭВМ, являющейся зоной загрузки для эмулятора объектной ЭВМ.

Постановка задачи

Необходимо выполнить доработку элементов макета учебной системы программирования до уровня, позволяющего обрабатывать «новые» для макета конструкции языка высокого уровня, примененные в соответствующем варианте:

Где на входе имеется текст программы на ЯВУ PL/I:

EX04: PROC OPTIONS (MAIN);

DCL A DECIMAL FIXED INIT (2);

DCL B DECIMAL FIXED;

DCL P POINTER;

DCL D DECIMAL FIXED BASED (P);

P = ADDR (A);

B = D;

END EX04;

На выходе строится эквивалент программы на ассемблере архитектуры IBM 370:

EX04START 0

BALR RBASE, 0

USING *, RBASE

LA RRAB, A

ST RRAB, P

LRRAB, D

LRRAB, 0(0,RRAB)

MVN B (3), 0(RRAB)

BCR 15,14

ADC PL3'2C'

BDS PL3

PDS A

DEQU P

RBASE EQU 15

RRABEQU 5

END EX04

Анализ поставленной задачи

В поставленной задаче на входе в компилятор ЯВУ представлена программа на языке PL/I, которая выполняет присваивание одной десятичной переменной другой через указатель. Для этого были введены новые лексемы, отсутствовавшие в исходном макете:

· DECIMAL — десятичные переменные с инициализацией и без

· POINTER — переменная указатель

· BASED-переменные — переменная, базирующаяся на данных, на которые ссылается указатель, указанный при инициализации

· Оператор ADDR — получение адреса переменной

· Оператор присваивания `=' - присваивание значения одной десятичной переменной другой

Набор новых конструкций языка PL/I

Соответствующий набор конструкций был добавлен в компилятор ЯВУ.

1. Форматы объявления переменных

1.1 Целые десятичные переменные:

Формат: DCL DECIMAL FIXED; или DCL DECIMAL FIXED INIT ();

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

· - значение при инициализации, напр. `234'

· Могут быть как инициализированными, так и не инициализированными Указатели Формат: DCL POINTER;

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

BASED-переменные:

Формат: DCL DECIMAL FIXED BASED ();

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

· - имя переменной — указателя

2. Форматы использования операторов

2.1 Оператор присваивания:

Формат: =

· предназначен для назначения нового значения переменной, идентификатор которой использован в левой части оператора;

2.2 Оператор ADDR:

Формат: = ADDR ();

· предназначен для получения адреса переменной, указанной в качестве операнда в скобках. Переменная должна иметь тип POINTER;

Входные ограничения компилятора ЯВУ

В поставленной задаче не рассмотрены следующие моменты:

· не описано, каким образом работать с целые десятичными переменными, а именно:

o не указан знак числа,

o не указана длина мантиссы.

· не описано, каким образом представлять BASED-переменные в ассемблеровском эквиваленте программы (на выходе).

· отсутствуют арифметические операции По этому, для определенности, были введены следующие ограничения на языковые конструкции компилятора ЯВУ:

· Ограничения на целые десятичные переменные:

o имеют тип `P' в ассемблеровском эквиваленте программы;

o определяются как без знаковые, т. е. всегда положительные;

o имеют длину 3 байта (мантисса равна 5 (одна тетрада на знак)), т. е. это числа от 0 до 99 999;

o не инициализированные десятичные переменные на ЯВУ инициализируются нулем в ассемблеровском эквиваленте программы.

· BASED-переменные:

o только целые десятичные

o не имеют свое представление в памяти программы, для этого они объявляются через оператор EQU ассемблера ЕС ЭВМ.

· Оператор присваивания кодируется в 6 байтовую команду типа SS (Storage — Storage) языка Ассемблера. Это означает, что присваивание работает без использования вспомогательных регистров.

· Указатели объявляются как тип `A' в ассемблеровском эквиваленте программы, имеют размер 4 байта (длину адреса в ЕС ЭВМ).

Описание разработанного синтаксиса языка

Синтаксис существующего макета был расширен следующими правилами:

· добавлено правило декларирования десятичных переменных с инициализацией и без

· добавлено правило декларирования указателей и десятичных переменных, базирующихся на данных, на которые ссылается этот указатель

· добавлено правило получения адреса существующей переменной

· добавлено правило работы оператора присваивания Таким образом, грамматика языка имеет следующий вид:

1. :=

2. := :PROC_OPTIONS (MAIN);

3. :=

4. := | |

5. := A | B | C | D | E | M | P | X

6. := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

7. := | |

8. := DCL__BIN_FIXED (); |

DCL__BIN_FIXED ()INIT (); |

DCL__DECIMAL_FIXED_INIT (); |

DCL__DECIMAL_FIXED; |

DCL__POINTER; |

DCL__DECIMAL_FIXED_BASED ();

9. :=

10. := |

11. := B

12. := 1 | 0 | 1

13. := =ADDR (); |

=;

14. := | | |

15. := + | ;

16. := END_

Рис. 1 Распознавание грамматических правил в формате продукций

Преобразования в код ассемблера ЕС ЭВМ Следуя введенным ограничениям, получаем следующий ассемблеровский эквивалент на выходе компилятора ЯВУ:

1. Переменные:

1.1. Целые десятичные переменные объявляются как тип PL3'X' через команду DC, где Х — значение при инициализации. `P' - стандартный тип десятичных переменных в ассемблере IBM 370. Литера `L' означает длину числа в байтах, которая соответствует 3 байтам — фиксированное значение, оговоренное в ограничениях к компилятору ЯВУ.

1.2. Указатели объявляются как тип A через команду DS. Команда DS ассемблера IBM 370 выделяет память на 4 байта не инициализированных данных, т.к. указатели не могут быть иницилизированы, а длина 4 байта соответствует длине адреса архитектуры IBM 370.

1.3. BASED-переменные объявляются через псевдокоманду EQU:

<�имя переменной> EQU <�имя указателя>. Т.к. BASED-переменные являются лишь представлением уже существующего десятичного числа через указатель, логично использование ассемблерной псевдокоманды EQU, которая не выделяет память под переменную. В дальнейшем, при компиляции с ассемблера в байт-код, будет использоваться подстановка соответствующего значения псевдокоманды EQU для соответствующей BASED-переменной.

2. Операторы:

2.1. Оператор присваивания кодируется в 6ти-байтовую SS команду MVN, имеющую формат:

MVN D1(L, B1), D2(B2)

где:

· D1 и D2 — смещение относительно базового адреса, содержащегося в регистре общего назначения;

· B1, B2 — регистры РОН, содержащие адрес данных;

· L — длина операндов в байтах Команда MVN специализирована под копирование числа из одного адреса памяти в другой. Эта SS-команда требует большее число тактов, чем RX-команда, однако упрощает выходной эквивалент программы и не требует дополнительного вмешательства для правильного копирования чисел.

2.2. Оператор ADDR кодируется в две 4ех-байтовые RX команды: LA и ST, т.к. в ассемблере IBM 370 отсутствует команда, которая бы копировала адрес переменной в соответствующее место памяти. Эти команды имеют одинаковый формат:

LA R1, D2(X2, B2)

ST R1, D2(X2, B2)

где:

· R1- регистр РОН;

· D2 — смещение относительно базового адреса, содержащегося в регистре общего назначения;

· X2 -регистр РОН, используемый в качестве индекса;

· B2 — регистр РОН, содержащие адрес данных;

Команда LA загружает адрес переменной, указанной в качестве второго операнда в первый операнд — регистр. А команда ST заносит значение первого операнда — регистра во второй операнд — переменную. Таким образом сначала считывается адрес переменной из памяти в регистр, а затем это значение заносится в переменную-указатель.

2.3. Оператор присваивания — `='. Переменные, расположенные по правую сторону от оператора кодируются в зависимости от типа:

2.3.1. Для BASED-переменных кодирование происходит в два этапа: 1) Загрузка значения указателя в регистр с помощью уже имеющейся в исходном макете команды L; 2) Загрузка значения переменной, расположенной по полученному адресу с помощью той же команды L.

2.3.2. Загрузка десятичных переменных происходит с помощью комманды L. Таким образом, если идет присвоение одной десятичной переменной другой, то сначала идет загрузка второй десятичной переменной в регистр с помощью комманды L, а затем происходит копирование памяти с помощью комманды MVN, описанной ранее.

Модификация базы данных исходного макета

В таблицу продукций (SINT) были добавлены разработанные синтаксические правила для переменных и операторов. Размер таблицы увеличился с 201 до 263 элементов. Матрица смежности, при этом, не модифицировалась.

Были введены дополнительные типы в семантику языка:

· для переменных, описывающих десятичные числа, был введен тип `D'

· для переменных, описывающих указатели — тип `A'

· для переменных типа BASED — тип `V'

Модификация алгоритма исходного макета

Функция декларирования переменных — ODC1 была модифицирована в соответствии с новыми типами переменных.

При попадании арифметическим оператором на указатель на втором проходе в функции OPA2, проверяется, является ли следующий за оператором присваивания оператор ADDR, и, если да, то формируется код комманд LA и ST.

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

В функции AVI2 (на втором проходе) при определении типа переменной — BASED, формируются две ассемблерные команды L: первая загружает значение переменной-указателя в регистр RRAB, вторая загружает значение десятичной переменной, расположенной по адресу, загруженному предыдущей командой L в регистр RRAB.

Если же в функции AVI2 встречается десятичная переменная, то формируется команда L, которая загружает значение переменной в регистр RRAB.

В результате, был разработан компилятор ЯВУ, который имеет ниже перечисленные приемущества и недостатки. Несмотря на недостатки, новая функциональностть позволяет выполнять поставленную задачу.

Плюсы данной реализации:

· Использование встроенных функций ассемблера для работы с числами и адресами;

· BASED-переменные имеют представление в выходном файле, что позволяет более точно восстановить исходный код по выходному эквиваленту;

· Не используется память для BASED-переменных;

Минусы данной реализации:

· Только беззнаковые десятичные числа;

· Фиксированная мантиса десятичных чисел;

· Отсутствие арифметических операций над десятичными числами;

· Выходой файл совместим только с ассемблером ЭВМ IBM 370;

2. Разработка компилятора ассемблера Получение практических навыков построения компилятора с языка высокого уровня (ЯВУ), являющегося одним из элементов системы программирования, образующих в совокупности следующий технологический конвейер:

При этом предполагается то, что данная система программирования работает на технологической ЭВМ (IBM PC) и является по существу кросс-системой для объектной ЭВМ (ЕС ЭВМ). В этой системе:

· в качестве языка высокого уровня (ЯВУ) выбран язык, образованный из подмножества языковых конструкций ПЛ1, а исходная программа готовится в виде текстового файла технологической ЭВМ с расширением *.pli;

· язык АССЕМБЛЕРА сформирован из языковых конструкций АССЕМБЛЕРА ЕС ЭВМ, а ассемблеровский эквивалент исходной программы формируется в виде текстового файла технологической ЭВМ с расширением *.ass;

· объектный эквивалент исходной программы готовится в формате объектных файлов операционной системы ОС ЕС ЭВМ и хранится в виде двоичного файла технологической ЭВМ с расширением *.tex;

· загрузочный эквивалент исходной программы представляет собой машинный код ЕС ЭВМ, запоминаемый в области ОЗУ технологической ЭВМ, являющейся зоной загрузки для эмулятора объектной ЭВМ.

Постановка задачи

Необходимо выполнить доработку элементов макета учебной системы программирования до уровня, позволяющего обрабатывать «новые» для макета конструкции языка высокого уровня, примененные в соответствующем варианте:

Где на входе имеется исходный код программы на ассемблере ЭВМ IBM 370:

EX04START 0

BALR RBASE, 0

USING *, RBASE

LA RRAB, A

ST RRAB, P

LRRAB, D

LRRAB, 0(0,RRAB)

MVN B (3), 0(RRAB)

BCR 15,14

ADC PL3'2C'

BDS PL3

PDS A

DEQU P

RBASE EQU 15

RRABEQU 5

END EX04

На выходе эквивалент исходной программы в виде байт-кода для IBM 370:

Offset 0 1 2 3 4 5 6 7 8 9 A B C D E F

0 02 45 53 44 40 40 40 40 40 40 00 10 40 40 00 01 ESD@@@@@@ @@

10 45 58 30 34 40 40 40 40 00 00 00 00 40 00 00 28 EX04@@@@ @ (

20 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

30 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

40 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

50 02 54 58 54 40 00 00 00 40 40 00 02 40 40 00 01 TXT@ @@ @@

60 05 F0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 р@@@@@@@@@@@@@@

70 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

80 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

90 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

00A0 02 54 58 54 40 00 00 02 40 40 00 04 40 40 00 01 TXT@ @@ @@

00B0 41 50 F0 1A 40 40 40 40 40 40 40 40 40 40 40 40 APр @@@@@@@@@@@@

00C0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

00D0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

00E0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

00F0 02 54 58 54 40 00 00 06 40 40 00 04 40 40 00 01 TXT@ @@ @@

100 50 50 F0 22 40 40 40 40 40 40 40 40 40 40 40 40 PPр" @@@@@@@@@@@@

110 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

120 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

130 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

140 02 54 58 54 40 00 00 0A 40 40 00 04 40 40 00 01 TXT@ @@ @@

150 58 50 F0 22 40 40 40 40 40 40 40 40 40 40 40 40 XPр" @@@@@@@@@@@@

160 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

170 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

180 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

190 02 54 58 54 40 00 00 0E 40 40 00 04 40 40 00 01 TXT@ @@ @@

01A0 58 50 50 00 40 40 40 40 40 40 40 40 40 40 40 40 XPP @@@@@@@@@@@@

01B0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

01C0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

01D0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

01E0 02 54 58 54 40 00 00 12 40 40 00 06 40 40 00 01 TXT@ @@ @@

01F0 D1 03 F0 1E 50 00 40 40 40 40 40 40 40 40 40 40 С р P @@@@@@@@@@

200 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

210 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

220 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

230 02 54 58 54 40 00 00 18 40 40 00 02 40 40 00 01 TXT@ @@ @@

240 07 FE 40 40 50 00 40 40 40 40 40 40 40 40 40 40 ю@@P @@@@@@@@@@

250 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

260 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

270 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

280 02 54 58 54 40 00 00 1C 40 40 00 04 40 40 00 01 TXT@ @@ @@

290 00 00 00 2C 50 00 40 40 40 40 40 40 40 40 40 40, P @@@@@@@@@@

02A0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

02B0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

02C0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

02D0 02 54 58 54 40 00 00 20 40 40 00 04 40 40 00 01 TXT@ @@ @@

02E0 00 00 00 0C 50 00 40 40 40 40 40 40 40 40 40 40P @@@@@@@@@@

02F0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

300 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

310 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

320 02 54 58 54 40 00 00 24 40 40 00 04 40 40 00 01 TXT@ $@@ @@

330 00 00 00 00 50 00 40 40 40 40 40 40 40 40 40 40P @@@@@@@@@@

340 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

350 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

360 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

370 02 45 4E 44 40 40 40 40 40 40 40 40 40 40 40 40 END@@@@@@@@@@@@

380 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

390 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

03A0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

03B0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

3. Загрузчик, Эмулятор, Отладчик

Анализ поставленной задачи

В поставленной задаче появились новые команды ассемблера, отсутствующие в исходном макете компилятора. Это следующие команды: LA, MVN, DC PL3'X', DS PL3, DS A, EQU.

Форматы команд

3. Команда LA. Загружает адрес переменной в регистр. Имеет следующий формат:

LA R1, D2(X2, B2)

ST R1, D2(X2, B2)

где:

· R1- регистр РОН;

· D2 — смещение относительно базового адреса, содержащегося в регистре общего назначения;

· X2 -регистр РОН, используемый в качестве индекса;

· B2 — регистр РОН, содержащие адрес данных;

· Первый операнд — адресат, второй — источник;

Длина команды составляет 4 байта. Тип команды — RX.

4. Команда MVN. Производит копирование числа из одного адреса памяти в другой. Эта команда имеет следующий формат:

MVN D1(L, B1), D2(B2)

где:

· D1 и D2 — смещение относительно базового адреса, содержащегося в регистре общего назначения;

· B1, B2 — регистры РОН, содержащие адрес данных;

· L — длина операндов в байтах Команда типа SS, имеет длину 6 байт.

Формат декларирования переменных

4.1. Команда DC с операндом PL3'X' используется для объявления и инициализации целых десятичных переменных, где Х — значение при инициализации. `P' - стандартный тип десятичных переменных в ассемблере IBM 370. Литера `L' означает длину числа в байтах, которая соответствует 3 байтам — фиксированное значение, оговоренное в ограничениях к компилятору ЯВУ.

4.2. Команда DS с операндом PL3 используется для объявления целых десятичных переменных. `P' - стандартный тип десятичных переменных в ассемблере IBM 370. Литера `L' означает длину числа в байтах, которая соответствует 3 байтам — фиксированное значение, оговоренное в ограничениях к компилятору ЯВУ.

4.3. Команда DS с операндом A используется для резервирования памяти под переменные-указатели. Выделяет память на 4 байта не инициализированных данных, т.к. указатели не могут быть иницилизированы, а длина 4 байта соответствует длине адреса архитектуры IBM 370.

4.4. Команда EQU, где правый операнд — это существующая переменная, используется для подстановки правого операнда вместо левого.

Ограничение компилятора ассемблера

Список ограничений в данной реализации компилятора ассемблера:

· Поддержка только 3ех-байтовых переменных типа `P';

· Команда EQU не может принимать в качестве правого операнда выражения;

· Поддержка только вышеописанных команд и псевдокоманд;

Преобразование команд в байт код

Рассмотрим формат байт-кода новых команд.

1. Команда LA:

· имеет размер 4 байта

· тип RX

· формат:

где

· 0×41 — код команды

· R1 содержит номер регистра РОН, в который будет записан результат работы команды

· X2 содержит номер регистра РОН, использующегося в качестве индекса

· B2 содержит номер регистра РОН, использующегося для хранения адреса в памяти, содержащего данные

· D2 представляет смещение относительно базового адреса, содержащегося в регистре общего назначения

2. Команда MVN:

· имеет размер 6 байт

· тип SS (StorageStorage)

· формат:

где:

· 0xD1 — код команды

· B1, B2 содержат номер регистра РОН, использующегося для хранения адреса в памяти, содержащего данные первого и второго операндов соответственно

· D1, D2 представляет смещение относительно базового адреса, содержащегося в регистре общего назначения для первого и второго операндов соответственно

3. Псевдокоманда DC с параметром PL3:

· Объявляет и инициализирует целую десятичную переменную, длинной 3 байта

4. Псевдокоманда DS с параметром PL3:

· Объявляет целую десятичную переменную, длинной 3 байта

5. Псевдокоманда DS с параметром A:

· Резервирует 4 байта памяти, использующихся в дальнейшем для запоминания адреса данных

6. Псевдокоманда EQU с параметром — именем переменной:

· Ассоциирует метку с указанным параметром. Используется для объявления BASED-переменных

Модификация базы данных исходного макета

В таблицу машинных операций (TMOP) были добавлены команды LA и MVN.

Добавлена структура буфера 6ти-байтовых команд.

Модификация алгоритма исходного макета

В существующий макет были внесены соответствующие изменения, для работы вышеописанных команд. Основная модификация коснулась обработки 6ти-байтовых команд. Эти изменения повлияли на организацию данных в памяти. Из-за сдвига адреса на 6 байт, данные программы оказывались не выровненными. По этому, соответствующие изменения пришлось внести в функцию объявления переменных.

В функцию FDC были внесены изменения, позволяющие обрабатывать объявление десятичных переменных типа `P', а в функцию FDS — позволяющие обрабатывать объявления переменных типа `A'.

Функция FEQU модифицирована для поддержки обработки не только цифр в качестве подставляемого значения, но слов.

Подпрограмма формирования TXT карты теперь поддерживает 6ти-байтовые команды.

Добавлены функции FSS и SSS для обработки шестибайтовых команд.

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

Плюсы данной реализации:

· Возможность использования псевдокоманды EQU для подстановки любого слова вместо имени переменной;

· Выравнивание данных по размеру адреса;

· Поддержка 6ти-байтовых команд;

Минусы данной реализации:

· Поддержка только 3ех-байтовых переменных типа `P';

· Команда EQU не может принимать в качестве правого операнда выражения;

· Поддержка только вышеописанных команд и псевдокоманд;

Построение компилятора с языка высокого уровня (ЯВУ), являющегося одним из элементов системы программирования, образующих в совокупности следующий технологический конвейер:

При этом предполагается то, что данная система программирования работает на технологической ЭВМ (IBM PC) и является по существу кросс-системой для объектной ЭВМ (ЕС ЭВМ). В этой системе:

· в качестве языка высокого уровня (ЯВУ) выбран язык, образованный из подмножества языковых конструкций ПЛ1, а исходная программа готовится в виде текстового файла технологической ЭВМ с расширением *.pli;

· язык АССЕМБЛЕРА сформирован из языковых конструкций АССЕМБЛЕРА ЕС ЭВМ, а ассемблеровский эквивалент исходной программы формируется в виде текстового файла технологической ЭВМ с расширением *.ass;

· объектный эквивалент исходной программы готовится в формате объектных файлов операционной системы ОС ЕС ЭВМ и хранится в виде двоичного файла технологической ЭВМ с расширением *.tex;

· загрузочный эквивалент исходной программы представляет собой машинный код ЕС ЭВМ, запоминаемый в области ОЗУ технологической ЭВМ, являющейся зоной загрузки для эмулятора объектной ЭВМ.

Постановка задачи

Необходимо выполнить доработку элементов макета учебной системы программирования до уровня, позволяющего обрабатывать «новые» для макета конструкции языка высокого уровня, примененные в соответствующем варианте:

Где на входе исходный текст программы в виде байт-кода ЭВМ IBM 370:

Offset 0 1 2 3 4 5 6 7 8 9 A B C D E F

0 02 45 53 44 40 40 40 40 40 40 00 10 40 40 00 01 ESD@@@@@@ @@

10 45 58 30 34 40 40 40 40 00 00 00 00 40 00 00 28 EX04@@@@ @ (

20 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

30 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

40 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

50 02 54 58 54 40 00 00 00 40 40 00 02 40 40 00 01 TXT@ @@ @@

60 05 F0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 р@@@@@@@@@@@@@@

70 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

80 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

90 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

00A0 02 54 58 54 40 00 00 02 40 40 00 04 40 40 00 01 TXT@ @@ @@

00B0 41 50 F0 1A 40 40 40 40 40 40 40 40 40 40 40 40 APр @@@@@@@@@@@@

00C0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

00D0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

00E0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

00F0 02 54 58 54 40 00 00 06 40 40 00 04 40 40 00 01 TXT@ @@ @@

100 50 50 F0 22 40 40 40 40 40 40 40 40 40 40 40 40 PPр" @@@@@@@@@@@@

110 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

120 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

130 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

140 02 54 58 54 40 00 00 0A 40 40 00 04 40 40 00 01 TXT@ @@ @@

150 58 50 F0 22 40 40 40 40 40 40 40 40 40 40 40 40 XPр" @@@@@@@@@@@@

160 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

170 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

180 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

190 02 54 58 54 40 00 00 0E 40 40 00 04 40 40 00 01 TXT@ @@ @@

01A0 58 50 50 00 40 40 40 40 40 40 40 40 40 40 40 40 XPP @@@@@@@@@@@@

01B0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

01C0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

01D0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

01E0 02 54 58 54 40 00 00 12 40 40 00 06 40 40 00 01 TXT@ @@ @@

01F0 D1 03 F0 1E 50 00 40 40 40 40 40 40 40 40 40 40 С р P @@@@@@@@@@

200 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

210 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

220 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

230 02 54 58 54 40 00 00 18 40 40 00 02 40 40 00 01 TXT@ @@ @@

240 07 FE 40 40 50 00 40 40 40 40 40 40 40 40 40 40 ю@@P @@@@@@@@@@

250 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

260 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

270 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

280 02 54 58 54 40 00 00 1C 40 40 00 04 40 40 00 01 TXT@ @@ @@

290 00 00 00 2C 50 00 40 40 40 40 40 40 40 40 40 40, P @@@@@@@@@@

02A0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

02B0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

02C0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

02D0 02 54 58 54 40 00 00 20 40 40 00 04 40 40 00 01 TXT@ @@ @@

02E0 00 00 00 0C 50 00 40 40 40 40 40 40 40 40 40 40P @@@@@@@@@@

02F0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

300 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

310 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

320 02 54 58 54 40 00 00 24 40 40 00 04 40 40 00 01 TXT@ $@@ @@

330 00 00 00 00 50 00 40 40 40 40 40 40 40 40 40 40P @@@@@@@@@@

340 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

350 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

360 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

370 02 45 4E 44 40 40 40 40 40 40 40 40 40 40 40 40 END@@@@@@@@@@@@

380 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

390 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

03A0 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 @@@@@@@@@@@@@@@@

03B0 40 40 40 40 40 40 40 40 45 58 30 34 40 40 40 40 @@@@@@@@EX04@@@@

На выходе пошаговое выполнение инструкций программы с отображением текущей команды, значением регистров и памяти программы:

Рис. 2 Вывод загрузчика

компилятор программирование ассемблер

Анализ поставленной задачи

Во входном файле появились две новые команды, неизвестные для загрузчика, это команды LA с кодом 0×41 и MVN с кодом 0xD1. Рассмотрим формат байт-кода этих команд:

1. Команда LA:

· имеет размер 4 байта

· тип RX

· формат:

где

· 0×41 — код команды

· R1 содержит номер регистра РОН, в который будет записан результат работы команды

· X2 содержит номер регистра РОН, использующегося в качестве индекса

· B2 содержит номер регистра РОН, использующегося для хранения адреса в памяти, содержащего данные

· D2 представляет смещение относительно базового адреса, содержащегося в регистре общего назначения

2. Команда MVN:

· имеет размер 6 байт

· тип SS (StorageStorage)

· формат:

где:

· 0xD1 — код команды

· B1, B2 содержат номер регистра РОН, использующегося для хранения адреса в памяти, содержащего данные первого и второго операндов соответственно

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

Ограничения

· Эмулятор команды MVN поддерживает данные длиной только 3 байта;

· Ограничения касаются загрузки TXT-карт. Поддерживается загрузка только одной команды на карте. Т. е. на TXT-карте может быть только одна команда длиной 2, 4 или 6 байт;

· Загрузчик может загружать только одну программу;

· Поддерживаются программы максимальной длиной в 50 карт;

Модификация базы данных исходного макета

В таблицу машинных операций (TMOP) были добавлены новые команды LA и MVN.

Модификация алгоритма исходного макета

В эмулятор добавлены программы реализации семантики команд LA и MVN.

В загрузчик добавлены функции загрузки 6ти-байтовых команд по аналогии обработки 2ух и 4ех-байтовых команд.

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

Плюсы данной реализации:

· Поддержка новых команд: LA и MVN;

· Загрузчик поддерживает 6ти-байтовые команды;

Минусы данной реализации:

· Эмулятор для команды MVN поддерживает данные длиной только 3 байта;

· Поддерживается загрузка только одной команды на TXT-карте;

· Загрузчик может загружать только одну программу;

· Поддерживаются программы максимальной длиной в 50 карт;

4. Компилятор с языка высокого уровня с использованием Flex и Bison

Построение компилятора с языка высокого уровня (ЯВУ), являющегося одним из элементов системы программирования, образующих в совокупности следующий технологический конвейер:

При этом предполагается то, что данная система программирования работает на технологической ЭВМ (IBM PC) и является по существу кросс-системой для объектной ЭВМ (ЕС ЭВМ). В этой системе:

· в качестве языка высокого уровня (ЯВУ) выбран язык, образованный из подмножества языковых конструкций ПЛ1, а исходная программа готовится в виде текстового файла технологической ЭВМ с расширением *.pli;

· язык АССЕМБЛЕРА сформирован из языковых конструкций АССЕМБЛЕРА ЕС ЭВМ, а ассемблеровский эквивалент исходной программы формируется в виде текстового файла технологической ЭВМ с расширением *.ass;

· объектный эквивалент исходной программы готовится в формате объектных файлов операционной системы ОС ЕС ЭВМ и хранится в виде двоичного файла технологической ЭВМ с расширением *.tex;

· загрузочный эквивалент исходной программы представляет собой машинный код ЕС ЭВМ, запоминаемый в области ОЗУ технологической ЭВМ, являющейся зоной загрузки для эмулятора объектной ЭВМ.

Постановка задачи

Необходимо выполнить доработку элементов макета учебной системы программирования до уровня, позволяющего обрабатывать «новые» для макета конструкции языка высокого уровня, примененные в соответствующем варианте:

Где на входе имеется текст программы на ЯВУ PL/I:

EX04: PROC OPTIONS (MAIN);

DCL A DECIMAL FIXED INIT (2);

DCL B DECIMAL FIXED;

DCL P POINTER;

DCL D DECIMAL FIXED BASED (P);

P = ADDR (A);

B = D;

END EX04;

На выходе строится эквивалент программы на ассемблере архитектуры IBM 370:

ex04START 0Programm start

BALR RBASE, 0Base initialization

USING *, RBASEBase declaration

LA RRAB, A Load address

ST RRAB, P Store address

LRRAB, D Variable value loading

LRRAB, 0(0,RRAB) Load by address

MVN B (3), 0(RRAB) Move numveric

BCR 15, RVIXReturn from programm

RBASE EQU 5

RVIXEQU 14

RRABEQU 3

ADC PL3'2C'Variable declaration with initialization

BDS PL3 Variable declaration without initialization

PDS AVariable declaration without initialization

DEQU P

END Programm end

Анализ поставленной задачи

В поставленной задаче на входе в компилятор ЯВУ представлена программа на языке PL/I, которая выполняет присваивание одной десятичной переменной другой через указатель. Для этого были введены новые лексемы, отсутствовавшие в исходном макете:

· DECIMAL — десятичные переменные с инициализацией и без

· POINTER — переменная указатель

· BASED-переменные — переменная, базирующаяся на данных, на которые ссылается указатель, указанный при инициализации

· Оператор ADDR — получение адреса переменной

· Оператор присваивания `=' - присваивание значения одной десятичной переменной другой

Набор новых конструкций языка PL/I

Соответствующий набор конструкций был добавлен в компилятор ЯВУ.

3. Форматы объявления переменных

3.1 Целые десятичные переменные:

Формат: DCL DECIMAL FIXED; или DCL DECIMAL FIXED INIT ();

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

· - значение при инициализации, напр. `234'

· Могут быть как инициализированными, так и не инициализированными

3.2 Указатели:

Формат: DCL POINTER;

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

3.3 BASED-переменные:

Формат: DCL DECIMAL FIXED BASED ();

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

· - имя переменной — указателя

4. Форматы использования операторов

4.1 Оператор присваивания:

Формат: =

· предназначен для назначения нового значения переменной, идентификатор которой использован в левой части оператора;

4.2 Оператор ADDR:

Формат: = ADDR ();

· предназначен для получения адреса переменной, указанной в качестве операнда в скобках. Переменная должна иметь тип POINTER;

Входные ограничения компилятора ЯВУ

В поставленной задаче не рассмотрены следующие моменты:

· не описано, каким образом работать с целые десятичными переменными, а именно:

o не указан знак числа,

o не указана длина мантиссы.

· не описано, каким образом представлять BASED-переменные в ассемблеровском эквиваленте программы (на выходе).

· отсутствуют арифметические операции По этому, для определенности, были введены следующие ограничения на языковые конструкции компилятора ЯВУ:

· Ограничения на целые десятичные переменные:

o имеют тип `P' в ассемблеровском эквиваленте программы;

o определяются как без знаковые, т. е. всегда положительные;

o имеют длину 3 байта (мантисса равна 5), т. е. это числа от 0 до 99 999;

o не инициализированные десятичные переменные на ЯВУ инициализируются нулем в ассемблеровском эквиваленте программы.

· BASED-переменные:

o только целые десятичные

o не имеют свое представление в памяти программы, для этого они объявляются через оператор EQU ассемблера ЕС ЭВМ.

· Оператор присваивания кодируется в 6 байтовую команду типа SS (Storage — Storage) языка Ассемблера. Это означает, что присваивание работает без использования вспомогательных регистров.

· Указатели объявляются как тип `A' в ассемблеровском эквиваленте программы, имеют размер 4 байта (длину адреса в ЕС ЭВМ).

Описание разработанного синтаксиса языка

Синтаксис существующего макета был расширен следующим образом:

· добавлено правило декларирования десятичных переменных с инициализацией и без

· добавлено правило декларирования указателей и десятичных переменных, базирующихся на данных, на которые ссылается этот указатель

· добавлено правило получения адреса существующей переменной

· добавлено правило работы оператора присваивания Таким образом, грамматика языка имеет следующий вид:

1. :=

2. := :PROC_OPTIONS (MAIN);

3. :=

4. := | |

5. := A | B | C | D | E | M | P | X

6. := 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

7. := | |

8. := DCL__BIN_FIXED (); |

DCL__BIN_FIXED ()INIT (); |

DCL__DECIMAL_FIXED_INIT (); |

DCL__DECIMAL_FIXED; |

DCL__POINTER; |

DCL__DECIMAL_FIXED_BASED ();

9. :=

10. := |

11. := B

12. := 1 | 0 | 1

13. := =ADDR (); |

=;

14. := | | |

15. := + | ;

16. := END_

Рис. 3 Распознавание грамматических правил в формате продукций

Преобразования в код ассемблера ЕС ЭВМ

Следуя введенным ограничениям, получаем следующий ассемблеровский эквивалент на выходе компилятора ЯВУ:

5. Переменные:

5.1. Целые десятичные переменные объявляются как тип PL3'X' через команду DC, где Х — значение при инициализации. `P' - стандартный тип десятичных переменных в ассемблере IBM 370. Литера `L' означает длину числа в байтах, которая соответствует 3 байтам — фиксированное значение, оговоренное в ограничениях к компилятору ЯВУ.

5.2. Указатели объявляются как тип A через команду DS. Команда DS ассемблера IBM 370 выделяет память на 4 байта не инициализированных данных, т.к. указатели не могут быть иницилизированы, а длина 4 байта соответствует длине адреса архитектуры IBM 370.

5.3. BASED-переменные объявляются через псевдокоманду EQU:

<�имя переменной> EQU <�имя указателя>. Т.к. BASED-переменные являются лишь представлением уже существующего десятичного числа через указатель, логично использование ассемблерной псевдокоманды EQU, которая не выделяет память под переменную. В дальнейшем, при компиляции с ассемблера в байт-код, будет использоваться подстановка соответствующего значения псевдокоманды EQU для соответствующей BASED-переменной.

6. Операторы:

6.1. Оператор присваивания кодируется в 6ти-байтовую SS команду MVN, имеющую формат:

MVN D1(L, B1), D2(B2)

где:

· D1 и D2 — смещение относительно базового адреса, содержащегося в регистре общего назначения;

· B1, B2 — регистры РОН, содержащие адрес данных;

· L — длина операндов в байтах Команда MVN специализирована под копирование числа из одного адреса памяти в другой. Эта SS-команда требует большее число тактов, чем RX-команда, однако упрощает выходной эквивалент программы и не требует дополнительного вмешательства для правильного копирования чисел.

6.2. Оператор ADDR кодируется в две 4ех-байтовые RX команды: LA и ST, т.к. в ассемблере IBM 370 отсутствует команда, которая бы копировала адрес переменной в соответствующее место памяти. Эти команды имеют одинаковый формат:

LA R1, D2(X2, B2)

ST R1, D2(X2, B2)

где:

· R1- регистр РОН;

· D2 — смещение относительно базового адреса, содержащегося в регистре общего назначения;

· X2 -регистр РОН, используемый в качестве индекса;

· B2 — регистр РОН, содержащие адрес данных;

Команда LA загружает адрес переменной, указанной в качестве второго операнда в первый операнд — регистр. А команда ST заносит значение первого операнда — регистра во второй операнд — переменную. Таким образом сначала считывается адрес переменной из памяти в регистр, а затем это значение заносится в переменную-указатель.

6.3. Оператор присваивания — `='. Переменные, расположенные по правую сторону от оператора кодируются в зависимости от типа:

6.3.1. Для BASED-переменных кодирование происходит в два этапа: 1) Загрузка значения указателя в регистр с помощью уже имеющейся в исходном макете команды L; 2) Загрузка значения переменной, расположенной по полученному адресу с помощью той же команды L.

6.3.2. Загрузка десятичных переменных происходит с помощью комманды L. Таким образом, если идет присвоение одной десятичной переменной другой, то сначала идет загрузка второй десятичной переменной в регистр с помощью комманды L, а затем происходит копирование памяти с помощью комманды MVN, описанной ранее.

Модификация базы данных исходного макета

В исходный код для flex был добавлен разбор новых лексем BASED, DECIMAL, ADDR и POINTER. Эти же лексемы добавлены в набор токенов для bison.

Модификация алгоритма исходного макета

Разработанные синтаксические правила были добавлены в набор правил для bison.

Были добавлены функции декларирования десятичных переменных, уакзателей и BASED-переменных.

Добавлена функция poi, которая обрабатывает лексему ADDR. Эта функция генерирует две ассемблерные команды — LA и ST.

Функция opa модифицирована для того, чтобы оператор присвоения заменялся на ассемблерную функцию MVN, если операндом является десятичное число.

В функцию avi_ipe добавлена возможность подстановки вместо слова, объявленного псевдокомандой EQU, имени переменной.

В результате был разработан компилятор ЯВУ, позволяющи справляться с поставленной задачей.

Плюсы данной реализации:

· использование встроенных функций ассемблера для работы с числами и адресами;

· BASED-переменные имеют представление в выходном файле, что позволяет более точно восстановить исходный код по выходному эквиваленту;

· не используется память для BASED-переменных;

Минусы данной реализации:

· беззнаковые десятичные числа;

· фиксированная мантиса десятичных чисел;

· отсутствие арифметических операций над десятичными числами;

· выходой файл совместим только с ассемблером ЭВМ IBM 370;

Основные преимущества Flex и Bison над первой реализацией компилятора ЯВУ:

· отсутствие таблицы проекций

· отсутствие стека целей и достижений

· отсутствие матрицы смежности и генерации матрицы связности

· отсутствие 2ух проходов при разборе программы

· обработка программы последовательно сразу лексическим и грамматическим анализатором, а не поэтапно — сначала лексическим, затем синтаксическим и потом семантическим Все эти преимущества позволяют легко модифицировать язык, не повредив разбору уже реализованных правил.