1.2 Структуры данных ассемблера и алгоритм его работы

Трансляция программ с языка ассемблера в

последовательность машииных кодов выполняется в общем случае

за два просмотра исходного текста. Цель первого просмотра

состоит в определении значений меток и адресов литералов. На

втором прсмотре формируеися последовательность команд и

констант в виде машинных кодов.

Во время первого просмотра выполняются :

- проверка правильности записи операторов языка,

- определение значений меток,

- обработка некоторых псевдокоманд,

- запоминание литералов.

Для работы ассемблера на первом просмотре необходимы:

- текст исходной программы,

- счетчик адреса (LC),

- таблица машинных команд (MOT),

- таблица псевдокоманд (POT),

- таблица символов, или меток (ST),

- таблица литералов (LT).

Все перечисленные структуры данных, кроме исходной

программы, являются внутренними переменными и таблицами

ассемблера. Таблица машинных команд и таблица псевдокоманд

являются постоянными таблицами ассемблера; их содержимое не

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

меток и литералов -- это таблицы, содержимое которых

изменяется во время трансляции программы.

Перечисленные таблицы имеют следующий формат

Таблица машинных команд(MOT) Таблица псевдокоманд(POT)

----------------------- -----------------------

| Мнемоника | Код | | Мнемоника | Тип |

----------------------- -----------------------

| | | | ORG | 1 |

----------------------- -----------------------

| | | | CON | 2 |

| .... | | -----------------------

----------------------- | BSS | 3 |

| | | -----------------------

----------------------- | END | 4 |

-----------------------

| EQU | 5 |

-----------------------

Таблица (символов) меток(ST) Таблица литералов(LT)

----------------------- -----------------------

| Метка | Адрес | | Литерал | Адрес |

----------------------- -----------------------

| | | | | |

----------------------- -----------------------

| | | | | |

| .... | | | .... | |

----------------------- -----------------------

| | | | | |

----------------------- -----------------------

Во время первого просмотра заполняются таблицы меток и

литералов. Они в дальнейшем на втором просмотре исходного

текста. Укрупненная схема алгоритма первого просмотра

ассемблера показана на рис. 1.

В результате первого просмотра исходного текста

становятся известными значения меток и адресов литералов,

использованных в программе. Значения меток и адреса

литералов во время первого просмотра записываются в таблицу

меток и таблицу литералов и сохраняются до второго

просмотра. Цель второго просмотра текта программы состоит в

создании программы на машинном языке, то есть в генерации

последовательности машинных кодов. Коды команд и константы

записываются в определенной форме для последующей обработки

загрузчиком. Кроме того на втором просмотре формируется

листинг, содержащий текст исходной программы, эквивалентные

ему машинные коды, а также некоторые другие данные,

например, перечень всех меток и соответствующих им адресов.

истинг также содержит сообщения об обнаруженных ошибках.

Для работы ассемблера на втором просмотре требуются:

- текст исходной программы,

- счетчик адреса (LC),

- таблица машинных команд (MOT),

- таблица псевдокоманд (POT),

- таблица символов, или меток (ST), заполненная во время

первого просмотра,

- таблица литералов (LT), заполненная во время первого просмотра.

+-----------+

| Начало |

+-----------+

|

+-----------+

| LC = 0 |

+-----------+

+----->|

| +-----------+ Обозначения:

| | L = 0 | LC - значение счетчика команд;

| +-----------+ L - приращение счетчика адреса;

| | VAL - значение операнда;

| +-----------+ КОП - код операции;

| | Читать | POT - таблица псевдоопераций;

| | строку | MOT - таблица машинных операций;

| +-----------+

| |

| +-----------+

| | Выделить |

| | метку,КОП,|

| | операнд |

| +-----------+

| |

| +-----------+

| | Поиск КОП | найден

| | в таблице |-----------------------------------------------------+

| | РОТ | CON | BSS | EQU | ORG | END |

| +-----------+ | | | | |

| | | | | | |

| +-----------+ | +-----------+ +-----------+ +-----------+ |

| | Поиск КОП | | | Вычислить | | Вычислить | | Вычислить | |

| | МОТ | | | значение | | значение | | значение | |

| +-----------+ | | операнда | | операнда | | операнда | |

| |<-------------+ +-----------+ +-----------+ +-----------+ |

| | | | | |

| +-----------+ +-----------+ | +-----------+ |

| | L = 1 | | L = VAL | | | LC = VAL | |

| +-----------+ +-----------+ | +-----------+ |

| |<---------------------+<------------+ | |

| ---------- да +-----------+ | +-----------+

| / Метка \_____| Занести | | | Занести |

| \ есть ? / | метку в ST| | |адреса в LT|

| ---------- +-----------+ | +-----------+

| |<----------------+ | |

| ---------- да +-----------+ | |

| / Литерал \_____|Занести ли-| | |

| \ есть ? / |терал в LT | | Ко второму

| ---------- +-----------+ | проходу

| |<----------------+ | ассемблера

| +-----------+ |

| | LC=LC+L | |

| +-----------+ |

+------+<-------------------------------------------------+

Рис 1. Укрупненный алгоритм первого прохода

ассемблера

+-----------+

| Начало |

+-----------+

|

+-----------+

| LC = 0 |

+-----------+

+----->|

| +-----------+ Обозначения:

| | L = 0 | LC - значение счетчика команд;

| +-----------+ L - приращение счетчика адреса;

| | VAL - значение операнда;

| +-----------+ КОП - код операции;

| | Читать | POT - таблица псевдоопераций;

| | строку | MOT - таблица машинных операций;

| +-----------+ Об. - объектный;

| |

| +-----------+

| | Выделить |

| | метку,КОП,|

| | операнд |

| +-----------+

| |

| +-----------+

| | Поиск КОП | найден

| | в таблице |---------------------------------------------+

| | РОТ | CON | BSS | EQU | ORG | END |

| +-----------+ | | | | |

| | | | | | |

| +-----------+ | +-----------+ | +-----------+ |

| | Поиск КОП | | | Вычислить | | | Вычислить | |

| | МОТ | | | значение | | | значение | |

| +-----------+ | | операнда | | | операнда | |

| | | +-----------+ | +-----------+ |

| +-----------+ +-----------+ | | | |

| | Вычислить | | Сформиро- | | | | |

| | значение | | вать | | | +-----------+ |

| | операнда | |констананту| | | | LC = VAL | |

| +-----------+ +-----------+ | | +-----------+ |

| | | | | | |

| +-----------+ | | |<--------+ +-----------+

| |Собрать | | | | |Вывод |

| |команду из | | | | |литералов в|

| |КОП и VAL | | | | |Об. модуль |

| +-----------+ | | | +-----------+

| |<-------------+ | | |

| +-----------+ +-----------+ | +-----------+

| | L = 1 | | L = VAL | | | Конец |

| +-----------+ +-----------+ | +-----------+

| | | |

| +-----------+ | |

| |Вывод | | |

| |команды в | | |

| |Об. модуль | | |

| +-----------+ | |

| |<----------------------+ |

| +-----------+ |

| | LC=LC+L | |

| +-----------+ |

+------+<--------------------------------+

Рис 2. Укрупненный алгоритм второго прохода ассемблера

В процессе второго просмотра текста программы

ассемблер формирует:

- строки объектной программы,

- строки листинга.

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

соответствующие файлы. Кроме того листинг может выводиться и

на экран. Укрупненная схема алгоритма второго просмотра

ассемблера показана на рис. 2.

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

следующие функции стандартной библиотеки языка С:

a) Обработка строк (прототипы описаны в файле string.h)

strcat, strncat (сцепление строк);

strcmp, strncmp (сравнение строк);

strcpy, strncpy (копирование строк);

и другие

б) Проверка символов (прототипы описаны в файле ctype.h)

isalpha, isdigit, isxdigit, isupper, islower, isspace, isascii и другие.

Подробное описание этих и других библиотечных функций, их параметров

и возвращаемых значений можно найти в любом руководстве по программированию

на языке С или с помощью контекстно-зависимой подсказки в интегрированной

системе программирования на языке С.

2. Порядок выполнения работы

1. После собеседования получить вариант задания.

2. Ознакомиться с текстом файлов easm.c и easm.h

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

на языке С.

3. Разработать программу, вызывающую разработанную функцию и проверяющую

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

4. Провести тестирование и отладку разработанной функции.

5. Построить вариант ассемблера простой ЭВМ, в котором используется

разработанная функция. Для этого нужно

а) создать проект в среде VC 6.0 или VC 5.0 типа Win32 Console

Application

b) включить в проект исходный файл easm.c , который содержит текст

функции main() и все глобальные переменные и таблицы

включить в проект файл с текстом разработанной Вами функции;

включить в проект файл содержащий библиотеку объектных модулей нужных

для построения ассемблера простой ЭВМ - asmlib.lib;

c) в опциях Linker поставить галочку Force file output

d) построить программу в соответствии с проектом; имя построенной

программы будет совпвдать с именем проекта с расширением ".exe".

6. Проверить работу построенного ассемблера. В качестве тестового примера

использовать программу на языке ассемблера простой ЭВМ, разработанную

при выполнении лабораторной работы N1.

7. Составить отчет по pаботе. Отчет должен содержать:

- развернутую постановку задачи с описанием входных и

выходных данных;

- схему алгоритмов превого и второго просмотра ассемблера

с указанием места, в котором выполняется разработанная функция;

- текст разработанных функций;

- результат выполнения контрольного примера.

3. ВАРИАНТЫ ЗАДАНИЙ

1. Разработать функцию вычисления значения операнда

long Calculate_Val( char * Str_Val, int LC, int V_Type )

Интерфейс функции и структуры данных описаны в файле "EASM.H"

2. Pазработать функцию paзбора строки на метку, код

операции, операнд и комментарий

void String_Decomposition(char *String, LPDECOMPOSEDSTRING DecStr);

Интерфейс функции и структуры данных описаны в файле "EASM.H"

3. Paзработать функцию поиска кода операции в таблице

машинных операций. Реализовать алгоритм двоичного поиска в

упорядоченной таблице

long Find_MOT( char *key )

Интерфейс функции и структуры данных описаны в файле "EASM.H"

4. Разработать функцию, реализующую первый проход

ассемблера

int asm1( FILE *InputFile, FILE *ListFile );

Интерфейс функции и структуры данных описаны в файле "EASM.H"

5. Разработать функцию, реализующую первый проход

ассемблера

int asm2( FILE *InputFile, FILE *ListFile, FILE *OutputFile );

Интерфейс функции и структуры данных описаны в файле "EASM.H"

6. Разработать функции обработки таблицы символов

LPVOID ST_Init( int ST_Size );

int ST_Append( char *Label, int Adr )

long Find_ST( char *Label );

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

Интерфейс функций и структуры данных описаны в файле "EASM.H"

7. Разработать функцию определения типа операнда

int Val_Type( char *Str_Val )

Интерфейс функции и структуры данных описаны в файле "EASM.H"

8. Разработать функции обработки таблицы символов

LPVOID ST_Init( int ST_Size );

int ST_Append( char *Label, int Adr )

long Find_ST( char *Label );

реализующие хэш-таблицу символов с линейным рехешированием

Интерфейс функций и структуры данных описаны в файле "EASM.H"

9. Разработать функции обработки таблицы символов

LPVOID ST_Init( int ST_Size );

int ST_Append( char *Label, int Adr )

long Find_ST( char *Label );

реализующие хэш-таблицу символов со случайным рехешированием

Интерфейс функций и структуры данных описаны в файле "EASM.H"

10. Разработать функции обработки таблицы символов

LPVOID ST_Init( int ST_Size );

int ST_Append( char *Label, int Adr )

long Find_ST( char *Label );

реализующие хэш-таблицу символов с рехешированием сложением

Интерфейс функций и структуры данных описаны в файле "EASM.H"

11. Разработать функции обработки таблицы символов

LPVOID ST_Init( int ST_Size );

int ST_Append( char *Label, int Adr )

long Find_ST( char *Label );

реализующие таблицу символов в виде бинарного дерева

Интерфейс функций и структуры данных описаны в файле "EASM.H"

12. Разработать функции обработки таблицы символов

LPVOID ST_Init( int ST_Size );

int ST_Append( char *Label, int Adr )

long Find_ST( char *Label );

реализующие таблицу символов в виде двоичного сбалансированного дерева

Интерфейс функций и структуры данных описаны в файле "EASM.H"

4. Вопросы для самопроверки

1. Какие особенности языка ассемблера приводят к

необходимости простроения двухпросмотрового ассемблера?

2. Почему при трансляции программы, написанной на

языке ассемблера, достаточно двух просмотров исходного

текста программы?

3. Каким ограничениям должен удовлетворять текст

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

просмотр текста?

4. Почему адреса литералов становятся известными

только к началу второго просмотра?

5. Чем ограничена длина таблицы символов (меток)?

ЛАБОРАТОРНАЯ РАБОТА N 3

-----------------------

ПРОГРАММИРОВАНИЕ НА МАКРОЯЗЫКЕ

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

(макрогенератора), изучение методов разработки,

программирования и отладки программ на макроязыке на примере

гипотетической ЭВМ.

1. МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО ПОДГОТОВКЕ

К ЛАБОРАТОРНОЙ РАБОТЕ

Макроязык представляет собой расширение языка

программирования. Наиболее часто, хотя и не всегда,

расширяемым языком программирования является язык

ассемблера. В ряде языков программирования высокого уровня,

например в С, также имеются средства макропрограммирования.

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

собой расширение языка ассемблера простой ЭВМ.

Определим основные термины и понятия, относящиеся к

макроязыку и макрообработке.

Макроопределение - представляет собой набор строк

расширяемого языка (языка ассемблера) с присвоенным именем.

Макроопределение может иметь формальные параметры.

Макрокоманды, называемые также макро, - являются

однострочными сокраще- ниями для группы команд. Макрокоманда

представляет собой использование макроопределения.

Макрокоманда может иметь фактические параметры.

Макрорасширение - результат подстановки

макроопределения вместо макро- команды; при этой подстановке

формальные параметры заменяются на факти- ческие. Процесс

порождения макрорасширений называется макрогенерацией. В

результате макрогенерации формируется текст на языке

ассемблера.

Программа, выполняющая макрогенерацию, называется

макропроцессором или макрогенератором. Исходными данными для

макрогенератора является текст программы на макроязыке,

результатом - текст программы на языке ассемблера.

Макроопределения записываются в соответствии с

некоторыми формальными правилами. В рассматриваемом случае

формат макроопределения имеет следующий вид :

ИМЯ macro СПИСОК ПАРАМЕТРОВ

+-

| Тело

| макроопределения

|

+-

mend

Имя макроопределения записывается в поле метки, имеет

длину не более восьми символов и может содержать буквы цифры

и символ подчеркивания ( _ ). После того как

макроопределение определено в тексте программы его имя может

использоваться в поле кода операции как макрокоманда.

В списке параметров перечисляются формальные параметры

макроопределения, которые при макровызовах будут заменяться

фактическими параметрами. Каждый формальный параметр

начинается со специального символа ( & ), который служит

только для идентификации формальных параметров.

Список параметров имеет вид

&par1,&par2,...,&parN ,

где N<=15, пробелы между параметрами не допускаются. Имена

формальных параметров должны начинаться с символа '&' и

должны иметь длину не более восьми символов. В теле

макроопределения формальные параметры могут фигурировать в

поле метки,кода операции или аргумента. В качестве фак-

тических параметров разрешается использовать выражения,

представляющие собой метку, код операции или операнд.

Макроопределение обязательно должно заканчиваться

словом 'mend' в поле кода операции.