Таблицы символов общие замечания

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

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

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

Очень часто распределение ключей таково, что размещение и поиск информации занимают значительное время, поскольку трудно расположить элемент в таблице, используя его ключ непосредственно. В этом случае положение элемента в таблице определяет не сам ключ, а другое производное от него значение. Функция отображения М определяется таким образом, что для любого ключа k величина Мк дает производный ключ для отыскания позиции в таблице того элемента, который идентифицируется ключом k. Функция М вырабатывает более простые и более эффективные (по сравнению с исходными) ключи для доступа к входам таблицы. Простой способ построения такой отображающей функции будет показан позднее в атом разделе. Некоторые более сложные процедуры обсуждаются в разд. 9.3.2.

Два общих способа построения таблиц иллюстрируются на рис. 5.6. На диаграмме (а) показана таблица с ключами, а на диаграмме (Ь) — таблица с производными ключами и указателями. Возможны также и другие комбинации, такие, как таблица <: ключами и указателями и таблица с производными ключами.

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

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


Что такое ассемблер? Языки ассемблеров Команды языка ассемблера Код операции Псевдооперации Литералы Свободный формат команд Некоторые типичные команды ассемблера для машин с побайтовой организацией Ассемблеры типа «трансляция — выполнение» Однопроходный ассемблер Двухпроходный ассемблер Символы Подробная блок-схема прохода Подробная блок-схема прохода 2 Пример трансляции Таблицы символов общие замечания Обработка таблицы Линейный поиск Двоичный поиск Сравнение двоичного и линейного способов поиска Метод хеширования Пример хеширования Скученность Назначение макрокоманды Различие между макрокомандами и подпрограммами Форматы макрокоманды Ключевой макрос Макропроцессор	Таблицы символов общие замечания Когда программы писались в машинном коде, наиболее утомительной работой было вычисление адресов операндов и запоминание всех двоичных кодов машины. Ассемблеры освобождают программистов от этого механического труда. Основная часть работы ассемблеров связана с преобразованием символических представлений адресов операндов и мнемонических кодов операций в двоичную форму. Это преобразование выполняется посредством таблиц символов. Содержимое таблицы обычно хранится в виде вектора, компонентами которого являются отдельные элементы (или входы). Каждый элемент имеет уникальный ключ, под которым он и связанная с ним информация размещаются в таблице. Например, в англо-венгерском словаре английское слово, для которого требуется венгерский эквивалент, является ключом к элементу таблицы, а венгерское слово (или слова) — связанной с ним информацией. В таблицах символов, которые строят ассемблеры, в качестве ключей выступают использованные в программе символы или идентификаторы, а основными элементами информации являются адреса регистров памяти, присвоенных этим символам. Часто оказывается желательным иметь в таблице единообразные элементы. Так как информация может широко варьироваться как по форме, так и по длине, вместе с ключом хранится не сама фактическая информация, а указатель на нее. Примером такой организации таблицы может служить предметный указатель книги. Перечисленные в предметном указателе понятия являются ключами, а расположенные за ними номера страниц — указателями, показывающими, где можно найти желаемую информацию. Очень часто распределение ключей таково, что размещение и поиск информации занимают значительное время, поскольку трудно расположить элемент в таблице, используя его ключ непосредственно. В этом случае положение элемента в таблице определяет не сам ключ, а другое производное от него значение. Функция отображения М определяется таким образом, что для любого ключа k величина Мк дает производный ключ для отыскания позиции в таблице того элемента, который идентифицируется ключом k. Функция М вырабатывает более простые и более эффективные (по сравнению с исходными) ключи для доступа к входам таблицы. Простой способ построения такой отображающей функции будет показан позднее в атом разделе. Некоторые более сложные процедуры обсуждаются в разд. 9.3.2. Два общих способа построения таблиц иллюстрируются на рис. 5.6. На диаграмме (а) показана таблица с ключами, а на диаграмме (Ь) — таблица с производными ключами и указателями. Возможны также и другие комбинации, такие, как таблица <: ключами и указателями и таблица с производными ключами. Таблицы можно разделить на две группы в зависимости от их размера. В первой группе максимальное число входов постоянно и известно заранее. Однако фактическое число входов может меняться, так как не все места в таблице должны быть заполнены. Порядок элементов в таблице может быть изменен, но размер таблицы меняться не должен. Очень простая таблица фиксированного размера — таблица кодов машинных операций, размеры которой, а также длина ключа и связанной с ним информации фиксированы. Более сложными являются таблицы, максимальное число возможных входов в которые заранее неизвестно. В этом случае могла бы быть выбрана очень большая верхняя граница для размера таблицы, но это привело бы к большим потерям пространства в среднем. На практике, однако, лучше выделить под таблицу меньшую область памяти и расширять ее по мере необходимости. Таблицы символов, образуемые ассемблерами и компиляторами, принадлежат к этой последней категории, так как число появляющихся в программах символических адресов меняется в широких пределах.