4.3 La Tabla de Símbolos

Un compilador utiliza una tabla de símbolos para llevar un registro de la información sobre el ámbito y el enlace de los nombres. Se examina la tabla de símbolos cada vez que se encuentra un nombre en el texto fuente. Si se descubre un nombre nuevo o nueva información sobre un nombre ya existente, se producen cambios en la tabla.

Un mecanismo de tabla de símbolos debe permitir añadir entradas nuevas y encontrar las entradas existentes eficientemente. Los dos mecanismos para tablas de símbolos presentadas en esta sección son listas lioeal.es y tablas de dispersión. Cada esquema se evalúa basándose en el tiempo necesario para añadir n entradas y realizar e consultas. Una lista lineal es lo más fácil de implantar, pero su rendimiento es pobre cuando e y n sé vuelven más grandes. Los esquemas de dispersión proporcionan un mayor rendimiento con un esfuerzo algo mayor de programación y gasto de espacio. Ambos mecanismos pueden adaptarse rápidamente para funcionar con la regla del anidamiento más cercano.

Es útil que un compilador pueda aumentar dinámicamente, la tabla de símbolos durante la compilación. Si la tabla de símbolos tiene tamaño fijo al escribir el compilador,  entonces el tamaño debe ser lo suficientemente grande como para albergar cualquier programa fuente. Es muy probable que dicho tamaño sea demasiado  grande para la mayoría de los programas e inadecuado para algunos.

Entradas de la tabla de símbolos

Cada entrada de la tabla de símbolos corresponde a la declaración de un nombre. El formato de las entradas no tiene que ser uniforme porque la información de un nombre  depende del uso de dicho nombre. Cada entrada se puede implantar como un registro que conste de una secuencia de palabras consecutivas de memoria. Para mantener uniformes los registros de la tabla de símbolos, es conveniente guardar una parte de la información de un nombre fuera de la entrada de la tabla, almacenando en el registro sólo un apuntador a esta información.

No toda la información se introduce en la tabla de símbolos a la vez. Las palabras clave se introducen, si acaso, al inicio.

El analizador léxico  busca secuencias de letras y dígitos en la tabla de símbolos para determinar si se ha encontrado una palabra clave reservada o un nombre. Con  este enfoque, las palabras clave deben estar en la tabla de símbolos antes de que comience el análisis léxico. En ocasiones, si el analizador léxico reconoce las palabras clave reservadas, entonces no necesitan aparecer en la tabla de símbolos. Si el lenguaje no convierte en reservadas las palabras clave, entonces es indispensable que las palabras clave se introduzcan en la tabla de símbolos advirtiendo su posible uso como palabras clave.

La entrada misma de la tabla de símbolos puede establecerse cuando se aclara el papel de un nombre y se llenan los  valores de los atributos cuando se dispone de la información. En algunos casos, el analizador léxico puede iniciar la entrada en cuanto aparezca un nombre en los datos de entrada. A menudo, un nombre puede indicar varios objetos distintos, quizás incluso en el mismo bloque o procedimiento. Por ejemplo, las declaraciones en C.

                                         Int      x;                                           (1)

struct x { float y, z; };

utilizan x como entero y como etiqueta de una estructura con dos campos. En dichos casos, el analizador léxico sólo puede devolver al analizador sintáctico el nombre solo (o un apuntador al lexema que forma dicho nombre), en lugar de un apuntador a la entrada en la tabla de símbolos. Se crea el registro en la tabla de símbolos cuando se descubre el papel sintáctico que desempeña este nombre. Para las declaraciones de (1), se crearían dos entradas en la tabla de símbolos para x; una con x como entero y otra como estructura.

Los atributos de un nombre se introducen en respuesta a las declaraciones, que pueden ser implícitas. Las etiquetas son a menudo identificadores seguidos de dos puntos, así que una acción asociada con el reconocimiento de dicho identificador puede ser introducir este hecho en la tabla de símbolos. Asimismo, la sintaxis de las declaraciones de procedimientos especifica que algunos identificadores son parámetros formales.

Caracteres dentro de un nombre

Existe una distinción entre el componente léxico id para un identificador o nombre, el lexema formado por la cadena de caracteres que componen el nombre, y los atributos del nombre. Las cadenas de caracteres pueden ser difíciles de manejar, así que los compiladores utilizan a menudo alguna representación de longitud fija del nombre en lugar del lexema. El lexema es necesario cuando se establece por primera vez una entrada a la tabla de símbolos y cuando se busca un lexema encontrado en los datos de entrada para determinar si es un nombre que ya ha aparecido. Una representación habitual de un nombre es un apuntador a una entrada en la tabla de símbolos para él.

Si hay un límite superior pequeño para la longitud de un nombre, entonces los caracteres del nombre pueden almacenarse en la entrada de la tabla de símbolos, como se muestra en la figura 2(a). Si no hay límite para la longitud de un nombre, o si rara vez se alcanza el límite, se puede utilizar el esquema indirecto de la figura 2(b). En lugar de asignar la cantidad máxima de espacio para guardar un lexema en cada entrada de la tabla, se puede utilizar el espacio más eficientemente si sólo hay espacio para un apuntador en cada entrada de la tabla. 

En el registro para un nombre, se coloca un apuntador a una matriz independiente de caracteres (la tabla de cadenas) que da la posición del primer carácter del lexema. El esquema indirecto de la figura (b) permite que el tamaño del campo del nombre de la entrada misma de la tabla de símbolos permanezca constante. El lexema completo que constituye un nombre debe almacenarse para garantizar que todos los usos del mismo nombre se puedan asociar con el mismo registro en la tabla de símbolos. Sin embargo, se debe distinguir entre casos.