Tabla de símbolos

En informática, una tabla de símbolos es una estructura de datos utilizada por un traductor de idiomas, como un compilador o intérprete, donde cada identificador (o símbolo), constante, procedimiento y función en un programa&# El código fuente de Google está asociado a información relativa a 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 a la entrada.

Fondo

Es posible que una tabla de símbolos solo exista en la memoria durante el proceso de traducción, o puede estar incrustada en la salida de la traducción, como en un archivo objeto ABI para su uso posterior. Por ejemplo, podría usarse 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.

Descripción

La información mínima contenida en una tabla de símbolos utilizada por un traductor y representación intermedia (IR) incluye el nombre del símbolo y su ubicación o dirección. Para un compilador dirigido a una plataforma con un concepto de reubicación, también contendrá atributos de reubicación (absolutos, reubicables, 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 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 se puede proporcionar 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 tablas de símbolos y listados 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. Se accede a la tabla de símbolos 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 usar una tabla de símbolos grande para todos los símbolos o usar 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 alcance de cada declaración es la sección del programa en la que se hacen referencias a "p" resolver 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 proporción de su tiempo buscando 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 están en formato 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 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 objetos, un vinculador identificará y resolverá estas referencias de símbolos. Normalmente, 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 con el primer archivo objeto y cualquier identificador externo no definido se agrega 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.

Al realizar ingeniería inversa en un ejecutable, muchas herramientas hacen referencia 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 convertirla 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 externaexterna doble bar()doble x);// Definir una función públicadoble Foo()int Cuenta){} doble suma = 0,0; // Sumar todos los valores barra(1) a bar(conta) para ()int i = 1; i . Cuenta; i++) suma += bar()doble) i); retorno suma;}

Un compilador de C que analice 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 expresión intermedios (por ejemplo, la expresión que convierte la variable de bucle i en un double, y el valor de retorno de la llamada a la función bar()), etiquetas de declaración, etc.

Ejemplo: SysV ABI

Se puede encontrar un ejemplo de una tabla de símbolos en la especificación SysV Application Binary Interface (ABI), que exige cómo se deben distribuir los símbolos en un archivo binario, de modo que diferentes compiladores, enlazadores y cargadores puedan encontrar y cargar consistentemente. trabajar con los símbolos en un objeto compilado.

La ABI de SysV se implementa en el paquete GNU binutils' utilidad nm. Este formato utiliza un campo de dirección de memoria ordenado, un campo de "tipo de símbolo" campo y un identificador de símbolo (llamado "Nombre").

Los tipos de símbolos 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 text de un archivo objeto). Además, el uso de mayúsculas en el tipo de símbolo indica 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. Las propiedades que se pueden consultar incluyen si un símbolo determinado es una variable libre o una variable vinculada, si es de alcance de bloque o de alcance global, si se importa y a qué espacio de nombres pertenece.

Ejemplo: tablas de símbolos dinámicas

Algunos lenguajes de programación permiten manipular la tabla de símbolos en tiempo de ejecución, de modo que se pueden agregar símbolos en cualquier momento. Racket es un ejemplo de tal lenguaje.

Tanto el lenguaje de programación LISP como el Scheme permiten asociar propiedades genéricas y arbitrarias con cada símbolo.

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 se pueden razonar las relaciones entre los símbolos. De manera similar, OpenCog proporciona una tabla de símbolos dinámica, llamada espacio atómico, que se utiliza para la representación del conocimiento.