|
P R O Y E C T O
DESARROLLO
|
|
Compilación Compilación es el proceso por el cual se traducen programas en código fuente a programas en código objeto. El programa que realiza esta traducción se llama compilador. El archivo de código objeto que se obtiene con la compilación está representado normalmente en código de máquina, aunque también puede ser un código intermedio binario multiplataforma (bytecode). Para conseguir el programa ejecutable final a partir de todos los archivos de código objeto se debe utilizar un programa llamado montador y un enlazador (linker). Este proceso de montaje tiene como resultado un archivo ejecutable que contiene el programa en código máquina listo para ser ejecutado con la ayuda del sistema operativo. El proceso de enlazamiento arregla las referencias a rutinas externas.
Ventajas de compilar frente a interpretar:
Un compilador no es un programa que funciona de manera aislada, sino que necesita de otros programas para conseguir su objetivo: obtener un programa ejecutable a partir de un programa fuente en un lenguaje de alto nivel. Algunos de esos programas son el preprocesador, el linker, el depurador y el ensamblador. El preprocesador se ocupa (dependiendo del lenguaje) de incluir ficheros, expandir macros, eliminar comentarios, y otras tareas similares. El linker se encarga de construir el fichero ejecutable añadiendo al fichero objeto generado por el compilador las cabeceras necesarias y las funciones de librería utilizadas por el programa fuente. El depurador permite, si el compilador ha generado adecuadamente el programa objeto, seguir paso a paso la ejecución de un programa. Finalmente, muchos compiladores, en vez de generar código objeto, generan un programa en lenguaje ensamblador que debe después convertirse en un ejecutable mediante un programa ensamblador.
Los compiladores pueden ser de: • Una sola pasada: examina el código fuente una vez, generando el código o programa objeto. • pasadas múltiples: requieren pasos intermedios para producir un código en otro lenguaje, y una pasada final para producir y optimizar el código producido durante los pasos anteriores. • Optimación: lee un código fuente, lo analiza y descubre errores potenciales sin ejecutar el programa. • Compiladores incrementales: generan un código objeto instrucción por instrucción (en vez de hacerlo para todo el programa) cuando el usuario teclea cada orden individual. El otro tipo de compiladores requiere que todos los enunciados o instrucciones se compilen conjuntamente. • Ensamblador: el lenguaje fuente es lenguaje ensamblador y posee una estructura sencilla. • Compilador cruzado: se genera código en lenguaje objeto para una máquina diferente de la que se está utilizando para compilar. Es perfectamente normal construir un compilador de Pascal que genere código para MS-DOS y que el compilador funcione en Linux y se haya escrito en C++. • Compilador con montador: compilador que compila distintos módulos de forma independiente y después es capaz de enlazarlos. • Autocompilador: compilador que está escrito en el mismo lenguaje que va a compilar. Evidentemente, no se puede ejecutar la primera vez. Sirve para hacer ampliaciones al lenguaje, mejorar el código generado, etc.
Código fuente Que es el Código fuente A diferencia del código objeto, el código fuente es texto simple, capaz de ser leído por cualquier editor de textos. En él están escritas las instrucciones que deberá realizar la computadora, según la sintaxis de un lenguaje de programación. Tener el código fuente es de gran importancia si se necesita modificar un programa.
Código objeto Se llama código objeto en programación al código resultante de la compilación del código fuente, por lo general está codificado en código de máquina y distribuido en varios archivos resultantes de la compilación de cada archivo de código fuente. Para obtener un archivo ejecutable se han de enlazar todos los archivos de código fuente con un programa llamado enlazador (linker).
Código binario El código binario es una codificación de programas en sistema binario que es el único que puede ser directamente ejecutado por un ordenador. Sin embargo, para los seres humanos, programar en sistema binario es molesto y propenso a errores. Incluso con la abreviatura octal o hexadecimal, es fácil confundir una cifra con otra y trabajoso acordarse del código de operación de cada una de las instrucciones de la máquina. Por esa razón se inventaron los lenguajes simbólicos, que se llaman así porque utilizan símbolos para representar las operaciones a realizar por cada instrucción y las direcciones de memoria sobre las que actúa. Ejemplo de códigos de operación, que se aplican a los microprocesadores de Intel. 00000101 ADD Sumar al acumular 00101101 SUB Restar al acumular 010000xx INC Incrementar el registro xx 010010xx DEC Decrementar el registro xx 11101011 JMP Saltar incondicional 101110xx MOV Cargar registro xx desde memoria
Enlazador Un enlazador es un programa que toma los ficheros de código objeto generado en los primeros pasos del proceso de compilación y los convierte en un fichero ejecutable o en una biblioteca. En el caso de los programas enlazados dinámicamente, el enlace entre el programa ejecutable y las bibliotecas se realiza en tiempo de carga o ejecución del programa.
Análisis del programa fuente n El análisis consta de tres fases: n Análisis lineal (o léxico) : se lee la cadena de caracteres de izda a dcha agrupando componentes léxicos, que son secuencias de caracteres que tienen un significado como agrupación.
Análisis léxico
n Realiza el análisis léxico. Dada la expresión : posición := inicial + velocidad * 60 se obtendrían los siguientes componentes léxicos:
Análisis sintáctico n Es un análisis de tipo jeráquico. Los componentes léxicos del programa fuente se agrupan en frases gramaticales que el compilador utiliza para sintetizar la salida. Las frases se representan mediante un árbol de análisis sintáctico como el que se ilustra en la figura n Podemos ver en el árbol sintáctico que la multiplicación se agrupa antes que la suma. La estructura jerárquica de un programa normalmente se expresa utilizando reglas recursivas. Por ejemplo, podemos dar las siguientes reglas para construir expresiones como la de arriba: 1. Cualquier identificador es una expresión, 2. Cualquier número es una expresión, 3. Si expresión1 y expresión2 son dos expresiones, entonces también lo son: a) Expresión1 + expresion2 b) Expresion1 * expresion2 c) (expresion1) n La división entre análisis léxico y análisis sintáctico puede ser arbitraria. Un factor a considerar es si una construcción es inherentemente recursiva o no. Las construcciones léxicas no requieren recursión, mientras que la construcciones sintácticas suelen requerirla. No se requiere recursión para reconocer los identificadores, que se agrupan en una tabla, llamada tabla de símbolos.
Análisis semántico n La fase de análisis semántico revisa el código fuente para tratar de encontrar errores semánticos y reúne información sobre los tipos para la fase posterior de generación de código. n También se lleva a cabo la verificación de tipos. En el análisis semántico se realizan comprobaciones de los tipo permitidos por un operador; en caso de que no coincidan con los permitidos se generará un error o se realizarán las operaciones de conversión necesarias (coerción).
Análisis en formadores de texto. n Los formadores o formateadores de texto realizan un análisis considerando una jerarquía de cajas: regiones rectangulares que se contienen elementos léxicos. Un ejemplo de éste es TEX.
Las fases de un compilador n Las principales fases son: n Análisis léxico, n Análisis sintáctico, n Análisis semántico, n Generación de código intermedio, n Optimización, n Generación de código objeto.
La tabla de símbolos n Una tabla de símbolos es una estructura de datos que contiene una entrada por cada identificador, cada una con los atributos: • Nombre, • Tipo, • Ámbito, n Y se trata de un procedimiento o función también: • Número de argumentos, • Tipos de los argumentos, • Paso por parámetro o referencia, • Tipo que devuelve. n La mayoría de los atributos son establecidos durante el análisis semántico.
Detección de errores n Cada fase puede encontrar errores. Cuando se encuentra un error, la fase que lo ha detectado tiene de alguna forma que recuperarse para poder seguir con el análisis. De esta forma se quiere conseguir que el compilador reporte la máxima cantidad de errores. n Cada fase detecta un tipo de error: • Léxico: la cadena de entrada no conforma ningún componente léxico, • Sintáctico: los componentes léxicos incumplen alguna regla sintáctica, • Semántico: una construcción no tiene el significado semántico apropiado. Herramientas para la construcción de compiladores n Algunas de estas herramientas son las siguientes: n Generadores de analizadores sintácticos. Producen analizadores sintácticos, normalmente a partir de una entrada fundamentada en una gramática independiente de contexto. n Generadores de analizadores léxicos. Generan automáticamente analizadores léxicos, por lo general, a partir de una especificación basada en expresiones regulares. La estructura básica del resultado es un autómata finito. n Dispositivos de traducción dirigida por la sintaxis. Estos producen grupos de rutinas que recorren el árbol de análisis sintáctico generando código intermedio. La idea básica es que se asocian una o más traducciones con cada nodo del árbol y cada traducción se define partiendo de traducciones en sus nodos vecinos en el árbol. n Generadores automáticos de código. Tales herramientas toman un conjunto de reglas que definen la traducción de cada operación del lenguaje intermedio al lenguaje máquina para la máquina objeto. Las reglas deben incluir suficiente detalle para poder manejar distintos métodos de acceso a los datos. n Dispositivos para el análisis de flujo de datos. Consiste en la recolección de información sobre la forma en que se transmiten los valores de una parte de un programa a cada una de las otras partes.
1. Obtener el conjunto de elementos léxicos (tokens) considerado en el lenguaje diseñado en la práctica anterior. 2. Confeccionar la tabla de tokens, la cual deberá recoger la siguiente información:
3. Confeccionar las especificaciones LEX y el correspondiente analizador de léxico. Igualmente, deberá añadirse la especificación LEX necesaria, junto con su expresión regular correspondiente, para el tratamiento de los comentarios asociados al código fuente de cualquier programa en nuestro lenguaje, de manera que se detecten dichos comentarios. 4. Completar la tabla de tokens elaborada en el punto 2, de manera que se añada para cada token el patrón elaborado en la especificación LEX, mostrándose por tanto la siguiente información:
5. Probar el analizador léxico elaborado con distintos ficheros que contendrán los correspondientes programas de prueba.
Información adicional El programa FLEX se encuentra en: \\almaden\alumnos\Leng_Pro y también puedes bajártelo en formato comprimido desde http://wwwdi.ujaen.es/~nacho. En dicha dirección se encuentran los siguientes ficheros:
Para ejecutar FLEX de forma estándar se sigue el siguiente formato: Flex –Sflex.skl fichero_descripción_flex Al ejecutar el programa flex se obtiene el fichero lexyy.c, que contiene el fuente C de la función yylex que realiza el análisis de léxico de su lenguaje. Para obtener el ejecutable es necesario compilarlo, llamándolo desde el programa principal. El generador de analizadores de léxico flex permite controlar si la entrada proviene de un fichero o de la entrada estándar (introduciendo directamente los tokens por teclado) mediante la variable yyin, de tipo puntero a FILE, la cual debería tomar valor nulo en caso de que queramos utilizar la entrada estándar, y apuntará al fichero fuente en caso contrario. Igualmente ocurre con la variable yyout, utilizada en este caso para enviar la salida a un fichero, en caso de que dicha variable apunte a un fichero; en caso contrario la salida se realizará por pantalla, con lo que inicializaremos dicha variable con el valor nulo. Una URL bastante útil (ojo con las mayúsculas de la URL) para profundizar en el conocimiento de la herramienta indicada, especialmente para el correcto tratamiento de los comentarios y, en algunos casos, de las cadenas, mediante la utilización de condiciones es: http://lucas.hispalinux.es/Manuales-LuCAS/FLEX/flex-es-2.5.html Puedes acceder a ella igualmente desde la página de la asignatura: http://wwwdi.ujaen.es/~nacho Ejemplo de analizador de léxico
a) lexico.l %{ /* Analizador de léxico */ #include <stdlib.h> #include <stdio.h> #include "tabla.h" #define __STDC__ int linea_actual = 0; %} letra [a-zA-Z] digito [0-9] alphanum [a-zA-Z_0-9] otros .
%% "(" return PIZ; ")" return PDE; "+" return SUM; "-" return RES; "*" return MUL; "/" return DIV; ":=" return ASI; [Pp][Rr][Oo][Gg][Rr][Aa][Mm][Aa] return PRG; "FIN" return FIN; {letra}{alphanum}* return ID; {digito}+ return NUM; (" ")+ ; \n linea_actual++; \t ; {otros} return ERR; %% FILE *abrir_entrada(int argc, char **argv) { FILE *f= NULL; if (argc > 1) { f = fopen(argv[1],"r"); if (f==NULL) { fprintf(stderr,"Fichero '%s' no encontrado",argv[1]); exit(1); } else printf("Leyendo fichero '%s'.",argv[1]); } else printf("Leyendo entrada standard"); return f; } FILE *abrir_salida(int argc, char **argv) { FILE *f= NULL; if (argc > 2) { f = fopen(argv[2],"w"); if (f==NULL) { fprintf(stderr,"Fichero '%s' no encontrado",argv[2]); exit(1); } else printf("Abriendo fichero '%s'.",argv[2]); } return f; } Práctica 2 de Lenguajes de Programación Curso 02/03 main(int argc, char **argv) { int val; yyin = abrir_entrada(argc, argv); yyout = abrir_salida(argc, argv); val = yylex(); if (yyout!=NULL) { while (val != 0) { fprintf(yyout, "%d,%s\n",val,yytext); val = yylex(); } } else { while (val != 0) { printf("%d,%s\n",val,yytext); val = yylex(); } } if (yyin!=NULL) fclose(yyin); if (yyout!=NULL) fclose(yyout); exit(1); }
a) tabla.h #define ERR 256 #define PDE 257 #define SUM 258 #define RES 259 #define MUL 260 #define DIV 261 #define ASI 262 #define PRG 263 #define FIN 264 #define ID 265 #define NUM 266 #define PIZ 267
Documentación a presentar 1. Tabla de tokens. 2. Listado del código fuente de todos los programas usados: fuente de flex y módulo o módulos adicionales, en el caso de que se hayan elaborado, así como una descripción detallada de las expresiones regulares adoptadas más llamativas (especialmente aquellas que requieran uso de condiciones y macros). NO se debe incluir el código del fichero lexyy.c. 3. Listado de los ficheros de prueba elaborados 4. Disco con directorio que se llamará prac2 con todos los ficheros necesarios para la compilación y ejecución de la práctica, incluyendo el fichero flex.skl 5. En dicho directorio deberán incluirse también ficheros con programas elaborados con vuestro lenguaje, y de distinta complejidad, los cuales se nombrarán como pruebai.extension_del_lenguaje, donde i será un valor numérico y extension_del_lenguaje serán unas siglas que referencien a vuestro lenguaje (p.e., como "pas" referencia a los fuentes en Pascal). 6. Será ejecutado el programa generado con los ficheros indicados, y se comprobará que devuelve el token y código correcto. Por tanto, deberá permitirse la posibilidad de pasar un fichero como parámetro al ejecutable generado para la presente práctica.
Necesidad del analizador léxico Un tema importante es el porqué se separan los dos análisis lexicográfico y sintáctico, en vez de realizar sólo el análisis sintáctico, del programa fuente, cosa perfectamente posible aunque no plausible. Algunas razones de esta separación son: • Un diseño sencillo es quizás la consideración más importante. Separar el análisis léxico del análisis sintáctico a menudo permite simplificar una u otra de dichas fases. El analizador léxico nos permite simplificar el analizador sintáctico.
Si el sintáctico tuviera la gramática de la Opción 1 , el lexicográfico sería: Opción 1:
Si en cambio el sintáctico toma la Opción 2, el lexicográfico sería: Opción 2:
Es más, si ni siquiera hubiera análisis léxico, el propio análisis sintáctico vería incrementado su número de reglas:
A modo de conclusión, diremos que tenemos dos gramáticas, una que se encarga del análisis léxico y otra que se encarga del análisis sintáctico. ¿Que consideramos componente básico?, ¿Donde ponemos el punto divisor de qué se encarga cada gramática?. Si las divisiones se hacen muy pequeñas estamos complicando la gramática, por ejemplo, en la opción 2, la gramática sintáctica se nos complica un poco. Seguiremos dos reglas para que no se nos complique. La primera es que tendremos que hacer divisiones de forma que no perdamos información, esto quedará más claro en capítulos posteriores, y nos veremos ayudados por el concepto de atributo. La segunda es que por regla general el analizador lexicográfico debe de encargarse de la parte que involucra una gramática regular (que nosotros expresaremos mediante expresiones regulares). • Se mejora la eficiencia del compilador. Un analizador léxico independiente permite construir un procesador especializado y potencialmente más eficiente para esa función. Gran parte del tiempo se consume en leer el programa fuente y dividirlo en componentes léxicos. Con técnicas especializadas de manejo de buffers para la lectura de caracteres de entrada y procesamiento de componentes léxicos se puede mejorar significativamente el rendimiento de un compilador. • Se mejora la portabilidad del compilador. Las peculiaridades del alfabeto de entrada y otras anomalías propias de los dispositivos pueden limitarse al analizador léxico. La representación de símbolos especiales o no estándares, como en Pascal, pueden ser aisladas en el analizador léxico. • Otra razón por la que se separan los dos análisis es para que el analizador léxico se centre en el reconocimiento de componentes básicos complejos. Por ejemplo en FORTRAN, existen el siguiente par de proposiciones : DO 5 I = 2.5 (Asignación de 2.5 a la variable DO5I) DO 5 I = 2,5 (Bucle que se repite para I = 2, 3, 4, 5) En éste lenguaje los espacios en blancos no son significativos fuera de los comentarios y de un cierto tipo de cadenas, de modo que supóngase que todos los espacios en blanco eliminables se suprimen antes de comenzar el análisis léxico. En tal caso, las proposiciones anteriores aparecerían al analizador léxico como DO5I = 2.5 DO5I = 2,5 El analizador léxico no sabe si DO es una palabra reservada o es el prefijo de una variable hasta que llegue a la coma. El analizador ha tenido que mirar más allá de la propia palabra a reconocer haciendo lo que se denomina lookahead (o prebúsqueda).
|
|
|
