Некоторые структуры данных 1-го прохода

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

Таблица директив содержит одну строку для каждой директивы Обработка каждой директивы происходит по индивидуальному алгоритму, поэтому параметры обработки нельзя представить в виде данных единого для всех директив формата. Для каждой директивы в таблице хранится только идентификация (имя или адрес, или номер) процедуры Ассемблера, выполняющей эту обработку. Некоторые директивы обрабатываются только на 1-м проходе, некоторые — только на 2-м, для некоторых обработка распределяется между двумя проходами.

Таблица символов является основным результатом 1-го прохода Ассемблера. Каждое имя, определенное в программе, должно быть записано в таблице символов. Для каждого имени в таблице хранится его значение, размер объекта, связанного с этим именем и признак перемещаемости/неперемещаемости. Значением имени является число, в большинстве случаев интерпретируемое как адрес, поэтому разрядность значения равна разрядности адреса.

Перемещаемость рассматривается в разделе, посвященном Загрузчикам, здесь укажем только, что значение перемещаемого имени должно изменяться при загрузке программы в память. Имена, относящиеся к командам или к памяти, выделяемой директивами DD, BSS, как правило, являются перемещаемыми (относительными), имена, значения которых определяются директивой EQU, являются неперемещаемыми (абсолютными).

Таблица литералов содержит запись для каждого употребленного в модуле литерала. Для каждого литерала в таблице содержится его символьное обозначение, длина и ссылка на значение. Литерал представляет собой константу, записанную в памяти. Обращение к литералам производится так же, как и к именам ячеек программы. По мере обнаружения в программе литералов Ассемблер заносит их данные в так называемый литеральный пул. Значение, записываемое в таблицу литералов является смещением литерала в литеральном пуле. После окончания 1-го прохода Ассемблер размещает литеральный пул в конце программы (то есть, назначает ему адрес, соответствующий последнему значению счетчик адреса) и корректирует значения в таблице литералов, заменяя их смещениями относительно начала программы. После выполнения этой корректировки таблица литералов может быть совмещена с таблицей символов.

Структура таблиц Ассемблера

Структура таблиц Ассемблера выбирается таким образом, чтобы обеспечить максимальную скорость поиска в них.

Таблицы команд и директив являются постоянной базой данных. Они заполняются один раз — при разработке Ассемблера, а затем остаются неизменными.

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

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

Таблица символов формируется динамически — в процессе работы 1-го прохода. Поиск же в этой таблице осуществляется как в 1-м проходе (перед занесением в таблицу нового имени, проверяется, нет ли его уже в таблице).

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

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

Эти же соображения относятся и к другим таблицам, формируемым Ассемблером в процессе работы. При больших размерах таблиц и размещении их на внешней памяти могут применяться и более сложные (но и более эффективные) методы их организации, например — B+-деревья.