Tabla de simbolos

Capítulo 2. Tablas de símbolos
Tabla: conjunto de pares clave-valor, llamados elementos de la tabla.
La tabla de símbolos es una componente necesaria de un compilador. Al declarar un identificador (normalmente una sola vez), éste es insertado en la tabla. Cada vez que se utilice el identificador se realizará una búsqueda en la tabla para obtener la información asociada (el valor).
Problemasasociados:
* Búsqueda: dada la clave de un elemento, encontrar su valor.
* Inserción: Dado un par clave-valor, añadir un elemento nuevo a la tabla.
* Cambio de valor: Buscar el elemento y cambiar su valor.
* Borrado: Eliminar un elemento de la tabla.
Longitud de búsqueda (o tiempo de acceso):
* De una clave: Li = número de comparaciones con elementos de la tabla paraencontrar esa clave.
* Máxima: LM = número máximo de comparaciones para encontrar cualquier clave.
* Media (esperada): Lm = número medio de comparaciones para encontrar un valor.
* Si la frecuencia de todas las claves es la misma:
* Lm = ( Li)/N
* Si la frecuencia de todas las claves no es la misma:
* Lm =  pi.LiGrado de ocupación:
 = n/N
donde n=número de elementos en la tabla y N=capacidad máxima de la tabla.
Función de búsqueda: B : K->E asocia a cada clave k un elemento B(k).
Valor asociado a una clave k: v(B(k)). Puede ser múltiple, en cuyo caso normalmente se convierte en un puntero. Si está en la tabla puede almacenarse consecutivamente o en subtablas paralelas.Tablas de símbolos (identificadores)
La clave es el identificador. El valor está formado por:
* Atributos del identificador.
* Puntero a la posición de memoria asignada.
La clave puede sustituirse por un puntero.
Los identificadores pueden estar empaquetados.
La longitud del identificador puede especificarse en la tabla o delante del nombre, o ser implícita.
* Tablas consecutivas:Todos los elementos ocupan posiciones de memoria adyacentes.
* Tablas ligadas: cada elemento apunta al siguiente.
* Tablas doblemente ligadas: cada elemento apunta al siguiente y al anterior.
Tablas no ordenadas
Inserción: en el primer lugar vacío.
Búsqueda: secuencial, elemento a elemento.
Lm = (n+1)/2
LM = N
La búsqueda es muy lentacuando el número de elementos es mayor que 20.
Tablas ordenadas
Los elementos se ordenan con algún criterio (p.e. alfabéticamente).
Búsqueda binaria o logarítmica.
Algoritmo de búsqueda en el bloque (1,n):
* Se mira el elemento (n+1)/2.
* Si es ese, encontrado.
* Si es menor, se busca en el bloque (1,(n-1)/2).
* Si es mayor, se busca en el bloque ((n+3)/2,n).
Longitudde búsqueda:
Lm = 1+log2 (n)
mucho mejor que en tablas no ordenadas.
Inserción:
* Se usa la búsqueda binaria para encontrar el elemento j tal que K(E(j)) Lm = 1 + (N-1)/(2N) < 1.5
Supresión de entradas: o bien se pone marca de entrada suprimida o un doble encadenamiento. En el primer caso, la inserción no se hace en la primera posición vacía, sino en la primeraposición suprimida por la que se pasó, quitándole la marca.
Encadenamiento con "overflow"
Es igual, sólo que el vector Hash se amplía para incluir también (k,v) y se incorpora a la tabla. Se reduce ligeramente el tiempo de búsqueda.
Función Hash
1. Suma/O exclusivo de las letras del identificador, formando una palabra (un byte) W.
2. Se reduce W a un índice para el vector Hash.
1.Si la tabla tiene N = 2*p entradas, se cogen los p bits medios de WxW.
2. O se usa una función lógica (ej. O exclusivo) con partes de W.
3. O se descompone W en secciones de p bits, se suman y nos quedamos con los p bits de la derecha.
4. O se usa el resto de W/N.
En PL/I IBM se usa esta versión con 211 elementos en el vector Hash.
5. O se toman los p últimos...