Objetivos de la práctica

​

• Revisar las bases para desarrollar un analizador léxico (scanner) y sintáctico (parser) con el uso de Flex y Bison.

​

• Realizar un ejemplo sencillo y mostrar la resolución del Ejercicio 47.

​

Flex y Bison

• Herramientas a utilizar

​

• Flex, Bison, Compilador C/C++

​

• Temas a revisar

​

• Instalación y configuración de las herramientas.

​

• Edición, compilación , enlace y ejecución del programa analizador.

​

• Ejercicios de ejemplo.

​

​

Flex y Bison

Bison y Flex

Flex:

​

Es un generador de analizadores léxicos de propósito general.

Esta herramienta trabaja sobre un conjunto de expresiones regulares que recibe como entrada. A partir de ellas, Flex genera un programa en C/C++ que implementa un “Scanner” para reconocer el lenguaje regular descripto por dichas expresiones.

​

Luego, al compilar dicho código en C/C++ se obtiene un programa ejecutable. El aplicativo ejecutable busca concordancias entre un fichero de entrada (código fuente del lenguaje que se esta analizando) y las expresiones regulares que se definieron; y ejecuta acciones asociadas en consecuencia.

​

Bison:

​

Convierte la descripción formal de un lenguaje, escrita como una gramática libre de contexto, en un programa en C que realiza análisis sintáctico. Para utilizar Bison, es necesario tener experiencia con la sintaxis usada para describir gramáticas.

​

​

Instalación

Descargar las herramientas desde la plataformas web

(“PROYECTO: tarea”>Herramienta BiosnFlex) e instalar bision y felx

Es necesario contar con un compilador de C.

Se sugiere el entorno Dev C++

(ver. 5.11 para Windows 10 https://dev-c.soft32.com/)

Configuración

Configuración de variables del ambiente Windows

​

Debemos agregar los paths de los ejecutables de flex y bison a la configuración del ambiente para que las librerías de estos sistemas sean alcanzables directamente por el programa enlazador “linker ld.exe”.

​

​

​

1°) Click en Inicio -> Panel de Control- > Sistema -> Configuración avanzada -> Variables de entorno

Configuración

Configuración de variables del ambiente Windows

​

2° ) Editar la variable “path”, agregando el camino de la carpeta donde están los ejecutables de las aplicaciones bisio y flex

​

c:\....\GnuWin32\bin\

Proceso de Edición, Compilación y Ejecución

• Edición:
• Editar la especificación léxica en un archivo de extensión .l
• Editar la especificación sintáctica en un archivo de extensión .y

​

• Compilación:
• Compilar la especificación léxica con Flex
• Compilar la especificación sintáctica con Bison

​

• Enlazado:
• Compilar y enlazar todo el código generado con el compilador C

​

• Ejecución:
• Ejecutar el analizador léxico-sintáctico obtenido.

​

Proceso de edición, compilación, enlazado y ejecución

Comandos para la compilación, enlazado y ejecución:

​

• Compilación en flex y bision:

​

C:\ejemplo\flex -olexico.yy.c lexico.l

C:\ejemplo\bison –t –d –v sintactico.y

​

• Compilación y enlazado de C:

​

C:\ejemplo\gcc sintactico.tab.c lexico.yy.c -o MiAnalizador -lm

​

• Ejecución:

​

C:\ejemplo\MiAnalizador.exe

Ingrese cadena

aabb

cadena valida

​

Compilación, enlazado y ejecución

Ejemplo

%{

#include "sintactico.tab.h"

#define yywrap() 1

%}

​

%%

[aA] { return X; }

[bB] { return Y; }

\n { return NL;}

. { return yytext[0]; }

​

%%

%{

#include <stdio.h>

%}

%token X Y NL

​

%%

stmt : s NL { printf("La cadena ingresada es valida"); return; }

;

s : X s Y

|

;

%%

int yyerror(char *msg)

{

printf("La cadena ingresada es invalida: %s\n", msg);

return;

}

int main()

{

printf("Ingrese cadena\n");

yyparse();

}

Reconocer [aA]ⁿ [bB]ⁿ

lexico.l

sintactico.y

Reglas de producción:

S -> a S b | λ

Edición de las especificaciones de flex

Un programa en flex tiene 4 secciones:

​

%{

Declaraciones en C

%}

Definiciones

%%

Lista de patrones y acciones

%%

Código C adicional

Edición de las especificaciones de flex

Declaraciones en C

​

• En la sección de declaraciones, el código que se encuentre entre %{ y %} se copiará literalmente al comienzo del fichero generado en C.

​

• Ejemplo:

#include <stdio.h>

​

Edición de las especificaciones de flex

Definiciones

​

• La sección de Definiciones está constituida por una secuencia de parejas de la forma:

nombre definición

conocidas como definiciones de nombre donde:

nombre: nombre del token

definición: expresión regular (patrón)

​

Ejemplo:

​

DIGITO [0-9]

ID [a-z][a-z0-9]*

Edición de las especificaciones de flex

Reglas

​

• La sección de Reglas contiene una serie de declaraciones de la forma:

patrón {acción}

(el patrón debe estar sin sangría, y la acción debe comenzar en la misma línea)

donde:

patrón: expresión regular

acción: código C con las acciones a ejecutar cuando se encuentra concordancia del patrón con el texto de entrada.

Ejemplo:

{DIGITO}+ { printf(“Número: %s”, yytext); }

\“{ID}*\“ { printf("Cadena: %s", yytext); }

Edición de las especificaciones de flex

Código C adicional

​

• La sección de Código adicional es opcional y puede incluir funciones en C que llaman al Scanner o son llamadas por él

Edición de las especificaciones de bison

Un programa en Bison se divide en 4 partes:

​

%{

Declaraciones en C

%}

Declaraciones Bison

%%

Reglas de producción de la gramática

%%

Código C adicional

Edición de las especificaciones de bison

Declaraciones en C

​

• Se pueden definir tipos y variables utilizadas luego en las acciones.
• Pueden también incluir comandos del preprocesador, tales como la directiva de inclusión #include para incluir archivos de cabecera que realicen cualquiera de estas cosas.

​

Ejemplo

%{

#define YYSTYPE int

#include <math.h>

char *cadena;

int errores = 0;

%}

​

Edición de las especificaciones de bison

Declaraciones de Bison

​

• Contiene los símbolos terminales y no terminales:

​

• Símbolos Terminales: por convención en mayúsculas y bajo el siguiente formato:

​

%token NOMBRE1, NOMBRE2,…

%token NOMBRE3

​

•Símbolos no Terminales: por convención en minúsculas, no es necesario declararlos.

​

Ejemplo

%token ENTERO

%token DIGITO

%token INICIO_PROGRAMA

%token FIN_PROGRAMA

Edición de las especificaciones de bison

Reglas de producción

​

• Son las reglas gramaticales, las cuales se pueden asociar a un conjunto de acciones en código en C que se ejecutan cuando el Parser encuentra concordancias con la regla correspondiente. Tiene la forma:

resultado: componentes-regla1 {sentencias en C}

|componentes-regla2 {sentencias en C}

….

;

donde:

resultado: es un “no terminal” a la izquierda de la producción.

componentes-regla: secuencia de terminales y no terminales que

definen una regla.

sentencias en C: acciones que se ejecutan cuando hay correspondencia con una regla (Es opcional).

​

• La primera regla de producción definida constituye el axioma de la gramática.

​

• Si para una regla no se definen componentes del lado derecho de la regla de producción, se entiende que la gramática acepta la cadena vacía (λ).

​

Edición de las especificaciones de bison

Código C adicional

​

• Debe contener la función main() que debe llamar a la función yyparse(), esta última es la que inicia el Parser.

​

• Pueden incluirse la función yyerror() para el tratamiento de errores sintácticos; y también yywrap() en donde se incluye el código que desee ejecutarse al finalizar el proceso de Análisis.

​

• Puede contener otras funciones, por ejemplo las llamadas desde la reglas de producción

Ejercicio 47

Gramática

​

rutina ::= identifier parameter_list

parameter_list ::= "(" defparameter {"," defparameter}* “)"

| ("&" identifier { "," "&" identifier}*

defparameter ::= parameter ["=" expression]

identifier ::= letter {letter | digit | "_"}*

parameter ::= identifier | "(" sublist ")"

expression ::= conditional_expression | lambda_form

letter ::= lowercase | uppercase

digit ::= "0"|"1"|...|"9"

identifier ::= (letter) {letter | digit | "_"}*

sublist ::= parameter ("," parameter)*

conditional_expression ::= "or_test" | "and_test"

lambda_form ::= "lambda"

lowercase ::= "a"|"b"|...|"z"

uppercase ::= "A"|"B"|...|"Z"

​

Ejemplos

​

algo1(alfa = or_test, Beta = lambda) // válido

algo1(alfa = or_test, &Beta) // inválido

algo1(alfa = or_test, _Beta = lambda) // inválido

​

​

Resolución del Ejercicio 47

Flex:

​

%option noyywrap

%{

#include "sintactico.tab.h"

%}

​

LETTER [A-Za-z]

DIGIT [0-9]

IDENTIFIER {LETTER}({LETTER}|{DIGIT} |”_”)*

%%

​

")" {printf(")\n"); return CPAR;}

"(" {printf("(\n"); return APAR;}

"=" {printf("=\n"); return IGUAL;}

"," {printf(",\n"); return COMA;}

"&" {printf("&\n"); return AMPERSAND;}

"or_test" {printf("or_test\n"); return ORTEST;}

"and_test" {printf("and_test\n"); return ANDTEST;}

"lambda" {printf("lambda\n"); return LAMBDA;}

{IDENTIFIER} {printf("%s\n" , yytext); return (IDENTIFIER);}

\n {return (NL);}

. {return yytext[0];}

%%

​

Resolución del Ejercicio 47

Bison:

​

%{

#include <stdio.h>

extern char* yytext;

extern FILE *yyin;

%}

​

%token IGUAL IDENTIFIER APAR CPAR COMA ORTEST ANDTEST LAMBDA AMPERSAND NL

%%

RUTINA : IDENTIFIER APAR PARAMETER_LIST CPAR NL { printf("RUTINA\n*** La cadena ingresada es valida. ***\n"); return; }

|

;

PARAMETER_LIST : DEFPARAMETER { printf("PARAMETER_LIST\n" , yytext) ; }

| PARAMETER_LIST COMA DEFPARAMETER { printf("PARAMETER_LIST\n" , yytext) ; }

| APAR AMPERSAND IDENTIFIER CPAR { printf("PARAMETER_LIST\n" , yytext) ; }

| PARAMETER_LIST COMA AMPERSAND IDENTIFIER { printf("PARAMETER_LIST\n" , yytext) ; }

;

​

DEFPARAMETER: PARAMETER { printf("DEFPARAMETER\n" , yytext) ; }

| PARAMETER IGUAL EXPRESION { printf("DEFPARAMETER\n" , yytext) ; }

;

​

​

​

​

​

PARAMETER: IDENTIFIER { printf("PARAMETER\n" , yytext) ; }

| APAR SUBLIST CPAR { printf("PARAMETER\n" , yytext) ; }

;

SUBLIST:

| PARAMETER { printf("SUBLIST\n" , yytext) ; }

| SUBLIST COMA PARAMETER { printf("SUBLIST\n" , yytext) ; }

;

​

CONDITIONAL_EXPRESSION: ORTEST { printf("CONDITIONAL_EXPRESSION\n" , yytext) ; }

| ANDTEST { printf("CONDITIONAL_EXPRESSION\n" , yytext) ; }

;

​

EXPRESION: CONDITIONAL_EXPRESSION { printf("EXPRESION\n" , yytext) ; }

| LAMBDA_FORM { printf("EXPRESION\n" , yytext) ; }

;

LAMBDA_FORM: LAMBDA { printf("LAMBDA_FORM\n" , yytext) ; }

;

​

%%

int yyerror(char *msg) {

printf("*** La cadena ingresada es invalida: %s ***\n ", msg);

return;

}

int main() {

yyin = fopen("datos.txt","rt");

/*printf("\nIngrese la cadena:\n");*/

yyparse();

}}

​

​