Compiladores (página 2)

5. Forma de examinar de un compilador

En la compilación hay dos partes: Análisis y Síntesis. La parte del análisis divide al programa fuente en sus elementos componentes y crea una representación intermedia. De las dos partes, la síntesis es la que requiere la técnica más especializada. Durante el análisis se determina las operaciones que implica el programa fuente y se registra en una estructura jerárquica llamada árbol. A menudo, se usa una clase especial de árbol llamado árbol sintáctico, donde cada nodo representa una operación y los hijos de un nodo son los argumentos de la operación. Por ejemplo, en la figura 5 se muestra un árbol sintáctico para una proposición de asignación.

Figura 5. Árbol sintáctico para posición := inicial + velocidad * 60

6. Como se sintetiza el código objeto un compilador estándar, teórica y gráficamente generación de código

En esta parte el código intermedio optimizado es traducido a una secuencia de instrucciones en ensamblador o en el código de máquina del procesador que nos interese. Por ejemplo, la sentencia A:=B+C se convertirá en: LOAD B ADD C STORE A suponiendo que estas instrucciones existan de esta forma en el ordenador de que se trate. Una conversión tan directa produce generalmente un programa objeto que contiene muchas cargas (loads) y almacenamientos (stores) redundantes, y que utiliza los recursos de la máquina de forma ineficiente. Existen técnicas para mejorar esto, pero son complejas. Una, por ejemplo, es tratar de utilizar al máximo los registros de acceso rápido que tenga la máquina. Así, en el procesador 8086 tenemos los registros internos AX, BX, CX, DX, etc. y podemos utilizarlos en vez de direcciones de memoria.

Tabla De Símbolos Un compilador necesita guardar y usar la información de los objetos que se va encontrando en el texto fuente, como variables, etiquetas, declaraciones de tipos, etc. Esta información se almacena en una estructura de datos interna conocida como tabla de símbolos. El compilador debe desarrollar una serie de funciones relativas a la manipulación de esta tabla como insertar un nuevo elemento en ella, consultar la información relacionada con un símbolo, borrar un elemento, etc. Como se tiene que acceder mucho a la tabla de símbolos los accesos deben ser lo más rápidos posible para que la compilación sea eficiente.

Manejo de errores Es una de las misiones más importantes de un compilador, aunque, al mismo tiempo, es lo que más dificulta su realización. Donde más se utiliza es en las etapas de análisis sintáctico y semántico, aunque los errores se pueden descubrir en cualquier fase de un compilador. Es una tarea difícil, por dos motivos:

• A veces unos errores ocultan otros.
• A veces un error provoca una avalancha de muchos errores que se solucionan con el primero.

Es conveniente un buen manejo de errores, y que el compilador detecte todos los errores que tiene el programa y no se pare en el primero que encuentre. Hay, pues, dos criterios a seguir a la hora de manejar errores:

• Pararse al detectar el primer error.
• Detectar todos los errores de una pasada.

En el caso de un compilador interactivo (dentro de un entorno de desarrollo integrado, como Turbo-Pascal o Borland C++) no importa que se pare en el primer error detectado, debido a la rapidez y facilidad para la corrección de errores.

7. Árboles sintácticos para representar como sintetiza el código objeto un compilador

Figura 6.- Generación de código.

figura 7.- Código en ensamblador para la figura 6.

8. Herramientas que muestran tipos de análisis de programas fuente

Muchas herramientas de software que manipulan porgraas fuente realizan primero algún tipo de análisis. Algunos ejemplos de tales herramientas son:

1. Editores de estructuras: un editor de estructuras toma como entrada uan secuencia de ordenes para construir un programa fuente. El editor de estructuras no sólo realiza las funciones de creación y modificación de textos de un editor de textos ordinario, sino que también analiza el texto del programa imponiendo al programa fuente una estructura jerárquica apropiada. De esa manera, el editor de estructuras puede realizar tareas adicionales útiles para la preparación de programas. Por ejemplo, puede comprobar si la entrada está formada correctamente, puede proporcionar palabras clave de manera automática y puede saltar desde un begin o un paréntesis izquierdo hasta su correspondiente end o paréntesis derecho. Además, la salida de tal editor suele ser similar a la salida de la fase del análisis de un compilador.
2. Impresoras estéticas: Una impresora estética analiza un programa y lo imprime de forma que la estructura del programa resulte claramente visible. Por ejemplo, los comentarios pueden aparecer con un tipo de letra especial, y las proposiciones pueden aparecer con una indentación proporcional a la profundidad de su anidamiento en la organización jerárquica de las proposiciones.
3. Verificadores estáticos: Un verificador estático lee un programa, lo analiza e intenta descubrir errores potenciales sin ejecutar el programa. La parte del análisis es similar a la que se encuentra en los compiladores de optimación. Así un verificador estático puede detectar si hay partes de un programa que nunca se podrán ejecutar o si cierta variable se usa antes de ser definida. Además, puede detectar errores de lógica como intentar utilizar una variable real como apuntador, empleando las técnicas de verificación de tipos.
4. Intérpretes: En lugar de producir un programa objeto como resultado de una traducción, un interprete realiza las operaciones que implica el programa fuente. Para una proposición de asignación, por ejemplo, un intérprete podría construir un árbol como el de la figura 5, y después efectuar las operaciones de los nodos conforme "recorre" el árbol. En la raíz descubriría que tiene que realizar una asignación, y llamaría a una rutina para evaluar la expresión de la derecha y después almacenaría el valor resultante en la localidad de memoria asignada con el identificador posición. En el hijo derecho de la raíz, la rutina descubriría que tiene que calcular la suma de dos expresiones. Se llamaría a si misma de manera recursiva para calcular el valor de la variable inicial.

9. Diagrama de análisis de un programa fuente, definiendo cada una de sus partes

Al principio de la historia de los compiladores, el tamaño del programa ejecutable era un recurso crítico, así como la memoria que utilizaba el compilador para sus datos, por lo que lo frecuente era que cada fase leyera un fichero escrito por la fase anterior y produjera un nuevo fichero con el resultado de las transformaciones realizadas en dicha fase. Esta técnica (inevitable en aquellos tiempos) hacía que el compilador realizara muchas pasadas sobre el programa fuente. En los últimos años el tamaño del fichero ejecutable de un compilador es relativamente pequeño comparado con el de otros programas del sistema, y además (gracias a los sistemas de memoria virtual) normalmente no tienen problemas de memoria para compilar un programa medio. Por estos motivos, y dado que escribir y leer un fichero de tamaño similar o mayor que el del programa fuente en cada fase es una pérdida considerable de tiempo (incluso en los sistemas modernos), la tendencia actual es la de reducir el número de ficheros que se leen o escriben y por tanto reducir el número de pasadas, incluso el de aquéllas que se realizan en memoria, sin escribir ni leer nada del disco. Las fases se agrupan en dos partes o etapas: front end (las fases de análisis) y back end (las fases de generación y optimización de código). Estas dos etapas se comunican mediante una representación intermedia (generada por el front end), que puede ser una representación de la sintaxis del programa (un árbol sintáctico abstracto) o bien puede ser un programa en un lenguaje intermedio. El front end depende del lenguaje fuente y casi siempre es independiente (o debe serlo) de la máquina objeto para la que se va a generar código; el back end depende del lenguaje objeto y debe ser independiente del lenguaje fuente (excepto quizá para algún tipo de optimización).

Análisis Léxico El analizador léxico, también conocido como scanner, lee los caracteres uno a uno desde la entrada y va formando grupos de caracteres con alguna relación entre sí (tokens), que constituirán la entrada para la siguiente etapa del compilador. Cada token representa una secuencia de caracteres que son tratados como una única entidad. Por ejemplo, en Pascal un token es la palabra reservada BEGIN, en C: WHILE, etc. Hay dos tipos de tokens: tiras específicas, tales como palabras reservadas (if, while, begin, etc.), el punto y coma, la asignación, los operadores aritméticos o lógicos, etc.; tiras no específicas, como identificadores, constantes o etiquetas. Se considera que un token tiene dos partes componentes: el tipo de token y su valor. Las tiras específicas sólo tienen tipo (lo que representan), mientras que las tiras no específicas tienen tipo y valor. Por ejemplo, si "Contador" es un identificador, el tipo de token será identificador y su valor será la cadena "Contador". El Analizador Léxico es la etapa del compilador que va a permitir saber si es un lenguaje de formato libre o no. Frecuentemente va unido al analizador sintáctico en la misma pasada, funcionando entonces como una subrutina de este último. Ya que es el que va leyendo los caracteres del programa, ignorará aquellos elementos innecesarios para la siguiente fase, como los tabuladores, comentarios, espacios en blanco, etc.

Figura 8.- Análisis léxico.

Análisis Sintáctico El analizador sintáctico, también llamado parser, recibe como entrada los tokens que le pasa el Analizador Léxico (el analizador sintáctico no maneja directamente caracteres) y comprueba si esos tokens van llegando en el orden correcto (orden permitido por el lenguaje). La salida "teórica" de la fase de análisis sintáctico sería un árbol sintáctico. Así pues, sus funciones son:

• Aceptar lo que es válido sintácticamente y rechazar lo que no lo es.
• Hacer explícito el orden jerárquico que tienen los operadores en el lenguaje de que se trate. Por ejemplo, la cadena A/B*C es interpretada como (A/B)*C en FORTRAN y comoA/(B*C) en APL.
• Guiar el proceso de traducción (traducción dirigida por la sintaxis).

Análisis Semántico El análisis semántico es posterior al sintáctico y mucho más difícil de formalizar que éste. Se trata de determinar el tipo de los resultados intermedios, comprobar que los argumentos que tiene un operador pertenecen al conjunto de los operadores posibles, y si son compatibles entre sí, etc. En definitiva, comprobará que el significado de lo que se va leyendo es válido. La salida "teórica" de la fase de análisis semántico sería un árbol semántico. Consiste en un árbol sintáctico en el que cada una de sus ramas ha adquirido el significado que debe tener. En el caso de los operadores polimórficos (un único símbolo con varios significados), el análisis semántico determina cuál es el aplicable. Por ejemplo, consideremos la siguiente sentencia de asignación: A := B + C En Pascal, el signo "+" sirve para sumar enteros y reales, concatenar cadenas de caracteres y unir conjuntos. El análisis semántico debe comprobar que B y C sean de un tipo común o compatible y que se les pueda aplicar dicho operador. Si B y C son enteros o reales los sumará, si son cadenas las concatenará y si son conjuntos calculará su unión. Ejemplo VAR ch : CHAR; (* Un identificador no se puede utilizar si *) ent: INTEGER; (* previamente no se ha definido. *) … ch := ent + 1; (* En Pascal no es válido, en C sí. *)

Análisis Léxico: Devuelve la secuencia de tokens: id asig id suma numero ptocoma Análisis Sintáctico: Orden de los tokens válido Análisis Semántico: Tipo de variables asignadas incorrecta

Estructura del programa fuente Programa fuente Programa objeto en lenguaje ensamblador Código de máquina relocalizable Código de máquina absoluto Figura 9.- Sistema para procesamiento de un lenguaje

Figura 10.- Árbol de análisis sintáctico para posición := inicial + velocidad * 60.

10. Conclusiones

Este trabajo servirá mucho en el momento de la creación de un compilador, ya que en él se detallan todas y cada una de las partes que involucran a este. Primeramente investigue que existen distintos tipos de compiladores, me gustaria crear un compilador de optimación, ya que pienso que es muy útil a la hora de crear un algoritmo o programa. La función de un compiladores es leer un programa escrito es un lenguaje, en este caso el lenguaje fuente, y lo traduce a un programa equivalente en otro lenguaje, el lenguaje objeto. Me parece fascinante que nosotros podamos crear un compilador en seis meses (en un curso), cuando en los años 50, ya que en aquellos tiempos se tardaron hasta 18 años trabajando en un compilador. Por otro lado, comprendí que un compilador, requiere de una sintaxis y lenguajes específicos, ya que, al igual que el lenguaje humano, si no lo escribimos correctamente el compilador no hará lo que deseamos. Y que en la compilación hay dos partes: Análisis y Síntesis. La parte del análisis divide al programa fuente en sus elementos componentes y crea una representación intermedia. Aprendí que las herramientas que muestran tipos de análisis de programas fuente, son muy útiles al momento de crear un programa al codificar un algoritmo, ya que estas herramientas nos ayudan formateando el texto, corrigiendo errores, dando tips; para que nosotros como programadores seamos más eficientes al momento de crear alguna aplicación. También he notado como todas nuestras materias se va complementando y enlazando, por ejemplo, en matemáticas discretas vimos la representación de árboles, los cuales usamos aquí. Igualmente en estructura de datos I, vimos métodos de ordenamiento que las gramáticas de los compiladores usan. Por lo tanto, no parece tan complicado crear un compilador, sólo se necesitan los conocimientos adecuados y dedicarle su tiempo para tener éxito.

11. Bibliografía

• Compiladores, Principios, técnicas y herramientas, Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman. Addison – Wesley iberoamericana.
• http://www.dlsi.ua.es/docencia/asignaturas/comp1/comp1.html
• http://www.cps.unizar.es/~ezpeleta/COMPI
• http://www.ii.uam.es/~alfonsec
• Compiladores: Conceptos Fundamentales. B. Teufel, S. Schmidt, T. Teufel. Addison Wesley Iberoamericana.

Ceballos Carmona Miguel Ángel, 25 años Estudiante universitario del ITESI, en Irapuato, Gto. Trabajo para la materia Lenguajes y autómatas. Creado en Febrero del 2002. Palabras clave para Búsqueda: compiladores, lenguajes y autómatas, análisis léxico, análisis sintáctico, análisis semántico, árboles sintácticos, Compilador cruzado, Compilador con montador, autocompilador, metacompilador, descompilador, código objeto.

Autor:

Miguel Ángel