Таблица символов
 | Эта статья нуждается в дополнительных цитатах для проверки . ( ноябрь 2012 г. ) |
В информатике таблица символов — это структура данных, языка, используемая переводчиком таким как компилятор или интерпретатор , где каждый идентификатор (или символ ), константа , процедура и функция программы в исходном коде связаны с информацией, относящейся к ее объявлению или появление в источнике. Другими словами, записи таблицы символов хранят информацию, относящуюся к соответствующему символу записи. [1]
Фон
[ редактировать ]Таблица символов может существовать в памяти только во время процесса перевода или может быть встроена в выходные данные перевода, например, в ABI объектный файл для последующего использования. Например, его можно использовать во время сеанса интерактивной отладки или как ресурс для форматирования диагностического отчета во время или после выполнения программы. [2]
Описание
[ редактировать ]Минимальная информация, содержащаяся в таблице символов, используемой транслятором и промежуточным представлением (IR), включает имя символа и его местоположение или адрес. Для компилятора, ориентированного на платформу с концепцией перемещаемости, он также будет содержать атрибуты перемещаемости (абсолютные, перемещаемые и т. д.) и необходимую информацию о перемещении для перемещаемых символов. Таблицы символов для языков программирования высокого уровня могут хранить тип символа: строка, целое число, с плавающей запятой и т. д., его размер, размеры и границы. Не вся эта информация включается в выходной файл, но может быть предоставлена для использования при отладке . символа Во многих случаях информация о перекрестных ссылках хранится вместе с таблицей символов или связана с ней. Большинство компиляторов печатают часть или всю эту информацию в таблице символов и списках перекрестных ссылок в конце перевода. [1]
Выполнение
[ редактировать ]многочисленные структуры данных Для реализации таблиц доступны . Деревья, линейные списки и самоорганизующиеся списки можно использовать для реализации таблицы символов. Доступ к таблице символов осуществляется на большинстве этапов компилятора, начиная с лексического анализа и заканчивая оптимизацией.
Компилятор может использовать одну большую таблицу символов для всех символов или использовать отдельные или иерархические таблицы символов для разных областей применения . Например, в языках с ограниченной областью действия, таких как Algol или PL/I, символ «p» может быть объявлен отдельно в нескольких процедурах, возможно, с разными атрибутами. Областью действия каждого объявления является раздел программы, в котором ссылки на «p» соответствуют этому объявлению. Каждое объявление представляет собой уникальный идентификатор «p». Таблица символов должна иметь некоторые средства различения ссылок на разные буквы «p».
Общей структурой данных, используемой для реализации таблиц символов, является хеш-таблица . Время поиска в хэш-таблицах не зависит от количества элементов, хранящихся в таблице, поэтому эффективно для большого количества элементов. Это также упрощает классификацию литералов в табличном формате, включая классификацию при вычислении хэш-ключа. [3]
Поскольку лексический анализатор тратит большую часть своего времени на поиск таблицы символов, эта деятельность оказывает решающее влияние на общую скорость компилятора. Таблица символов должна быть организована таким образом, чтобы записи можно было найти как можно быстрее. Хэш-таблицы обычно используются для организации таблицы символов, где ключевое слово или идентификатор «хешируется» для создания индекса массива. Коллизии в хеш-таблице неизбежны, и распространенный способ их устранения — сохранить синоним в следующем доступном свободном месте таблицы.
Приложения
[ редактировать ]Объектный файл будет содержать таблицу символов содержащихся в нем идентификаторов, видимых извне. Во время связывания различных объектных файлов компоновщик идентифицирует и разрешает эти ссылки на символы. Обычно все неопределенные внешние символы будут искаться в одной или нескольких библиотеках объектов . Если найден модуль, определяющий этот символ, он связывается с первым объектным файлом, а любые неопределенные внешние идентификаторы добавляются в список идентификаторов для поиска. Этот процесс продолжается до тех пор, пока все внешние ссылки не будут разрешены. Это ошибка, если одна или несколько проблем остаются неразрешенными в конце процесса.
При обратном проектировании исполняемого файла многие инструменты обращаются к таблице символов, чтобы проверить, какие адреса были назначены глобальным переменным и известным функциям. Если таблица символов была удалена или очищена перед преобразованием в исполняемый файл, инструментам будет сложнее определить адреса или понять что-либо о программе.
Пример
[ редактировать ]Рассмотрим следующую программу, написанную на 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 <= count; i++)
sum += bar((double) i);
return sum;
}
Компилятор AC, который анализирует этот код, будет содержать как минимум следующие записи таблицы символов:
| Имя символа | Тип | Объем |
|---|---|---|
bar |
функция, двойная | внешний |
x |
двойной | параметр функции |
foo |
функция, двойная | глобальный |
count |
интервал | параметр функции |
sum |
двойной | блокировать локально |
i |
интервал | оператор цикла for |
Кроме того, таблица символов может также содержать записи, сгенерированные компилятором для значений промежуточных выражений (например, выражения, которое преобразует i зациклить переменную в doubleи возвращаемое значение вызова функции bar()), метки операторов и т. д.
Пример: SysV ABI
[ редактировать ]| Адрес | Тип | Имя |
|---|---|---|
| 00000020 | а | Т_БИТ |
| 00000040 | а | Ф_БИТ |
| 00000080 | а | Я_БИТ |
| 20000004 | т | ирквек |
| 20000008 | т | фиквек |
| 2000000с | т | ИнитСброс |
| 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_Настроить |
| 200003dc | т | AT91F_US_SetBaudrate |
| 2000041c | т | AT91F_US_Скорость передачи данных |
| 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 | Д | _данные |
| 200009a0 | А | _etext |
| 200009a4 | А | __bss_end__ |
| 200009a4 | А | __bss_start |
| 200009a4 | А | __bss_start__ |
| 200009a4 | А | _edata |
| 200009a4 | А | _конец |
Пример таблицы символов можно найти в SysV спецификации двоичного интерфейса приложения (ABI), которая определяет, как символы должны располагаться в двоичном файле, чтобы разные компиляторы, компоновщики и загрузчики могли последовательно находить и работать с символы в скомпилированном объекте.
SysV ABI реализован в GNU binutils утилите nm . В этом формате используется отсортированное поле адреса памяти , поле «типа символа» и идентификатор символа (называемый «Имя»). [4]
Типы символов в SysV ABI (и выходных данных nm) указывают природу каждой записи в таблице символов. Каждый тип символа представлен одним символом. Например, записи таблицы символов, представляющие инициализированные данные, обозначаются символом «d», а записи таблицы символов для функций имеют тип символа «t» (поскольку исполняемый код находится в текстовой части объектного файла). Кроме того, использование заглавных букв типа символа указывает на тип связи: строчные буквы указывают, что символ является локальным, а прописные буквы указывают на внешнюю (глобальную) связь.
Пример: таблица символов Python
[ редактировать ]Язык программирования Python включает обширную поддержку создания таблиц символов и управления ими. [5] Свойства, которые можно запросить, включают в себя, является ли данный символ свободной переменной или связанной переменной , является ли он областью действия блока или глобальной областью действия , импортирован ли он и к какому пространству имен он принадлежит.
Пример: Таблицы динамических символов
[ редактировать ]Некоторые языки программирования позволяют манипулировать таблицей символов во время выполнения, поэтому символы можно добавлять в любое время. Рэкет является примером такого языка. [6]
Языки программирования LISP . и Scheme позволяют связать произвольные общие свойства с каждым символом [7]
Язык программирования Пролог по сути является языком манипулирования таблицами символов; символы называются атомами , и отношения между символами можно проанализировать. Аналогично, OpenCog предоставляет динамическую таблицу символов, называемую атомным пространством , которая используется для представления знаний .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Перейти обратно: а б Медь и Торчон 2011 , с. 253.
- ^ Нгуен, Бинь (2004). Словарь Linux . п. 1482 . Проверено 14 апреля 2018 г.
- ^ Copper & Torczon 2011 , с. 254.
- ^ «нм» . исходное программное обеспечение.org . Проверено 30 мая 2020 г.
- ^ symtable — документация Python
- ^ Символы - Документация по ракеткам
- ^ Символы - Документация Guile
Библиография
[ редактировать ]- Коппер, Кейт Д.; Торчон, Линда (18 января 2011 г.). Разработка компилятора (2-е изд.). Хьюстон , Техас : Elsevier , Университет Райса . дои : 10.1016/C2009-0-27982-7 . ISBN 978-0-12-088478-0 . S2CID 40425497 .
| Базы данных органов управления : Национальные |
|---|
