Войти
В информатике, таблица символов представляет собой структуру данных, используемый язык переводчик, такие как компилятор или интерпретатор, где каждый идентификатор (или символ) в программе в исходном коде связан с информацией, касающейся его заявление или появлениями в источнике. Другими словами, записи таблицы символов хранят информацию, относящуюся к соответствующему символу записи.
Таблица символов может существовать в памяти только во время процесса перевода или может быть встроена в выходные данные перевода, например, в объектный файл ABI для дальнейшего использования. Например, его можно использовать во время сеанса интерактивной отладки или как ресурс для форматирования диагностического отчета во время или после выполнения программы.
Минимальная информация, содержащаяся в таблице символов, используемой переводчиком, включает имя символа и его местоположение или адрес. Для компилятора, ориентированного на платформу с концепцией перемещаемости, он также будет содержать атрибуты перемещаемости (абсолютные, перемещаемые и т. Д.) И необходимую информацию о перемещении для перемещаемых символов. Таблицы символов для языков программирования высокого уровня могут хранить тип символа: строка, целое число, число с плавающей запятой и т. Д., Его размер, а также его размеры и его границы. Не вся эта информация включена в выходной файл, но может быть предоставлена для использования при отладке. Во многих случаях информация о перекрестных ссылках символа сохраняется или связана с таблицей символов. Большинство компиляторов печатают часть или всю эту информацию в таблице символов и списках перекрестных ссылок в конце перевода.
Для реализации таблиц доступны многочисленные структуры данных. Деревья, линейные списки и самоорганизующиеся списки могут использоваться для реализации таблицы символов. К таблице символов обращаются на большинстве этапов компилятора, начиная с лексического анализа и заканчивая оптимизацией.
Компилятор может использовать одну большую таблицу символов для всех символов или использовать отдельные иерархические таблицы символов для различных областей видимости. Например, в языке с ограниченной областью видимости, таком как Algol или PL / I, символ «p» может быть объявлен отдельно в нескольких процедурах, возможно, с разными атрибутами. Объем каждого объявления - это раздел программы, в котором ссылки на «p» соответствуют этому объявлению. Каждое объявление представляет собой уникальный идентификатор «p». Таблица символов должна иметь некоторые средства различения ссылок на разные "p".
Распространенной структурой данных, используемой для реализации таблиц символов, является хеш-таблица. Время поиска в хеш-таблицах не зависит от количества элементов, хранящихся в таблице, поэтому оно эффективно для большого количества элементов. Это также упрощает классификацию литералов в табличном формате, включая классификацию при вычислении хеш-ключа.
Поскольку лексический анализатор тратит большую часть своего времени на просмотр таблицы символов, это действие имеет решающее влияние на общую скорость компилятора. Таблица символов должна быть организована таким образом, чтобы записи можно было найти как можно быстрее. Хеш-таблицы обычно используются для организации таблицы символов, где ключевое слово или идентификатор «хешируются» для создания нижнего индекса массива. Коллизии неизбежны в хеш-таблице, и общий способ их обработки - сохранить синоним в следующем доступном свободном месте в таблице.
Объектный файл будет содержать таблицу символов идентификаторов, которые он содержит, которые являются видимыми извне. Во время связывания различных объектных файлов компоновщик идентифицирует и разрешает эти ссылки на символы. Обычно все неопределенные внешние символы ищутся в одной или нескольких библиотеках объектов. Если найден модуль, который определяет этот символ, он связан с первым объектным файлом, и любые неопределенные внешние идентификаторы добавляются в список идентификаторов для поиска. Этот процесс продолжается до тех пор, пока не будут разрешены все внешние ссылки. Если одна или несколько проблем остаются нерешенными в конце процесса, это ошибка.
При обратном проектировании исполняемого файла многие инструменты обращаются к таблице символов, чтобы проверить, какие адреса были назначены глобальным переменным и известным функциям. Если таблица символов была удалена или очищена перед преобразованием в исполняемый файл, инструментам будет труднее определить адреса или понять что-либо о программе.
Рассмотрим следующую программу, написанную на C :
// Declare an external function extern double bar(double x); // Define a public function double foo(int count) { double sum = 0.0; // Sum all the values bar(1) to bar(count) for (int i = 1; i lt;= count; i++) sum += bar((double) i); return sum; } Компилятор AC, который анализирует этот код, будет содержать как минимум следующие записи таблицы символов:
| Название символа | Тип | Сфера |
|---|---|---|
bar | функция, двойная | внешний |
x | двойной | параметр функции |
foo | функция, двойная | Глобальный |
count | int | параметр функции |
sum | двойной | заблокировать местный |
i | int | оператор цикла |
Кроме того, таблица символов также будет содержать записи, сгенерированные компилятором для промежуточных значений выражений (например, выражение, которое iпреобразует переменную цикла в a doubleи возвращаемое значение вызова функции bar()), метки операторов и т. Д.
| Адрес | Тип | Имя |
|---|---|---|
| 00000020 | а | T_BIT |
| 00000040 | а | F_BIT |
| 00000080 | а | I_BIT |
| 20000004 | т | irqvec |
| 20000008 | т | фиквек |
| 2000000c | т | InitReset |
| 20000018 | Т | _главный |
| 20000024 | т | Конец |
| 20000030 | Т | AT91F_US3_CfgPIO_useB |
| 2000005c | т | AT91F_PIO_CfgPeriph |
| 200000b0 | Т | главный |
| 20000120 | Т | AT91F_DBGU_Printk |
| 20000190 | т | AT91F_US_TxReady |
| 200001c0 | т | AT91F_US_PutChar |
| 200001f8 | Т | AT91F_SpuriousHandler |
| 20000214 | Т | AT91F_DataAbort |
| 20000230 | Т | AT91F_FetchAbort |
| 2000024c | Т | AT91F_Undef |
| 20000268 | Т | AT91F_UndefHandler |
| 20000284 | Т | AT91F_LowLevelInit |
| 200002e0 | т | AT91F_DBGU_CfgPIO |
| 2000030c | т | AT91F_PIO_CfgPeriph |
| 20000360 | т | AT91F_US_Configure |
| 200003dc | т | AT91F_US_SetBaudrate |
| 2000041c | т | AT91F_US_Baudrate |
| 200004ec | т | AT91F_US_SetTimeguard |
| 2000051c | т | AT91F_PDC_Open |
| 2000059c | т | AT91F_PDC_DisableRx |
| 200005c8 | т | AT91F_PDC_DisableTx |
| 200005f4 | т | AT91F_PDC_SetNextTx |
| 20000638 | т | AT91F_PDC_SetNextRx |
| 2000067c | т | AT91F_PDC_SetTx |
| 200006c0 | т | AT91F_PDC_SetRx |
| 20000704 | т | AT91F_PDC_EnableRx |
| 20000730 | т | AT91F_PDC_EnableTx |
| 2000075c | т | AT91F_US_EnableTx |
| 20000788 | Т | __aeabi_uidiv |
| 20000788 | Т | __udivsi3 |
| 20000884 | Т | __aeabi_uidivmod |
| 2000089c | Т | __aeabi_idiv0 |
| 2000089c | Т | __aeabi_ldiv0 |
| 2000089c | Т | __div0 |
| 200009a0 | D | _данные |
| 200009a0 | А | _etext |
| 200009a0 | D | Holaamigosh |
| 200009a4 | А | __bss_end__ |
| 200009a4 | А | __bss_start |
| 200009a4 | А | __bss_start__ |
| 200009a4 | А | _edata |
| 200009a4 | А | _конец |
Пример таблицы символов можно найти в спецификации двоичного интерфейса приложения SysV (ABI), которая определяет, как символы должны быть размещены в двоичном файле, чтобы различные компиляторы, компоновщики и загрузчики могли последовательно находить и работать с символы в скомпилированном объекте.
SysV ABI реализован в утилите nm GNU binutils. В этом формате используется отсортированное поле адреса памяти, поле «Тип символа» и идентификатор символа (называемый «Имя»).
Типы символов в SysV ABI (и выводе nm) указывают на природу каждой записи в таблице символов. Каждый тип символа представлен одним символом. Например, записи таблицы символов, представляющие инициализированные данные, обозначаются символом «d», а записи таблицы символов для функций имеют тип символа «t» (поскольку исполняемый код находится в текстовой части объектного файла). Кроме того, заглавные буквы в типе символа указывают на тип связи: строчные буквы указывают, что символ является локальным, а верхний регистр указывает на внешнюю (глобальную) связь.
Язык программирования Python включает обширную поддержку для создания таблиц символов и управления ими. Свойства, которые могут быть запрошены, включают, является ли данный символ свободной переменной или связанной переменной, является ли это областью блока или глобальной областью, импортируется ли он и какому пространству имен он принадлежит.
Некоторые языки программирования позволяют манипулировать таблицей символов во время выполнения, так что символы могут быть добавлены в любое время. Ракетка - пример такого языка.
И LISP, и языки программирования Scheme позволяют связывать произвольные общие свойства с каждым символом.
Язык программирования Prolog - это, по сути, язык манипулирования таблицей символов; символы называются атомами, и отношения между символами можно рассуждать. Точно так же OpenCog предоставляет динамическую таблицу символов, называемую атомным пространством, которая используется для представления знаний.
