Compilador Con Bison y Flex

GENERADOR DEL EJECUTABLE E INSTALACIÓN DE PROGRAMAS

A continuación vamos a explicar como funciona un analizador léxico sintáctico utilizando las herramientas de flex y bison , para empezar tenemos que tener descargados los programas de bison, flex y mingw que los dejo en el ultimo de link de descarga, las instalamos, luego vamos a proceder a configurar nuestras variables de entorno, para eso vamos a: propiedades de equipo>propiedades del sistema>variables de entorno en este cuadro buscamos PATH y ponemos editar y agregamos en la ruta ya dada la direccion de la carpeta bin de cada carpeta de los instaladores: bison, flex y mingw, separándolas con punto y coma; una vez terminado esto damos en aceptar a todo y necesariamente tenemos que reiniciar el sistemas.

Una vez ya hecho esto, nosotros usaremos nuestro analizador léxico en flex y nuestro analizador sintáctico en bison, de la carpeta de instaladores los archivos"lexico.l" que va a ser para flex y "sintactico.y" que va a ser para bison, copiamos estos archivos a la carpeta C:/>GnuWin32>bin; una vez copiada hacia esa carpeta, copiamos la direccion en donde se pegó esos archivos y abrimos el cmd; ya en el cmd escribimos "cd" ponemos espacio seguido pegamos la ruta copiada y le damos enter.


Luego escribimos en el cmd "flex lexico.l" y damos enter para general algunos archivos de flex, lo mismo realizamos para bison, escribimos en el cmd "bison -dy sintactico.y" y le damos enter y generamos algunos archivos de bison .


A continuación, vamos a copiar los archivos "lex.yy" , "y.tab" y el otro "y.tab" de la carpeta bin de la carpeta GnuWin32 y lo pegamos en la carpeta bin de la carpeta MinGW; luego vamos a copiar también el archivo "libfl.a" de la carpeta lib de la carpeta GnuWin32 y lo pegamos en la carpeta lib de la carpeta MinGW; ahora copiamos la dirección de la carpeta bin  de la carpeta MinGW y nos vamos a cmd, en el cmd escribimos "cd" espacio y pegamos la dirección que copiamos y le damos enter.


Ahora vamos a utilizar MinGW para que nos proporcione un ejecutable es decir la ejecución final ya de nuestro compilador, para ello necesitamos la siguiente linea de código "gcc y.tab.c lex.yy.c -lfl -o salida7" aquí están escritos todos los archivos que se nos ejecutaron y que nos proporcionó flex y bison salida7 es el nombre de nuestro ejecutable, copiamos esa linea de código y lo pegamos en el cmd y le damos enter.

 
Ahora podemos observar que se nos generó el ejecutable "salida7".


EXPLICACIÓN DE LA LÓGICA

INTRODUCCIÓN A FLEX

Flex es un una herramienta que permite generar analizadores léxicos. A partir de un conjunto de expresiones regulares, Flex busca concordancias en un fichero de entrada y ejecuta acciones asociadas a estas expresiones. Es compatible casi al 100% con Lex, una herramienta clásica de Unix para la generación de analizadores léxicos, pero es un desarrollo diferente realizado por GNU bajo licencia GPL.

Los ficheros de entrada de Flex (normalmente con la extensión .l) siguen el siguiente esquema:

%%
patrón1 {acción1}
patrón2 {acción2}
 ...

Donde:
patrón: expresión regular
acción: código C con las acciones

Flex lee los ficheros de entrada dados, o la entrada estándar si no se le ha indicado ningún nombre de fichero, con la descripción de un escáner a generar. La descripción se encuentra en forma de parejas de expresiones regulares y código C, denominadas reglas. Flex genera como salida un fichero fuente en C, ‘lex.yy.c’, que define una función ‘yylex()’. Este fichero se compila y se enlaza con la librería de Flex para producir un ejecutable. Cuando se arranca el fichero ejecutable, este analiza su entrada en busca de casos de las expresiones regulares. Siempre que encuentra uno, ejecuta el código C correspondiente.

El fichero de entrada de Flex está compuesto de tres secciones, separadas por una línea donde aparece únicamente un ‘%%’ en esta:

Definiciones
%%
reglas
%%
código de usuario

La sección de definiciones contiene declaraciones de definiciones de nombres sencillas para simplificar la especificación del escáner. Las definiciones de nombre tienen la forma:

nombre definición

El "nombre" es una palabra que comienza con una letra o un subrayado (‘_’) seguido por cero o más letras, dígitos, ‘_’, o ‘-’ (guión). La definición se considera que comienza en el primer carácter que no sea un espacio en blanco siguiendo al nombre y continuando hasta el final de la línea. Posteriormente se puede hacer referencia a la definición utilizando "{nombre}", que se expandirá a "(definición)".

La sección de reglas en la entrada de Flex contiene una serie de reglas de la forma:

patrón acción

Donde el patrón debe estar sin sangrar y la acción debe comenzar en la misma línea.

Finalmente, la sección de código de usuario simplemente se copia a ‘lex.yy.c’ literalmente. Esta sección se utiliza para rutinas de complemento que llaman al escáner o son llamadas por este. La presencia de esta sección es opcional; Si se omite, el segundo ‘%%’ en el fichero de entrada se podría omitir también.

Explicando Nuestro Analizador Léxico En Flex

Código de Usuario:

%{

  #include <stdio.h>

  #include <stdlib.h>

  #include "y.tab.h"

  int linea=0;

%}

Definiciones:

DIGITO [0-9]

LETRA [a-zA-Z]

IDENTIFICADOR {LETRA}({LETRA}|{DIGITO})*

constEntera {DIGITO}({DIGITO})*

/*SIGNO [< <= > >= != ;]*/

Boleano "True"|"False"|"<"|"<="|">"|">="|"!="

Reglas:

%%

"="         {return(IGUAL);}

"+"         {return(MAS);}

"-"         {return(MENOS);}

","         {return(COMA);}

";"         {return(PTOCOMA);}

"*"         {return(POR);}

"/"         {return(DIV);}

"("         {return(PARENTABIER);}

")"         {return(PARENTCERR);}

"Dim"       {return(DIM);}

"As"        {return (AS);}

"Integer"   {return (TIPO);}

"End"       {return(END);}

"Else"      {return(ELSE);}

"If"         {return(IF);}

"Then"      {return(THEN);}

"Select"               {return(SELECT);}

"Case"                  {return(CASE);}

"While"                               {return(WHILE);}

"Do"        {return(DO);}

"Loop"      {return(LOOP);}

"Until"     {return(UNTIL);}

"Next"      {return(NEXT);}

"For"       {return(FOR);}

"Step"      {return(STEP);}

"To"        {return(TO);}

{Boleano}   {return BOLEANO;}

{constEntera} {return (INT);}

{IDENTIFICADOR} {return (ID);}

"\n"        {linea++;}

[\t\r\f] {}

" "                          {}

.            {printf("Error lexico en linea %d",linea);}

%%

INTRODUCCIÓN A BISON

Bison es un generador de analizadores sintácticos de propósito general que convierte una descripción para una gramática independiente del contexto (en realidad de una subclase de éstas, las LALR) en un programa en C que analiza esa gramática. Es compatible al 100% con Yacc, una herramienta clásica de Unix para la generación de analizadores léxicos, pero es un desarrollo diferente realizado por GNU bajo licencia GPL. Todas las gramáticas escritas apropiadamente para Yacc deberían funcionar con Bison sin ningún cambio. Usándolo junto a Flex esta herramienta permite construir compiladores de lenguajes.

Una fuente de Bison (normalmente un fichero con extensión .y) describe una gramática. El ejecutable que se genera indica si un fichero de entrada dado pertenece o no al lenguaje generado por esa gramática. La forma general de una gramática de Bison es la siguiente:

%{
declaraciones en C
%}
Declaraciones de Bison
%%
Reglas gramaticales
%%
Código C adicional

Los ‘%%’, ‘%{‘ y ‘%}’ son signos de puntuación que aparecen en todo archivo de gramática de Bison para separar las secciones.

Las declaraciones en C pueden definir tipos y variables utilizadas en las acciones. Puede también usar comandos del preprocesador para definir macros que se utilicen ahí, y utilizar #include para incluir archivos de cabecera que realicen cualquiera de estas cosas.

Las declaraciones de Bison declaran los nombres de los símbolos terminales y no terminales, y también podrían describir la precedencia de operadores y los tipos de datos de los valores semánticos de varios símbolos.

Las reglas gramaticales son las producciones de la gramática, que además pueden llevar asociadas acciones, código en C, que se ejecutan cuando el analizador encuentra las reglas correspondientes.

El código C adicional puede contener cualquier código C que desee utilizar. A menudo suele ir la definición del analizador léxico yylex, más subrutinas invocadas por las acciones en las reglas gramaticales. En un programa simple, todo el resto del programa puede ir aquí.

SÍMBOLOS, TERMINALES Y NO TERMINALES

Los símbolos terminales de la gramática se denominan en Bison tokens y deben declararse en la sección de definiciones. Por convención se suelen escribir los tokens en mayúsculas y los símbolos no terminales en minúsculas.

Los nombres de los símbolos pueden contener letras, dígitos (no al principio), subrayados y puntos. Los puntos tienen sentido únicamente en no-terminales.

Hay tres maneras de escribir símbolos terminales en la gramática. Aquí se describen las dos más usuales:

• Un token declarado se escribe con un identificador, de la misma manera que un identificador en C. Por convención, debería estar todo en mayúsculas. Cada uno de estos nombres debe definirse con una declaración de %token.

• Un token de carácter se escribe en la gramática utilizando la misma sintaxis usada en C para las constantes de un carácter; por ejemplo, ‘+’ es un tipo de token de carácter. Un tipo de token de carácter no necesita ser declarado a menos que necesite especificar el tipo de datos de su valor semántico, asociatividad, o precedencia. Por convención, un token de carácter se utiliza únicamente para representar un token consistente en ese carácter en particular.

SINTAXIS DE LAS REGLAS GRAMATICALES (PRODUCCIONES)

Una regla gramatical de Bison tiene la siguiente forma general:

resultado: componentes...
 ;

donde resultado es el símbolo no terminal que describe esta regla y componentes son los diversos símbolos terminales y no terminales que están reunidos por esta regla. Por ejemplo,

exp:       exp ‘+’ exp
 ;

dice que dos agrupaciones de tipo exp, con un token ‘+’ en medio, puede combinarse en una agrupación mayor de tipo exp.

Los espacios en blanco en las reglas son significativos únicamente para separar símbolos. Puede añadir tantos espacios en blanco extra como desee.

Distribuidas en medio de los componentes pueden haber acciones que determinan la semántica de la regla. Una acción tiene el siguiente aspecto:

{sentencias en C}

Normalmente hay una única acción que sigue a los componentes.

Se pueden escribir por separado varias reglas para el mismo resultado o pueden unirse con el caracter de barra vertical ‘|’ así:

resultado:           componentes-regla1...
|  componentes-regla2...
 ... ;

Estas aún se consideran reglas distintas incluso cuando se unen de esa manera. Si los componentes en una regla están vacíos, significa que resultado puede concordar con la cadena vacía (en notación formal sería ε). Por ejemplo, aquí aparece cómo definir una secuencia separada por comas de cero o más agrupaciones exp:

expseq:                /* vacío */
| expseq1
 ;

expseq1:             exp
| expseq1 ‘,’ exp
;

Es habitual escribir el comentario ‘/* vacío */’ en cada regla sin componentes.

Una regla se dice recursiva cuando su no-terminal resultado aparezca también en su lado derecho. Casi todas las gramáticas de Bison hacen uso de la recursión, ya que es la única manera de definir una secuencia de cualquier número de cosas. Considere esta definición recursiva de una secuencia de una o más expresiones:

expseq1:             exp
| expseq1 ‘,’ exp
;

Puesto que en el uso recursivo de expseq1 este es el símbolo situado más a la izquierda del lado derecho, llamaremos a esto recursión por la izquierda. Por contraste, aquí se define la misma construcción utilizando recursión por la derecha:

expseq1:             exp
| exp ‘,’ expseq1
;

Cualquier tipo de secuencia se puede definir utilizando ya sea la recursión por la izquierda o recursión por la derecha, pero debería utilizar siempre recursión por la izquierda, porque puede analizar una secuencia de elementos sin ocupar espacio de pila (es decir, de forma mucho más eficiente en memoria). La recursión indirecta o mutua sucede cuando el resultado de la regla no aparece directamente en su lado derecho, pero aparece en las reglas de otros no terminales que aparecen en su lado derecho.

Por ejemplo:

expr:     primario
| primario ‘+’ primario
;

primario:             constante
| ‘(‘ expr ‘)’
 ;

define dos no-terminales recursivos mutuamente, ya que cada uno hace referencia al otro.

Explicando Nuestro Analizador Sintáctico En Bison

Declaraciones en C:

%{

  #include <stdio.h>

  #include <stdlib.h>

  #include <math.h>

  extern int yylex(void);

  extern char *yytext;

  extern int linea;

  extern FILE *yyin;

  void yyerror(char *s);

%}

Declaraciones de Bison:

%token DIM AS TIPO COMA MAS MENOS IGUAL PTOCOMA POR DIV PARENTABIER PARENTCERR MAYOR MAYORI MENOR MENORI ID INT END ELSE IF BOLEANO THEN SELECT CASE WHILE

%token DO LOOP UNTIL NEXT FOR STEP TO

%union

{

  float real;

}

%start Expresiones;

Reglas Gramaticales:

%%

/*Expresion general*/

Expresiones: Expresiones Expresion | Expresion | Expresiones Ex | Ex | Expresiones Ex2 | Ex2 | Expresiones Ex3 | Ex3 | Expresiones Ex4 | Ex4 | Expresiones Ex5 | Ex5

                ;

/*gramatica que me reconoce declaracion de variables : "Dim a,b As Integer" */

Expresion  : DIM ListDec

                ;

ListDec    : Dec ListDec | Dec

                                                               ;

Dec        : ID ListId

                                                               ;

ListId        : AS TIPO | COMA ID ListId  

                                                               ;

/*gramatica para sentencias If a>b Then sentencia Else sentencia End If */

Ex          : Ife END IF | Ife ELSE ID END IF

                                                               ;

Ife              : IF Condicion THEN ID

                                                               ;

Condicion   : ID BOLEANO ID | ID BOLEANO INT

                                                               ;

/* Instrucciones Select...Case */

Ex2                                        : SELECT CASE ID CaseStatement CaseElseStatement END SELECT

                ;

CaseStatement : Caso | CaseStatement Caso

                                                               ;

Caso                      : CASE TipoId ID

                                                               ;

TipoId                   : ID | INT

                                                               ;

CaseElseStatement : CASE ELSE ID

                                                               ;

/* Instrucciones While...End While */

Ex3                                        : WHILE Condi

                                                 ID

                                                 END WHILE

                                                 ;

Condi                                     : ID BOLEANO ID | ID BOLEANO INT

                                                 ;  


              

/* Instrucciones Do...Loop */

Ex4                      : DO Opcion

                                                   ;

Opcion                 : Decla ID LOOP | ID LOOP Decla

                                                               ;

Decla                    : WhileOrUntil Cond

                                                               ;

Cond                    : ID BOLEANO ID | ID BOLEANO INT

                                                               ;

WhileOrUntil: WHILE | UNTIL

                                                               ;

/* For...Next (Instrucciones) */

Ex5                                        : FOR LoopControlVariable IGUAL INT TO INT STEP INT

                                                ID

                                                NEXT

                                                   ;

LoopControlVariable : ID AS TIPO | ID  

                                                               ;

%%

Código 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();

  system("Pause");

  return 0;

}



EJEMPLO
Aquí se muestra cuando una declaración esta correctamente escrita.

y cuando no esta correctamente escrita se mostrara asi:

ANALIZADOR SEMÁNTICO

Se empezará elaborando una tabla con los tokens definidos en nuestro analizador Lexico con ayuda del java. En el cual elaboraremos el siguiente formulario general:

En nuestro proyecto GUICOMPILADOR haremos uso de la tabla de token para evaluar la ejecución de nuestro ejecutable.exe mediante la interfaz de Java.

1.  Crearemos el formulario abrir que servirá para entrar al archivo que deseamos evaluar.

2. Crear un formulario GUICompiladorC con el cual se accederá al proyecto ejecutable.exe que en nuestro caso es salida7.exe para poder trabajar con nuestro analizador creado con flex y bison.

3. Se hará uso de un formulario “nuevo” en el caso de crear un archivo distinto a los anteriores si se desea ingresar nuevas cadenas.

4.Si se desea ver los token definidos en nuestro analizador léxico se hará uso del formulario VerTokens.

5.Se creó clase tokens en el cual creamos 2 arreglos uno del tipo String y otro del tipo entero:

·   public static String yytname[]  el cual almacenara los nombres de los terminales definidos en nuestro analizador léxico-sintactico.

·     public static int yytoknum[] el cual tendrá los números asignados para cada token.

No olvidar que estos nombres de terminales y los números correspondientes se pueden encontrar en el archivo y.tab

Abrirlo con un bloc de notas o con c++ e ir a la siguiente sección:

LINK:
DESCARGAR ARCHIVOS