Hispanopedia WikiEn informática , una tabla de símbolos es una estructura de datos donde cada identificador o símbolo (que se refiere a variables, constantes , procedimientos , funciones , etc.) en el código de un programa está asociado con la información necesaria para su funcionamiento. Esto puede presentarse en dos formas principales:
- Con los archivos objeto y ejecutables , el "código" es código máquina y la "información" es típicamente la dirección de memoria de la entidad a la que se refiere el símbolo .
- En el caso de los traductores de lenguaje , como los compiladores o los intérpretes , el "código" suele ser el código fuente, y la "información" se refiere a la declaración o aparición de la entrada en el código fuente. (Los intérpretes también necesitan una forma de encontrar el "valor" de la entrada en la tabla, que suele ser una dirección que apunta a otra estructura de datos). [ 1 ]
- En el caso de archivos de código intermedios , la "información" puede ser intermedia entre los dos tipos mencionados anteriormente.
Una tabla de símbolos del segundo tipo generalmente solo existe en memoria durante el proceso de traducción. Una tabla de símbolos del primer tipo se integra en la salida de la traducción, como en un archivo objeto ABI , para su uso posterior. Por ejemplo, podría utilizarse al cargar una biblioteca dinámica , 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 ]
Archivos objeto y ejecutables
La información mínima contenida en una tabla de símbolos utilizada por un archivo de código máquina 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 las listas de la tabla de símbolos y de referencias cruzadas al final de la traducción. [ 1 ]
Las tablas de símbolos de código máquina están optimizadas para ser compactas y suelen ser una matriz plana de estructuras. (Si fuera necesario, la conversión a una estructura de datos más "inteligente" puede realizarse en el núcleo del sistema una vez que se carga el archivo).
Aplicaciones
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.
Ejemplo: C
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 archivo objeto constaría de al menos dos cosas: una dirección de la función fooy una forma de indicar su uso bar.
Ejemplo: ABI de SysV
Un ejemplo de tabla de símbolos se encuentra en la especificación de la interfaz binaria de aplicación (ABI) SysV , que establece cómo deben organizarse los símbolos en un archivo binario, de modo que diferentes compiladores, enlazadores y cargadores puedan encontrar y trabajar con los símbolos de un objeto compilado de forma consistente. 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"). La tabla de símbolos se puede leer mediante la utilidad nm . [ 3 ] [ 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).
Al compilar el código anterior ( foo.c) en un archivo objeto foo.ousando gcc -c foo.c, podemos usar nm foo.opara examinar su tabla de símbolos:
barra en U 0000000000000000 T foo
La salida anterior indica que "bar" está presente como un símbolo global indefinido (U), a la espera de resolución por parte del enlazador, y que "foo" está presente como un símbolo de texto global (G) en el desplazamiento 0, lo cual se puede verificar mediante objdump -d foo.o:
foo.o: formato de archivo elf64-x86-64 Desmontaje de la sección .text: 0000000000000000 <foo>: 0:55 empuje %rbp 1: 48 89 e5 mov %rsp,%rbp 4: 48 83 ec 20 sub $0x20,%rsp (...)
Un ejemplo más detallado está disponible en nm (Unix) § nm output sample .
traductores de idiomas
Los traductores de idiomas tienen mucha más libertad para implementar la tabla de símbolos. Existen numerosas estructuras de datos disponibles para su implementación. Á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. [ 5 ]
Ejemplo: compilador de C
El compilador AC que analiza el código del ejemplo C anterior 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.
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. [ 6 ] 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.
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 se pueden añadir símbolos en cualquier momento. Racket es un ejemplo de este tipo de lenguaje. [ 7 ]
Tanto el lenguaje de programación LISP como el Scheme permiten asociar propiedades arbitrarias y genéricas a cada símbolo. [ 8 ]
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 .
Véase también
Referencias
- 1 2 Copper & Torczon 2011 , pág. 253.
- ↑ Nguyen, Binh (2004). Diccionario de Linux . pág. 1482. Consultado el 14 de abril de 2018 .
- ↑ "nm" . sourceware.org . Consultado el 30 de mayo de 2020 .
- ↑ "Tabla de símbolos" . refspecs.linuxbase.org .
- ↑ Copper & Torczon 2011 , pág. 254.
- ↑ tabla de símbolos — documentación de Python
- ↑ Símbolos - Documentación de Racket
- ↑ Símbolos - Documentación de Guile
Bibliografía
- Estructuras del compilador