• Author / Uploaded
• Cristian Proaño Estévez

Citation preview

PONTIFICIA UIVERSIDAD CATÓLICA DEL ECUADOR SEDE IBARRA

1. DATOS INFORMATIVOS 1.1 Nombre: Cristian Proaño 1.2 Carrera: Sistemas 1.3 Nivel: 7mo 1.4 Tema: Trabajo de Compiladores 1.5 Fecha: 08-07-2015

2. DESARROLLO Herramientas para la construcción de procesadores de lenguaje A continuación se muestran algunas de las herramientas disponibles que pueden utilizarse para la realización de la Práctica de Procesadores de Lenguajes. Estas herramientas funcionan bajo Windows, aunque se puede utilizar, si se desea, cualquier otra herramienta.

Aplicación de los lenguajes Los lenguajes de programación hoy en día tienen una infinidad de aplicaciones, básicamente cualquier objeto electrónico tiene cierto grado de programación. Algunos de los más comunes son C++ y JAVA, también existe HTML, HTTP, XML, XAML y C#, este último actualmente es el más utilizado en todos los dispositivos y redes basados en MICROSOFT (Xbox 350, Windows Mobile, Windows Phone, Windows Cloud, Zune, etc.). Ya que los lenguajes de programación son informáticamente un puente entre el Hardware y el Software estos permiten que las computadoras puedan establecer conexión con un celular, una cámara o una consola portátil de videojuego. Otra de las aplicaciones de los lenguajes de programación son las matemáticas como las calculadoras, cajas registradoras, cajeros automáticos, por solo mencionar algunos ejemplos sencillos.

Reseña Histórica Los primeros lenguajes de programación surgieron de la idea de Charles Babagge, la cual se le ocurrió a este hombre a mediados del siglo XIX. Era un profesor matemático de la universidad de Cambridge e inventor inglés, que al principio del siglo XIX predijo muchas de las teorías en que se basan los actuales ordenadores. Consistía en lo que él denominaba la maquina analítica, pero que por motivos técnicos no pudo construirse hasta mediados del siglo XX. Con él colaboro Ada Lovedby, la cual es considerada como la primera programadora de la historia, pues realizo programas para aquélla supuesta máquina de Babagge, en tarjetas perforadas. Como la maquina no llego nunca a construirse, los programas de Ada, lógicamente, tampoco llegaron a ejecutarse, pero si suponen un punto de partida de la programación, sobre todo si observamos que en cuanto se empezó a programar, los programadores utilizaron las técnicas diseñadas por Charles Babagge, y Ada, que consistían entre otras, en la programación mediante tarjetas perforadas. A pesar de ello, Ada ha permanecido como la primera programadora de la historia. Se dice por tanto que estos dos genios de antaño, se adelantaron un siglo a su época, lo cual describe la inteligencia de la que se hallaban dotados. En 1823 el gobierno Británico lo apoyo para crear el proyecto de una máquina de diferencias, un dispositivo mecánico para efectuar sumas repetidas. Pero Babagge se dedicó al proyecto de la máquina analítica, abandonando la máquina de diferencias, que se pudiera programar con tarjetas perforadas, gracias a la creación de Charles Jacquard (francés). Este hombre era un fabricante de tejidos y había creado un telar que podía reproducir automáticamente patrones de tejidos, leyendo la información codificada en patrones de agujeros perforados en tarjetas de papel rígido. Entonces Babagge intento crear la máquina que se pudiera programar con tarjetas perforadas para efectuar cualquier cálculo con una precisión de 20 dígitos. Pero la tecnología de la época no bastaba para

hacer realidad sus ideas. Si bien las ideas de Babagge no llegaron a materializarse de forma definitiva, su contribución es decisiva, ya que los ordenadores actuales responden a un esquema análogo al de la máquina analítica. En su diseño, la máquina constaba de cinco unidades básicas: 1) Unidad de entrada, para introducir datos e instrucciones; 2) Memoria, donde se almacenaban datos y resultados intermedios; 3) Unidad de control, para regular la secuencia de ejecución de las operaciones; 4) Unidad Aritmético-Lógica, que efectúa las operaciones; 5) Unidad de salida, encargada de comunicar al exterior los resultados. Charles Babbage, conocido como el "padre de la informática" no pudo completar en aquella época la construcción del computador que había soñado, dado que faltaba algo fundamental: la electrónica. El camino señalado de Babbage, no fue nunca abandonado y siguiéndolo, se construyeron los primeros computadores. Cuando surgió el primer ordenador, el famoso ENIAC (Electronic Numerical Integrator And Calculator), su programación se basaba en componentes físicos, o sea, que se programaba, cambiando directamente el Hardware de la máquina, exactamente lo que sé hacia era cambiar cables de sitio para conseguir así la programación de la máquina. La entrada y salida de datos se realizaba mediante tarjetas perforadas.

Diseño y construcción de un compilador En el proceso de construcción de compiladores se integran muchos conceptos diferentes de las Ciencias de la Computación:    

Algoritmos de búsqueda. Árboles, Hashing. Programación modular. Lenguaje Assembly.

Análisis: Se trata de la comprobación de la corrección del programa fuente, e incluye las fases correspondientes al Análisis léxico (que consiste en la descomposición del programa fuente en componentes léxicos), Análisis sintáctico (agrupación de los componentes léxicos en frases gramaticales) y Análisis

 

semántico (comprobación de la validez semántica de las sentencias aceptadas en la fase de Análisis Sintáctico). Síntesis: Su objetivo es la generación de la salida expresada en el lenguaje objeto y suele estar formado por una o varias combinaciones de fases de Generación de Código (normalmente se trata de código intermedio o de código objeto) y de Optimización de Código (en las que se busca obtener un código lo más eficiente posible).

Que es Flex y Bison Son dos herramientas útiles para crear programas que reaccionen a una entrada de datos con una estructura y un lenguaje predeterminado, como por ejemplo, podemos crear compiladores, intérpretes y analizadores de línea de comando. Flex: El Flex define las reglas de reconocimiento de símbolos (Tokens) a partir de expresiones regulares. Cuando un Token es reconocido por uno de estos patrones de agrupamiento se le define una acción, por lo general esta acción es devolver el Tipo y el valor (lexema). El Flex cuando se utiliza combinado con el Bison, utiliza las definiciones de los Tokens realizadas en el Bison para la comunicación entre ellos, Bison: GNU bison es un programa generador de analizadores sintácticos de propósito general perteneciente al proyecto GNU disponible para prácticamente todos los sistemas operativos, se usa normalmente acompañado de flex aunque los analizadores léxicos se pueden también obtener de otras formas. Bison convierte la descripción formal de un lenguaje, escrita como una gramática libre de contexto LALR, en un programa en C, C++, o Java que realiza análisis sintáctico. Es utilizado para crear analizadores para muchos lenguajes, desde simples calculadoras hasta lenguajes complejos. Para utilizar Bison, es necesaria experiencia con la sintaxis usada para describir gramáticas.

Como se instala Flex y Bison 1. Descarga el software disponible en el sitio de la cátedra. 2. Instalar el software en la unidad C: (para explicar a partir del punto 4 se tendrá como hipótesis de que flex y bison han sido instalados en la ruta: C:\GnuWin32\ donde contiene una subcarpeta llamada bin donde se encuentran los programas respectivos) 3. Flex y bison son aplicaciones de consola, por lo que se deberá entrar al Símbolo del sistema y tipear líneas de comando para ejecutar Flex. Una alternativa es crear un archivo de proceso por lotes (*.bat) que contenga las líneas de comando para la ejecución de Flex y Bison y/o la compilación del archivo generado.

4. Si deseas que flex y bison se integren al conjunto de variables del entorno (esto te va a permitir llamar a flex/bison desde cualquier ubicación en la línea de comandos) debes hacer lo siguiente:  Clic derecho en “Mi PC”.  Selecciona “Propiedades”  Clic en la pestaña “Opciones Avanzadas”  Presiona el botón “Variables de entorno”  En la ventana de variables de entorno, ubicarse en la sección “Variables del sistema” luego haz clic en PATH y luego en el botón “Modificar” (si no está hacer clic en “Nueva” y agregar PATH) • En la nueva ventana, escribir la ruta completa al directorio “bin” de la aplicación flex/bison. Si existe otro valor, separarlos con comas.  Aceptar los cambios y luego reiniciar el sistema operativo.

5. Si deseas instalar un compilador de C como MinGwin, deberás integrar la ruta de acceso al compilador a las variables de entorno para facilitar la llamada al programa. Por ejemplo si se instaló MingWin en “C:\Mingw” y dentro de la carpeta “bin” se encuentra “gcc.exe” que es el ejecutable, entonces de deberá agregar (análogo a los pasos anteriores) lo siguiente: 6. Cuando tengas listo podrás llamar a flex/bison desde el símbolo del sistema sin necesidad de ubicarte en la carpeta donde ha sido instalado flex/bison.

Como se compila con Flex y Bison Luego de escribir las especificaciones de flex y bison realizar lo siguiente. Si se desea invocar a flex:

Si se desea invocar a bison (recordar que bison trabaja en conjunto con flex):

Para invocar a Bison en conjunción con flex realizar lo siguiente:

Para compilar los archivos generados. Flex: MinGW

Una alternativa es utilizar un compilador para windows como DevC++ o Borland C++ 4.5 Abriendo el archivo lex.yy.c y luego compilándolo se generará el ejecutable “lex.yy.exe” BISON y FLEX en conjunción:

Ejemplos de la creación de un compilador utilizando Flex y Bison Vamos a realizar un ejemplo de una calculadora sencilla que reconocerá las principales operaciones aritmética (+,-,* y /). Abrimos un editor de texto y pegamos el siguiente código que será nuestro scanner /***************** Definiciones Se colocan las cabeceras, variables y expresiones regulares ********************/ %{ #include #include #include "sintactico.tab.h" int linea=0; %} /* Creamos todas las expresiones regulares Creamos la definición llamada DIGITO, podemos acceder esta definición usando {DIGITO}*/ DIGITO [0-9] NUMERO {DIGITO}+("."{DIGITO}+)?

%% /*************** Reglas *****************/ /* Creamos las reglas que reconocerán las cadenas que acepte Nuestro scanner y retornaremos el token a bison con la funcion return. */ {NUMERO} {yylval.real=atof(yytext); return(NUMERO);} "=" {return(IGUAL);} "+" {return(MAS);} "-" {return(MENOS);} ";" {return(PTOCOMA);} "*" {return(POR);} "/" {return(DIV);} "(" {return(PAA);} ")" {return(PAC);} "\n" {linea++;} [\t\r\f] {} "" {}

/* Si en nuestra entrada tiene algún caracter que no pertenece a las reglas anteriores, se genera un error léxico */ . {printf("Error lexico en linea %d",linea);} %% /* Código de Usuario Aquí podemos realizar otras funciones, como por ejemplo ingresar símbolos a nuestra tabal de símbolos o cualquier otra accione del usuario. Todo lo que el usuario coloque en esta sección se copiara al archvi lex.yy.c tal y como esta. */

Guardamos el archivo como lexico.l. Luego creamos un nuevo archivo y colocamos el siguiente código.

%{ /******************** Declaraciones en C **********************/ #include #include #include extern int yylex(void); extern char *yytext; extern int linea; extern FILE *yyin; void yyerror(char *s); %} /************************ Declaraciones de Bison *************************/ /* Especifica la coleccion completa de tipos de datos para poder usar varios tipos de datos en los terminales y no terminales*/ %union { float real; } /* Indica la produccion con la que inicia nuestra gramatica*/ %start Exp_l /* Especificacion de termines, podemos especificar tambien su tipo */

%token NUMERO %token MAS %token MENOS %token IGUAL %token PTOCOMA %token POR %token DIV %token PAA %token PAC /* No Terminales, que tambien podemos especificar su tipo */ %type Exp %type Calc %type Exp_l /* Definimos las precedencias de menor a mayor */ %left MAS MENOS %left POR DIV %% /********************** Reglas Gramaticales ***********************/

Exp_l:

Exp_l Calc |Calc ; Calc : Exp PTOCOMA {printf ("%4.1f\n",$1)} ; /* Con el símbolo de $$ asignamos el valor semántico de toda la acción de la derecha y se la asignamos al no terminal de la izquierda, en la siguiente regla, se la asigna a Exp. Para poder acceder al valor de los terminales y no terminales del lado derecho usamos el símbolo $ y le concatenamos un número que representa la posición en la que se encuentra es decir si tenemos A --> B NUMERO C Si queremos usar le valor que tiene el no terminal B usamos $1, si queremos Usar el valor que tiene NUMERO usamos $2 y así sucesivamente.

*/ Exp :

%%

NUMERO {$$=$1;} |Exp MAS Exp {$$=$1+$3;} |Exp MENOS Exp {$$=$1-$3;} |Exp POR Exp {$$=$1*$3;} |Exp DIV Exp {$$=$1/$3;} |PAA Exp PAC {$$=$2;} ;

/******************** Codigo C Adicional **********************/ void yyerror(char *s) { printf("Error sintactico %s",s); } int main(int argc,char **argv) { if (argc>1) yyin=fopen(argv[1],"rt"); else yyin=stdin; yyparse(); return 0; } Guardamos este archivo con el nombre sintáctico.y y con eso ya tenemos nuestro scanner y nuestro parser terminado. Para compilar estos archivos usamos los comandos Compilando sintactico.y ~> bison -d sintactico.y El parámetro –d, crea el fichero t.tab.h, que contiene los identificadores de los tokens de bison usados por flex Compilando lexico.l ~> flex lexico.l Compilando arhivos generados y crear ejecutable ~> cc lex.yy.c sintactico.tab.c -o analizador -lfl -lm Esto nos genera un ejecutable llamado analizador. Muchas veces necesitamos modificar nuestro archivo sintáctico.y o lexico.l y tenemos que compilar todo cada vez que hacemos un cambio, para no estar escribiendo los comandos cada vez que realizamos un cambio, crearemos un script, que al ejecutarlo realizara todos los comandos de compilación. Para eso creamos un nuevo archivo en blanco y escribimos

#!/bin/bash bison -d sintactico.y flex lexico.l cc lex.yy.c sintactico.tab.c -o analizador -lfl –lm

Guardamos este archivo con cualquier nombre, por ejemplo compilar.sh. Ahora cambiaremos las propiedades de este archivo para poder ejecutar. Le damos clic derecho sobre este archivo y en la pestaña permisos elegimos la opción de “Permitir ejecutar el archivo como un programa”, cerramos esa ventana.

Para poder compilar, desde consola nos ubicamos donde se encuentra este archivo .sh y escribimos ./compilar.sh Esto nos genera nuestro ejecutable que podemos correr para poder probar nuestra calculadora. Para ejecutar este ejemplo usamos el comando ./analizador Ingresamos algunas expresiones y el resultado que obtenemos es:

EJEMPLO 2

Archivo para FLEX ? 1 %{ #include 2 #include 3 #include "parser.h" 4 %} 5 %option noyywrap 6 %option yylineno 7 letra [a-zA-Z] [0-9] 8 digito binario [0-1] 9 ignora " "|\t|\n 10operarit *|+|-|/ 11operlog &|$ 12comparador |=|==|!= %% 13{ignora}+ {;} 14"Entero" {printf("Palabra reservada para tipo de dato 15entero\n");return PRENTERO;} 16"Real" {printf("Palabra reservada para tipo de dato 17real\n");return PRREAL;} 18"Booleano" {printf("Palabra reservada para tipo de dato 19booleano\n");return PRBOOLEANO;} {printf("Palabra reservada para tipo de dato 20"Caracter" caracter\n");return PRCARACTER;} 21 {printf("Palabra reservada para 22"Si" condicional\n");return PRSI;} 23 {printf("Palabra reservada para otro 24"Sino" condicional\n");return PRSINO;} 25 "SinoSi" {printf("Palabra reservada para definir 26condicionales secundarias\n");return PRSINOSI;} 27"Entonces" {printf("Palabra reservada para definir accion a 28realizar\n");return PRENTONCES;} 29"FinSi" {printf("Palabra reservada finalizar 30condicional\n");return PRFINSI;} 31"Para" {printf("Palabra reservada para bucle de tipo 32Para\n");return PRPARA;} {printf("Palabra reservada para fin de bucle de 33"FinPara" tipo Para\n");return PRFINPARA;} 34 "Mientras" {printf("Palabra reservada para bucle de tipo 35 Mientras\n");return PRMIENTRAS;} 36 {printf("Palabra reservada para indicar que se 37"Hacer" empieza algo\n");return PRHACER;} 38"FinMientras" {printf("Palabra reservada fin de bucle de tipo 39Mientras\n");return PRFINMIENTRAS;} 40"FinHacerMientras" {printf("Palabra reservada para indicar fin 41de bucle Hacer-Mientras\n");return PRFINHACERMIENTRAS;} 42"Funcion" {printf("Palabra reservada para declaracion de 43funciones\n");return PRFUNCION;} {printf("Palabra reservada para declaracion de 44"Estructura" estructuras\n");return PRESTRUCTURA;} 45

46"FinFuncion" {printf("Palabra reservada para finalizar 47funcion\n");return PRFINFUNCION;} {printf("Palabra reservada para retorno de 48"Retorna" funcion\n");return PRRETORNA;} 49 {printf("Palabra reservada para funcion sin valor 50"SinValor" de retorno\n");return PRSINVALOR;} 51 {printf("Palabra reservada para definir 52"Definir" funciones\n");return PRDEFINIR;} 53 "Constante" {printf("Palabra reservada para definir 54constantes\n");return PRCONSTANTE;} 55"Entrada" {printf("Palabra reservada para definir 56entradas\n");return PRENTRADA;} 57"Salida" {printf("Palabra reservada para definir 58salidas\n");return PRSALIDA;} {printf("Identificador\n");return 59{letra}({letra}|{digito})* IDENT;} 60 {letra}+ {printf("Caracter\n");return CARACTER;} 61{binario}+ {printf("Binario\n");return BOOLEANO;} 62{digito}+ {printf("Entero\n");return ENTERO;} {digito}+"."{digito}+ {printf("Real\n");return REAL;} 63 {comparador} {printf("Comparador\n");return 64 COMPARADOR;} 65 ":=" {printf("Asignador\n");return ASIG;} 66 {printf("Fin sentencia\n");return PCOMA;} 67";" "!=" {printf("Diferente\n");return DIF;} 68 {printf("Coma\n");return COMA;} 69"," {printf("Igual\n");return IGUAL;} 70"==" "." {printf("Punto\n");return PTO;} 71 {printf("Signo mayor-igual\n");return MAIGU;} 72">=" "\n");return MAYOR;} 76">" "