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

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

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

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

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

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