Cómo crear una tabla de símbolos
Para realizar un seguimiento de los nombres en un programa de ámbito estático, el compilador se basa en una estructura de datos llamada tabla de símbolos. En el nivel más básico, una tabla de símbolos es un diccionario: asigna nombres a información relevante conocida por el compilador. La operación más básica aquí es colocar la nueva relación de mapeo (restricción de nombre de objeto) en la tabla y (de forma no destructiva) extraer la información debajo del mapeo usando el nombre de pila. Más adelante nos referiremos a estas dos operaciones como inserción y búsqueda respectivamente.
Otra complejidad proviene de las reglas de alcance estáticas en la mayoría de los lenguajes, que requieren el uso de diferentes entornos de referencia en diferentes partes del programa. Para manejar reglas de rango, es posible que deseemos simplemente agregar una operación de eliminación. Debido a que el compilador escanea el código de principio a fin durante la fase de análisis semántico, puede insertar nuevas restricciones al principio del rango y revocarlas al final del rango. Sin embargo, hay algunos factores que hacen que este enfoque directo no sea práctico.
En muchos lenguajes con ámbitos anidados, los efectos de las declaraciones internas pueden eclipsar las declaraciones externas, lo que significa que la tabla de símbolos debe poder contener cualquier número de asignaciones para un nombre determinado. La operación de búsqueda debe devolver el mapeo más interno y el mapeo externo debe volver a ser visible al final del alcance.
Los registros (estructuras) en lenguajes tipo Algol tienen algunas propiedades de alcance, pero no tienen la agradable estructura de anidamiento que tienen los alcances. Cuando el analizador semántico ve una declaración de registro, debe anotar los nombres de los campos de cada registro (también son recursivos, ya que los registros se pueden anidar). Al final de la declaración, cada nombre de dominio debe volver a ser invisible. Sin embargo, después de esto, tan pronto como aparezca una variable de ese tipo de registro en el cuerpo del programa (por ejemplo, en my_rec.field_name), estos nombres de dominio deben volver a ser visibles en la parte posterior al punto en la referencia. En Pascal y otros lenguajes con declaraciones with, los nombres de los campos de registro también deberían ser visibles en el contexto de varias declaraciones.
A veces algunos nombres pueden usarse antes de ser declarados, incluso en lenguajes como Algol. Por ejemplo, tanto Algol 60 como Algol 68 permiten etiquetas de referencia directas. Pascal evita esto al exigir que las etiquetas se declaren al principio del alcance, pero aún permite referencias directas para declaraciones de puntero:
type
company=record
CEO: ^persona; (*referencia directa*)
...
Fin;
Persona=registro
Empleador :^empresa;
...
Fin;
Pascal y otros lenguajes permiten la declaración directa de subrutinas para soportar la recursividad mutua :
Proceso Q (A, B: entero);
Proceso P (A, B: entero);
Inicio
...
q(3,4);
...
Fin;
Programa Q ( * Los parámetros en Pascal no son repetido*)
Inicio
...
p(4.5);
...
Fin;
Al ver la declaración directa en este código, el analizador semántico debe recordar los parámetros de Q para que puedan mostrarse nuevamente más adelante en el cuerpo de los parámetros de Q, pero al mismo tiempo, deben ser invisible. Esta operación es similar a recordar los nombres de los campos de registro.
Aunque es posible que queramos olvidar los nombres asociados al final del alcance, o incluso recuperar el espacio ocupado por estos nombres en la tabla de símbolos, aún necesitamos guardar información sobre ellos para el alcance simbólico. depurador. Este sistema de corrección de errores es una herramienta muy útil que los usuarios pueden utilizar para operar programas cómodamente, como iniciar el programa, detenerlo, leer o modificar datos en el programa, etc. Para analizar nombres de alto nivel del usuario (por ejemplo, es necesario imprimir el valor de my_firm. En [1999]), el depurador de símbolos debe tener acceso a la tabla de símbolos del compilador. Para que una tabla de símbolos esté disponible en tiempo de ejecución, los compiladores generalmente guardan la tabla en una sección oculta del último programa en lenguaje de máquina.
La mayoría de los cambios en el alcance estático se pueden manejar extendiendo la tabla de símbolos base y manteniendo el seguimiento de visibilidad agregando un par de operaciones enter_scope y left_scope. No se eliminará nada de la lista de símbolos, todas las estructuras se conservarán durante la fase de compilación y, al final, se guardarán para que las utilice el sistema de depuración. Las tablas de símbolos con manejo de visibilidad se pueden implementar de muchas maneras diferentes, y el enfoque que se describe a continuación se atribuye a LeBlanc y Cook [CL83].
A medida que se encuentra cada rango, se le asigna un número de secuencia. Dado que el alcance más externo (que contiene el identificador predefinido) tiene el número 0, el alcance que contiene el nombre global definido por el usuario tiene el número 1. Otros rangos están numerados en el orden en que se encuentran. Todos los números son diferentes entre sí y no representan el nivel de anidamiento léxico, pero otro punto es que el número de subrutinas anidadas en su interior es naturalmente mayor que el número de ámbitos circundantes.
Todos los nombres se colocan en una tabla hash grande, con el nombre como código clave, independientemente de su rango. Cada entrada en la tabla contiene un nombre de símbolo, su categoría (variable, constante, tipo, procedimiento, nombre de dominio, parámetro, etc.). ), número de rango, tipo (un puntero a otra entrada de la tabla de símbolos) y otra información contenida en una clase específica.
Además de esta tabla hash, la tabla de símbolos también contiene una pila de alcances, que indica en orden todos los alcances que componen el entorno de referencia actual. Durante el escaneo del programa por parte del analizador semántico, la pila se empuja o se abre al entrar o salir del programa, respectivamente. Los elementos de la pila de alcance contienen el número de alcance, que indica si el alcance está cerrado y, en algunos casos, posiblemente otra información.
Figura 3.13 Algoritmo de búsqueda de la tabla de símbolos de LeBron-Cook.
Cuando necesitamos buscar un nombre en una tabla, seguimos una cadena de tabla hash adecuada para encontrar algunos elementos que correspondan al nombre que estamos buscando. Para cada coincidencia, escaneamos la pila de rango para ver si el rango del elemento es visible. La profundidad de esta vista de pila no debe exceder el cierre superior. Para que los elementos importados y exportados sean visibles fuera de su alcance, cree elementos adicionales en la tabla para que contengan punteros a los elementos reales. Para todos los elementos con alcance número 0, no necesitamos verificar la pila de alcance porque son penetrables. La Figura 3.13 es el pseudocódigo del algoritmo de búsqueda.
La esquina inferior derecha de la Figura 3.14 es el esquema del programa Modula-2, y el resto de la figura muestra la configuración de la tabla de símbolos del entorno de referencia en la declaración with en el proceso P2. La pila de alcance contiene cuatro elementos, que representan la declaración with, el procedimiento P2, el módulo M y el alcance global. El alcance de una declaración with indica a qué variable de registro pertenece el nombre en ese alcance en particular. El rango de permeabilidad de la capa más externa no se indica claramente.
Figura 3.14 Tabla de símbolos de LeBron-Cook del programa de ejemplo Modula-2. La pila de alcance representa el entorno de referencia de la declaración with en el procedimiento P2. Para mayor claridad, muchos de los elementos de la lista de punteros que corresponden a números enteros y reales están representados por (1) y (2) entre paréntesis, y no se dibujan flechas.
Debido a que la tabla hash aquí usa nombres como claves, todos los elementos de un nombre específico aparecen en la misma cadena hash. En este ejemplo, una colisión hash hace que A2, F2 y T aparezcan en la misma cadena. Las variables V e I (I de M) tienen otros términos que las hacen visibles después de cruzar los límites del rango circundante M. Cuando estemos en P2, una operación de búsqueda en I encontrará la I de P2, mientras que ambos elementos de la I de M son invisibles. Un elemento de tipo t indica el número de alcance colocado en la pila de alcance durante la declaración with. Cada entrada de subrutina contiene un puntero principal a una lista vinculada de parámetros de subrutina utilizados en el análisis de llamadas (algunos vínculos a estas cadenas no se muestran en la figura). Durante la generación de código, muchas entradas de la tabla de símbolos también pueden contener campos adicionales que representan información como el tamaño del objeto y la dirección de ejecución.
Consulta Recursos para obtener información sobre la imagen. . .