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

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

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

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

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

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

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

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

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