Juntado los archivos de FLEX y BISON

Pasos a seguir

1. Compilamos bison
        >  bison -v -d bison.y
2. Compilamos fo1.flex (debemos de añadir el fichero de "bison.tab.h" al fichero de fo.flex , descargar fichero fo1.flex )
        >  flex fo1.flex
3. Compilamos el fichero lex.yy.c que requiere de bison,tab.c
       >  gcc bison.tab.c lex.yy.c -lfl -o salida.out
4. Por fin ejecutamos el parse que reconoce a nuestro lenguaje
       > ./salida.out

Dejo unas ficheros con alguna de las instrucciones del lenguaje, reconocidas por el parse.
       if_else
       mietras_

Posible Makefile (no esta probado)

        bison:  bison.y
           bison -v -d bison.y
        flex:    fo1.flex
           flex fo1.flex
        all:    bison flex lex.yy.c
           gcc bison.tab.c lex.yy.c -lfl -o salida.out
        clean:   lex.yy.c output.out Proalg.output Proalg.tab.c Proalg.tab.h
           rm Proalg.tab.c
           rm Proalg.tab.h
           rm lex.yy.c
           rm output.out
           rm Proalg.output

Implementación En Bison.

PRECEDENCIA
La precedencia de una regla , esta determina por la precedencia  del terminal mas a derecha de dicha regla.
La precedencia de los terminales , esta determina por el orden en que se declararon , el primer terminal declarado es el de mayor precedencia y así sucesivamente.
Entendiendo estos conceptos es suficiente para nuestro propósito.Podemos jugar el orden de declaración de los terminales para favorecer un shift o un reduce
    Ejemplo
        Reglas :
               1 ) exp_a -> exp_a + exp_a
               2 ) exp_a -> exp_a * exp_a
        Entrada t : = x + t *p
        En algún momento y tras varias reducciones ,nos encontraremos en esta situación :
                      exp_a + exp_a .*  p
        En este punto el parse puede reducir(incorrecto) por la regla 1 o seguir leyendo (correcto) he intentar
        alcanzar la regla 2 .
        La precedencia de la regla 1 , es la de su terminal más a la derecha "+" ,mientras que la precedencia de         la regla 2 esta determinada por la precedencia del terminal "*".
        En esta situación , debemos continuar leyendo ya que la multiplicación debe de realizar antes que la
        suma.En la sección de "declaraciones de token" de nuestro fichero "fichero.y" , la declaración del token
        "*" debe de preceder a la declaración del token   "+".
        Incorrecto :
           ....
          %token  SUMA
          %token  MULTIPLICACION
           ....
        %%
   
        Solución :
           ....
          %token  MULTIPLICACION
          %token  SUMA
           ....
        %%  
      El archivo de bison lo puede descargar aqui

Gramatica Libre de Contexto

Nota : Toda programa ha de empezar con un comentario.Las variables que se van a utilizar
  han de declararse al inicio del programa.Solo trabajamos con variables , no existen
  constantes.

La grámatica

Axioma : I
Variable : {I,S,L,declaracion_var,lista_d_var,lista_id,tipo_base,asig,operando,exp_a,exp_b}
Tokens :{ comentario,inicion fin,si,entonces,fsi,en_caso_contrare,mientras,hacer,fmientras,var,
                fvar,entero,real,booleano,caracter,string,identificador,y,o,no,parentesis_abierto,
               parantesis_cerrado,operador_rel,+,*,/}

Todo debe ir entre los tokens INICIO y FIN , que hacen referencia a las palabras inicio
y fin respectivamente. Los saltos condicionales , su condicion es una expresion booleana.

I -> COMENTARIO INICIO declaracion_var L FIN
S -> SI exp_b ENTONCES S FSI
S -> SI exp_b ENTONCES S EN_CASO_CONTRAREO S FSI
S -> MIENTRAS exp_b HACER S FMIENTRAS
S -> asig
S -> exp_b
L -> L S
L -> S

Declaración de Tipos

Acotamos la declaracion de tipos a entero,caracter,real,string,booleano
Esquema
tipo_base -> ENTERO | CARACTER | REAL | STRING | BOOLEANO

Declaración de Variables

Las variables de declaran indicante el tipo y a continuacion el identificado o identificadores.
Esquema :
declaracion_var -> VAR lista_d_var FVAR
lista_d_var -> tipo_base lista_id  lista_d_var | /*epsilon*/
lista_id -> IDENTIFICADOR , lista_id | IDENTIFICADOR

Asignación

La asignación ,solo de expresiones aritméticas sencillas.
Esquema :
asig  -> operando := exp_a

Expresiones 

El lenguaje trabaja con expresiones aritmeticas y logicas sencillas .Los operandos han de ser variables.

Esquema expresiones aritméticas :
operando -> IDENTIFICADOR
exp_a -> exp_a + exp_a
exp_a -> exp_a * exp_a
exp_a -> - exp_a
exp_a -> (exp_a)
exp_a -> operando

Esquema expresiones lógicas :
exp_b -> exp_b Y exp_b
exp_b -> exp_b O exp_b
exp_b -> NO exp_b
exp_b -> (exp_b )
exp_b -> exp_a OPERADOR_REL exp_a

Implementación en FLEX

Para obtener los tokens que posteriormente seran utilizados por Bison vamos a utilizar FLEX.
Formato del archivo fo.flex

         declaracion        -->        token+expresiones_regulares
         %%                            %%
         reglas             -->        token+accion
         %%                            %%
         funciones          -->        main

En la sección de "reglas" tenemos que tener mucho cuidado en la declaración de las reglas.Flex va leyendo nuestro programa y cuando encuentra un entrada que concuerda con una o más reglas declaras, elige la primera regla que se declaró en la sección de reglas de FLEX.
Ejemplo :

IDENTIFICADOR {LETRA}({LETRA_O_DIGITO})*
ENTERO [eE][nN][tT][Ee][Rr][Oo]
%%
{IDENTIFICADOR} {printf( "( id : %s, )\n", yytext );}
{ASIGNACION} {printf( "( asig : %s, )\n", yytext );}
{ENTERO} {printf( "(tipo_basico : %s, )\n", yytext );}

Introducimos por linea de comando tras ejecutar el archivo "fo.flex".
> ENTERO

Flex encuentras que tanto la primera como la tercera, son validas .Pero expande la primera regla ya que esta declara antes que la tercera.
"ENTERO" es una palabra reservada por lo que no puede ser reconocida como un identificador.

Solución : intercambiar regla 3ª por la 1ª

IDENTIFICADOR {LETRA}({LETRA_O_DIGITO})*
ENTERO [eE][nN][tT][Ee][Rr][Oo]
%%
{ENTERO} {printf( "(%s, )\n", yytext );}
{IDENTIFICADOR} {printf( "(%s, )\n", yytext );}
{ASIGNACION} {printf( "(%s, )\n", yytext );}

Por ultimo , declarar los tokens y  reglas al comienzo de cada linea , no dejar ningún espacio en blanco anterior a su declaración. 

Compilación y Ejecución (fo.flex)
   > flex fo.flex
   > gcc lex.yy.c -lfl
   > /a.out

Descargar el fichero de ejemplo de flex .Pincha aqui

Tokens

Vamos a inventarnos un lenguaje de programación muy simple , que nos va a permitir declarar variables de tipo básicos como enteros , reales , booleanos , caracteres.Asi como la definición de instrucciones básicas de control de flujo si/si_no y mientras que darán lugar al código intermedio

Un ejemplo del lenguaje
            {esto es una prueba}

            INICIO  

                var entero x,z,p fvar

                si x  >  z  entonces
                    x := x +p

                [ ]
                    z := z +p

                fsi

            FiN

El código intermedio se genera en tiempo de compilación por lo que desconocemos el valor que tomaran las variables que no sean constantes,por ese motivo no declararemos un token literal_entero que identificara una constante entera.

LOS TOKENS

IDENTIFICADOR

Son los nombres de variables.

Los nombre de las variables han de empezar por una letra mayúscula o miniscula seguido de un número indefinido de letras o digitos

digito -> [0-9]

letra -> [aA-zZ]

letra_o_digito -> letra|digito

identificador  -> letra letra_o_digito*

               

PALABRAS RESERVADAS

Son las palabras entero,real,booleano,string,char,si,entonces,fsi,mientras fmientras,hacer
,y,o,no,var,fvar,inicio,fin,para,fpara.

Nota tanto ENTERO,eNtero o algunas del resto de las combinaciones deben de considerarse como la palabra reservada “entero” ,igual pasa con el resto de palabras reservadas.

OTROS TOKENS

                ()  parentesis
                [ ]  en_caso_contrareo
                "," separador

                “ : “ definición del tipo de variable

                “:=” asignación

                “+,-,*,/” operadores operaciones matemáticas básicas

                “>,<,>=,<=,==” operadores relacionales

COMENTARIOS
   Aparecen al principio del programa, van entre conchetes.Ejemplo {codigo de /}prueba } . Si se quiere meter otro corchete dentro del comentario a de estar precedido por "/".

Objetivos

La generación de código intermedio,partiendo de una gramática libre de contexto.Para ello, utilizaremos una de las representación más sencillas ,"Codigo de tres direcciones mediante cuadruplas".

Índice

• Objetivos
• Tokens

            -Implemtación en FLEX

• Especificación de la Gramática libre de contexto 

            -Implemtación en Bison

• Tabla de simbolos

            -Implemtación de la tabla de simbolos

• Generación de Código Intermedio

             -Asignaciones

             -Expresiones Booleanas
             -Instrucciones de control de flujo (if -else , while)

(Sus comentarios son necesarios y me ayudaran a seguir publicando más entradas.GRACIAS)