Теория языков программирования методов трансляции (стр. 37 )

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

Для многих языков программирования в общем случае число возможных идентификаторов хотя и конечно, но очень велико.

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

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

CAR DOG CAB ASS EGG

таблица примет вид табл.7.1; позиции идентификаторов зависят от порядка их внесения в таблицу.

Если идентификатор не может быть внесен в ту позицию, которая задается функцией хеширования, происходит так называемый конфликт. Чем больше таблица (и меньше число идентификаторов, отражающихся на каждую запись), тем меньше вероятность конфликтов. При наличии в программе только вышеперечисленных идентификаторов и использовании рассмотренной функции хеширования таблица заполнялась бы неравномерно, и имела бы место кластеризация. Функция хеширования, которая зависела бы от последней литеры идентификатора, вероятно, меньше бы способствовала кластеризации. Конечно, чем сложнее функция, тем больше времени требуется для ее вычисления при внесении в таблицу идентификатора или при поиске конкретного идентификатора в таблице. Поэтому выбор функции хеширования – важная задача при построении компиляторов.

Таблица 7.1.

1 2 3 4 5 6 7 .

ASS CAR DOG CAB EGG

Обычно выход из конфликтов осуществляется циклической проверкой один за другим элементов таблицы до тех пор, пока не находится идентификатор или пустой элемент. Однако на практике используются и другие методы. Обычно вырабатывается некоторое правило, последовательное применение которого позволило бы (при необходимости) просмотреть все записи таблицы, прежде чем какая-либо из них встретится вторично. Действие, выполняемое функцией хеширования, называют первичным хешированием, а вычисление последующих адресов в таблице – вторичным хешированием или перехешированием. Функция перехеширования, рассматриваемая в примере, предполагает просто добавление единицы (циклично) к адресу таблицы. Эта функция, как и все функции хеширования, обладает следующим свойством: если n – некий адрес в таблице, а p – число элементов в таблице, то

все являются адресами, и

.

Описанная выше функция перехеширования определяется процедурой

int procedure rehash(int n)

if n<p then n+1 else 1.

У этой функции есть тенденция создавать в таблице кластеры в той же мере, в какой вероятность кластеризации возрастает в связи с перехешированием. Весьма желательно, чтобы функция перехеширования могла находить адреса подальше от того, с которого начала. Если элементы таблицы простые числа (т. е. не имеют других делителей кроме 1), то вместо 1 функция перехеширования может добавлять к адресу любое положительное целое число h, такое что h<p; в результате бы имели

int procedure rehash(int n)

if n+h<p then n+h else n+h-p.

Подходящее значение h сводило бы кластеризацию к минимуму. Так как p - простое число, функция перехеширования выдаст последовательно все адреса в таблице, прежде чем она повторится.

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

·  Сцепление элементов. В этом случае переполнения таблиц можно избежать путем использования указателей (рис. 7.1.)

AGE
BAT
CAT				COW				CASE

Рис. 7.1. Сцепление элементов

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

·  Бинарное дерево. Бинарное дерево (рис. 7.2.) состоит из некоторого количества вершин, каждая из которых содержит идентификатор, его тип и т. д., и двух указателей на другие вершины.

LEMON

EGG

MOUSE

BUS

HADDOCK

Рис. 7.2. Бинарное дерево

Бинарное дерево, приведенное на рис. 7.2, упорядочено в алфавитном порядке слева направо (т. е. его вершины расположены в алфавитном порядке их обхода изнутри). Поддерево любой вершины обозначается с помощью указателя. Поиск осуществляется с использованием рекурсивного алгоритма обхода: пересечь левое поддерево, пройти корень, пересечь правое поддерево. К бинарному дереву всегда можно добавить новую вершину, поместив ее в соответствующее место. Время поиска зависит от глубины дерева.

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

8.3.  Таблица видов

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

В существующих языках существует 5-7 вариантов видов:

1)  основные виды, например int, real, char, bool и др.;

2)  длинные и короткие виды, которые содержат символы long или short, появляющиеся перед основными видами;

3)  указатели на адрес ячейки памяти, выделенной для данного вида;

4)  структурные виды, типа struct и последовательностью полей; каждое поле имеет вид и селектор, обычно заключенные в скобки;

5)  виды массивов;

6)  объединенные виды, состоящие из символов union или void, используемых для выражения значений, которые могут принадлежать нескольким видам;

7)  виды процедур, представленные символами procedure, function и др., используемых для выражения значений, являющихся процедурами.

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