В информатике таблица символов — это структура данных , используемая переводчиком языка, таким как компилятор или интерпретатор , где каждый идентификатор (или символ ), константа , процедура и функция в исходном коде программы связаны с информацией, относящейся к ее объявлению или появление в источнике. Другими словами, записи таблицы символов хранят информацию, относящуюся к соответствующему символу записи. [1]
Таблица символов может существовать в памяти только во время процесса перевода или может быть встроена в выходные данные перевода, например, в объектный файл ABI для дальнейшего использования. Например, его можно использовать во время сеанса интерактивной отладки или как ресурс для форматирования диагностического отчета во время или после выполнения программы. [2]
Минимальная информация, содержащаяся в таблице символов, используемой транслятором и промежуточным представлением (IR), включает имя символа и его местоположение или адрес. Для компилятора, ориентированного на платформу с концепцией перемещаемости, он также будет содержать атрибуты перемещаемости (абсолютные, перемещаемые и т. д.) и необходимую информацию о перемещении для перемещаемых символов. Таблицы символов для языков программирования высокого уровня могут хранить тип символа: строка, целое число, с плавающей запятой и т. д., его размер, размеры и границы. Не вся эта информация включается в выходной файл, но может быть предоставлена для использования при отладке . Во многих случаях информация о перекрестных ссылках символа хранится вместе с таблицей символов или связана с ней. Большинство компиляторов печатают часть или всю эту информацию в таблице символов и списках перекрестных ссылок в конце перевода. [1]
Для реализации таблиц доступны многочисленные структуры данных . Деревья, линейные списки и самоорганизующиеся списки можно использовать для реализации таблицы символов. Доступ к таблице символов осуществляется на большинстве этапов компилятора, начиная с лексического анализа и заканчивая оптимизацией.
Компилятор может использовать одну большую таблицу символов для всех символов или использовать отдельные или иерархические таблицы символов для разных областей применения . Например, в языках с ограниченной областью действия, таких как Algol или PL/I, символ «p» может быть объявлен отдельно в нескольких процедурах, возможно, с разными атрибутами. Областью действия каждого объявления является раздел программы, в котором ссылки на «p» соответствуют этому объявлению. Каждое объявление представляет собой уникальный идентификатор «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 ); сумма возврата ; } Компилятор AC, который анализирует этот код, будет содержать как минимум следующие записи таблицы символов:
Кроме того, таблица символов может также содержать записи, сгенерированные компилятором для значений промежуточных выражений (например, выражение, которое преобразует переменную цикла iв a doubleи возвращаемое значение вызова функции bar()), метки операторов и т. д.
Пример таблицы символов можно найти в спецификации двоичного интерфейса приложения SysV (ABI), которая определяет, как символы должны располагаться в двоичном файле, чтобы различные компиляторы, компоновщики и загрузчики могли последовательно находить и работать с символы в скомпилированном объекте.
SysV ABI реализован в утилите nm GNU binutils . В этом формате используется отсортированное поле адреса памяти , поле «типа символа» и идентификатор символа (называемый «Имя»). [4]
Типы символов в SysV ABI (и выходных данных nm) указывают природу каждой записи в таблице символов. Каждый тип символа представлен одним символом. Например, записи таблицы символов, представляющие инициализированные данные, обозначаются символом «d», а записи таблицы символов для функций имеют тип символа «t» (поскольку исполняемый код находится в текстовой части объектного файла). Кроме того, использование заглавных букв типа символа указывает на тип связи: строчные буквы указывают, что символ является локальным, а прописные буквы указывают на внешнюю (глобальную) связь.
Язык программирования Python включает обширную поддержку создания таблиц символов и управления ими. [5] Свойства, которые могут быть запрошены, включают в себя, является ли данный символ свободной переменной или связанной переменной , является ли он областью действия блока или глобальной областью действия , импортирован ли он и к какому пространству имен он принадлежит.
Некоторые языки программирования позволяют манипулировать таблицей символов во время выполнения, поэтому символы можно добавлять в любое время. Рэкет является примером такого языка. [6]
Языки программирования LISP и Scheme позволяют связать произвольные общие свойства с каждым символом. [7]
Язык программирования Пролог по сути является языком манипулирования таблицами символов; символы называются атомами , и отношения между символами можно проанализировать. Аналогично, OpenCog предоставляет динамическую таблицу символов, называемую атомпространством , которая используется для представления знаний .