Введение
Структура данных, используемая языковым переводчиком, таким как компилятор или интерпретатор.
В информатике таблица символов — это структура данных, используемая языковым переводчиком, таким как компилятор или интерпретатор, в которой каждому идентификатору (или символу), константе, процедуре и функции в исходном коде программы сопоставлена информация, относящаяся к его объявлению или месту появления в исходном тексте. Иными словами, записи в таблице символов хранят информацию, связанную с соответствующим символом.
Предыстория
Таблица символов может существовать только в памяти в процессе трансляции или быть включенной в результат трансляции, например, в объектный файл ABI для последующего использования. Она может быть использована, например, в интерактивной сессии отладки или как ресурс для формирования диагностического отчета во время или после выполнения программы.
Описание
Минимальная информация, содержащаяся в таблице символов, используемой транслятором и промежуточным представлением (IR), включает имя символа и его местоположение или адрес. Для компилятора, ориентированного на платформу с поддержкой перемещаемости, она также будет содержать атрибуты перемещаемости (абсолютный, перемещаемый и т.п.) и необходимую информацию для перемещения перемещаемых символов. Таблицы символов для языков программирования высокого уровня могут хранить тип символа – строка, целое число, число с плавающей точкой и т.д., его размер, а также размерности и границы. Не вся эта информация включается в выходной файл, но может быть предоставлена для использования при отладке. Во многих случаях информация о перекрестных ссылках на символ хранится вместе с таблицей символов или связана с ней. Большинство компиляторов выводят часть или всю эту информацию в листингах таблицы символов и перекрестных ссылок в конце трансляции.
Реализация
Для реализации таблиц доступны многочисленные структуры данных. Деревья, линейные списки и самоорганизующиеся списки могут использоваться для реализации таблицы символов. К таблице символов обращаются большинство фаз компилятора, начиная с лексического анализа и заканчивая оптимизацией. Компилятор может использовать одну большую таблицу символов для всех символов или отдельные, либо иерархические таблицы символов для различных областей видимости. Например, в языках с областями видимости, таких как Algol или PL/I, символ "p" может быть объявлен отдельно в нескольких процедурах, возможно, с различными атрибутами. Область видимости каждой декларации – это часть программы, в которой ссылки на "p" разрешаются к этой декларации. Каждая декларация представляет собой уникальный идентификатор "p". Таблица символов должна иметь средства для различения ссылок на различные экземпляры "p".
Распространенной структурой данных, используемой для реализации таблиц символов, является хеш-таблица. Время поиска в хеш-таблицах не зависит от количества хранимых в ней элементов, что делает ее эффективной для большого объема данных. Она также упрощает классификацию литералов в табличном виде, включая классификацию при вычислении хеш-ключа. Поскольку лексический анализатор тратит значительную часть времени на поиск в таблице символов, эта операция оказывает существенное влияние на общую скорость компиляции. Таблица символов должна быть организована таким образом, чтобы обеспечить максимально быстрый поиск записей. Обычно для организации таблицы символов используются хеш-таблицы, где ключевое слово или идентификатор преобразуется в индекс массива с помощью хеширования. Столкновения в хеш-таблице неизбежны, и распространенный способ их обработки – хранение синонимов в следующем доступном свободном месте в таблице.
Приложения
Файл объекта содержит таблицу символов идентификаторов, видимых извне. При компоновке различных файлов объектов, компоновщик идентифицирует и разрешает эти внешние ссылки. Обычно поиск всех неопределенных внешних символов осуществляется в одной или нескольких библиотеках объектов. Если найден модуль, определяющий этот символ, он компонуется с первым файлом объекта, а любые неопределенные внешние идентификаторы добавляются в список для дальнейшего поиска. Этот процесс продолжается до тех пор, пока все внешние ссылки не будут разрешены. Если в конце процесса одна или несколько ссылок остаются неразрешенными, возникает ошибка. При обратной разработке исполняемого файла многие инструменты обращаются к таблице символов для проверки адресов, назначенных глобальным переменным и известным функциям. Если таблица символов была удалена или очищена перед преобразованием в исполняемый файл, инструментам будет сложнее определить адреса или понять структуру программы.
Пример: таблица символов Python
Язык программирования Python включает в себя широкую поддержку для создания и обработки таблиц символов. Среди свойств, которые можно запросить, – является ли данный символ свободной или связанной переменной, имеет ли он область видимости блока или глобальную область видимости, был ли он импортирован и к какому пространству имён он принадлежит.
Пример: Динамические таблицы символов
Некоторые языки программирования позволяют манипулировать таблицей символов во время выполнения, так что символы можно добавлять в любой момент. Racket является примером такого языка. Как LISP, так и Scheme позволяют связывать с каждым символом произвольные, универсальные свойства. Язык программирования Prolog по сути является языком манипулирования таблицей символов; символы в нём называются атомами, и отношения между символами могут быть подвергнуты логическому выводу. Аналогично, OpenCog предоставляет динамическую таблицу символов, называемую атомным пространством, которая используется для представления знаний.