En informática , una tabla de símbolos es una estructura de datos utilizada por un traductor de lenguaje como un compilador o intérprete , donde cada identificador (o símbolo ), constante , procedimiento y función 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. [1]
Una tabla de símbolos puede existir únicamente en la memoria durante el proceso de traducción, o puede estar incorporada en la salida de la traducción, como en un archivo de objeto ABI para su uso posterior. Por ejemplo, puede utilizarse durante una sesión de depuración interactiva o como recurso para dar formato a un informe de diagnóstico durante o después de la ejecución de un programa. [2]
La información mínima contenida en una tabla de símbolos utilizada por un traductor y una representación intermedia (IR) incluye el nombre del símbolo y su ubicación o dirección. Para un compilador que apunta a una plataforma con un concepto de reubicabilidad, también contendrá atributos de reubicabilidad (absoluto, reubicable, etc.) y la información de reubicación necesaria para los símbolos reubicables. Las tablas de símbolos para lenguajes de programación de alto nivel pueden almacenar el tipo del 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 se puede proporcionar para su uso en la depuración . En muchos casos, la información de referencia cruzada del símbolo se almacena con o está vinculada a la tabla de símbolos. La mayoría de los compiladores imprimen parte o toda esta información en la tabla de símbolos y en los listados de referencia cruzada al final de la traducción. [1]
Existen 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 tabla de símbolos se accede en la mayoría de las fases de un compilador, comenzando con el análisis léxico y continuando con la optimización.
Un compilador puede utilizar una tabla de símbolos grande para todos los símbolos o utilizar tablas de símbolos separadas o jerárquicas para diferentes ámbitos . Por ejemplo, en un lenguaje con ámbito como Algol o PL/I, un símbolo "p" se puede declarar por separado en varios procedimientos, quizás con diferentes atributos. El ámbito de cada declaración es la sección del programa en la que las referencias a "p" se resuelven en 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 los 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 las tablas hash es independiente del número 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. [3]
Como el analizador léxico pasa 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 estar organizada de tal manera que las entradas se puedan encontrar lo más rápido 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.
Un archivo de objeto contendrá una tabla de símbolos de los identificadores que contiene y que son visibles externamente. Durante la vinculación de diferentes archivos de objeto, un enlazador identificará y resolverá estas referencias de símbolos. Por lo general, se buscarán todos los símbolos externos no definidos 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 todos los identificadores externos no definidos 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 una o más permanecen sin resolver al final del proceso.
Al realizar ingeniería inversa de un ejecutable, muchas herramientas consultan la tabla de símbolos para verificar qué direcciones se han asignado a las variables globales y las funciones conocidas. Si se ha eliminado o vaciado la tabla de símbolos antes de convertirla en un ejecutable, a las herramientas les resultará más difícil determinar las direcciones o comprender algo sobre el programa.
Considere el siguiente programa escrito en C :
// Declarar una función externa extern double bar ( double x ); // Define una función pública double foo ( int count ) { double sum = 0.0 ; // Suma todos los valores bar(1) a bar(count) para ( int i = 1 ; i <= count ; i ++ ) suma += bar (( double ) i ); return suma ; } El compilador AC que analiza este código contendrá al menos las siguientes entradas de la tabla de símbolos:
Además, la tabla de símbolos también puede contener entradas generadas por el compilador para valores de expresiones intermedias (por ejemplo, la expresión que convierte la ivariable de bucle en a doubley el valor de retorno de la llamada a la función bar()), etiquetas de declaraciones, etcétera.
Se puede encontrar un ejemplo de una tabla de símbolos en la especificación de la Interfaz Binaria de Aplicación (ABI) de SysV , que establece cómo deben disponerse los símbolos en un archivo binario, de modo que los diferentes compiladores, enlazadores y cargadores puedan encontrar y trabajar consistentemente con los símbolos en un objeto compilado.
La ABI SysV está implementada 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"). [4]
Los tipos de símbolos en la ABI de SysV (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, la capitalización del tipo de símbolo indica el tipo de enlace: las letras minúsculas indican que el símbolo es local y las mayúsculas indican un enlace externo (global).
El lenguaje de programación Python incluye un amplio soporte para crear y manipular tablas de símbolos. [5] Las propiedades que se pueden consultar incluyen si un símbolo dado es una variable libre o una variable vinculada , si es de ámbito de bloque o de ámbito global , si es importado y a qué espacio de nombres pertenece.
Algunos lenguajes de programación permiten manipular la tabla de símbolos en tiempo de ejecución, de modo que se puedan agregar símbolos en cualquier momento. Racket es un ejemplo de este tipo de lenguaje. [6]
Tanto el lenguaje de programación LISP como el Scheme permiten asociar propiedades genéricas arbitrarias a cada símbolo. [7]
El lenguaje de programación Prolog es esencialmente un lenguaje de manipulación de tablas de símbolos; los símbolos se denominan átomos y las relaciones entre símbolos se pueden razonar. De manera similar, OpenCog proporciona una tabla de símbolos dinámica, denominada espacio de átomos , que se utiliza para la representación del conocimiento .