Tabla de símbolos en el compilador

Requisito previo: fases de un compilador 

La tabla de símbolos es una estructura de datos importante creada y mantenida por el compilador para realizar un seguimiento de la semántica de las variables, es decir, almacena información sobre el alcance e información vinculante sobre nombres, información sobre instancias de varias entidades, como nombres de variables y funciones, clases, objetos, etc 

• Está integrado en las fases de análisis léxico y sintáctico.
• La información es recopilada por las fases de análisis del compilador y es utilizada por las fases de síntesis del compilador para generar código.
• Es utilizado por el compilador para lograr eficiencia en tiempo de compilación.
• Es utilizado por varias fases del compilador de la siguiente manera: – 
  1. Análisis léxico: crea nuevas entradas de tabla en la tabla, por ejemplo, como entradas sobre tokens.
  2. Análisis de sintaxis: agrega información sobre el tipo de atributo, alcance, dimensión, línea de referencia, uso, etc. en la tabla.
  3. Análisis semántico: utiliza la información disponible en la tabla para verificar la semántica, es decir, para verificar que las expresiones y las asignaciones sean semánticamente correctas (verificación de tipos) y actualizarlas en consecuencia.
  4. Generación de código intermedio: se refiere a la tabla de símbolos para saber cuánto y qué tipo de tiempo de ejecución se asigna y la tabla ayuda a agregar información de variables temporales.
  5. Optimización de código: utiliza la información presente en la tabla de símbolos para la optimización dependiente de la máquina.
  6. Generación de código de destino: genera código utilizando la información de dirección del identificador presente en la tabla.

Entradas de la tabla de símbolos: cada entrada en la tabla de símbolos está asociada con atributos que respaldan al compilador en diferentes fases. 

Elementos almacenados en la tabla de símbolos: 

• Nombres de variables y constantes
• Nombres de procedimientos y funciones
• Constantes literales y strings
• Temporales generados por el compilador
• Etiquetas en los idiomas de origen

Información utilizada por el compilador de la tabla de símbolos:  

• Tipo de datos y nombre
• Declaración de procedimientos
• Compensación en almacenamiento
• Si estructura o registro entonces, un puntero a la tabla de estructura.
• Para parámetros, ya sea que el parámetro pase por valor o por referencia
• Número y tipo de argumentos pasados ​​a la función
• Dirección básica

Operaciones de la tabla de símbolos: las operaciones básicas definidas en una tabla de símbolos incluyen: 
 

Implementación de la tabla de símbolos: las 
siguientes son estructuras de datos de uso común para implementar la tabla de símbolos:  

1. Lista – 
   • En este método, se utiliza una array para almacenar nombres e información asociada.
   • Se mantiene un puntero «disponible» al final de todos los registros almacenados y se agregan nuevos nombres en el orden en que llegan
   • Para buscar un nombre, comenzamos desde el principio de la lista hasta el puntero disponible y, si no se encuentra, obtenemos un error «uso del nombre no declarado»
   • Al insertar un nuevo nombre, debemos asegurarnos de que no esté ya presente; de ​​lo contrario, se producirá un error, es decir, «Múltiples nombres definidos».
   • La inserción es rápida O (1), pero la búsqueda es lenta para tablas grandes: O (n) en promedio
   • La ventaja es que ocupa una cantidad mínima de espacio.
2. Lista enlazada – 
   • Esta implementación utiliza una lista enlazada. Se agrega un campo de enlace a cada registro.
   • La búsqueda de nombres se realiza en el orden indicado por el enlace del campo de enlace.
   • Se mantiene un puntero «Primero» para apuntar al primer registro de la tabla de símbolos.
   • La inserción es rápida O (1), pero la búsqueda es lenta para tablas grandes: O (n) en promedio
3. Tabla hash – 
   • En el esquema hash, se mantienen dos tablas: una tabla hash y una tabla de símbolos, y son el método más utilizado para implementar tablas de símbolos.
   • Una tabla hash es una array con un rango de índice: 0 a tamaño de tabla – 1. Estas entradas son punteros que apuntan a los nombres de la tabla de símbolos.
   • Para buscar un nombre, usamos una función hash que dará como resultado un número entero entre 0 y el tamaño de la tabla: 1.
   • La inserción y la búsqueda se pueden hacer muy rápido: O (1).
   • La ventaja es que la búsqueda rápida es posible y la desventaja es que el hashing es complicado de implementar.
4. Árbol de búsqueda binaria – 
   • Otro enfoque para implementar una tabla de símbolos es usar un árbol de búsqueda binaria, es decir, agregamos dos campos de enlace, es decir, hijo izquierdo y derecho.
   • Todos los nombres se crean como hijos del Node raíz que siempre sigue la propiedad del árbol de búsqueda binaria.
   • La inserción y la búsqueda son O (log ₂ n) en promedio.