Простейшие способы организации таблицы идентификаторов

Определение таблица идентификаторов это

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

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

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

7.1 Таблицы идентификаторов

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

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

Заметим, что в большинстве языков программирования символьное представление идентификатора может иметь произвольную длину. Кроме того, различные объекты в одной или в разных областях видимости могут иметь одинаковые имена, и нет большого смысла занимать память для повторного хранения идентификатора. Таким образом, удобно имя объекта и его описание хранить по отдельности.

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

7.2 Таблицы расстановки

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

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

Определим некоторую функцию h 1 (первичную функцию расстановки), определенную на множестве идентификаторов и принимающую значения от 0 до N — 1 (т.е. 0 h 1(id) N — 1, где id — символьное представление идентификатора). Таким образом, функция расстановки сопоставляет идентификатору некоторый адрес в таблице символов.

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

Для этого вычисляется вторичная функция расстановки h 2(h) (значением которой опять таки является некоторый адрес в таблице символов). Возможны четыре варианта:

— элемент таблицы не заполнен (т.е. идентификатора в таблице нет),

— идентификатор элемента таблицы совпадает с искомым (т.е. идентификатор найден),

— адрес элемента совпадает с уже просмотренным (т.е. таблица вся просмотрена и идентификатора нет)

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

Для продолжения поиска применяется следующая функция расстановки h 3(h 2), h 4(h 3) и т.д. Как правило, h i = h 2 для i 2. Аргументом функции h 2 является целое в диапазоне [0, N — 1] и она может быть быть устроена по-разному. Приведем три варианта.

1) h 2(i) = (i + 1) mod N.

Берется следующий (циклически) элемент массива. Этот вариант плох тем, что занятые элементы «группируются», образуют последовательные занятые участки и в пределах этого участка поиск становится по-существу линейным.

2) h 2(i) = (i + k) mod N, где k и N взаимно просты.

По-существу это предыдущий вариант, но элементы накапливаются не в последовательных элементах, а «разносятся».

3) h 2(i) = (a * i + c) mod N — «псевдослучайная последовательность».

Здесь c и N должны быть взаимно просты, b = a — 1 кратно p для любого простого p, являщегося делителем N, b кратно 4, если N кратно 4 [5].

Поиск в таблице расстановки можно описать следующей функцией:

Функция IdComp(H,Id) сравнивает элемент таблицы на входе H с идентификатором и вырабатывает 0, если они равны. Функция Empty(H) вырабатывает NULL, если вход H пуст. Функция Search присваивает параметрам Yes и Pointer соответственно следующие значения :

true, P — если нашли требуемый идентификатор, где P — указатель на соответствующий этому идентификатору вход в таблице,

false, NULL — если искомый идентификатор не найден, причем в таблице нет свободного места, и

false, P — если искомый идентификатор не найден, но в таблице есть свободный вход P.

Занесение элемента в таблицу можно осуществить следующей функцией:

Здесь функция InsertId(Point,Id) заносит идентификатор Id для входа Point таблицы.

7.3 Таблицы расстановки со списками

Только что описанная схема страдает одним недостатком — возможностью переполнения таблицы. Рассмотрим ее модификацию, когда все элементы, имеющие одинаковое значения (первичной) функции расстановки, связываются в список (при этом отпадает необходимость использования функций h i для i 2). Таблица расстановки со списками — это массив указателей на списки элементов (рис. 7.3).

Вначале таблица расстановки пуста (все элементы имеют значение NULL). При поиске идентификатора Id вычисляется функция расстановки h(Id) и просматривается соответствующий линейный список. Поиск в таблице может быть описан следующей функцией:

struct Element
struct Element * Next;
>;
struct Element * T[N];

Занесение элемента в таблицу можно осуществить следующей функцией:

Процедура Include заносит идентификатор в таблицу идентификаторов. Алгоритм иллюстрируется рис. 7.4.

7.4 Функции расстановки

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

1. По символам строки s определяем положительное целое H. Преобразование одиночных символов в целые обычно можно сделать средствами языка реализации. В Паскале для этого служит функция ord, в Си при выполнении арифметических операций символьные значения трактуются как целые.

2. Преобразуем H, вычисленное выше, в номер элемента, т.е. целое между 0 и N — 1, где N — размер таблицы расстановки, например, взятием остатка при делении H на N.

Функции расстановки, учитывающие все символы строки, распределяют лучше, чем функции, учитывающие только несколько символов, например, в конце или середине строки. Но такие функции требуют больше вычислений.

Простейший способ вычисления H — сложение кодов символов. Перед сложением с очередным символом можно умножить старое значение H на константу q. Т.е. полагаем H 0 = 0, H i = q * H i-1 + c i для 1 i k, k — длина строки. При q = 1 получаем простое сложение символов. Вместо сложения можно выполнять сложение c i и q*H j-1 по модулю 2. Переполнение при выполнении арифметических операций можно игнорировать.

Функция Hashpjw, приведенная ниже [10], вычисляется, начиная с H = 0 (предполагается, что используются 32-битовые целые). Для каждого символа c сдвигаем биты H на 4 позиции влево и добавляем очередной символ. Если какой-нибудь из четырех старших бит H равен 1, сдвигаем эти 4 бита на 24 разряда вправо, затем складываем по модулю 2 с H и устанавливаем в 0 каждый из четырех старших бит, равных 1.

7.5 Таблицы на деревьях

Рассмотрим еще один способ организации таблиц символов с использованием двоичных деревьев.

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

Пусть на множестве идентификаторов задан некоторый линейный (например, лексикографический) порядок , т.е. некоторое транзитивное, антисимметричное и антирефлексивное отношение. Таким образом, для произвольной пары идентификаторов id 1 и id 2 либо id 1 id 2, либо id 2 id 1, либо id 1 совпадает с id 2.

Каждой вершине двоичного дерева, представляющего таблицу символов, сопоставим идентификатор. При этом, если вершина (которой сопоставлен id) имеет левого потомка (которому сопоставлен id L), то id L id; если имеет правого потомка (id R), то id id R. Элемент таблицы изображен на рис. 7.5.

Поиск в такой таблице может быть описан следующей функцией:

где структура для для элемента дерева имеет вид

Занесение в таблицу осуществляется функцией

struct TreeElement * InsertTree(String Id, struct TreeElement * TP)
IdentP);
if (comp Left, &(TP->Left)));
if (comp>0) return(Fill(Id,TP->Right, &(TP->Right)));
return(TP);
>

struct TreeElement * Fill(String Id,
struct TreeElement * P,
struct TreeElement ** FP)
< if (P==NULL)
P->IdentP=Include(Id);
P->Left=NULL;
P->Right=NULL;
*FP=P;
return(P);
>
else return(InsertTree(Id,P));
>

Как показано в работе [8], среднее время поиска в таблице размера n, организованной в виде двоичного дерева, при равной вероятности появления каждого объекта равно (2 ln 2) log 2n + O(1). Однако, на практике случай равной вероятности появления объектов встречается довольно редко. Поэтому в дереве появляются более длинные и более короткие ветви, и среднее время поиска увеличивается.

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

Определим для каждой вершины дерева характеристику, равную разности высот выходящих из нее правой и левой ветвей. В сбалансированном дереве характеристика вершины может быть равной -1, 0 и 1, для листьев она равна 0.

Пусть мы определили место новой вершины в дереве. Ее характеристика равна 0. Назовем путь, ведущий от корня к новой вершине, выделенным. При добавлении новой вершины могут измениться характеристики только тех вершин, которые лежат на выделенном пути. Рассмотрим заключительный отрезок выделенного пути, такой, что до добавления вершины характеристики всех вершин на нем были равны 0. Если верхним концом этого отрезка является сам корень, то дерево перестраивать не надо, достаточно лишь изменить характеристики вершин на этом пути на 1 или -1, в зависимости от того, влево или вправо пристроена новая вершина.

Пусть верхний конец заключительного отрезка — не корень. Рассмотрим вершину A — «родителя» верхнего конца заключительного отрезка. Перед добавлением новой вершины характеристика A была равна ±1. Если A имела характеристику 1 (-1) и новая вершина добавляется в левую (правую) ветвь, то характеристика вершины A становится равной 0, а высота поддерева с корнем в A не меняется. Так что и в этом случае дерево перестраивать не надо.

Пусть теперь характеристика A до перестраивания была равна -1 и новая вершина добавлена к левой ветви A (аналогично — для случая 1 и добавления к правой ветви). Рассмотрим вершину B — левого потомка A. Возможны следующие варианты.

Если характеристика B после добавления новой вершины в D стала равна -1, то дерево имеет структуру, изображенную на рис. 7.6, а. Перестроив дерево так, как это изображено на рис. 7.6, б, мы добьемся сбалансированности (в скобках указаны характеристики вершин, где это существенно, и соотношения высот после добавления).

Если характеристика вершины B после добавления новой вершины в E стала равна 1, то надо отдельно рассмотреть случаи, когда характеристика вершины E, следующей за B на выделенном пути, стала равна -1, 1 и 0 (в последнем случае вершина E — новая). Вид дерева до и после перестройки для этих случаев показан соответственно на рис. 7.7, 7.8 и 7.9.

7.6 Реализация блочной структуры

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

7.7 Сравнение методов реализации таблиц

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

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

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

Наилучшим, по-видимому, является механизм доступа по указателям и использование факта магазинной организации памяти в компиляторе. Для этого процедура выделения памяти выдает необходимый кусок из подряд идущей памяти, а при выходе из процедуры вся память, связанная с этой процедурой, освобождается простой перестановкой указателя свободной памяти в состояние перед началом обработки процедуры. В чистом виде это не всегда, однако, возможно. Например, локальный модуль в Модуле-2 может экспортировать некоторые объекты наружу. При этом схему реализации приходится «подгонять» под механизм распределения памяти. В данном случае, например, необходимо экспортированные объекты вынести в среду охватывающего блока и свернуть блок локального модуля.

Источник

Хеш-таблицы

Предисловие

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

Возможно, она не столь полезна для опытных программистов, но будет интересна для студентов технических ВУЗов и начинающих программистов-самоучек.

Мотивация использовать хеш-таблицы

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

Контейнер \ операция	insert	remove	find
Array	O(N)	O(N)	O(N)
List	O(1)	O(1)	O(N)
Sorted array	O(N)	O(N)	O(logN)
Бинарное дерево поиска	O(logN)	O(logN)	O(logN)
Хеш-таблица	O(1)	O(1)	O(1)

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

Из этой таблицы очень хорошо понятно, почему же стоит использовать хеш-таблицы. Но тогда возникает противоположный вопрос: почему же тогда ими не пользуются постоянно?
Ответ очень прост: как и всегда, невозможно получить все сразу, а именно: и скорость, и память. Хеш-таблицы тяжеловесные, и, хоть они и быстро отвечают на вопросы основных операций, пользоваться ими все время очень затратно.

Понятие хеш-таблицы

Хеш-таблица — это контейнер. Реализация у него, возможно, и не очевидная, но довольно простая.

Для начала объяснение в нескольких словах. Мы определяем функцию хеширования, которая по каждому входящему элементу будет определять натуральное число. А уже дальше по этому натуральному числу мы будем класть элемент в (допустим) массив. Тогда имея такую функцию мы можем за O(1) обработать элемент.

Теперь стало понятно, почему же это именно хеш-таблица.

Проблема коллизии

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

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

Решения проблемы коллизии методом двойного хеширования

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

Одна хеш-функция (при входе g) будет возвращать натуральное число s, которое будет для нас начальным. То есть первое, что мы сделаем, попробуем поставить элемент g на позицию s в нашем массиве. Но что, если это место уже занято? Именно здесь нам пригодится вторая хеш-функция, которая будет возвращать t — шаг, с которым мы будем в дальнейшем искать место, куда бы поставить элемент g.

Мы будем рассматривать сначала элемент s, потом s + t, затем s + 2*t и т.д. Естественно, чтобы не выйти за границы массива, мы обязаны смотреть на номер элемента по модулю (остатку от деления на размер массива).

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

Реализация хеш-таблицы

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

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

Чтобы идти дальше, нам необходимо разобраться с проблемой: что же будет, если мы удалим элемент из таблицы? Так вот, его нужно пометить флагом deleted, но просто удалять его безвозвратно нельзя. Ведь если мы так сделаем, то при попытке найти элемент (значение хеш-функции которого совпадет с ее значением у нашего удаленного элемента) мы сразу наткнемся на пустую ячейку. А это значит, что такого элемента и не было никогда, хотя, он лежит, просто где-то дальше в массиве. Это основная сложность использования данного метода решения коллизий.

Помня о данной проблеме построим наш класс.

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

Из необходимых методов осталось еще реализовать динамическое увеличение, расширение массива — метод Resize.

Увеличиваем размер мы стандартно вдвое.

Немаловажным является поддержание асимптотики O(1) стандартных операций. Но что же может повлиять на скорость работы? Наши удаленные элементы (deleted). Ведь, как мы помним, мы ничего не можем с ними сделать, но и окончательно обнулить их не можем. Так что они тянутся за нами огромным балластом. Для ускорения работы нашей хеш-таблицы воспользуемся рехешом (как мы помним, мы уже выделяли под это очень странные переменные).

Теперь воспользуемся ими, если процент реальных элементов массива стал меньше 50, мы производим Rehash, а именно делаем то же самое, что и при увеличении таблицы (resize), но не увеличиваем. Возможно, это звучит глуповато, но попробую сейчас объяснить. Мы вызовем наши хеш-функции от всех элементов, переместим их в новых массив. Но с deleted-элементами это не произойдет, мы не будем их перемещать, и они удалятся вместе со старой таблицей.

Но к чему слова, код все разъяснит:

Ну теперь мы уже точно на финальной, хоть и длинной, и полной колючих кустарников, прямой. Нам необходимо реализовать вставку (Add), удаление (Remove) и поиск (Find) элемента.

Начнем с самого простого — метод Find элемент по значению.

Далее мы реализуем удаление элемента — Remove. Как мы это делаем? Находим элемент (как в методе Find), а затем удаляем, то есть просто меняем значение state на false, но сам Node мы не удаляем.

Ну и последним мы реализуем метод Add. В нем есть несколько очень важных нюансов. Именно здесь мы будем проверять на необходимость рехеша.

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

Источник

Электронная библиотека

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

Начальные элементы таблицы создаются лексическим анализатором. В дальнейшем, по мере распознавания описаний идентификаторов в процессе синтаксического анализа вызываются соответствующие семантические подпрограммы, которые и формируют элементы таблицы. При этом для каждого нового идентификатора элемент добавляется только один раз, но поиск ведется всякий раз, когда встречается этот идентификатор. Так как на поиск уходит много времени, таблица должна быть организована таким образом, чтобы она допускала эффективный поиск. С применяемыми при этом методами упорядочения (сортировки) элементов таблицы можно познакомится в работах [6, 11]. Здесь же нас будет интересовать содержимое таблицы идентификаторов.

В общем случае для каждого типа идентификатора в таблице хранится специфическая информация. Так, например, для имен переменных это может быть следующее [11]:

· тип (вещественный, целый, строка и т.д.);

· точность, масштаб, длина;

· вид (простая переменная, массив, структура и т.д.);

· адрес во время выполнения программы;

· если массив, то число измерений, если граничные пары — константы, то их значение;

· если структура или компоненты структуры, то связь ее с другими компонентами;

· формальный параметр или нет, если да, то тип соответствия параметров;

· обрабатывалось ли уже описание переменной;

· существует ли инструкция, присваивающая значение переменной и т.д.

· А для имен процедур характерна другая информация:

· является ли она внешней по отношению к программе;

· является ли она функцией, каков ее тип;

· является ли она рекурсивной;

· каковы ее формальные параметры и т.д.

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

В этом случае один и тот же идентификатор может быть описан и использован много раз в различных блоках и процедурах, и каждое такое описание должно иметь единственный, связанный с ним, элемент в таблице идентификаторов. При использовании идентификатора возникает проблема, как отыскать соответствующий ему элемент в таблице идентификаторов. Решить эту проблему достаточно просто, если допустить блочную организацию таблицы идентификаторов. В этом случае создание элементов таблицы идентификаторов инициируется при входе в блок (процедуру) и заканчивается при выходе из него.- Для этих целей создается таблица блоков, одно из полей таблицы блоков содержит указатель на список элементов таблицы идентификаторов, описанных в данном блоке. На рис. 4.1 и 4.2 приведены фрагмент блочной программы и возможный для нее вариант организации и содержимое таблицы идентификаторов.

Рис. 4.1. Фрагмент блочной программы

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

Рис. 4.2. Вариант организации таблицы идентификаторов

Срочно?
Закажи у профессионала, через форму заявки
8 (800) 100-77-13 с 7.00 до 22.00

Источник

Простейшие способы организации таблицы идентификаторов

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

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

Поиск может быть выполнен более эффективно, если элементы таблицы упорядочены (отсортированы) согласно некоторому естественному порядку. В нашем случае, где поиск будет осуществляться по имени идентификатора, наиболее естественным будет расположить элементы таблицы в алфавитном порядке. Эффективным методом поиска в упорядоченном списке из n элементов является бинарный или логарифмический поиск. Символ S, который следует найти, сравнивается с элементом (n + 1)/2 в середине таблицы. Если этот элемент не является требуемым, мы должны просмотреть только блок элементов, пронумерованных от 1 до (n + 1)/2 — 1, или блок элементов от (n + 1)/2 + 1 до n в зависимости от того, меньше искомый элемент S или больше того, с которым его сравнили. Затем мы повторяем процесс над блоком меньшего размера. Так как на каждом шаге число элементов, которые могут содержать S, сокращается наполовину, то максимальное число сравнений равно 1 + log2 n. Для сравнения: при для n = 128 бинарный поиск требует самое большее 8 сравнений, поиск в неупорядоченной таблице — в среднем 64 сравнения.

Существует часто используемый метод упорядочивания элементов в таблице, называемый хеш-адресация. Этот метод преобразует символ в индекс элемента в таблице. Индекс получается «хешированием» символа — выполнением над символом некоторых простых арифметических и логических операций. Простой хеш-функцией является внутреннее представление первой литеры символа. Так, если двоичное ASCII представление символа А есть 00100001, то результатом хеширования идентификатора ATable будет код 00100001.

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

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

Лучших результатов можно достичь, если применить методы, связанные с использованием хеш-функций и хеш-адресации.

Хеш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r) = n, rÎR, nÎZ. Сам термин «хеш-функция» происходит от английского термина «hash function» (hash — «мешать», «смешивать», «путать»). Вместо термина «хеширование» иногда используются термины «рандомизация», «переупорядочивание».

Множество допустимых входных элементов R называется областью определения хеш-функции. Множеством значений хеш-функции F называется подмножество M из множества целых неотрицательных чисел Z: MÍZ, содержащее все возможные значения, возвращаемые функцией F: «rÎR: F(r)ÎM и «mÎM: $rÎR: F(r)=m. Процесс отображения области определения хеш-функции на множество значений называется «хешированием».

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

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

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

Источник