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

Introducción | Contenido | Bibliografía

Introducción
Contenido
UNIDAD I
UNIDAD II
UNIDAD III
UNIDAD IV
UNIDAD V
UNIDAD VI
UNIDAD VII Introducción 7.1 Diseño, implementación y administración de la tabla de símbolos 7.2 Implantación de bloques y tipos de datos 7.3 Especificación de alcance de variables

7.4 Funciones y procedimientos

7.5 Registros de activación

7.6 Paso de parámetros

7.7 Llamada por valor

7.8 Llamada por referencia

UNIDAD VIII
UNIDAD IX
PROBLEMARIO
Bibliografía

7.1 Diseño, implementación y administración de la tabla de símbolos

> La tabla de símbolos o también llamada «tabla de nombres» o «tabla de identificadores», está compuesta de una estructura de datos de alto rendimiento que almacena toda la información necesaria sobre los identificadores del usuario.

> Esta tiene dos funciones principales:

> - Efectuar chequeos semánticos.

> - Generar código.

> Además, esta estructura permanece en la memoria sólo el tiempo de compilación, no de ejecución, excepto en aquellos casos en que se compila con opciones de depuración. Los intérpretes también suelen mantener la tabla de símbolos en memoria durante la ejecución, ya que ésta se produce simultáneamente con la traducción.

> La tabla de símbolos almacena la información que en cada momento se necesita sobre las variables del programa; información tal como: nombre, tipo, dirección de localización en memoria, tamaño, etc. Una adecuada y eficaz gestión de la tabla de símbolos es muy importante, ya que su manipulación consume gran parte del tiempo de compilación. De ahí que su eficiencia sea crítica.

> La tabla de símbolos también sirve para guardar información referente a los tipos de datos creados por el usuario, los tipos enumerados y, en general, cualquier identificador creado por el usuario. En estos casos, el desarrollador puede optar por mezclar las distintas clases de identificadores en una sola tabla, o bien disponer de varias tablas, donde cada una de ellas albergará una clase distinta de identificadores: tabla de variables, tabla de tipos de datos, tabla de funciones de usuario, etc.

> Información sobre los identificadores de usuario.

> La información que el desarrollador decida almacenar en esta tabla dependerá de las características concretas del traductor que esté desarrollando. Entre esta información puede incluirse:

> - Nombre del elemento. El nombre o identificador puede almacenarse limitando o no la longitud del mismo. Si se almacena con límite empleando un tamaño máximo fijo para cada nombre, se puede aumentar la velocidad de creación y manipulación, pero a costa de limitar la longitud de los nombres en unos casos y desperdiciar espacio en la mayoría. El método alternativo consiste en habilitar la memoria que necesitemos en cada caso para guardar el nombre. En C esto es fácil con el tipo char *; si hacemos el compilador en Modula-2, por ejemplo, habría que usar el tipo ADDRESS. En el caso de Java, esto no entraña dificultad alguna gracias al tipo String. Las búsquedas en la tabla de símbolos suelen hacerse por este nombre; por ello, y para agilizar al máximo esta operación, la tabla de símbolos suele ser una tabla de dispersión (hash) en la que las operaciones de búsqueda e inserción poseen un costo aproximadamente constante (O(1)).

> - Tipo del elemento. Cuando se almacenan variables, resulta fundamental conocer el tipo de datos a que pertenece cada una de ellas, tanto si es primitivo como si no, con objeto de poder controlar que el uso que se hace de tales variables es coherente con el tipo con que fueron declaradas.

> - Dirección de memoria en que se almacenará su valor en tiempo de ejecución. Esta dirección es necesaria, porque las instrucciones que referencian a una variable deben saber donde encontrar el valor de esa variable en tiempo de ejecución con objeto de poder generar código máquina, tanto si se trata de variables globales como de locales. En lenguajes que no permiten la recursión, las direcciones se van asignando secuencialmente a medida que se hacen las declaraciones. En lenguajes con estructuras de bloques, la dirección se da con respecto al comienzo del área de memoria asignada a ese bloque (función o procedimiento) en concreto.

> - Valor del elemento. Cuando se trabaja con intérpretes sencillos, y dado que en un intérprete se solapan los tiempos de compilación y ejecución, puede resultar más fácil gestionar las variables si almacenamos sus valores en la tabla de símbolos. En un compilador, no obstante, la tabla de símbolos no almacena nunca el valor.

> - Número de dimensiones. Si la variable a almacenar es un array, también pueden almacenarse sus dimensiones. Aunque esta información puede extraerse de la estructura de tipos, se puede indicar explícitamente para un control más eficiente.

> - Tipos de los parámetros formales. Si el identificador a almacenar pertenece a una función o procedimiento, es necesario almacenar los tipos de los parámetros formales para controlar que toda invocación a esta función sea hecha con parámetros reales coherentes. El tipo de retorno también se almacena como tipo del elemento.

> - Otra información. Con objeto de obtener resúmenes estadísticos e información varia, uede resultar interesante almacenar otros datos: números de línea en los que se ha sado un identificador, número de línea en que se declaró, tamaño del registro de activación, si es una variable global o local, en qué función fue declarada si es local, etc.

> Consideraciones sobre la tabla de símbolos

> La tabla de símbolos puede inicializarse con cierta información útil, que puede almacenarse en una única estructura o en varias:

> Constantes: PI, E, NUMERO_AVOGADRO, etc.
> Funciones de librería: EXP, LOG, SQRT, etc.

> Palabras reservadas. Algunos analizadores lexicográficos no reconocen directamente las palabras reservadas, sino que sólo reconocen identificadores de usuario. Una vez tomado uno de la entrada, lo buscan en la tabla de palabras reservadas por si coincide con alguna; si se encuentra, devuelven al analizador sintáctico el token asociado en la tabla; si no, lo devuelven como identificador de verdad. Esto facilita el trabajo al lexicográfico, es más, dado que esta tabla es invariable, puede almacenarse en una tabla de dispersión perfecta (aquélla en la que todas las búsquedas son exactamente de O(1)) constituyendo así una alternativa más eficiente a PCLex o JavaCC.

> En general, conforme avanza la etapa de análisis y van apareciendo nuevas declaraciones de identificadores, el analizador léxico o el analizador sintáctico según la estrategia que sigamos, insertará nuevas entradas en la tabla de símbolos, evitando siempre la existencia de entradas repetidas. El analizador semántico efectúa las comprobaciones sensibles al contexto gracias a la tabla de símbolos y, ya en la etapa de síntesis, el generador de código intermedio usa las direcciones de memoria asociadas a cada identificador para generar un programa equivalente al de entrada. Por regla general el optimizador de código no necesita hacer uso de ella, aunque nada impide que pueda accederla.

> Aunque la eficiencia en los accesos y manipulación de la tabla de símbolos son primordiales para hacer un buen compilador, suele ser conveniente realizar un desarrollo progresivo del mismo. Así, en las fases tempranas de la construcción del compilador, dada su complejidad es mejor incluir una tabla de símbolos lo más sencilla posible (por ejemplo, basada en una lista simplemente encadenada) para evitar errores que se difundan por el resto de fases del compilador. Una vez que las distintas fases funcionen correctamente puede concentrarse todo el esfuerzo en optimizar la gestión de la tabla de símbolos. Para que este proceso no influya en las fases ya desarrolladas del compilador es necesario dotar a la tabla de símbolos de una interfaz claramente definida e invariable desde el principio: en la optimización de la tabla de símbolos se modifica su implementación, pero se mantiene su interfaz.

> En esta figura se menciona una distinción importante entre la construcción de compiladores para lenguajes que obligan al programador a declarar todas las variables (C, Modula-2, Pascal, Java, etc.), y lenguajes en los que las variables se pueden usar directamente sin necesidad de declararlas (BASIC, Logo, etc.). Cuando un lenguaje posee área de declaraciones y área de sentencias, la aparición de un identificador tiene una semántica bien diferente según el área en que se encuentre:

> - Si aparece en el área de declaraciones, entonces hay que insertar el identificador en la tabla de símbolos, junto con la información que de él se conozca. Si el identificador ya se encontraba en la tabla, entonces se ha producido una re declaración y debe emitirse un mensaje de error semántico.

> - Si aparece en el área de sentencias, entonces hay que buscar el identificador en la tabla de símbolos para controlar que el uso que de él se está haciendo sea coherente con su tipo. Si el identificador no se encuentra en la tabla, entonces es que no ha sido previamente declarado, lo que suele considerarse un error semántico del que hay que informar al programador.

> En estos casos, el analizador lexicográfico, cuando se encuentra un identificador desconoce en qué área lo ha encontrado, por lo que no resulta fácil incluir una acción léxica que discrimine entre realizar una inserción o una búsqueda; así, deberá ser el analizador sintáctico quien haga estas operaciones. Así, el atributo del token identificador suele ser su propio nombre.

> Sin embargo, hay unos pocos lenguajes de programación en los que no es necesario declarar las variables, bien porque sólo existe un único tipo de datos (como en nuestro ejemplo de la calculadora donde todo se consideran valores enteros) o bien porque el propio nombre de la variable sirve para discernir su tipo (en BASIC las variables que acaban en “$” son de tipo cadena de caracteres). En estos casos, el propio analizador lexicográfico puede insertar el identificador en la tabla de símbolos la primera vez que aparezca; antes de insertarlo realiza una operación de búsqueda por si ya existía. Y sea cual sea el caso, se obtiene la entrada o índice de la tabla en la que se encontraba o se ha incluido; dicho índice será el valor que el analizador léxico pasa al sintáctico como atributo de cada identificador.

> Por último, es importante recalcar que la tabla de símbolos contiene información útil para poder compilar, y por tanto sólo existe en tiempo de compilación, y no de ejecución. Sin embargo, en un intérprete dado que la compilación y la ejecución se producen a la vez, la tabla de símbolos permanece en memoria todo el tiempo.

> Ejemplo: una calculadora con variables.

> Llegados a este punto, vamos a aumentar las posibilidades de la calculadora propuesta, incluyendo la posibilidad de manipular variables.

> Para simplificar el diseño no incluiremos un área de declaraciones de variables, sino que éstas se podrán utilizar directamente inicializándose a 0, puesto que tan sólo disponemos del tipo entero.

> Para introducir las variables en la calculadora necesitamos una nueva construcción sintáctica con la que poder darle valores: se trata de la asignación.

> Además, continuaremos con la sentencia de evaluación y visualización de expresiones a la que antepondremos la palabra reservada PRINT. En cualquier expresión podrá intervenir una variable que se evaluará al valor que tenga en ese momento. Así, ante la entrada:

> Ø a := 7 * 3;
> Ù b := 3 * a;
> Ú a := a + b;

> se desea almacenar en la variable a el valor 21, en la b el valor 63 y luego modificar a para que contenga el valor 84. Para conseguir nuestros propósitos utilizaremos una tabla de símbolos en la que almacenaremos tan sólo el nombre de cada variable, así como su valor ya que estamos tratando con un intérprete. La tabla de símbolos tendrá una estructura de lista no ordenada simplemente encadenada, ya que la claridad en nuestro desarrollo prima sobre la eficiencia. En los desarrollos con Java se hace uso de la clase HashMap.

> Para actualizar la tabla de símbolos para reflejar las asignaciones propuestas. Así, en la sentencia Ø una vez evaluada la expresión 7*3 al valor 21 se inspeccionará la tabla de símbolos en busca del identificador a. Dado que éste no está, el analizador léxico lo creará inicializándolo a 0; a continuación la regla asociada a la asignación modificará la entrada de la a para asignarle el valor 21. En la sentencia Ù, la evaluación de la expresión requiere buscar a en la tabla de símbolos para recoger su valor -21- para multiplicarlo por 3. El resultado -63- se almacena en la entrada asociada a la b de igual forma que se hizo para la variable a en la sentencia Ø. Por último, la sentencia Ú evalúa una nueva expresión en la que intervienen a y b, asignando su suma -84- a la entrada de a en la tabla de símbolos.

> Interfaz de la tabla de símbolos

> Como ya se ha comentado, la interfaz de la tabla de símbolos debe quedar clara desde el principio de manera que cualquier modificación en la implementación de la tabla de símbolos no tenga repercusión en las fases del compilador ya desarrolladas. Las operaciones básicas que debe poseer son:

> - crear( ): crea una tabla vacía.

> - insertar(simbolo): añade a la tabla el símbolo dado.

> - buscar(nombre): devuelve el símbolo cuyo nombre coincide con el parámetro. Si el símbolo no existe devuelve null.

> - imprimir( ): a efectos informativos, visualiza por la salida estándar la lista de variables almacenadas en la tabla de símbolos junto con sus valores asociados.

> Solución con Lex/Yacc

> Asumimos que no hay área de declaraciones en nuestro lenguaje, por lo que la inserción de los símbolos en la tabla se debe hacer desde una acción léxica. Como atributo del token ID se usará un puntero a su entrada en la tabla de símbolos.
> Las acciones semánticas usarán este puntero para acceder al valor de cada variable: si el identificador está a la izquierda del token de asignación, entonces se machacará el valor; y si forma parte de una expresión, ésta se evaluará al valor de la variable.

> Por otro lado, el atributo del token NUM sigue siendo de tipo int. Dado que se necesitan atributos de tipos distintos (para NUM y para ID), habrá que declarar un %union en Yacc, de la forma:

> %union {
> int numero;
> simbolo * ptrSimbolo;
> }
> y los terminales y no terminales de la forma:
> %token <numero> NUM
> %token <ptrSimbolo> ID
> %type <numero> expr

> Para finalizar, podemos optar por permitir asignaciones múltiples o no. Un ejemplo de asignación múltiple es:

> a := b := c := 16;

> que asigna el valor 16 a las variables c, b y a en este orden. Para hacer esto, consideraremos que las asignaciones vienen dadas por las siguientes reglas:

> asig : ID ASIG expr
> | ID ASIG asig
> ;

> Por medio de un árbol sintáctico que reconoce este ejemplo. Como puede verse en él, el no terminal asig también debe tener asociado como atributo el campo numero del %union, con objeto de ir propagando el valor de la expresión y poder realizar las asignaciones a medida que se asciende en el árbol sintáctico.

> La tabla de símbolos viene dada por el código siguiente, almacenado en el archivo TabSimb.c:

> 1 #include <stdlib.h>
> 2 #include <stdio.h>
> 3 typedef struct _simbolo {
> 4 struct _simbolo * sig;
> 5 char nombre [20];
> 6 int valor;
> 8 } simbolo;
> 9 simbolo * crear() {
> 10 return NULL;
> 11 };
> 12 void insertar(simbolo **pT, simbolo *s) {
> 13 s->sig = (*pT);
> 14 (*pT) = s;
> 15 };
> 16 simbolo * buscar(simbolo * t, char nombre[20]){
> 17 while ( (t != NULL) && (strcmp(nombre, t->nombre)) )
> 18 t = t->sig;
> 19 return (t);
> 20 };
> 21 void imprimir(simbolo * t) {
> 22 while (t != NULL) {
> 23 printf("%s\n", t->nombre);
> 24 t = t->sig;
> 25 }
> 26 };

> El programa Lex resulta sumamente sencillo. Tan sólo debe reconocer los lexemas e insertar en la tabla de símbolos la primera vez que aparezca cada identificador. El siguiente archivo Calcul.lex ilustra cómo hacerlo:

> 1 %%
> 2 [0-9]+ {
> 3 yylval.numero = atoi(yytext);
> 4 return NUMERO;
> 5 }
> 6 ":=" { return ASIG; }
> 7 "PRINT" { return PRINT; }
> 8 [a-zA-Z][a-zA-Z0-9]* {
> 9 yylval.ptrSimbolo = buscar(t,yytext);
> 10 if (yylval.ptrSimbolo == NULL) {
> 11 yylval.ptrSimbolo=(simbolo *) malloc(sizeof(simbolo));
> 12 strcpy(yylval.ptrSimbolo->nombre, yytext);
> 13 yylval.ptrSimbolo->valor=0;
> 14 insertar(&t, yylval.ptrSimbolo);
> 15 }
> 16 return ID;
> 17 }
> 18 [b¯& \t\n]+ { ; }
> 19 . { return yytext[0]; }

> El programa Yacc tan sólo difiere de la calculadora tradicional en los accesos a la tabla de símbolos para obtener y alterar el valor de cada variable. El siguiente código se supone almacenado en el archivo Calcuy.yac:

> 1 %{
> 2 #include "TabSimb.c"
> 3 simbolo * t;
> 4 %}
> 5 %union {
> 6 int numero;
> 7 simbolo * ptrSimbolo;
> 8 }
> 9 %token <numero> NUMERO
> 10 %token <ptrSimbolo> ID
> 11 %token ASIG PRINT
> 12 %type <numero> expr asig
> 13 %left '+' '-'
> 14 %left '*' '/'
> 15 %right MENOS_UNARIO
> 16 %%
> 17 prog : prog asig ';' { printf("Asignacion(es) efectuada(s).\n"); }
> 18 | prog PRINT expr ';' { printf("%d\n",$3); }
> 19 | prog error ';' { yyerrok; }
> 20 | /* Épsilon */
> 21 ;
> 22 asig : ID ASIG expr {
> 23 $$ = $3;
> 24 $1->valor = $3;
> 25 }
> 26 | ID ASIG asig {
> 27 $$ = $3;
> 28 $1->valor = $3;
> 29 }
> 30 ;
> 31 expr : expr '+' expr {$$ = $1 + $3;}
> 32 | expr '-' expr {$$ = $1 - $3;}
> 33 | expr '*' expr {$$ = $1 * $3;}
> 34 | expr '/' expr {$$ = $1 / $3;}
> 35 | '(' expr ')' {$$ = $2;}
> 36 | '-' expr %prec MENOS_UNARIO {$$ = - $2;}
> 37 | ID {$$ = $1->valor; }
> 38 | NUMERO {$$ = $1;}
> 39 ;
> 40 %%
> 41 #include "Calcul.c"
> 42 #include "errorlib.c"
> 43 void main()
> 44 { t = crear();
> 45 yyparse ();
> 46 imprimir(t);
> 47 }

> 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