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

Начальные элементы таблицы создаются лексическим анализатором. В даль­нейшем, по мере распознавания описаний идентификаторов в процессе син­таксического анализа вызываются соответствующие семантические подпрограммы, которые и формируют элементы таблицы. При этом для каж­дого нового идентификатора элемент добавляется только один раз, но поиск ведется всякий раз, когда встречается этот идентификатор. Так как на поиск уходит много времени, таблица должна быть организована таким образом, чтобы она допускала эффективный поиск. С применяемыми при этом методами упо­рядочения (сортировки) элементов таблицы можно познакомится в работах [6, 11]. Здесь же нас будет интересовать содержимое таблицы идентификаторов.

В общем случае для каждого типа идентификатора в таблице хранится спе­цифическая информация. Так, например, для имен переменных это может быть следующее [11]:

· тип (вещественный, целый, строка и т.д.);

· точность, масштаб, длина;

· вид (простая переменная, массив, структура и т.д.);

· адрес во время выполнения программы;

· если массив, то число измерений, если граничные пары — кон­станты, то их значение;

· если структура или компоненты структуры, то связь ее с другими компонентами;

· формальный параметр или нет, если да, то тип соответствия пара­метров;

· обрабатывалось ли уже описание переменной;

· существует ли инструкция, присваивающая значение переменной и т.д.

· А для имен процедур характерна другая информация:

· является ли она внешней по отношению к программе;

· является ли она функцией, каков ее тип;

· является ли она рекурсивной;

· каковы ее формальные параметры и т.д.

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

Рис. 4.1. Фрагмент блочной программы

В конце трансляции таблица идентификаторов, как правило, упразд­няется, хотя может сохраняться и на время выполнения программы, на­пример, в отладочном режиме работы транслятора.

Рис. 4.2. Вариант организации таблицы идентификаторов