Tabla de símbolos

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 , símbolo , constante , procedimiento y función del código fuente de un programa se asocia con información relativa a su declaración o aparición en el código fuente. En otras palabras, las entradas de una tabla de símbolos almacenan la información relacionada con el símbolo correspondiente a cada entrada. ^{[ 1 ]}

Una tabla de símbolos puede existir únicamente en memoria durante el proceso de traducción, o puede estar integrada en la salida de la traducción, como en un archivo objeto ABI para su uso posterior. Por ejemplo, podría utilizarse 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. ^{[ 2 ]}

La información mínima contenida en una tabla de símbolos utilizada por un traductor y una representación intermedia (RI) incluye el nombre del símbolo y su ubicación o dirección. Para un compilador que se dirige a una plataforma con el 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 puede proporcionarse para su uso en la depuración . En muchos casos, la información de referencia cruzada del símbolo se almacena con la tabla de símbolos o está vinculada a ella. La mayoría de los compiladores imprimen parte o la totalidad de esta información en la tabla de símbolos y en los listados de referencias cruzadas al final de la traducción. ^{[ 1 ]}

Existen numerosas estructuras de datos para implementar tablas. Árboles, listas lineales y listas autoorganizadas pueden utilizarse para implementar una tabla de símbolos. La tabla de símbolos es consultada en la mayoría de las fases de un compilador, desde el análisis léxico hasta la optimización.

Un compilador puede usar una tabla de símbolos grande para todos los símbolos o tablas de símbolos separadas o jerárquicas para diferentes ámbitos . Por ejemplo, en un lenguaje con ámbitos definidos como Algol o PL/I, un símbolo "p" puede declararse 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 mecanismo para diferenciar las referencias a los distintos "p".

Dado que el analizador semántico y el generador de código dedican una gran parte de su tiempo a buscar entradas en la tabla de símbolos, estas etapas tienen un efecto crítico en la velocidad general del compilador; la tabla de símbolos debe estar organizada de manera que las entradas se puedan encontrar lo más rápido posible. 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 relativamente independiente del número de elementos almacenados en la tabla (tiempo constante), por lo que es eficiente para un gran número de elementos. También simplifica la clasificación de literales en un formato tabular al incluir la clasificación en el cálculo de la clave hash. ^{[ 3 ]}

Un archivo objeto contiene una tabla de símbolos con los identificadores visibles externamente. Durante la vinculación de diferentes archivos objeto, un enlazador identifica y resuelve estas referencias a símbolos. Generalmente, se buscan todos los símbolos externos no definidos en una o más bibliotecas de objetos . Si se encuentra un módulo que define dicho símbolo, se vincula con el primer archivo objeto y los identificadores externos no definidos se añaden a la lista de identificadores que se deben buscar. Este proceso continúa hasta que se hayan resuelto todas las referencias externas. Si al final del proceso queda alguna referencia sin resolver, se produce un error.

Al realizar ingeniería inversa de un ejecutable, muchas herramientas consultan la tabla de símbolos para verificar las direcciones asignadas a las variables globales y las funciones conocidas. Si la tabla de símbolos se ha eliminado o vaciado antes de convertir el programa en un ejecutable, a las herramientas les resultará más difícil determinar las direcciones o comprender el programa.

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 de 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 en 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 del bucle en un double, y el valor de retorno de la llamada a la función bar()), etiquetas de sentencias, etc.

Un ejemplo de tabla de símbolos se puede encontrar en la especificación de la interfaz binaria de aplicación (ABI) de SysV , que establece cómo deben organizarse los símbolos en un archivo binario, de modo que los diferentes compiladores, enlazadores y cargadores puedan encontrar y trabajar con los símbolos de un objeto compilado de forma coherente.

La ABI SysV está implementada en la utilidad nm de GNU binutils . Este formato utiliza un campo de dirección de memoria ordenado , 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 en la salida de nm) indican la naturaleza de cada entrada en la tabla de símbolos. Cada tipo de símbolo se representa con 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 objeto). Además, el uso de mayúsculas en el 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 ligada , si tiene ámbito de bloque o á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 pueden añadir 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 arbitrarias y genéricas 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 se pueden analizar las relaciones entre ellos. 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 .

• Símbolo de depuración
• .debug_info

• Copper, Keith D.; Torczon, Linda (18 de enero de 2011). Ingeniería de un compilador (2.ª  ed.). Houston , Texas : Elsevier , Rice University . doi : 10.1016/C2009-0-27982-7 . ISBN 978-0-12-088478-0. S2CID 40425497 .