Tabla de STabla de Síímbolosmbolos

Diseño y Construcción de Compiladores-2011-

Tabla de STabla de Síímbolosmbolos

¿Qué es?

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.

Tabla de STabla de Síímbolosmbolos

Analizador LexicográficoInserta en TS cada id que detecta y si corresponde da error si ya existe.

Analizador SintácticoInserta el tipo del id.

Analizador SemánticoVerifica que cada id sea declarado antes de usarlo.Recupera el tipo del id.

Generación de Código IntermedioRecupera tipo y dirección del id.

Generación de CódigoInserta y recupera información sobre la memoria asignada.

Estructuras usadas para implementar Estructuras usadas para implementar una tabla de suna tabla de síímbolosmbolos

ListaSimple de implementar.Lenta cuando se trabaja con muchos identificadores.

ÁrbolRápida.Consume más memoria.Es útil cuando hay muchas declaraciones.

Tabla de HashingRápida.Difícil de implementar.Se debe definir una función de hashingapropiada para evitar colisiones.

Operaciones sobre TSOperaciones sobre TS

Búsqueda(lexema): entero;

Inserción(lexema,descriptor): boolean;

Obt_atributo(lexema,atributo): valor;

Eliminación (lexema): entero.

Contenido de la TSContenido de la TS

¿Qué debe insertarse en TS?

Tipos de datosNombre de VariablesConstantes definidasNombres de procedimientos FuncionesRótulos

¿Qué info puede necesitar el compilador?

Tipo de las VariablesDimensiones de tipos estructuradosNivel lexicográfico de una declaración.Dirección base y desplazamientoRegistro: sus camposParámetro: tipo de pasaje y tipo de datoNúmero y tipo de argumentos de una función

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.Si el scanner no las diferencia de los identificadores:

Pueden almacenarse en una tabla separada.Estar inicializadas al principio de la TS.Una entrada, en TS para una palabra reservada.

while código-while

Entradas en la TSEntradas en la TS

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

No todos los atributos se introducen a la vez, estos se completan conforme avanzan las etapas de compilación.

parte fija parte variante

Entrada en TSEntrada en TS

Nombre Clase Tipo Dirección Almac.

Variable Simple / Estructurada.Función.Procedimiento.Tipo.

Básico.Predefinido.Definido por el usuario.

Dirección de Memoria (nivel y desplaz).

Cantidad requerido.

Parte Fija

Entrada en TSEntrada en TSParte Variante

Depende del objeto computacional asociado con el identificador.Variable Simple: la parte variante es vacía excepto cuando se admitan valores de inicialización.Variable Estructurada (Arreglo)

Tipo Base Límite Inferior Límite Superior

Entrada en TSEntrada en TS

Procedimiento o Función

Cant. de Par. Tipo1 Pas. Ptro. … Tipon Pas. Ptro.

Operaciones sobre TS: Lenguajes Operaciones sobre TS: Lenguajes Estructurados a BloquesEstructurados a Bloques

Crean un ámbito, una visibilidad y un tiempo de vida para los identificadores.Tareas que se deben realizar cuando se ingresa a un nuevo bloque:

Dar de alta un nuevo bloque.Insertar cada identificador encontrado en dicho bloque.

Tareas realizadas cuando se finaliza el análisis de un bloque:

Eliminar cada identificador en el bloque.Eliminar el bloque.

Operaciones sobre TS: Lenguajes Operaciones sobre TS: Lenguajes Estructurados a BloquesEstructurados 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

Lectura obligatoria

Capítulo 8 de “The Theory and Practiceof Compiler Writing”, Tremblay & Sorenson. Mc Graw Hill. 1985.