CI-1322 Autómatas y compiladores

Tarea #6

Analizador Sintáctico para dialecto de Prolog.

                                                                                                                                                              Realizado por :

Sharon Amador Vargas A10218 
 Roberto Hernández Montoya A11727

---

Tabla de Contenidos

Introducción 2

Descripción del problema 2

Problema 2

Solución 2

Objetivos 3

Requerimientos 3

Herramientas usadas 3

Formato del archivo de entrada 3

Formato del archivo de salida 5

Abstracción 5

Clases creadas 5

Implementación 7

Cambios realizados ¡Error! Marcador no definido.

Compilador Usado 7

Cómo compilar el programa 7

Guía de uso del programa 8

Datos de prueba del programa 9

Código fuente 11

Bibliografía 18

---

Introducción

En esta tarea se vuelve a ejemplificar el uso de herramientas para la construcción de compiladores como lex, para reconocer el alfabeto del programa, pero también se enfatiza en la construcción de una gramática capaz de reconocer un programa especifico, definiendo los tokens y lexemas y llegando a una gramática no ambigua, factorizada a la izquierda y eliminada de esta la recursividad izquierda. La solución de esta tarea se encuentra en la página http://oocities.com/roberto_hern/t6/t6solA11727.htm

Descripción del problema

Problema

Se usa como base la solución al primer examen parcial para implementar un analizador sintáctico para Prolog. Se debe implementar el analizador léxico usando Lex/Flex.

      Además se debe escribir la gramática para el programa, y luego obtener un programa para factorizarla por la izquierda y eliminarle la recursividad izquierda. Con ese programa se debe obtener la gramática base para escribir el analizador sintáctico.

      El analizador sintáctico debe imprimir un mensaje de error si el programa que recibe de entrada es no sintácticamente correcto; en caso contrario debe terminar la ejecución en silencio.

Solución

El problema se soluciona creando un analizador léxico con el programa Flex, al cual le corresponde el archivo lex.yy.c . Luego este archivo se incorpora a un proyecto con una nueva clase analiza, que mediante el yylex() lee desde la entrada de consola el programa y haciendo uso de la gramatica previamente definida, se define un código que logra reconocer el programa de manera eficiente, y si encuentra un error termina la ejecución e indica que hay un error en la ultima línea que se especificó.

Objetivos

R Crear un analizador léxico con la herramienta Flex.

R Crear un analizador sintáctico capaz de reconocer el programa de la pregunta #1 del primer parcial

Requerimientos

R Conocimiento básico en la creación de gramáticas.

R Se debe conocer el funcionamiento del programa flex.

R Programa Anagra.bat, utilizado para factorizar y quitar la recursividad izquierda a la gramática

---

Herramientas usadas

La principal herramienta que se usó fue el generador de analizadores léxicos Flex.

Como se puede observar en la figura 1, Flex recibe en el archivo de entrada las definiciones en lenguaje LEX y produce como salida un archivo en C, que define la rutina yylex().

		lex.yy.c
		lex.yy.obj

Fig. 1. Creación de un analizado léxico con FLEX

Formato del archivo de entrada

El programa en LEX consta de tres partes:

declaraciones

%%

reglas de traducción

%%

procedimientos auxiliares

Para el caso de la calculadora el archivo de entrada fue:

%{

#define OP_SUM 321

#define NUM 323

#define PABRE 324

#define PCIERRA 325

#define ID 326

#define NL 327

#define IS 328

#define OP_AS 330

#define FINLI 331

#define COMA 332

#define RAYA 333

#define ADMI 334

#define PABREC 335

#define PCIERRAC 336

#define ERROR 666

#define FIN 999

%}

delim [ \t\n]

blancos {delim}+

letra [A-Za-z]

admir [!]

digito [0-9]

id {letra}({letra}|{digito})*

numero {digito}+

%%

{blancos} { /*no realiza accion*/}

is { return(IS);}

nl { return(NL);}

eof { return(FIN);}

{id} { return(ID); }

{numero} { return(NUM);}

"." { return(FINLI);}

":-" { return(OP_AS);}

"-" { return(OP_SUM); }

"(" { return(PABRE); }

")" { return(PCIERRA); }

"[" { return(PABREC); }

"]" { return(PCIERRAC); }

"," { return(COMA); }

"_" { return(RAYA); }

{admir} { return(ADMI); }

En la primera parte se definen las constantes que se van a usar en el programa.

En las definiciones regulares, se especifica un delimitador como un espacio en blanco, una tabulación o un cambio de línea, luego un espacio en blanco consiste en cero o más delimitadores. También se especifican los dígitos, y los números como secuencias de dígitos con una parte decimal opcional.

Finalmente se presentan las reglas de traducción para cada expresión regular.

¿Cómo funciona LEX?

Cuando el analizador léxico se está ejecutando, analiza la entrada buscando cadenas de caracteres que concuerden con uno de sus patrones definidos. Una vez que lo ha encontrado, lo hace disponible a través de la variable global yytext, que es un puntero a caracter. Su longitud se encuentra en el entero global yyleng. Luego se ejecuta la acción correspondiente.

Formato del archivo de salida

Flex genera el archivo de salida lex.yy.c, el cual contiene la rutina yylex(), un número de tablas usadas para encontrar los tokens, y ciertas rutinas auxiliares y macros. Cada vez que se hace un llamado a yylex, éste revisa los tokens del archivo de entrada hasta que ejecute alguna acción o sea fin de archivo.

---

Abstracción

Clases creadas

Clase analiza

h Especificación de la clase:

Especifica el analizador sintáctico que recibirá de entrada un programa para su análisis.

h Métodos y variables:

public:

§ analiza(): Constructor, llama a programa para iniciar el reconocimiento

§ void programa(): no terminal programa

§ void lp(): no terminal lista_props

§ void lp1(): no terminal lista_props'

§ void prop(): no terminal prop

§ void der(): no terminal der

§ void izq(): no terminal izq

§ void lt(): no terminal lista_term

§ void lt1(): no terminal lista_term'

§ void expa(): no terminal expa

§ void arit(): no terminal arit

§ void arit1(): no terminal arit'

§ void termino(): no terminal termino

§ void id(): terminal

§ void num(): terminal

§ void asig(): no terminal asig

§ void asig1(): no terminal asig'

§

private :

§ int tok: guarda el token actual devuelto por yylex()

---

Implementación

Compilador Usado

Visual C++ 6.0 Microsoft Compiler.

Cómo compilar el programa

Se proveen 4 archivos necesarios para la compilación del programa: Analizador.cpp, Analizador.h, lex.yy.c y LIBFLEX.lib.

Para compilar el programa se debe crear un nuevo proyecto de consola en Visual C++ y luego agregar al proyecto los dos primeros archivos. Luego se debe agregar la librería de la siguiente forma:

Se elige del menú principal Project, luego Settings.

Fig. 2. Opción del menú

Fig. 3. Agregar la librería.

En la opción de Link se debe agregar la librería en la parte de Object/Library modules, como se muestra en la figura 3.

Por último se compila el proyecto.

---

Guía de uso del programa

1. El programa solicita introducir el programa

Si no se da ningún error el programa termina de la siguiente forma

2. Si hay algún error se le dirá al terminar de escribir la línea que tiene el error, y se le pedirá revisar su código e intentar de nuevo la inserción del programa, para lo que deberá reiniciar el programa.

---

Datos de prueba del programa

Los datos de prueba del programa fueron

1.

hanoi(N) :- move(N, left, center, right).
 
move(0,_,_,_) :- !.
move(N,A,B,C) :-
 M is N-1, move(M,A,C,B), w(A,B), move(M,C,B,A).
 
w(From,To) :- write([move, from, From, to, To]), nl.

2. hanoi(N) :- moveN, left, center, right). (Falta un parentesis)

3. w(From,To) :- write([move, from, From, to, To]). nl.

4. move(N,A,B,C) :-
    M = N-1, move(M,A,C,B), w(A,B), move(M,C,B,A).

Salidas del programa

---

Código fuente

1. Analizador.cpp

#include "analizador.h"

#include <string.h>

#include <stdlib.h>

#include <string.h>

#include "lex.yy.c"

#include <iostream.h>

#include <stdio.h>

void analiza::programa(){ //programa-> lista_prop

tok = yylex();

lp();

}

void analiza::lp(){ //lista_prop -> prop lista_prop'

prop();

tok = yylex(); //**************************************************************

if (tok != FIN)

lp1();

else{

printf("\nAnalisis terminado, no se encontraron errores\n");

exit(0);

}

}

void analiza::lp1(){ //lista_prop' -> prop lista_prop'

prop();

tok = yylex(); //*******************************************************

if (tok != FIN)

lp1();

else{

printf("\nAnalisis terminado, no se encontraron errores\n");

exit(0);

}

}

void analiza::prop(){ //prop -> izq :- asig

izq();

if(strcmp(yytext, ":-")==0)

{

tok = yylex();

asig();

if(strcmp(yytext, ".")!=0){

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

}

else{

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

}

void analiza::asig(){ //asig-> der , asig' .

der();

if(tok != FINLI && tok == COMA)

{

tok = yylex();

asig1();

}

}

void analiza::asig1(){ //asig'-> der , asig' | epsilon

der();

if(tok != FINLI && tok == COMA)

{

tok = yylex();

asig1();

}

}

void analiza::der(){ //der -> ! | nl | expa | izq

if(tok == ADMI || tok == NL)

{

tok = yylex();

}

expa();

izq();

}

void analiza::izq(){ //izq -> id ( lista_term )

if(tok != FINLI)

{

// tok = yylex();

id();

//tok= yylex();

if(strcmp(yytext, "(")==0)

{

lt();

if(strcmp(yytext, ")")!=0){

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

}

else{

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

tok = yylex();

}

}

void analiza::lt(){ //lista_term -> termino lista_termm' | expa lista_term'

//aqui mismo se havce la transformación lista_term -> [lista_term]

termino();

lt1();

if(strcmp(yytext, "[")==0)

{

lt();

if(strcmp(yytext, "]")!=0){

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

tok = yylex();

}

lt1();

}

void analiza::lt1(){ //lista_term' -> , termino lista_term' | epsilon

if(strcmp(yytext, ",")==0){

termino();

lt1();

if(strcmp(yytext, "[")==0)

{

lt();

if(strcmp(yytext, "]")!=0){

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

yylex();

}

lt1();

}

}

void analiza::expa(){ //expa -> id is arit

if(tok != FINLI){

id();

if(strcmp(yytext, "is")==0)

arit();

else{

if(tok != PABREC && tok != PCIERRAC &&tok != PABRE && tok != PCIERRA && tok != FINLI)

{printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);}

}

if(tok != PABREC && tok != PABRE)

{

tok = yylex();

}

}

}

void analiza::arit(){ //arit -> termino arit'

termino();

arit1();

}

void analiza::arit1(){ //arit' -> termino arit' | epsilon

if(strcmp(yytext, "-")==0)

{

termino();

arit1();

}

}

void analiza::termino(){ //termino -> id | numeroo | nl | !

if(tok == FIN)

{

printf("\nAnalisis terminado, no se encontraron errores\n");

exit(0);

}

tok = yylex();

if(tok != 333){

id();

//tok = yylex();

num();

}

else{

tok= yylex();

}

}

void analiza::id(){ //identificador, es un terminal

if(tok == FIN)

{

printf("\nAnalisis terminado, no se encontraron errores\n");

exit(0);

}

if(tok != PABREC && tok != PCIERRAC && tok!=ID && tok != PABRE && tok != PCIERRA && tok != FINLI && tok != NUM && tok != OP_SUM)

{

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

if(tok == ID)

tok = yylex();

}

void analiza::num(){ //numero, es un terminal

if(tok == FIN)

{

printf("\nAnalisis terminado, no se encontraron errores\n");

exit(0);

}

if(tok != PABREC && tok != PCIERRAC && tok!=NUM && tok != PABRE && tok != PCIERRA && tok != COMA && tok != ID && tok != OP_SUM && tok != FINLI )

{

printf("error en la linea anterior, revise su programa e intente de nuevo.\n");

exit(0);

}

if(tok == NUM)

tok = yylex();

}

int main(){ //procedimiento principal.

printf("________________________________________________________________\n\n");

printf("Digite el codigo de su programa (para terminar, digite \"eof\"):\n");

printf("________________________________________________________________\n\n");

analiza a1;

}

2. Analizador.h

#ifndef ANALIZ_H

#define ANALIZ_H

class analiza{

public :

analiza(){tok = 0; programa();} //constructor, llama a prograa para iniciar el reconocimiento

void programa(); //no terminal programa

void lp(); //no terminal lista_props

void lp1(); //no terminal lista_props'

void prop(); //no terminal prop

void der(); //no terminal der

void izq(); //no terminal izq

void lt(); //no terminal lista_term

void lt1(); //no terminal lista_term'

void expa(); //no terminal expa

void arit(); //no terminal arit

void arit1(); //no terminal arit'

void termino(); //no terminal termino

void id(); //terminal

void num(); //terminal

void asig(); //no terminal asig

void asig1(); //no terminal asig'

private :

int tok;

};

#endif

---

Bibliografía

Aho, A. et al. Compiladores: principios, técnicas y herramientas. Addison Wesley.1990