Свойства и принципы построения таблиц ассемблера

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

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

Д/З: в конспекте, понятия:

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

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

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

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