Организация таблиц символов
В данном документе рассматриваются способы организации, построения и поиска в таблице символов. Останавливаясь на организации таблиц вообще, мы обратим особое внимание на нашу конкретную проблему — проблему организации таблиц символов.
1. ВВЕДЕНИЕ В ОРГАНИЗАЦИЮ ТАБЛИЦ
Таблицы всех типов имеют общий вид ( таблица меток, таблица литералов, таблица имен макроопределений , таблица машинных операций )
где слева перечисляются аргументы, а справа — соответствующие значения. Каждый элемент обычно занимает в машине более одного байта. Если элемент занимает k байт и нужно хранить N элементов, то необходимо иметь k*N байт памяти. Расположить информацию можно двумя способами:
1. Каждый элемент поместить в k последовательных байт и иметь таблицу из k*N байт.
2. Иметь k таблиц, скажем, Tl, T2, . . . , Tk, каждая из N байт. Весь i-й элемент при этом будет находиться в байтах Т1[i], . . . , Tk[i],.
Вопрос выбора между этими двумя методами — это только вопрос удобства программирования.
В нашем частном случае аргументами таблицы являются символы или идентификаторы, а значениями — их характеристики. Так как число литер в идентификаторе непостоянно, в аргументе часто помещают вместо самого идентификатора указатель на идентификатор. Это сохраняет фиксированным размер аргумента.
Рис. 1. Два способа запоминания аргументов.
Идентификаторы хранятся в специальном списке строк. Число литер в каждом идентификаторе может храниться как часть аргумента или в списке идентификаторов прямо перед идентификатором. На рис. 9.1 показаны оба способа на примере таблицы, содержащей элементы для идентификаторов I, МАХ и J.
Когда компилятор( ассемблер ) начинает трансляцию исходной программы, таблица символов пуста или содержит только несколько элементов для служебных слов и стандартных функций. В процессе компиляции для каждого нового идентификатора элемент добавляется только один раз, но поиск ведется всякий раз, когда встречается этот идентификатор. Так как на этот процесс уходит много времени при компиляции, важно выбрать такую организацию таблиц, которая допускала бы эффективный поиск.
Желательно сравнить различные методы работы с таблицами по времени поиска. Мы будем проводить сравнение в терминах ожидаемого числа Е сравнений аргументов, которые нужно выполнить, чтобы найти данный символ. Это число, зависящее от коэффициента загрузки lf (load factor) таблицы в данный момент, представляет собой отношение текущего числа элементов n к максимально возможному числу элементов N:
lf = n/N.
Простейший способ организации таблицы состоит в том, чтобы, добавлять элементы для