| INSTITUTO POLITÉCNICO NACIONAL ESCUELA SUPERIOR DE CÓMPUTO |

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II Introducción 2.1 Estructura de un Compilador 2.1.1 Función del analizador léxico 2.1.2 Función del analizador sintáctico

2.1.3 Tabla de Símbolos

2.1.4 Función del analizador Semántico

2.1.5 Etapa de análisis

2.1.6 Etapa de Síntesis

UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII
UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

2.1.3 Tabla de Símbolos

> Una tabla de símbolos es una estructura de información para manejar los nombres de Identificadores y palabras reservadas del código fuente, se usa durante la comprobación semántica o dependiente del contexto además del proceso de generación de código. La información almacenada en la tabla será completada durante las fases de análisis y luego se empleará en la generación de código. En general, una tabla de símbolos consta de nombres y atributos, como se muestra en la siguiente figura.

> La información almacenada en una tabla de símbolos varía de un compilador a otro y de un lenguaje a otro; es decir, la información que se incluirá en una tabla de símbolos depende del lenguaje y del diseñador del compilador. Por ello, en esta sección destacaremos la organización y las estructuras de datos de la tabla de símbolos, más que su contenido. De todos modos, se pueden hacer unos cuantos comentarios generales sobre el contenido de una tabla de símbolos. En dicha tabla, el campo Nombres contiene los nombres (identificadores), mientras que los atributos pueden ser, entre otros:

> - Tipo o valor de un nombre, o ambos;

> - la dimensión o el número de parámetros de un procedimiento;

> - un apuntador al lugar donde se declara y referencia un nombre;

> - algún tipo de dirección, por lo regular un desplazamiento;

> - información del alcance en el caso de un lenguaje orientado a bloques.

> Si un nombre en una tabla de símbolos se refiere a una constante, es necesario almacenar el tipo y el valor de la constante. Los apuntadores al lugar donde se declara y referencia un nombre pueden apoyar la generación de listados de errores, mientras que la información del alcance sólo será necesaria en lenguajes orientados a bloques que permiten la declaración del mismo nombre en distintos bloques.

> Hay muchas formas de manejar nombres de longitud variable. Si el lenguaje de programación que se considera sólo permite nombres con un número máximo de caracteres (digamos seis), es fácil el manejo de los nombres: pueden almacenarse en un campo de nombre con longitud máxima de tamaño fijo. Sin embargo, si los nombres pueden ser de longitud arbitraria o si la longitud máxima es relativamente grande (digamos 32 caracteres), este método de almacenamiento directo no es aplicable o puede ser muy ineficiente, lo cual se visualiza en la siguiente figura.

> Una estrategia popular para manejar tales nombres en una tabla de símbolos consiste en dividir el campo de nombre de la tabla en dos subcampos, uno que contiene un apuntador a una tabla aparte de cadenas y otro que contiene la longitud del nombre. El apuntador especifica la posición del primer carácter del nombre en la tabla de cadenas.

> Al considerar la funcionalidad antes mencionada de la tabla de símbolos (o sea, el almacenamiento de nombres y la información apropiada), vemos que sólo se requieren dos operaciones relacionadas con la tabla: inserción y búsqueda.

> Podemos buscar un identificador (o un nombre en general) usando la función de búsqueda. Si la búsqueda no tiene éxito, puede insertarse un identificador nuevo mediante la función de inserción. Obviamente, es posible distinguir entre identificadores y palabras reservadas si se inicia la tabla con las palabras reservadas.

> La operación de búsqueda debe implantarse con una estructura de datos o un algoritmo muy elaborado (o ambas cosas), porque los programas con miles de líneas de código fuente pueden contener cientos de identificadores diferentes. Algunas investigaciones (no necesariamente representativas) sobre distintos proyectos de software con unas 5000 a 10 000 líneas de código fuente en Modula-l han mostrado que los programadores usan de 500 a 1500 nombres diferentes. Como estos nombres no aparecen una, sino muchas veces, la búsqueda de un nombre puede ser un proceso que consume mucho tiempo si se efectúa de manera incorrecta.

> El método de búsqueda más ineficiente es la búsqueda lineal, que usa una lista lineal como estructura de datos de la tabla de símbolos; en otras palabras, la tabla se organiza como una lista enlazada de registros que contienen los campos de nombre y de atributos.

> Una lista enlazada es la forma más sencilla de organizar una tabla de símbolos, pero las búsquedas en la lista son puramente secuenciales, si la lista no está ordenada, podría necesitarse hacer una revisión de toda la tabla antes de saber si está incluida o no en ella un nombre. En promedio, se localizará un nombre después de n/l búsquedas, donde n es el número total de nombres en la tabla, por consiguiente, el costo de la búsqueda es proporcional a n.

> Podemos mejorar la búsqueda lineal por medio de la indización unidimensional o incluso la indización bidimensional, en lugar de una lista enlazada individual, tenemos una matriz de registros enlazados. En la indización unidimensional se emplea una matriz unidimensional [A..Z] de listas enlazadas, suponiendo que los nombres sólo pueden comenzar con letras mayúsculas (para simplificar las cosas). Los elementos al, a2, b1, etc., representan el primero, segundo, etc., nombres, comenzando con A, B, ..., Z.

> Para la indización bidimensional se requiere una matriz bidimensional [A..Z, A..Z, O..9ℓ] de registros (representa un espacio en blanco). En ella, se usan el primero y el segundo caracteres de un nombre para seleccionar la lista donde se hará la búsqueda lineal (una vez más, za1, za2,… representan el primero, segundo, ... nombres que comienzan con ZA). En el caso de nombres de un sólo carácter, se supone que el segundo carácter es ℓ.

> Cuando analicemos el texto de un programa, es probable que encontremos que muchos índices de la matriz tengan una referencia al apuntador nulo, ya que no hay ningún identificador que comience con determinados caracteres. Por tanto, el costo de la búsqueda es menor que n/2 con la indización unidimensional, pero sólo en aquellos casos en que los primeros caracteres de los nombres se distribuyan uniformemente. En la indización bidimensional es aplicable un razonamiento similar. Sin embargo, con base en las investigaciones estadísticas de los lenguajes naturales, se sabe que las letras (en especial las primeras de las palabras) no se distribuyen de manera uniforme.

> Podemos suponer lo mismo para los nombres de los programas, incluso para aquellos que parecen ser un poco artificiales. Así mismo, los programadores comúnmente tienden a estructurar o agrupar los nombres de variables, por ejemplo, banco, bancointrl, bancointr2, etc., lo cual significa que al usar la indización unidimensional o bidimensional, unos nombres se localizarán muy pronto y otros no.

> La desventaja más importante en este caso es que los tiempos de acceso varían mucho, lo que se necesita son algoritmos que efectúen una distribución más uniforme de estos tiempos de acceso. Una primera mejora para la indización bidimensional podría ser utilizar el primero y el último carácter (en vez del primero y el segundo) para determinar la entrada de la tabla. Éste es un método muy simple que, además, permite calcular fácilmente la dirección del índice del nombre. La indización bidimensional con el primero y los últimos caracteres de un nombre produce resultados bastante adecuados para el caso de nombres agrupados.

> Otra alternativa común a los métodos anteriores es la dispersión (hashing), la cual es una tabla de símbolos por dispersión, el costo de la búsqueda es esencialmente independiente de n, el número de nombres en la tabla; es decir, el tiempo de búsqueda es constante para cualquier n. La dispersión o codificación por dispersión significa que la dirección donde se almacenará un nombre es una función del propio nombre y se determina por medio de un algoritmo de correspondencia aplicado al nombre, para procesos de búsqueda se aplica el mismo algoritmo a la clave de búsqueda.

> De esta manera, la dispersión implica que los nombres no se almacenan en algún orden (alfabético), de otra forma el orden parece caótico (como lo indica el término dispersión), aunque el caos está bien definido.

> Hay que observar lo siguiente:

> Hay que determinar el tamaño N del espacio de direcciones, o sea, hay que decidir cuántos nombres se esperan. Sea H (v) la dirección de un nombre v.

> Entonces,

> H (v) E [1, N]

> Hay que encontrar una función f (v) para transformar los nombres alfanuméricos v en un entero. Por ejemplo, sea v = C1 C2 ...Ck un nombre de longitud k. Entonces, f (v) puede definirse como:

> f (v) = ord(c1) + ord(ck) + 16 * k,

> Donde ord es la función de posición original, éste es sólo un ejemplo de una larga lista de funciones de transformación que se han publicado.

> Debe hallarse una correspondencia entre la representación entera de un nombre v y el espacio de direcciones [1, N]. La correspondencia más común está dada por:

> H (v) = f (v) MOD N + 1 H (v) E [1, N]

> El tamaño del espacio de direcciones N debe ser un número primo para garantizar una distribución uniforme de las direcciones calculadas.

> - La función de transformación introducida f (v) se parece al método de indización unidimensional mejorado, ya que en ambos casos participan el primero y el último caracteres del nombre v. Con base en estas funciones, el conjunto de caracteres ASCII y un espacio de direcciones N = 13, podemos considerarlos siguientes ejemplos:

> H (ALPHA1) = f (ALPHA1) MOD 13 + 1
> = (ord (A) + ord (1) + 16 * 6) MOD 13 + 1
> = (65 + 49 + 96) MOD 13 + 1
> = l10 MOD 13 + 1
> = 3

> H (a) = f (a) MOD 13 + 1
> = (ord (a) + ord (a) + 16 * 1) MOD 13+ 1
> = (97 + 97 + 16) MOD 13 + 1
> = 210 MOD 13 + 1
> = 3

> Estos ejemplos nos muestran los problemas que pueden surgir con la codificación por dispersión: dos nombres se codifican al mismo índice (dirección). Comprendemos ahora por qué es importante que la función de dispersión distribuya los nombres (es decir, sus direcciones) de manera uniforme por el espacio de direcciones. Pero incluso las “mejores" funciones de dispersión no garantizan que todas las direcciones calculadas sean distintivas. Por consiguiente, se requieren algunas estrategias para manejar tales colisiones.

> Las estrategias más populares para generar índices secundarios son:

> Encadenamiento directo: Todos los nombres v con el mismo índice primario H (v) se enlazan para formar una lista enlazada ordinaria. Esta solución es muy similar a la indización unidimensional o bidimensional.

> Direccionamiento abierto: Cuando ocurre una colisión, el nombre se inserta en el siguiente espacio disponible de la tabla. Para recuperar información de la tabla de dispersión se lleva a cabo una búsqueda lineal tras no haber hallado el hombre en la posición de dispersión H(v), comenzando en la posición de dispersión H(v), hasta hallar la cadena.

> Atrás Siguiente

##### Introducción / Contenido / Unidad I / Unidad II / Unidad III / Unidad IV / Unidad V / Unidad VI / Unidad VII / Unidad VIII / Unidad IX / Problemario / Bibliografía

##### Inicio

##### Créditos

José Sánchez Juárez, Andrés Ortigoza Campos, Fabiola Ocampo Botello