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

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

Простейший способ организации таблицы состоит в том, чтобы добавлять элементы в порядке их поступления. Поиск в этом случае требует сравнения с каждым элементом таблицы, пока не будет найден подходящий. Для таблицы, содержащей 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. Процесс отображения области определения хеш-функции на множество значений называется «хешированием».

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

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

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

Вопрос 9