Enlazando la entrada de Bison con Flex (muy básico) forGeeks

Como me falta mucho mucho mucho mucho mucho mucho estudio (mucho) para usar Bison y Flex a la perfección, pues solamente pondré lo que yo he comprendido, ejemplificandolo con la práctica que nos puso el profesor (un indentador).

Primero, usando Bison. Antes que nada, deberían de dar un "man bison" o "info bison" para checar las especificaciones de la herramienta.

Como deberíamos saber (para el que no lo sepa: RTFM), la estructura de una gramática para YACC/BISON, es:

/*----------------------------------------------------------------------------------------------------------------*/
%{
/*declaraciones en C*/
%}
/*Definiciones de Bison*/
%%
/*Gramática*/
%%
/*Código auxiliar en C*/
/*----------------------------------------------------------------------------------------------------------------*/

Ahora, modelemos la gramática para el lenguaje que genera expresiones de la forma:

hola{mundo{cruel}}
hola{}
.
.
.

La gramática a la que llegamos fué:

S-> IS
S-> {S}
S-> I
I-> cadena
I-> epsilon

Codificamos esa gramática para Bison:

S: I S {printf("Regla 1");}
| CORI S CORD {printf("Regla 2");}
| I {printf("Regla 3");}
;

I: CADENA {printf("Regla 4");}
| /*vacio*/ {printf("Regla 5");}
;

Aquí, los printf se ejecutarán cada vez que el analizador sintáctico compruebe que se está utilizando esa producción. El archivo quedaría hasta el momento:

/*----------------------------------------------------------------------------------------------------------------*/

/*indentador.y*/

%{
#include<'stdio.h>
%}
%token CADENA CORI CORD /*CORI = '{' CORD='}'*/
%start S /*Le decimos a bison cual es nuestro simbolo inicial*/
%%
S: I S {printf("Regla 1");}
| CORI S CORD {printf("Regla 2");}
| I {printf("Regla 3");}
;

I: CADENA {printf("Regla 4");}
| /*vacio*/ {printf("Regla 5");}
;
%%
main(){
yyparse(); /*ejecuta el analizador sintáctico*/
}

/*----------------------------------------------------------------------------------------------------------------*/

Bueno, si recordamos, podemos accesar a los valores semánticos de Bison con pseudo variables. Digamos que en la regla I: CADENA quisieramos saber el valor de CADENA. Como CADENA está en la posición 1, podemos decir que cadena es la variable $1. Entonces, pudieramos hacer:

I: CADENA {printf("Se esta recibiendo la cadena: %s",$1);}
/*{$$=$1} asignaría a I el valor de CADENA*/

Lo que nos tendría que regresar el valor semánticode cadena. El problema con esto, es que las pseudo variables están declaradas como entero, es decir, espera que CADENA tenga un valo entero (y nosotros estamos pidiendole que imprima un tipo char*). Tambien esperaríamos que CORI(D) sea un caracter. Para definir el tipo que recibirán CADENA y CORI(D), declaramos una %union.

%union{
char caracter;
char *cadena;
}

y le decimos en las definiciones que tipo de valor deben tener los símbolos no terminales:

%token <'caracter> CORI CORD
%token <'cadena> CADENA

y los símbolos terminales de los cuales pretendamos saber el valor semántico:

%type <'cadena> S
%type <'cadena> I

con lo que la gramática quedaría:

/*----------------------------------------------------------------------------------------------------------------*/

/*indentador.y*/

%{
#include <'stdio.h>
%}

%union{
char caracter;
char *cadena;
}

%token <'caracter> CORI CORD
%token <'cadena> CADENA
%type <'cadena> S
%type <'cadena> I
%start S
%%
S: I S {printf("Regla 1");}
| CORI S CORD {printf("Regla 2");}
| I {printf("Regla 3");}
;

I: CADENA {printf("Regla 4 nos da la cadena: %s",$1);}
| /*vacio*/ {printf("Regla 5");}
;
%%
main(){
yyparse(); /*ejecuta el analizador sintáctico*/
}

/*----------------------------------------------------------------------------------------------------------------*/

Finalmente, un problema con la gramática. Como la entrada desde el teclado, recibirá cadenas que terminan con el fin de linea (\n), entonces necesitamos poner una regla de producción que contemple el fin de linea como parte del lenguaje. Declararemos NL como un símbolo terminal (\n) y añadiremos la siguiente producción:

INICIO: INICIO NL S
| S
;

Así, la gramática final sería:

/*----------------------------------------------------------------------------------------------------------------*/

/*indentador.y*/

%{
#include ...<'stdio.h>
%}

%union{
char caracter;
char *cadena;
}

%token <'caracter> CORI CORD NL
%token <'cadena> CADENA
%type <'cadena> S
%type <'cadena> I
%start INICIO
%%
INICIO: INICIO NL S {printf("Regla con NL");}
| S {printf("Regla sin NL");}
;
S: I S {printf("Regla 1");}
| CORI S CORD {printf("Regla 2");}
| I {printf("Regla 3");}
;

I: CADENA {printf("Regla 4 nos da la cadena: %s",$1);}
| /*vacio*/ {printf("Regla 5");}
;
%%
main(){
yyparse(); /*ejecuta el analizador sintáctico*/
}

/*----------------------------------------------------------------------------------------------------------------*/

Ahora, la entrada con Flex. Ya saben, "man flex" o "info flex".

La estructura de un archivo para crear analizadores léxicos, es esta:

/*----------------------------------------------------------------------------------------------------------------*/
%{
/*Se hacen definiciones, se llaman librerias, etc.*/
%}
/*Se definen los conjuntos que se usarán en las expresiones regulares, por ejemplo*/
%%
/*Aquí se ponen las expresiones regulares que el analizador léxico va a reconocer, y la acción que llevará acabo cuando reconozca los tokens*/
%%
/*Código en C. Aquí se pone el main (si lo tiene), o cualquier código auxiliar que se necesite.*/

/*----------------------------------------------------------------------------------------------------------------*/

Como Flex dará la entrada para Bison, no tenemos que preocuparnos por poner un main (el main está en Bison), solo necesitamos las expresiones regulares que reconocerá.

Declaramos un "y.tab.h" que Bison usará para enlazarse. Se creará al compilarlo.

Para cada expresión que reconozcamos (y que Bison use), tendremos que poner un return seguido del nombre del token (como nosotros lo nombramos en la gramática).

La estructura %union en Bison, al compilarla se convierte en una estructura yylval. Para asignarle la cadena que queremos a la pseudo variable, necesitamos pasarle a la estructura yylval el valor que hay en yytext (que es donde Flex guarda momentaneamente el valor de la cadena reconocida). Una vez pasado a la pseudo variable, podemos decirle que regrese el token deseado (en este ejemplo, CADENA, NL, CORI, CORD). Por ejemplo, para regresar un salto de linea {yylval.caracter='\n'; return NL;}

/*----------------------------------------------------------------------------------------------------------------*/
/*indentador.l*/
%{
#include <'stdio.h>
#include "y.tab.h"
%}

SIM [a-zA-Z][a-zA-Z0-9]*
CAD {SIM}({SIM})*

%%
{CAD} {yylval.cadena=(char *)malloc(255*sizeof(char));strcpy(yylval.cadena,yytext);return (CADENA);}
"{" {yylval.caracter='{';return (CORI);}
"}" {yylval.caracter='}';return (CORD);}
\n {yylval.caracter='\n';return (NL);}
. ECHO;
%%

/*----------------------------------------------------------------------------------------------------------------*/

Finalmente, para compilar:

bison -yd indentador.y
flex indentador.l
gcc y.tab.c lex.yy.c -ll -ly -o salida

Para ejecutar:
./salida

Bueno, eso es todo, espero que les sirva para iniciar al menos. Cualquier duda, o siguen mi consejo (RTFM!!!) o se la guardan, porque no la voy a contestar. Va, ahí luego.

Actualización:

Los archivos:

ejemplo.tar.gz

make
make run

Intenten con cadenas hola{mundo{cruel}} y así. No está completo, falta que imprima las llaves, pero ahí está.