Лекция 10

3.2. Взаимодействие сканера с таблицей идентификаторов

3.2.1.Назначение и особенности построения таблиц идентификаторов

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

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

●для переменных:

– имя переменной;

– тип данных переменной;

– область памяти, связанная с переменной;

– вид (простая переменная, массив, структура) и другие характеристики, уточняющие основные;

● для констант:

– название константы (если оно имеется);

– значение константы;

– тип данных константы (если требуется);

● для функций:

– имя функции;

– количество и тип формальных аргументов функции;

– тип возвращаемого результата;

– адрес кода функции.

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

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

3.2.2. Простейшие методы построения таблиц идентификаторов

Структура ТИ определяется на фазе лексического анализа и на других фазах компиляции может только поддерживаться.

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

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

Заполнение такой таблицы будет происходить элементарно просто – добавлением нового элемента в конец таблицы. При этом время, необходимое для новой записи (T₃) не зависит от числа элементов в таблице N.

При больших значениях N (несколько тысяч элементов) время поиска T_n = Ф(N) >> T₃ и такой способ организации ТИ является неэффективным.

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

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

Искомый элемент сравнивается с элементом в середине таблицы:

(N + 1)/2 при N – нечетном;

N/2 при N – четном.

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

Так как на каждом шаге число элементов, которые могут содержать искомый элемент, сокращается в 2 раза, максимальное число сравнений равно 1 + log₂ N, тогда T_n  = Ф(log₂ N). Для сравнения посмотрим: Пусть N = 128, тогда бинарный поиск потребует 8 сравнений (8 единиц времени), а поиск в неупорядоченной таблице – в среднем 64 сравнения.

Метод называют «бинарным поиском», поскольку на каждом шаге объем рассматриваемой информации сокращается в два раза, а «логарифмический» поскольку T_n имеет логарифмическую зависимость от N.

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