Tablas de símbolos

Las tablas de símbolos (también llamadas tablas de identificadores y tablas de nombres), realizan dos importantes funciones en el proceso de traducción: verificar que la semántica sea correcta y ayudar en la generación apropiada de código.

Ambas funciones se realizan insertando o recuperando desde la tabla de símbolos los atributos de las variables usadas en el programa fuente. Estos atributos, tales como: el nombre, tipo, dirección de almacenamiento y dimensión de una variable, usualmente se encuentran explícitamente en las declaraciones o más implícitamente a través del contexto en que aparecen los nombres de variables en el programa.

Una de las estructuras de datos que se encuentran relacionadas con las fases del proceso de compilación es la tabla de símbolos, la cual tiene como propósito registrar información que se comparte entre varias etapas y que permite administrar los recursos asociados a las entidades que manipulará el programa. La tabla de símbolos tiene típicamente la siguiente estructura:

En donde podemos apreciar la designación de la entidad y su token -derivados del análisis de léxico- asi como una serie de atributos (tipo de dato, dirección en memoria) que emanan de otras fases (análisis gramatical y semántico). Las consultas a la tabla de símbolos se realizan por medio del lexema con que se designa a la entidad.

Esta concepción de la tabla de símbolos es demasiado simple para fines prácticos si consideramos que el lexema de la entidad es de longitud variable y se desea que la estructura sea homogenea.

Una solución es considerar que en el campo lexema se tiene un apuntador (que siempre ocupa el mismo espacio) hacia donde se registrarán propiamente los lexemas. Eso evitará el desperdicio de memoria al tener el espacio justo para representar a cada lexema.

La creación de la tabla de símbolos compete inicialmente al analizador de léxico, quien registrará a las entidades (reconocidas bajo el patrón de Identificador) de manera única, por medio del binomio de operaciones Búsqueda-Inserción.

En el contexto de un programa las entidades pueden describir propiamente objetos manipulables por el lenguaje (por ejemplo variables, constantes o funciones) o descriptores de acciones (las palabras reservadas); ambas situaciones son reconocidas bajo el mismo patrón de identificador y la tabla de símbolos se emplea para hacer su discriminación. El analizador de léxico funciona bajo el siguiente mecanismo:

REPITE
	Token = AnaLex();
	SI Token == Identificador
	ENTONCES
		Token= REVISA_RESERVADAS(lexema)
	FSI
HASTA QUE Token == EOF
FREPITE

Como las palabras reservadas es un conjunto de entidades conocido y finito, la tabla de símbolos se inicializa con ellas y cuando se reconoce un identificador, su lexema se busca en la tabla y si se encuentra en ella, se regresa el token correspondiente a través de invocar a la función REVISA_RESERVADAS.

El algoritmo de la funcion REVISA_RESERVADAS es el siguiente:

REVISA_RESERVADAS(lexema)
INICIO
	p=BUSQUEDA(lexema)
	SI p == 0
	ENTONCES
		p=INSERTAR(lexema)
	FSI
	Regresa TABLA[p].Token
FIN

Este algoritmo supone al existencia de dos funciones que realizan la búsqueda y la inserción de un lexema en la tabla de símbolos, considerando de la existencia de la siguiente estructura de la tabla de símbolos:

donde última_entrada direcciona la última entidad registrada y último_lexema la primera localidad disponible donde se registran los lexemas. La función BUSQUEDA se guia bajo el siguiente algoritmo:

BUSQUEDA (lexema)
INICIO
	Indice=última_entrada
	MIENTRAS índice>0
	REPITE
	Si contenido(TABLA[Indice].Ap_lexema)==lexema
	ENTONCES
		regresa Indice
	SINO 
		Indice:=Indice-1
	FSI
	FREPITE
	Regresa Indice 
FIN

donde es de notar que la búsqueda se inicia de la última entidad registrada hacia la primera bajo el supuesto que en un programa se encuentran con mayor frecuencia referencias a variables (que se registran al final) que a palabras reservadas (que estan registradas al inicio de la tabla).

Si la búsqueda fracasa, la entidad tiene que darse de alta por la función INSERTAR, cuyo algoritmo es:

INSERTAR (lexema)
INICIO
	LEXEMAS[último_lexema] = lexema
	última_entrada = última_entrada + 1
	TABLA[última_entrada].Ap_lexema = último_lexema.
	TABLA[última_entrada].Token = última entrada.
	último_lexema = último_lexema + LONGITUD(lexema).
	Regresa última_entrada 
FIN

Donde LONGITUD es una función que determina el número de caracteres que conforman al lexema insertado.