Compildores

Estructuras de Datos de un Compilador
La interacción entre los algoritmos utilizados por las fases de un compilador y estructuras de datos que soportan estas fases es, naturalmente, muy fuerte. El escritor del compilador se esfuerza por implementar estos algoritmos de una manera tan eficaz como sea posible, sin aumentar demasiado la complejidad. De manera ideal, un compilador debería podercompilar un programa en un tiempo proporcional al tamaño del programa, es decir, en O(n) tiempo, donde n es una medida del tamaño del programa (por lo general el número de caracteres). En esta sección señalaremos algunas de las principales estructuras de datos que son necesarias para las fases como parte de su operación y que sirven para comunicar la información entre las fases.

Tokens – Cuando unrastreador o analizador léxico reúne los caracteres en un token, generalmente representa el token de manera simbólica, es decir, como un valor de un tipo de datos enumerado que representa el conjunto de tokens del lenguaje fuente. En ocasiones también es necesario mantener la cadena de caracteres misma u otra información derivada de ella, tal como el nombre asociado con un token identificador o elvalor de un token de número.
En la mayoría de los lenguajes el analizador léxico sólo necesita generar un token a la vez. En este caso se puede utilizar una variable global simple para mantener la información del token. En otros casos, puede ser necesario un arreglo de tokens.

Árbol sintáctico – Si el analizador sintáctico genera un árbol sintáctico, por lo regular se construye como unaestructura estándar basada en un apuntador que se asigna de manera dinámica a medida que se efectúa el análisis sintáctico. El árbol entero puede entonces conservarse como una variable simple que apunta al nodo raíz. Cada nodo en la estructura es un registro cuyos campos representan la información recolectada tanto por el analizador sintáctico como, posteriormente, por el analizador semántico. Porejemplo, el tipo de datos de una expresión pude conservarse como un campo en el nodo del árbol sintáctico para la expresión. En ocasiones, para ahorrar espacio, estos campos se asignan de manera dinámica, o se almacenan en otras estructuras de datos, tales como la tabla de símbolos, que permiten una asignación y desasignación selectivas. En realidad, cada nodo de árbol sintáctico por sí mismo puederequerir de atributos diferentes para ser almacenado, de acuerdo con la clase de estructura del lenguaje que represente. En este caso, cada nodo en el árbol sintáctico puede esta representado por un registro variable, con cada clase de nodo conteniendo solamente la información necesaria para ese caso.

Tabla de Símbolos – Esta estructura de datos mantiene la información asociada con losidentificadores: funciones, variables, constantes y tipos de datos. Tabla de símbolos interactúa con caso todas las fases del compilador; el rastreador o analizador léxico, el analizador sintáctico o el analizador semántico puede introducir identificadores dentro de la tabla; el analizador semántico agregará tipos de datos y otra información; y las fases de optimización y generación de código utilizarán lainformación proporcionada por la tabla de símbolos tendrá solicitudes de acceso con tanta frecuencia, las operaciones de inserción, eliminación y acceso necesitan ser eficientes, preferiblemente operaciones de tiempo constante. Una estructura de datos estándar para este propósito es la tabla de dispersión o de cálculo de dirección, aunque también se pueden utilizar diversas estructuras de árbol.En ocasiones se utilizan varias tablas y se mantienen en una lista o pila.



Tabla de Literales – La búsqueda y la inserción rápida son esenciales también para la tabla de literales, la cual almacena constantes y cadenas utilizadas en el programa. Sin embargo, una tabla de literales necesita impedir las eliminaciones porque sus datos se aplican globalmente al programa y una constante o...