Clase4

Clase 4:

Tablas de símbolos

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

Almacena información sobre:

*Los identificadores.

*Las palabras reservadas.

*Las constantes.

TABLA DE SÍMBOLOS

*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.

CONTENIDO

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 lo encuentra crea una nueva entrada.

¿UTILIDAD DE LA TABLA DE SÍMBOLOS?

Esquema general

DATOS QUE SE ALMACENAN:

Para un array:

•   Tipo de los elementos.

•   Número de elementos.

•   Límites inferior y superior.

Para una función:

•   Número de parámetros.

•   Tipo de los parámetros.

•   Forma de paso de parámetros.

•   Tipo de retorno

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 de un símbolo cuando ya no se utiliza

EJEMPLOS 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 :

TABLA DE SÍMBOLOS

Ejemplo:

Estructuras usadas para implementar una tabla de símbolos

 - Lista

*  Simple de implementar.

*  Lenta cuando se trabaja con muchos identificadores.

- Árbol

*Rápida. z Consume más memoria.

*Es útil cuando hay muchas declaraciones.

- Tabla de Hashing z Rápida.

*Difícil de implementar.

*Se debe definir una función de hashing apropiada para evitar colisiones.

- Operaciones sobre TS

*Búsqueda(lexema): entero;

*Inserción(lexema,descriptor): boolean;

*Obt_atributo(lexema,atributo): valor;

*Eliminación (lexema): entero.

- Contenido de la TS

* ¿Qué debe insertarse en TS?

          *Tipos de datos z Nombre de Variables z Constantes definidas z Nombres de      procedimientos

          *Funciones z Rótulos

- ¿Qué info puede necesitar el compilador? z Tipo de las Variables z Dimensiones de tipos estructurados

   *Nivel lexicográfico de una declaración.

*Dirección base y desplazamiento

*Registro: sus campos z Parámetro: tipo de pasaje y tipo de dato

*Nú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. z Estar inicializadas al                                principio de la TS. z Una entrada, en TS para una palabra reservada.

while

código-while

Entradas en la TS

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

parte fija

parte variante

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

  *Entrada en TS

  *Parte Fija

Entrada en TS

{  Parte Variante z Depende         del      objeto            computacional asociado con el identificador.

y Variable Simple: la parte variante es vacía excepto cuando se admitan valores de inicialización.

y Variable Estructurada (Arreglo)

Tipo Base

Límite Inferior

Límite Superior

Entrada en TS { Procedimiento o Función

Cant. de Par.

Tipo1

Pas.

Ptro.

…

Tipon

Pas.

Ptro.

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

z  Dar de alta un nuevo bloque.

z  Insertar cada identificador encontrado en dicho bloque.

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

z  Eliminar cada identificador en el bloque. z Eliminar el bloque.

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.

Tabla de símbolos

DEFINICIÓN DE TABLA DE SÍMBOLOS

Una tabla de símbolos es una estructura de datos usada en el proceso de traducción de un lenguaje de programación (por un compilador o un intérprete), dónde cada símbolo en el código fuente de un programa está asociado con información tal como la ubicación, el tipo de datos y el ámbito de cada variable, constante o procedimiento. Esta estructura de datos contiene una entrada o registro para cada identificador. Cada registro incluye los campos para los atributos del identificador.

El administrador de la tabla de símbolos se encarga de manejar los accesos a la tabla de símbolos, en cada una de las etapas de compilación de un programa.

Se examina la tabla de símbolos cada vez que se encuentra un nombre en el texto fuente. Si Dicho nombre ya existiese, se realizan cambios sobre la tabla existente.

Un mecanismo de tabla de símbolos debe permitir añadir entradas nuevas y encontrar entradas existentes de manera eficaz.

La tabla de símbolos se construye durante el proceso de análisis. La información en la tabla de símbolos se utiliza tanto en el análisis (para especificar restricciones contextuales) como en la síntesis/traducción (para interpretar/traducir el significado de los tokens).

La información se reúne en las fases de análisis del compilador y la emplea la fase de síntesis para generar el código objeto. Por ejemplo, durante el análisis léxico, la cadena de caracteres, o lexema, que forma un identificador se guarda en una entrada de la tabla de símbolos. Las fases posteriores del compilador pueden añadir a esta entrada información, como el tipo del identificador, su uso (por ejemplo, procedimiento, variable o etiqueta) y su posición en la memoria. La fase de generación de código usaría después esta información para generar el código apropiado para almacenar y acceder a esta variable.

ESTRUCTURA

Cada entrada de la tabla de símbolos corresponde a al declaración de un nombre. El formato de las entradas no tiene que ser uniforme porque la información de un nombre depende del uso de dicho nombre. Cada entrada en principio puede considerarse: 

      ( Nombre,   descriptor )

      

 

      LEXEMA     ATRIBUTOS

•      LEXEMA: distintas políticas de almacenamiento.

•      ATRIBUTOS: cuanta información contiene dicho campo depende del objeto que denota el lexema.

La estructura inicial de la tabla de símbolos suele constar de dos partes:

PARTE FIJA

PARTE VARIABLE

•      PARTE FIJA: formada por las palabras clave del lenguaje (suelen ser de uso reservado y del orden de unas decenas de palabras en un lenguaje programación típico)

•      PARTE VARIABLE: definida por el programador: con el significado de los identificadores utilizados en cada frase (programa).

La información se introduce en la tabla de símbolos a la vez. Las palabras claves se introducen al inicio, o bien también podrían iniciarse en una tabla separada. El analizador léxico busca secuencia de letras y dígitos en la tabla de símbolos para determinar si se ha encontrado una palabra clave reservada o un nombre, este es el motivo por el que las palabras reservadas deben estar en la tabla de símbolos antes de que comience el análisis. Si se da el caso que el analizador léxico reconoce las palabras clave reservadas, entonces no necesitan aparecer en la tabla de símbolos

Puede tratarse como una estructura transitoria o volátil, que sea utilizada únicamente en el proceso de traducción de un lenguaje de programación, para luego ser descartada, o integrada en la salida del proceso de compilación para una explotación posterior, como puede ser por ejemplo, durante una sesión de depuración, o como recurso para obtener un informe de diagnóstico durante o después la ejecución de un programa.

La construcción de la tabla de símbolos debe seguirse de una correcta especificación de la misma. Como la definición de la parte dinámica de la tabla de símbolos está basada en las restricciones del lenguaje de programación, la especificación de la construcción de la tabla de símbolos está dirigida por la sintaxis de este sub-lenguaje de declaración y utiliza las mismas técnicas utilizadas para especificar y construir otros elementos del procesador de lenguaje (La construcción de la tabla de símbolos es una tarea del módulo de análisis sintáctico en la que coopera inicialmente el módulo de análisis léxico).

FUNCIONAMIENTO

Conforme van apareciendo nuevas declaraciones de identificadores, el analizador léxico, o el analizador sintáctico según la estrategia que sigamos, insertará nuevas entradas en la tabla de símbolos, evitando siempre la existencia de entradas repetidas. El analizador semántico efectúa las comprobaciones sensibles al contexto gracias a la tabla de símbolos, y el generador de código intermedio usa las direcciones de memoria asociadas a cada identificador en la tabla de símbolos, al igual que el generador de código.

La tabla de símbolos contiene información útil para poder compilar, por tanto existe en tiempo de compilación, y no de ejecución. Sin embargo, en un intérprete, dado que la compilación y ejecución se producen a la vez, la tabla de símbolos permanece todo el tiempo.

IMPLEMENTACIÓN

Una implementación común de una tabla de símbolos puede ser una tabla hash, la cual será mantenida a lo largo de todas las fases del proceso de compilación.

La estructura más sencilla y fácil de implementar una tabla de símbolos es mediante una lista lineal de registros. Se utiliza una sola matriz, o varias, para almacenar los nombres y su información asociada. Los nombres nuevos se añaden a la lista en el orden en el que aparecen. La posición final de la matriz se marca con el apuntador disponible, que apunta hacia donde irá la siguiente entrada en la tabla de símbolos. La búsqueda un nombre se realiza hacia atrás desde el final de la matriz. En cuanto al coste, si la tabla de símbolos contiene n nombres, el trabajo necesario para insertar un nombre nuevo es constante si se realiza la inserción sin comprobar si el nombre ya se encuentra en la tabla. Si no se permiten entradas múltiples para los nombres, entonces es necesario recorrer toda la tabla para descubrir que un nombre no está en la tabla, realizando un trabajo proporcional a n en la búsqueda.

La tabla de símbolos puede construirse de manera muy sencilla, utilizando las siguientes funciones (funciones básicas utilizadas en la definición dirigida por sintaxis):

•      creaTS: crea una nueva TS que incluye las palabras reservadas del lenguaje (en los lenguajes organizados en bloques incluiría una referencia al contexto)

•      añadeID: El resultado es la nueva TS que resulta de añadir a la anterior el identificador id y sus atributos. Para obtener los atributos de id puede ser necesario procesar varias estructuras sintácticas

•      obtenerID: El resultado es una entrada a la TS donde está toda la información sobre id (null si id no está en la TS).

Se mantiene en la tabla de símbolos la información acerca de las posiciones de memoria que se ligarán a nombres durante la ejecución. Considérese primero los nombres con posiciones de memoria estática. Si el código objeto es lenguaje ensamblador, el ensamblador puede encargarse de las posiciones de memoria para los distintos nombres. Basta con examinar la tabla de símbolos, después de generar código ensamblador para el programa, y generar definiciones de datos en lenguaje ensamblador para añadirlos al programa en lenguaje ensamblador para cada nombre.

Sin embargo, si el compilador genera código máquina, entonces se debe indagar la posición de cada objeto de datos relativa a un origen fijo, como el principio de un registro de activación. La misma observación sirve para un bloque de datos cargado como un módulo independiente del programa.

Cuando el lenguaje permite al programador para definir nuevos símbolos cuyo significado se obtiene componiendo otros símbolos previamente definidos, la estructura de la tabla de símbolos (que en principio tenia una estructura sencilla) se convierte en más compleja. La complejidad se puede aumentar cuando se puede organizar los programas en módulos o bloques, anidados o no, y cada uno con un vocabulario específico del módulo y otro global compartido con todos, o con algunos, módulos del programa. En este caso lo normal es no tener una tabla de símbolos, si no un conjunto de tablas relacionadas de la misma forma que los módulos. 

Ejemplo