М.Ю. Харламов, ВНУ им. В.Даля, 2009. Таблицы идентификаторов Таблицы идентификаторов (символов) хранят все найденные идентификаторы и связанные с ними. - презентация

1 М.Ю. Харламов, ВНУ им. В.Даля, 2009

2 Таблицы идентификаторов Таблицы идентификаторов (символов) хранят все найденные идентификаторы и связанные с ними характеристики в течение всего процесса компиляции, чтобы иметь возможность использовать их на различных фазах компиляции Основное требование - компилятор должен иметь возможность максимально быстрого поиска нужного ему элемента Тема 3. Организация таблиц идентификаторов

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

4 Списки (таблицы) T з ~ 0; Т п =O(N) Упорядоченные списки (таблицы) Т п = O(log 2 N) Бинарное дерево (узел – элементы таб-цы) Т з = N*O(log 2 N); Т п = O(log 2 N) Тема 3. Организация таблиц идентификаторов Последовательность идентификаторов: GA, D1, М22, Е, А12, ВС, F Последовательность идентификаторов: GA, D1, М22, Е, А12, ВС, F Ga D1 A12 E M22 BCF GaD1M22EA12BCF GaD1M22EA12BCF

5 Хеш-функцией Хеш-функцией F называется некоторое отображение множества входных элементов R на множество целых неотрицательных чисел Z: F(r) = n, r R, n Z Область определения хеш-функции - множество допустимых входных элементов R Множество значений хеш-функции - М Z, содержащее все возможные значения, возвращаемые функцией F Хеширование - процесс отображения области определения хеш-функции на множество значений Тема 3. Организация таблиц идентификаторов

6 Хеш-адресация заключается в использовании значения, возвращаемого хеш-функцией, в качестве адреса ячейки из некоторого массива данных Тема 3. Организация таблиц идентификаторов A1A1 A2A2 A3A3 F A1A1 A3A3 A3A3 Иденти- фикаторы Хеш-функция Таблица Поиск ? F Результат поиска

7 Хеширование обычно достигается за счет выполнения над цепочкой символов некоторых простых арифметических и логических операций = коду внутреннего представления в компьютере литеры символа Недостатки хеш-адресации неэффективное использование объема памяти под таблицу идентификаторов Необходимость разумного выбора хэш-функции Коллизии Коллизии - ситуация, когда двум или более идентификаторам соответствует одно и то же значение функции Тема 3. Организация таблиц идентификаторов

8 если для элемента А адрес h(A), вычисленный с помощью хэш-функции h, указывает на уже занятую ячейку, то необходимо вычислять значения функций n i = h i (A) до тех пор, пока не будет найдена свободная ячейка Тема 3. Организация таблиц идентификаторов h i =(h(A)+p i )mod N m h i =(h(A)+i)mod N m P i – вычисляемое число; N m - максимальное значение из области значений хеш-функции A1A1 A1A1 h(A 1 ) n 1 1. A 1 A1A1 A1A1 h(A 2 ) n 1 2. A 2 n2n2 A2A2 A2A2 h 1 (A 2 ) A1A1 A1A1 n1n1 3. A 3 h(A 3 ) n 2 A2A2 A2A2 n3n3 A3A3 A3A3 h 1 (A 3 ) h i =(h(A)*i)mod N m T п =O((1-L f /2)/(1-L f ))

9 Основная идея – использование «промежуточной» хеш-таблицы со значениями указателей на области памяти из основной таблицы идентификаторов Тема 3. Организация таблиц идентификаторов n1n1 n2n2 n3n3 n4n4 n5n5 A1A1 A1A1 - - H(A 1 ) 1. A 1 Free Ptr n1n1 n2n2 n3n3 n4n4 n5n5 A1A1 A1A1 H(A 1 ),H(A 2 ) 3. A 1 Free Ptr A2A2 A2A2 - - A3A3 A3A3 - - H(A 3 )