В мир информатики # 89 (1–15 апреля).
Эксприменты

Отладчик Debug и язык Ассемблер

Е.А. Еремин,
г. Пермь

Конструируем программу-ассемблер сами

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

Разумеется, мы возьмем максимально простую систему машинных кодов — систему команд вычислительной машины, которая предложена в учебнике [1]; она называется “Кроха”. Полный перечень команд “Крохи” приведен в табл. 4, где для каждой операции также указана ее мнемоника (в исходном учебнике не использовалась). Мнемонические имена команд выбраны вполне стандартными и совпадают с принятыми в ассемблере компьютеров типа IBM PC.

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

· Каждая команда занимает отдельную строку, пустые строки запрещены. Согласно устройству “Крохи”, любая команда занимает ровно одну ячейку, значит, номер ячейки фактически совпадет с номером строки.

· Части команды (метка, операция и три адреса) разделены между собой произвольным количеством пробелов (M: ADD X Y R).

· Все метки (идентификаторы) условимся обозначать одной латинской буквой, после которой ставится двоеточие. Хотя это и несложно, проверять каждую новую метку на совпадение со старыми не будем; факт того, что это именно латинская буква, для простоты также не проверяется.

· Константы (десятичные числа), заносимые ассемблером в ячейки, будем записывать после обозначения DN, например, DN 19. Правильность значения константы (для “Крохи” она должна быть целой и неотрицательной, не превышающей 4095) контролировать не будем.

· Так как практическая эксплуатация нашего программного продукта не предполагается, диагностику ошибок в нем предусматривать не будем (известно, что часто это наиболее трудоемкая часть процесса разработки программы).

· Вместо длинных 12-разрядных двоичных кодов, которые вполне оправданны в учебнике для демонстрации принципов фон Неймана, везде будем пользоваться более короткими восьмеричными кодами; подчеркнем, что данная система прекрасно гармонирует с командами “Крохи”, у которых и код операции, и адреса состоят именно из трех двоичных разрядов.

Таблица 4

Благодаря принятым упрощениям ассемблирующая программа на Паскале получается совсем небольшой (ниже приводится ее листинг).

Program kroha_asm;

Const

{Мнемоники команд}

kop: Array[0..7] Of string[3] = ('MOV','ADD','DIV','SUB','JE','MUL','JG','HLT');

{Ассемблируемая программа}

prg: Array [0..7] Of String =

('B: MUL F K F',

' ADD K E K',

' JG N K B',

' HLT F F F',

'K: DN 1',

'F: DN 1',

'N: DN 3',

'E: DN 1');

Var

{tab – массив всех идентификаторов (их имя и код)}

tab: Array [0..15] Of Record

sym: string[3]; num: byte

End;

{Вспомогательные переменные}

i, Nid, k, e, c: integer;

{Функция Get_code выделяет из строкис номером i, начиная с позиции k,

очередной идентификатор и находит в массиве tab его код}

Function Get_code(i: integer; Var k: integer): byte;

Var p, id: string; j, m, q: integer;

{Вспомогательные переменные}

Begin

p := prg[i] + ' '; {Добавим пробел для удобства выделения последней метки}

While (k < Length(p)) And (p[k] = ' ') Do

k := k + 1; {Пропускаем пробелы,а затем выберем все до следующего пробела, т.е. получим имя идентификатора}

id := '';

While p[k] <> ' ' Do

Begin

id := id + p[k]; k := k + 1

End;

q := 255;

{Найдем идентификатор, если он есть в массиве, и поместим его код в переменную q}

For j := 0 To Nid Do

If id = tab[j].sym Then q := tab[j].num;

{Результатом функции является код, заносимый в программу}

Get_code := q

End;

BEGIN {Основная часть программы}

FOR i := 0 To 7 Do

{Заносим в массив tab имена и коды операций}

Begin

tab[i].sym := kop[i]; tab[i].num := i

End;

{Добавляем условный код для констант DN}

tab[8].sym := 'DN';

tab[8].num := 8;

Nid := 8;

{Первый проход – занесение в массив tab меток программиста}

For i := 0 To 7 Do

If prg[i][2] = ':' Then

{после метки — двоеточие}

Begin

{Добавляем метку в массив; (ее адрес равен номеру строки!)}

inc(Nid);

tab[Nid].sym := prg[i][1];

tab[Nid].num := i;

{Удаляем метку из текста}

prg[i][1]:=' ';

prg[i][2]:=' '

End;

{Для контроля выведем массив tab}

For i := 0 To Nid Do

Writeln(tab[i].sym:4, tab[i].num:4);

{Второй проход – генерация кода программы и вывод его на экран}

For i := 0 To 7 Do

Begin

k := 1;

c := Get_code(i, k); {Код операции}

{Выделяем команды или DN}

Case c Of

0..7: {код операции}

Begin

Write(c);

While k <= Length(prg[i]) Do {3 адреса}

Write(' ', Get_code(i, k))

End;

8:{DN}

Begin

{Выделяем десятичное число и переводимего в восьмеричную систему}

Val(Copy(prg[i], k, 255), k, e);

Write(' '); e := 512;

Repeat

Write(k Div e);

k := k Mod e; e := e Div 8

Until e = 0

End {Конец случая с = 8}

End; {Конец вывода команды}

Writeln

END.

Программа работает следующим образом. Ядром ее данных служит массив tab с данными типа “запись”, в котором содержатся сведения об идентификаторах — их имена (в поле sym) и коды, которые вместо этих имен надо подставлять в программу (поле num). Например, операция ADD имеет код 1 (см. табл. 4), поэтому tab[1].sym = 'ADD' и tab[1].num = 1. Становится очевидным, что центральная идея работы программы-ассемблера состоит в замене каждого символьного имени соответствующим ему числовым кодом (на основе массива tab).

После занесения в строки таблицы с номерами от 0 до 7 мнемоник команд “Крохи” добавим далее оператор определения константы DN и все найденные в программе метки, которые поставил пользователь в тексте. Метки пользователя распознаются по наличию после них двоеточия; чтобы обработанные метки не мешали ассемблеру в дальнейшем, программа их просто стирает. Обработка меток в литературе носит название первого прохода, поскольку сначала надо “пройти” всю программу и подготовить полную таблицу идентификаторов, и только потом повторно просмотреть текст (второй проход), заменяя с помощью массива tab все идентификаторы их кодами.

При выполнении второго прохода наш ассемблер опирается на “мощную” функцию Get_code, которая выделяет из текста программы очередной идентификатор. Несмотря на сложный вид, идея функции достаточно проста: в заданной строке, начиная с заданной позиции, она пропускает пробелы, а затем, наоборот, “собирает” все отличающиеся от пробела символы, формируя тем самым имя очередного идентификатора. Когда имя выделено, оно ищется в таблице, и в качестве результата выдается его код (или 255, если имя в таблице отсутствует).

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

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

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

Для тестирования демо-ассемблера реализована традиционная задача — вычисление факториала числа n. Обозначим k вспомогательную переменную, которая является текущим множителем для факториала и меняется от 1 до n. Тогда итоговая программа приобретает вид, приведенный в табл. 5.

Таблица 5

Второй столбец данной таблицы может быть использован для проверки результатов ассемблирования, которые наша программа выводит на экран. Более подробно программа вычисления факториала для “Крохи” рассматривалась в недавней публикации [2].

В качестве продолжения нашего эксперимента предлагаем читателям самостоятельно написать обратную программу — диcассемблер, которая по восьмеричному 4-разрядному коду восстанавливает ассемблерную мнемонику команд³. Для решения задачи советуем воспользоваться массивом, аналогичным массиву tab, разделив его, если потребуется, на части. Разумеется, первоначальные имена меток по коду не восстановить, поэтому можно присваивать им по мере появления последовательные значения букв латинского алфавита.

А теперь подведем итоги того, что мы узнали.

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

Примечание. В последнее время появляются и более причудливые схемы трансляции с языков высокого уровня. Например, в языке Ява (Java) компилятор транслирует текст программы в код некоторой виртуальной машины; тем самым итоговый результат компиляции также перестает быть машинно-зависимым. Вся “привязка” к конкретному компьютеру сосредоточена теперь в реализации Ява-машины, которая разрабатывается один раз и способна исполнить на данной платформе любую Ява-программу вне зависимости от того, на какой машине она была откомпилирована. Похожие идеи заложены и в идеологию платформы .NET (читается “дот-нэт”, или “точка-нэт”) фирмы Microsoft: компилятор с любого языка программирования генерирует код для единой виртуальной машины. Таким образом, делаются попытки сделать машинно-независимым не только исходный текст программы на языке высокого уровня, но и результат его компиляции.

Литература

1. Гейн А.Г., Линецкий Е.В., Сапир М.В., Шолохович В.М. Информатика. М.: Просвещение, 1994.

2. Еремин Е.А. Моделирование работы ЭВМ с помощью программы Microsoft Excel. / Информатика № 21–22/2006.

³ Программу, пожалуйста, пришлите в редакцию. Все приславшие правильную программу будут награждены дипломами. — Ред.