La tabla de símbolos es una estructura de datos importante creada y mantenida por los compiladores para rastrear información sobre las ocurrencias de varias entidades, como nombres de variables, objetos, nombres de funciones, interfaces, etc. La información recopilada por el compilador dentro del La tabla de símbolos en la fase de análisis es utilizada por la fase de síntesis para generar el código de destino.
Comparación entre diferentes implementaciones de la tabla de símbolos:
1. Array (ordenada):
- Tiempo de inserción:
al insertar un elemento, se debe realizar un desplazamiento para cambiar los elementos a la derecha. Por lo tanto, toma O(n) tiempo. - Tiempo de búsqueda:
mientras se busca, se puede usar una búsqueda binaria para encontrar un elemento. Por lo tanto, toma un tiempo O (log n).
2. Lista vinculada:
- Tiempo de inserción:
similar a las arrays aquí para buscar la posición para insertar el elemento, se requiere atravesar. Por lo tanto, toma O(n) tiempo. - Tiempo de búsqueda: al
obtener un elemento de datos, la lista vinculada debe recorrerse por completo (búsqueda lineal). Por lo tanto, esta operación requiere un tiempo O(n).
3. Lista desordenada:
- Tiempo de inserción:
en una array desordenada, la inserción se puede realizar al principio, mientras que en una lista enlazada desordenada, la inserción se puede realizar al final. Por lo tanto, requiere tiempo O(n). - Tiempo de búsqueda:
como se trata de una lista desordenada, se debe buscar una lista completa para encontrar un elemento. Por lo tanto, toma O(n) tiempo.
Desventajas de usar Array, Linked Lists o Unsorted Lists para implementaciones de tablas de símbolos:
- El tiempo de búsqueda es directamente proporcional al tamaño de la tabla.
- Cada operación de inserción va precedida de una operación de búsqueda.
4. Lista autoorganizada:
- Tiempo de inserción:
generalmente es una lista desordenada, por lo tanto, el tiempo necesario para insertar un elemento es O (1). - Tiempo de búsqueda: la
búsqueda de un elemento aquí requiere buscar un elemento y luego cambiarlo al principio de la lista para que los elementos más utilizados estén al principio de la lista. Tal como es, en general, una búsqueda en una lista no ordenada requiere tiempo O(n).
Desventajas de usar listas autoorganizadas para implementaciones de tablas de símbolos:
La desventaja de esta implementación es que cada vez que se buscan elementos menos frecuentes, el rendimiento se vuelve pobre.
5. Árboles de búsqueda (equilibrados):
- Tiempo de inserción:
si hay n elementos en el árbol y el orden del árbol es k, entonces se registrará la altura del árbol. Ahora, en el peor de los casos, la inserción ocurriría a la altura del árbol. Por lo tanto, el tiempo requerido es O(logkn). - Tiempo de búsqueda:
en un árbol de búsqueda equilibrado, el tiempo requerido para buscar es O (logkn).
Desventajas de usar árboles de búsqueda para implementaciones de tablas de símbolos:
La desventaja de esta implementación es que el árbol siempre debe mantenerse equilibrado.
6. Hashing:
- Tiempo de inserción:
como en una tabla hash, la inserción toma un tiempo constante, por lo que el tiempo requerido para la inserción es O (1). - Tiempo de búsqueda: la
búsqueda en una tabla hash requiere un tiempo constante, por lo que el tiempo requerido es O (1).
Desventajas de usar Hashing para implementaciones de tablas de símbolos:
La desventaja de esta implementación es que cuando hay demasiadas colisiones, la complejidad del tiempo aumenta a O(n).
Por lo tanto, podemos ver que cada implementación de la tabla de símbolos es única y tiene sus propias desventajas. El implementador de acuerdo con sus requisitos puede elegir cualquiera de las implementaciones anteriores de tablas de símbolos.