En informática , una tabla de símbolos es una estructura de datos utilizada por un traductor de idiomas , como un compilador o un intérprete , donde cada identificador (o símbolo) en el código fuente de un programa está asociado con información relacionada con su declaración o aparición en la fuente. En otras palabras, las entradas de una tabla de símbolos almacenan la información relacionada con el símbolo correspondiente de la entrada.
Fondo
Una tabla de símbolos solo puede existir en la memoria durante el proceso de traducción, o puede estar incrustada en la salida de la traducción, como en un archivo de objeto ABI para uso posterior. Por ejemplo, se puede utilizar durante una sesión de depuración interactiva o como recurso para formatear un informe de diagnóstico durante o después de la ejecución de un programa. [1]
Descripción
La información mínima contenida en una tabla de símbolos utilizada por un traductor incluye el nombre del símbolo y su ubicación o dirección. Para un compilador que tenga como objetivo una plataforma con un concepto de reubicación, también contendrá atributos de reubicación (absolutos, reubicables, etc.) e información de reubicación necesaria para símbolos reubicables. Las tablas de símbolos para lenguajes de programación de alto nivel pueden almacenar el tipo de símbolo: cadena, entero, punto flotante, etc., su tamaño, sus dimensiones y sus límites. No toda esta información se incluye en el archivo de salida, pero puede proporcionarse para su uso en la depuración . En muchos casos, la información de referencia cruzada del símbolo se almacena o se vincula a la tabla de símbolos. La mayoría de los compiladores imprimen parte o toda esta información en una tabla de símbolos y listas de referencias cruzadas al final de la traducción.
Implementación
Hay numerosas estructuras de datos disponibles para implementar tablas. Se pueden utilizar árboles, listas lineales y listas autoorganizadas para implementar una tabla de símbolos. La mayoría de las fases de un compilador acceden a la tabla de símbolos, comenzando con el análisis léxico y continuando con la optimización.
Un compilador puede usar una tabla de símbolos grande para todos los símbolos o usar tablas de símbolos jerárquicas separadas para diferentes ámbitos . Por ejemplo, en un lenguaje de ámbito como Algol o PL / I, un símbolo "p" se puede declarar por separado en varios procedimientos, quizás con diferentes atributos. El alcance de cada declaración es la sección del programa en la que las referencias a "p" resuelven esa declaración. Cada declaración representa un identificador único "p". La tabla de símbolos debe tener algún medio para diferenciar las referencias a las diferentes "p".
Una estructura de datos común utilizada para implementar tablas de símbolos es la tabla hash . El tiempo de búsqueda en tablas hash es independiente de la cantidad de elementos almacenados en la tabla, por lo que es eficiente para una gran cantidad de elementos. También simplifica la clasificación de literales en formato tabular al incluir la clasificación en el cálculo de la clave hash.
Como el analizador léxico pasa una gran parte de su tiempo buscando en la tabla de símbolos, esta actividad tiene un efecto crucial en la velocidad general del compilador. Una tabla de símbolos debe organizarse de tal manera que las entradas se puedan encontrar lo más rápidamente posible. Las tablas hash se utilizan generalmente para organizar una tabla de símbolos, donde la palabra clave o el identificador se 'hash' para producir un subíndice de matriz. Las colisiones son inevitables en una tabla hash y una forma común de manejarlas es almacenar el sinónimo en el siguiente espacio libre disponible en la tabla.
Aplicaciones
Un archivo de objeto contendrá una tabla de símbolos de los identificadores que contiene que son visibles externamente. Durante la vinculación de diferentes archivos de objetos, un vinculador identificará y resolverá estas referencias de símbolos. Por lo general, todos los símbolos externos no definidos se buscarán en una o más bibliotecas de objetos . Si se encuentra un módulo que define ese símbolo, se vincula junto con el primer archivo de objeto, y los identificadores externos indefinidos se agregan a la lista de identificadores que se buscarán. Este proceso continúa hasta que se hayan resuelto todas las referencias externas. Es un error si uno o más quedan sin resolver al final del proceso.
Mientras se aplica ingeniería inversa a un ejecutable, muchas herramientas se refieren a la tabla de símbolos para verificar qué direcciones se han asignado a variables globales y funciones conocidas. Si la tabla de símbolos se ha eliminado o limpiado antes de convertirse en un ejecutable, a las herramientas les resultará más difícil determinar direcciones o comprender algo sobre el programa.
Ejemplo
Considere el siguiente programa escrito en C :
// Declarar una función externa extern double bar ( double x );// Definir una función pública double foo ( int count ) { double sum = 0.0 ; // Suma todos los valores bar (1) a bar (count) for ( int i = 1 ; i <= count ; i ++ ) sum + = bar (( double ) i ); devolución de suma ; }
El compilador de CA que analiza este código contendrá al menos las siguientes entradas de la tabla de símbolos:
Nombre del símbolo | Tipo | Alcance |
---|---|---|
bar | función, doble | externo |
x | doble | parámetro de función |
foo | función, doble | global |
count | En t | parámetro de función |
sum | doble | bloque local |
i | En t | declaración for-loop |
Además, la tabla de símbolos también contendrá entradas generadas por el compilador para valores de expresión intermedios (p. Ej., La expresión que i
convierte la variable de bucle en a double
, y el valor de retorno de la llamada a la función bar()
), etiquetas de instrucciones, etc.
Ejemplo: SysV ABI
Habla a | Tipo | Nombre |
---|---|---|
00000020 | a | T_BIT |
00000040 | a | F_BIT |
00000080 | a | I_BIT |
20000004 | t | irqvec |
20000008 | t | fiqvec |
2000000c | t | InitReset |
20000018 | T | _principal |
20000024 | t | Final |
20000030 | T | AT91F_US3_CfgPIO_useB |
2000005c | t | AT91F_PIO_CfgPeriph |
200000b0 | T | principal |
20000120 | T | AT91F_DBGU_Printk |
20000190 | t | AT91F_US_TxReady |
200001c0 | t | AT91F_US_PutChar |
200001f8 | T | AT91F_SpuriousHandler |
20000214 | T | AT91F_DataAbort |
20000230 | T | AT91F_FetchAbort |
2000024c | T | AT91F_Undef |
20000268 | T | AT91F_UndefHandler |
20000284 | T | AT91F_LowLevelInit |
200002e0 | t | AT91F_DBGU_CfgPIO |
2000030c | t | AT91F_PIO_CfgPeriph |
20000360 | t | AT91F_US_Configure |
200003dc | t | AT91F_US_SetBaudrate |
2000041c | t | AT91F_US_Baudrate |
200004ec | t | AT91F_US_SetTimeguard |
2000051c | t | AT91F_PDC_Open |
2000059c | t | AT91F_PDC_DisableRx |
200005c8 | t | AT91F_PDC_DisableTx |
200005f4 | t | AT91F_PDC_SetNextTx |
20000638 | t | AT91F_PDC_SetNextRx |
2000067c | t | AT91F_PDC_SetTx |
200006c0 | t | AT91F_PDC_SetRx |
20000704 | t | AT91F_PDC_EnableRx |
20000730 | t | AT91F_PDC_EnableTx |
2000075c | t | AT91F_US_EnableTx |
20000788 | T | __aeabi_uidiv |
20000788 | T | __udivsi3 |
20000884 | T | __aeabi_uidivmod |
2000089c | T | __aeabi_idiv0 |
2000089c | T | __aeabi_ldiv0 |
2000089c | T | __div0 |
200009a0 | D | _datos |
200009a0 | A | _etext |
200009a0 | D | holaamigosh |
200009a4 | A | __bss_end__ |
200009a4 | A | __bss_start |
200009a4 | A | __bss_start__ |
200009a4 | A | _edata |
200009a4 | A | _final |
Un ejemplo de una tabla de símbolos se puede encontrar en el SysV interfaz binaria de aplicación especificación (ABI), que los mandatos de cómo los símbolos deben ser presentadas en un archivo binario, de manera que diferentes compiladores, enlazadores y cargadores pueden encontrar y trabajar con el todo coherente símbolos en un objeto compilado.
La ABI de SysV se implementa en la utilidad nm de GNU binutils . Este formato utiliza un campo de dirección de memoria ordenada , un campo de "tipo de símbolo" y un identificador de símbolo (llamado "Nombre"). [2]
Los tipos de símbolo en SysV ABI (y la salida de nm) indican la naturaleza de cada entrada en la tabla de símbolos. Cada tipo de símbolo está representado por un solo carácter. Por ejemplo, las entradas de la tabla de símbolos que representan datos inicializados se indican con el carácter "d" y las entradas de la tabla de símbolos para funciones tienen el tipo de símbolo "t" (porque el código ejecutable se encuentra en la sección de texto de un archivo de objeto). Además, las mayúsculas del tipo de símbolo indican el tipo de vínculo: las letras minúsculas indican que el símbolo es local y las mayúsculas indican un vínculo externo (global).
Ejemplo: la tabla de símbolos de Python
El lenguaje de programación Python incluye un amplio soporte para crear y manipular tablas de símbolos. [3] Las propiedades que se pueden consultar incluyen si un símbolo dado es una variable libre o una variable vinculada , si es un alcance de bloque o un alcance global , si se importa y a qué espacio de nombres pertenece.
Ejemplo: tablas de símbolos dinámicos
Algunos lenguajes de programación permiten manipular la tabla de símbolos en tiempo de ejecución, de modo que los símbolos se pueden agregar en cualquier momento. La raqueta es un ejemplo de este tipo de lenguaje. [4]
Los lenguajes de programación LISP y Scheme permiten asociar propiedades genéricas arbitrarias con cada símbolo. [5]
El lenguaje de programación Prolog es esencialmente un lenguaje de manipulación de tablas de símbolos; los símbolos se llaman átomos , y las relaciones entre los símbolos se pueden razonar. De manera similar, OpenCog proporciona una tabla de símbolos dinámica, denominada espacio atómico , que se utiliza para la representación del conocimiento .
Ver también
- Símbolo de depuración
Referencias
- ^ Nguyen, Binh (2004). Diccionario de Linux . pag. 1482 . Consultado el 14 de abril de 2018 .
- ^ "nm" . sourceware.org . Consultado el 30 de mayo de 2020 .
- ^ symtable - documentación de Python
- ^ Símbolos - Documentación de la raqueta
- ^ Símbolos - Documentación de Guile