Sobre tablas de símbolos

Índice de la página

  1. Contenido de la tabla de símbolos.
  2. Manipulación de la TS.
  3. Volver a la página principal.

Contenido de la tabla de símbolos

La tabla de símbolos es una estructura de datos utilizada por los compiladores para guardar información que no es directamente accesible a través de los token devueltos por el analizador léxico. El valor de una constante numérica es directamente accesible a través del token, puesto que se calcula desde el propio lexema del token, pero el tipo de una variable no es directamente accesible, ya que la asociación de un tipo a una variable se hace en una sentencia de declaración, que está compuesta por varios tokens agrupados en una o varias producciones de la gramática.

Los identificadores son los elementos de los lenguajes que necesitan una estructura de datos donde acumular toda la información referente a ellos. Los tipos de identificadores dependen del lenguaje de programación utilizado. Algunos tipos de identificadores podrían ser: variables, funciones, procedimientos, clases o tipos definidos por el usuario.

De los identificadores, la tabla de símiblos contendrá: su lexema, información sobre el tipo y el ámbito de visibilidad del identificador; los dos últimos siempre dependiendo del lenguaje. Veamos unos ejemplos:

Variable
Lexema y tipo.
Matriz
Lexema, dimensiones de la matriz y tipo de los elementos.
Procedimiento
Lexema, parámetros formales.
Función
Lo mismo que el procedimiento junto con el valor devuelto.
Tipo definido por el usuario
Lexema y definición del tipo.

El ámbito de visibilidad de un identificador se define mediante entornos. Un entorno es una parte del programa fuente delimitada de alguna forma, por ejemplo el cuerpo de una función, o el cuerpo de un bucle. La información del ámbito de visibilidad de un identificador se puede guardar de muchas formas. Una forma podría ser asignando números a entornos, guardándolo como un dato más y sabiendo en todo momento el entorno activo. Otra forma es creando la estructura de la tabla de símbolos a modo de árbol, de forma que la raíz es el entorno principal y sus nodos hijos son los entornos creados a partir de él, por ejemplo una función es una entrada en el entorno principal, y a su vez tiene asignado un entorno propio. También se puede dar el caso de entornos sin identificador asociado (entornos anónimos), por ejemplo variables declaradas dentro otros entornos; en estos casos se crea un entorno debajo del entorno padre, donde se insertarán las entradas correspondientes. A continuación se ve un ejemplo:

y el código que lo produce:

PROGRAM Ejemplo;
VAR 
  a,b: INTEGER;
  PROCEDURE proc2(VAR y: INTEGER);
  VAR 
    b2: INTEGER; 
    b1: INTEGER;
    b3: INTEGER;
  BEGIN
    b3:=3;
    VAR 
      b21, b22: INTEGER; 
    BEGIN
      b21:=3;
    END

    ...
Índice de la página / Volver a la página principal.

Manipulación de la TS.

La manipulación de la tabla de símbolos consiste en la creación de entornos, inserción de entradas en dichos entornos y, modificación y eliminación de dichas entradas.

La inserción se puede realizar desde el propio analizador léxico ya que él sabe si un token es un identificador o no, pero sólo podría insertar el lexema, puesto que otra información, como el tipo asociado, sólo es conocida por el analizador semántico, y será este quien complete el resto de información.

También puede ser el analizador semántico quien se encargue de todas las tareas relacionadas con la tabla de símbolos, inserción incluída.

Como es evidente el acceso a la tabla de símbolos debe ser eficiente, puesto que va a ser consultada y modificada frecuentemente durante la compilación, por ello se suele elegir a las tablas hash como base para implementar los entornos en los que se insertan los identificadores.

Las operaciones de manipulación más comunes de la tabla de símbolos son:

Localización de entradas
Ésta es una operación básica. Dado un lexema se busca una ocurrencia suya en la estructura de la tabla de símbolos (por ejemplo tanto en el entorno actual como en los entornos padres de él). Esta operación puede devolver acceso a la entrada buscada o un error, debido a que la entrada buscada no está declara en el ámbito de visibilidad actual.
Creación de entradas
Cuando se inserta una entrada, hay que comprobar los posibles errores de duplicidad de lexemas. Estos errores dependen de las características del lenguaje (puede ir desde no permitir duplicidad de lexemas en todo el programa, hasta permitirla en el mismo entorno con tal de que no produzcan ambigüedades semánticas). Al crear una entrada se podría crear sólo con el lexema o con más datos.
Acceso a los atributos de la entrada
Una vez creada o localizada una entrada, se necesitará acceder a ella tanto para modificar datos (declaración) como para consultarlos (comprobación de tipos).
Índice de la página / Volver a la página principal.