Таблицы и алгоритмы ассемблера

Наш простой ассемблер использует две основные внутренние таблицы: таблицу кодов операций (ОРТАВ) и таблицу символических имен (SYMTAB). ОРТАВ используется для поиска мнемонических кодов операций и перевода их в эквивалентные им представления на машинном языке SYMTAB используется для хранения значений (адресов), присвоенных символическим именам.

Еще нам потребуется счетчик адреса (LOCCTR). LOCCTR это переменная, которая используется для назначения адресов. Начальное значение LOCCTR определяется операндом предложения START. После обработки очередного предложения исходной программы длина полученной команды или области данных прибавляется к LOCCTR. Таким образом, если мы встречаем помеченное предложение исходной программы, то значение этой метки определяется текущим значением LOCCTR.

Таблица кодов операций должна по крайней мере содержать мнемонические коды операций и их машинные эквиваленты. В более сложных ассемблерах эта таблица, кроме того, содержит информацию о длине и формате каждой команды. Во время первого просмотра ОРТАВ используется для поиска и проверки корректности задания кодов операций в исходной программе. Во время второго просмотра она используется для перевода мнемонических кодов в их машинное представление. Фактически в нашем простом ассемблере для УУМ оба эти процесса можно совместить в одном просмотре (неважно, в первом или во втором). Однако для машин, имеющих форматы команд переменной длины (например, УУМ/ДС), нам необходимо просматривать ОРТАВ и при первом просмотре для того, чтобы определить приращение переменной LOCCTR. При втором просмотре мы используем ОРТАВ для определения формата и других специальных характеристик ассемблируемой команды. В нашем случае мы решили придерживаться именно этой структуры, поскольку она типична для большинства ассемблеров.

 

Pass1:

begin

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

if OPCODE = "START" then

begin

запомнить #[OPERAND] в качестве начального адреса

занести начальный адрес в LOCCTR

записать строку в промежуточный файл

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

end

else

занести 0 в LOCCTR

while OPCODE <> "END" do

begin

if это не строка-комментарий then

begin

if есть символ в поле метки then

begin

поиск метки в SYMTAB

if нашли then

занести признак ошибки (второе определение)

else

занести (LABEL, LOCCTR) в SYMTAB

end

поиск OPCODE в OPTAB

if нашли then

прибавить 3 { длина команды } к LOCCTR

else if OPCODE = "WORD" then

прибавить 3 к LOCCTR

else if OPCODE = "RESW" then

прибавить 3 * #[COPERAND] к LOCCTR

else if OPCODE = "RESB" then

прибавить #[COPERAND] к LOCCTR

else if OPCODE = "BYTE" then

begin

определить длину константы в байтах

прибавить длину к LOCCTR

end

else

занести признак ошибки (неверный код операции)

end { if не комментарий }

записать строку в промежуточный файл

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

end { while }

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

запомнить (LOCCTR – начальный адрес) в качестве длины программы

end { Pass 1 }

Рис.2.4а. Алгоритм первого просмотра ассемблера.

 

 

Pass2:

begin

прочитать первую входную строку (из промежуточного файла)

if OPCODE = "START" then

begin

выдать строку листинга

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

end

занести запись – заголовок в объектную программу

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

while OPCODE <> "END" do

begin

if это не строка-комментарий then

begin

поиск OPCODE в OPTAB

if нашли then

begin

if в поле операнда есть имя then

begin

поиск имени в SYMTAB

if нашли then

запомнить значение имени

в качестве адреса операнда

else

begin

запомнить 0 в качестве адреса операнда

занести признак ошибки (имя не определено)

end

end { if есть имя }

else

запомнить 0 в качестве адреса операнда

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

end { if нашли }

else if OPCODE = "BYTE" или "WORD" then

преобразовать константу в объектное преставление

if объектный код не помещается

в текущей записи тела программы then

begin

занести текущую запись в объектную программу

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

end

занести объектный код в запись тела программы

end { if не комментарий }

выдать строку листинга

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

end { while }

занести последнюю запись тела в объектную программу

занести запись – конец в объектную программу

выдать последнюю строку листинга

end { Pass 2 }

Рис.2.4б. Алгоритм второго просмотра ассемблера.

 

Обычно ОРТАВ организуется в виде хеш-таблицы (В нашей литературе иногда используется термин "перемешанные таблицы"), в которой в качестве ключа используется мнемонический код операции. (Конечно, ОРТАВ строится заранее - при создании ассемблера, а не во время его работы.) Такая организация очень удобна, поскольку обеспечивает быстрый поиск при минимальном числе сравнений. В большинстве случаев ОРТАВ представляет собой статическую таблицу, т. е. в процессе работы в ней не создаются новые элементы, а уже определенные не исключаются. В этом случае можно построить специальную хеш-функцию или другую структуру данных, обеспечивающую для конкретного набора ключей оптимальное время доступа. Однако чаще всего используются стандартные хеш-функции. Подробную информацию о построении хеш-таблиц можно найти в любом хорошем учебнике по структурам данных, например в Стендиш [1980] или Кнут [1973б].

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

Для повышения эффективности поиска и внесения новых имен SYMTAB обычно организуется также в виде хеш-таблицы. Поскольку операция исключения элемента из таблицы применяется крайне редко (скорее никогда)то вопрос об эффективности ее выполнения не возникает. Интенсивное использование SYMTAB на протяжении всей работы ассемблера требует тщательного подбора хеш-функции. Очень часто программисты используют много похожих друг на друга имен, например имена, начинающиеся или заканчивающиеся одними и теми же символами (такие как LOOP1, LOOP2, LOOPA)или имена, имеющие одинаковую длину (А, X, Y, Z). Важно, чтобы используемая хеш-функция обеспечивала хорошую работу с такими неслучайными именами. Часто хороший результат достигается путем деления входного ключа на простое число, равное длине таблицы.

Хотя в качестве входной информации на этапе второго просмотра можно использовать исходную программу, однако должна быть учтена и информация, полученная ранее - после первого просмотра (например, адрес предложения или признак ошибки). Поэтому обычно во время первого просмотра создается промежуточный файл, который содержит каждое предложение исходной программы вместе с его адресом, признаком ошибки и другой необходимой информацией. Промежуточный файл является входным для второго просмотра. Рабочая копия исходной программы, содержащаяся в промежуточном файле, может быть использована для того, чтобы сохранить результаты некоторых операций, выполненных во время первого просмотра (например, операции сканирования поля операндов для определения имен и способов адресации). Это дает возможность не выполнять их еще раз при втором просмотре. Аналогично для кодов операций и имен могут быть сохранены указатели на таблицы ОРТАВ и SYMTAB, что позволит избежать повторных операций поиска.

На рис.2.4а и 2.4б представлены алгоритмы соответственно первого и второго просмотров нашего ассемблера. Эти алгоритмы, несмотря на то что они описывают простой ассемблер, являются основой для более сложных двухпросмотровых ассемблеров, которые мы рассмотрим позднее. Для простоты мы будем полагать, что исходная программа записана в фиксированном формате с полями МЕТКА, ОПЕРАЦИЯ и ОПЕРАНДЫ. Если какое-либо из этих полей содержит строку символов, представляющую число, мы будем обозначать это с помощью префикса # (например, #[OPERAND]).

На данном этапе очень важно, чтобы вы досконально разобрались с алгоритмами, представленными на рис. 2.4а и 2.4б. Вам настоятельно рекомендуется тщательно разобраться в этих алгоритмах, применив их для ручной трансляции программы на рис.2.1 в ее объектное представление на рис. 2.3.

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