Ensayos

UNIVERSIDAD NACIONAL DE TRUJILLO
FACULTAD DE INGENIERÍA

CURSO :
AUTÓMATAS
TEMA :
TABLA DE SÍMBOLOS
CICLO :
V
PROFESOR :
RICARDO MENDOZA
INTEGRANTES :
* GADEA AVILA JEAN
* HUAMAN LA TORRE NATALY
* LEON MOSTACERO WUICLET
* LOPEZ MINCHOLA JHON
* RODRIGUEZ SHAPIAMA JOSÉ LUIS

TRUJILLO – PERÚ
2011

TABLA 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

Posee información sobre los identificadores definidos por el usuario, ya sean constantes, variables o tipos. Dado que puede contener información de diversa índole, debe hacerse deforma que no sea uniforme. Hace funciones de diccionario de datos y su estructura puede ser una tabla hash, un árbol binario de búsqueda, etc.

Esquema definitivo de un traductor:

Esta tabla debida a su complejidad es tratada como un objeto:

1. CARACTERÍSTICAS:
* Almacena todos los nombres declarados en el programa y sus atributos (tipo, valor, dirección, parámetros, etc.)
*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.
* Se usa en las distintas fases del compilador para:
* Recuperar los atributos de un nombre.
* Verificar que todos losidentificadores son declarados antes de utilizarlos (cuando el lenguaje así lo requiere).
* Detectar múltiples definiciones de un identificador en un mismo alcance (cuando el lenguaje así lo requiere).
* Permitir la declaración de un mismo nombre con alcances diferentes (cuando el lenguaje así lo requiere).

2. FORMA DE ALMACENAMIENTO
3.1. Tablas Hash o de entrada calculada
Es el métodomás usado. Se trata de trasformar la clave en un índice de entrada aplicándole una función Hash, I(k), que puede no ser biyectiva.
Es equivalente a una tabla de acceso directo mientras no aparezcan dos claves tales que I(k1) = I(k2): colisión.
Hay dos métodos principales para resolver la colisión.
3.2. Tablas Hash abiertas (con rehash)
Supongamos que los elementos de T son 0,1,...,N-1.Búsqueda de la clave k.
* Se calcula h = I(k).
* Se compara k con T(h). Si es igual, encontrado.
* Si hay colisión (k!=T(h)&&T(h)!=NULL) se compara k con T(mod(h+p1,N)).
* Si hay nueva colisión se compara k con T(mod(h+p2,N)).
* ...
* Si hay nueva colisión se compara k con T(mod(h+pi,N)).
* hasta que se encuentre la clave buscada, un lugar vacío o se vuelva aT(h). En el primer caso, se ha encontrado. En el segundo, no está en la tabla. En el tercero, tampoco está, y la tabla está llena para ese valor de la función Hash.
Este almacenamiento se llama espaciado, porque los elementos ocupados están esparcidos por la tabla.
Tipos de rehash: lineal, aleatorio, multiplicativo, cuadrático.
3. FUNCIÓN DE LA TABLA DE SÍMBOLOS DENTRO DE UN COMPILADOR.
Latabla almacena la información que en cada momento se necesita sobre las variables del programa, información tal como: nombre, tipo, dirección de localización, tamaño, etc. La gestión de la tabla de símbolos es muy importante, ya que consume gran parte del tiempo de compilación. De ahí que su eficiencia sea crítica. Aunque también sirve para guardar información referente a los tipos creados por...