МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО

ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

_________________________

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ АВИАЦИОННЫЙ ИНСТИТУТ

(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)

_________________________

Ю.А.ГОЛУБКОВ

А.С.АЛЕЩЕНКО

СИСТЕМНОЕ ПРОГРАММИРОВАНИЕ

ЛАБОРАТОРНЫЕ РАБОТЫ

Часть I

Проектирование простейшего символического ассемблера

Москва

2000

Лабораторная работа №1

ОБРАБОТКА ТЕКСТА ПРИ АССЕМБЛИРОВАНИИ

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

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

Когда ассемблеру требуется очередной элемент, он обращается ко второму модулю ввода. Если этот модуль исчерпал запас входных символов (конец строки), то автоматически вызывается первый модуль для пополнения буфера. В простейшем случае при разборке строки могут встретиться следующие конструкции:

• метка (последовательность символов), которая начинается с буквы и состоит из букв и цифр. Метка может отсутствовать;

• константа (последовательность цифр);

• разделитель (пробел, запятая или точка);

• ограничитель (конец поля КП, конец строки КС);

• мнемокод операции;

• операнды, разделенные запятыми.

Модуль ввода при обращении к нему выдает очередной элемент и код (0,1,2,3,…), отвечающий типу элемента. Если формат входного текста фиксирован, то выделение полей упрощается. Не вызывает затруднений и случай, когда мнемокод операнда заканчивается пробелом. Первый пробел считается разделителем, а остальные пропускаются до появления символа, отличного от пробела.

При свободном формате требуется более сложный контекстный анализ. Предположим, что поле метки, если она присутствует, заканчивается символом “:”, мнемокод ограничен пробелом, а поле операнда ограничено символом “;”. Тогда алгоритм разделения полей можно представить следующим образом.

1. Пропустить начальные пробелы.

2. Прочесть очередной термин: он должен быть последовательностью символов, которые соответствуют или мнемокоду или метке. Если это метка, то ее ограничивает символ “:”.

3. Прочесть очередной термин: очевидно, он должен быть пробелом, т.е. это конец поля мнемокода.

4. Прочесть очередной термин ; теперь это должен быть операнд. Далее читаем следующий термин. Он должен быть запятой, если далее идет очередной операнд, или символом конца строки.

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

Это возможно, т.к. в большинстве случаев еще до введения очередного термина нам известно, какого типа он должен быть. Например, поле метки или поле мнемокода содержит символы. Поэтому можно ввести индикатор типа термина Е. Получив очередной термин, мы можем определить его тип. А далее сравнить полученный тип с тем, который должен быть. При несоответствии формируется сообщение об ошибке.

Например,

Значение Е	Ожидаемый термин
1	символ (буква)
2	ограничитель : (конец поля метки)
3	символ мнемокода
4	ограничитель мнемокода (пробел)
5	запятая
6	конец строки (;)
7	символ цифры

Тогда можно вести проверку по такой схеме. Для упрощения предположим, что длина метки не превосходит 5 символов (первая буква, остальные цифры или буквы), длина мнемокода – три буквы. Очевидно, что строка программы может начинаться с метки или непосредственно с мнемокода. В обоих случаях первый символ буква, т.е. ожидаемое значение Е1. Если полеченное значение Е1, имеем ошибку. Можно регистрировать место появления ошибки (номер строки от начала).

Считываем очередной элемент строки. Это может быть или цифра (если это метка) или буква, т.е. ожидаемое значение Е={1 или 7}. Если появится символ “:” (Е=2), то имеем метку. Заметим, что появление пробела говорит о том, что это был мнемокод. Причем число символов в метке не может быть более 5.

Задание

Требуется спроектировать программу разбора текста строки при заданном формате с выработкой сообщения об ошибке указанного типа в соответствии с вариантом задания. При наличии в исходном тексте ошибок другого рода предусмотреть прерывание процесса обработки без индикации типа ошибки.

Продемонстрировать работу на собственной программе, соответствующей принятым допущениям.

Варианты заданий

№ варианта	Формат строки	Максимальная длина метки	Максимальное число операндов в строке	Фиксируемая ошибка
	Фиксированный	5	2	Превышение длины метки
	Свободный	6	3	Неверный ограничитель после метки
	Фиксированный	7	4	Неверный мнемокод
	Свободный	5	3	Неверный ограничитель в поле операндов
№ варианта	Формат строки	Максимальная длина метки	Максимальное число операндов в строке	Фиксируемая ошибка
	Фиксированный	7	2	Неверный ограничитель после мнемокода
	Свободный	7	3	Ошибка в константе
	Фиксированный	6	2	Не обозначен конец строки
	Свободный	5	4	Превышение числа операндов

Лабораторная работа №2

ОБРАБОТКА МЕТОК СИМВОЛИЧЕСКИМ АССЕМБЛЕРОМ

В РАМКАХ ПЕРВОГО ПРОХОДА

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

В данной лабораторной работе рассматривается процесс построения программы, которая выполняет обработку меток, т.е. формирует таблицу вида «символическая метка  адрес (номер строки) ее появления в тексте программы».

Упрощающие допущения:

1. Программа – это последовательность строк фиксированного формата. Последняя строка программы содержит признак конца программы, например, ‘E’.

2. Текст программы не содержит псевдокоманд, т.е. нет дополнительных символических имен.

3. Каждая строка отвечает машинной команде в символическом виде. Предполагаем, что она имеет жесткий формат и состоит из нескольких полей. Первое поле – это поле метки. Это поле включает 5 символов. Метка может отсутствовать. Она обязательна, если на эту строку есть ссылка в команде перехода.

Метка называется символическим именем. Ошибкой является появление двух одинаковых меток в тексте программы («переопределение» меток), т.к. возникает неопределенность перехода. В качестве метки можно использовать группу от одного до 5 символов. Первый символ – буква, последующие – буквы или цифры. Будем считать, что если число символов менее 5, то метка дополняется пробелами.

В основе работы первого прохода упрощенного ассемблера находится использование счетчика строк, т.е. некоторой переменной i, которая увеличивается на 1 после обработки каждой строки входной программы. При отсутствии ПСК можно считать, что в качестве начального значения i ассемблер использует стандартное значение. Например, i = 0 (отсчет от начала программы). Будем для простоты считать, что длина строки входной программы кратна байту. Следовательно, если в строке, отвечающей счетчику с номером i = i_o, есть метка, то можно определить адрес строки, где появляется эта метка.

На первом проходе символические метки заносятся в таблицу символов (меток), и в качестве значения им присваивается текущее состояние счетчика размещения (i). Т.к. счетчик отсчитывает от начала программы, то тип значения метки – относительный. Строка таблицы символов имеет вид:

Символ метки

Значение (относительно начала программы)

При заполнении таблицы символов потребуется вести проверку на повторное вхождение. Если символ уже встречался в таблице, то эту повторно определенную метку следует поместить в другую таблицу с соответствующим значением счетчика. Это таблица “переопределенных” меток, а номера соответствующих значений указывают место их появления в тексте входной программы (места переопределения).Такая таблица отмечает ошибки (error) во входной программе, но, естественно, не все. Желательно использовать для таблицы символов ХЭШ-таблицу.

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

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

Задание

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

Продемонстрировать работу на собственной программе, соответствующей принятым допущениям.

Варианты заданий

№ варианта	Формат строки	Максимальная длина метки	Максимальное число строк в программе	Максимальное число меток
	Фиксированный	5	20	10
	Фиксированный	4	25	12
	Фиксированный	6	15	10
	Фиксированный	5	18	8
	Фиксированный	4	22	15
	Фиксированный	6	24	8
	Фиксированный	4	25	10
	Фиксированный	5	20	8

Лабораторная работа №3

ОБРАБОТКА СТРОК ВХОДНОЙ ПРОГРАММЫ

В РАМКАХ ВТОРОГО ПРОХОДА

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