Diseño del compilador: tabla de símbolos

La tabla de símbolos es una estructura de datos importante creada y mantenida por los compiladores para almacenar información sobre la aparición de varias entidades, como nombres de variables, nombres de funciones, objetos, clases, interfaces, etc. La tabla de símbolos es utilizada tanto por el análisis como por la síntesis. partes de un compilador.

Una tabla de símbolos puede servir para los siguientes propósitos dependiendo del idioma en cuestión:

  • Para almacenar los nombres de todas las entidades en forma estructurada en un solo lugar.

  • Para verificar si se ha declarado una variable.

  • Para implementar la verificación de tipos, verificando que las asignaciones y expresiones en el código fuente sean semánticamente correctas.

  • Determinar el alcance de un nombre (resolución de alcance).

Una tabla de símbolos es simplemente una tabla que puede ser lineal o una tabla hash. Mantiene una entrada para cada nombre en el siguiente formato:

<symbol name,  type,  attribute>

Por ejemplo, si una tabla de símbolos tiene que almacenar información sobre la siguiente declaración de variable:

static int interest;

entonces debería almacenar la entrada como:

<interest, int, static>

La cláusula de atributo contiene las entradas relacionadas con el nombre.

Implementación

Si un compilador va a manejar una pequeña cantidad de datos, entonces la tabla de símbolos se puede implementar como una lista desordenada, que es fácil de codificar, pero solo es adecuada para tablas pequeñas. Una tabla de símbolos se puede implementar de una de las siguientes formas:

  • Lista lineal (ordenada o no ordenada)
  • Árbol de búsqueda binaria
  • Tabla de picadillo

Entre todas, las tablas de símbolos se implementan principalmente como tablas hash, donde el símbolo del código fuente en sí mismo se trata como una clave para la función hash y el valor de retorno es la información sobre el símbolo.

Operaciones

Una tabla de símbolos, ya sea lineal o hash, debe proporcionar las siguientes operaciones.

insertar()

Esta operación se usa con más frecuencia por fase de análisis, es decir, la primera mitad del compilador donde se identifican los tokens y los nombres se almacenan en la tabla. Esta operación se utiliza para agregar información en la tabla de símbolos sobre nombres únicos que aparecen en el código fuente. El formato o estructura en la que se almacenan los nombres depende del compilador en mano.

Un atributo de un símbolo en el código fuente es la información asociada con ese símbolo. Esta información contiene el valor, el estado, el alcance y el tipo del símbolo. La función insert () toma el símbolo y sus atributos como argumentos y almacena la información en la tabla de símbolos.

Por ejemplo:

int a;

debe ser procesado por el compilador como:

insert(a, int);

buscar()

La operación lookup () se usa para buscar un nombre en la tabla de símbolos para determinar:

  • si el símbolo existe en la tabla.
  • si se declara antes de que se utilice.
  • si el nombre se usa en el alcance.
  • si el símbolo está inicializado.
  • si el símbolo se declara varias veces.

El formato de la función lookup () varía según el lenguaje de programación. El formato básico debe coincidir con lo siguiente:

lookup(symbol)

Este método devuelve 0 (cero) si el símbolo no existe en la tabla de símbolos. Si el símbolo existe en la tabla de símbolos, devuelve sus atributos almacenados en la tabla.

Gestión del alcance

Un compilador mantiene dos tipos de tablas de símbolos: una global symbol table al que se puede acceder mediante todos los procedimientos y scope symbol tables que se crean para cada ámbito del programa.

Para determinar el alcance de un nombre, las tablas de símbolos se organizan en una estructura jerárquica como se muestra en el siguiente ejemplo:

. . . 
int value=10;

void pro_one()
   {
   int one_1;
   int one_2;
   
      {              \
      int one_3;      |_  inner scope 1 
      int one_4;      | 
      }              /
      
   int one_5; 
   
      {              \   
      int one_6;      |_  inner scope 2
      int one_7;      |
      }              /
   }
   
void pro_two()
   {
   int two_1;
   int two_2;
   
      {              \
      int two_3;      |_  inner scope 3
      int two_4;      |
      }              /
      
   int two_5;
   }
. . .

El programa anterior se puede representar en una estructura jerárquica de tablas de símbolos:

La tabla de símbolos globales contiene nombres para una variable global (valor int) y dos nombres de procedimiento, que deberían estar disponibles para todos los nodos secundarios que se muestran arriba. Los nombres mencionados en la tabla de símbolos pro_one (y todas sus tablas secundarias) no están disponibles para los símbolos pro_two y sus tablas secundarias.

Esta jerarquía de la estructura de datos de la tabla de símbolos se almacena en el analizador semántico y cada vez que se necesita buscar un nombre en una tabla de símbolos, se busca utilizando el siguiente algoritmo:

  • primero se buscará un símbolo en el ámbito actual, es decir, en la tabla de símbolos actual.

  • si se encuentra un nombre, la búsqueda se completa; de lo contrario, se buscará en la tabla de símbolos principal hasta que,

  • o se encuentra el nombre o se ha buscado el nombre en la tabla de símbolos global.