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).
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 para encontrar 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 = (S Li)/N
Si la frecuencia de todas las claves no es la misma:
Lm = S pi.Li
Grado de ocupación:
s = 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.
No hay comentarios:
Publicar un comentario