Таблица символов

Таблица символов может существовать только в оперативной памяти во время процесса трансляции, либо быть встроенной в выходные данные трансляции, например, в объектный файл ABI — для последующего использования. Например, таблица символов может использоваться во время отладки или как источник сведений при формировании диагностического отчёта во время или после выполнения программы^[2].

Минимальная информация, содержащаяся в таблице символов, используемой транслятором и промежуточным представлением, включает в себя имя символа и его местоположение или адрес. Для компиляторов, целевыми платформами которых являются системы с поддержкой перемещаемости кода, таблица также содержит соответствующие атрибуты (абсолютный, релокейтабельный(перемещаемый) и т. д.) и необходимые сведения для обработки таких символов. В таблицах символов для языков высокого уровня могут храниться сведения о типе (строка, целое число, число с плавающей запятой и др.), размере, измерениях и границах символа. Не вся эта информация включается в выходной файл, но может предоставляться для целей отладки. Во многих случаях к каждому символу хранится перекрёстная ссылка. Большинство компиляторов формируют итоговые отчёты, где перечисляют информацию из таблицы символов и перекрестных ссылок^[1].

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

Компилятор может использовать единую большую таблицу символов для всех символов или раздельные (иерархические) таблицы для каждого блока видимости. Например, в языках с блочной структурой, таких как ALGOL или PL/I, символ «p» может быть объявлен неоднократно — в разных процедурах и с разными атрибутами. Область видимости каждого объявления — это участок программы, где использование «p» разрешается к этой конкретной декларации. Таблица символов должна обеспечивать различие между такими случаями.

Часто таблицы символов реализуются в виде хеш-таблиц. Время поиска в хеш-таблице не зависит от количества хранимых элементов, что делает этот подход эффективным при большом их числе. Кроме того, это упрощает классификацию литералов — необходимая информация включается в вычисление хеш-ключа^[3].

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

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

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

Рассмотрим следующий фрагмент программы на языке C:

// Объявление внешней функции
extern double bar(double x);

// Определение публичной функции
double foo(int count)
{
    double sum = 0.0;

    // Суммирование значений bar(1) до bar(count)
    for (int i = 1; i <= count; i++)
        sum += bar((double) i);
    return sum;
}

Компилятор C, который анализирует этот код, как правило, сформирует как минимум следующие записи таблицы символов:

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

Пример таблицы символов можно найти в спецификации SysV ABI (англ. System V Application Binary Interface), где стандартизируется способ размещения символов в бинарных файлах. Это обеспечивает совместную работу различных компиляторов, компоновщиков и загрузчиков с символами в скомпилированных объектах.

SysV ABI реализован, например, в утилите англ. nm пакета GNU binutils. Формат таблицы включает отсортированное поле с адресом памяти, поле «тип символа» и идентификатор символа («имя»)^[4].

Типы символов в спецификации SysV ABI (и выводе утилиты англ. nm) характеризуют назначение каждой записи: например, «d» для инициализированных данных, а «t» для функций (исполняемый код размещается в секции «text» объектного файла). Заглавные буквы обозначают внешнюю (глобальную) связь, а строчные — локальную.

Язык программирования Python содержит широкие возможности для создания и анализа таблиц символов^[5]. Можно, например, проверять, является ли символ свободной или связанной переменной, к какому пространству имён относится, импортирован ли он и принадлежит ли к блочной или глобальной области видимости.

В некоторых языках таблица символов может изменяться во время выполнения программы — позволяется создавать новые символы на лету. Примером такого языка является англ. Racket^[6].

Языки LISP и Scheme позволяют ассоциировать с каждым символом произвольные свойства^[7].

Язык Prolog во многом представляет собой язык обработки таблицы символов: символы называются атомами, а взаимосвязи между ними могут анализироваться логически. Похожая система реализована в OpenCog, где динамическая таблица символов («atomspace») служит для представления знаний.