Clase 4 - Tabla de Simbolos

Tabla de Símbolos

¿Qué es la tabla de simbolos?

Almacena todos los nombres declarados en el programa y sus atributos (tipo, valor, dirección, parámetros, etc.).

Se usa en las distintas fases del compilador.

Estructura de datos.

Almacena información sobre:

Los identificadores.

Las palabras reservadas.

Las constantes.

Contiene una entrada para cada uno de los símbolos definidos en el programa fuente.

Sobre los identificadores, y opcionalmente sobre las palabras reservadas y las constantes.

Información sobre el lexema, tipo de datos, ámbito y dirección en memoria.

Por cada entrada en la tabla de símbolos habrá que guardar:

Lexema correspondiente.

Tipo.(depende de la implementación).

Ámbito.(depende de la implementación).

Dirección de memoria asignada.

Forma.(depende de la implementación).

¿Utilidad de la tabla de símbolos?

·  Analizador Léxico: Pasa en el token y la entrada de la TS creada.

·    Analizador Sintáctico y Semántico: busca el token y si no la encuentra crea una nueva entrada.

Operaciones Principales.

Insertar: introduce un símbolo tras una declaración.

Buscar: recupera información asociada a un símbolo.

Eliminar: borra la información.

Ejemplo de Uso I.

Declaración previa al uso de variables:

·         En las declaraciones, inserción en la TS.

Aparición de una variable en una sentencia, búsqueda en la TS:

·         Si se encuentra Fue declarada.

·         Si no se encuentra Error de compilación.

Ejemplos de Uso II.

Acceso a una posición de un array:

·         Declaración > Inserción en la TS.

·         Acceso a un array > Búsqueda en la TS.

1. Comprobación de tipo array.
2. Comprobación acceso a una posición válida.

Ejemplo:

Estructuras usadas para implementar una tabla de símbolos.

Lista

1. Simple de implementar.
2. Lenta cuando se trabaja con muchos identificadores.

Árbol

1. Rápida.
2. Consume más memoria.
3. Es útil cuando hay muchas declaraciones.

Tabla de Hashing

1. Rápida.
2. Difícil de implementar.
3. Se debe definir una función de hashing apropiada para evitar colisiones.

Manejo de palabras claves

Si el scanner diferencia entre un identificador y una palabra reservada, entonces devuelve al parser el código correspondiente. Aquí no se requiere el ingreso de la palabra clave en la TS.

Entradas en la TS

Una primera desagregación de una entrada de la tabla de símbolos:

Parte Fija:

Parte Variante:

Procedimiento o Función:

Operaciones sobre TS: Lenguajes Estructurados a Bloques.

Cuando se busque un identificador en la TS se debe retornar el último identificador insertado, es decir, el identificador declarado en el bloque actual, si en tal bloque no existe el identificador buscarlo en el bloque que lo contenga, y así sigue hasta encontrarlo. Si el identificador no se encuentra en ninguno de los bloques anidados entonces no existe.

Ejemplo: