Download Documentacion_v2

Universidad de Costa Rica
Facultad de Ingeniería
Escuela de Computación
Autómatas y Compiladores
Grupo 03
Profesor Adolfo DiMare H.
Elaborado por:
Christian Chinchilla Brizuela
A01209
email: khristtian2@gmail.com
URL: http://khristtian.angelfire.com/index.htm
Viernes, 21 de Noviembre de 2008
índice de contenidos
Introducción ........................................................................................................................ 3
Dirección en Internet .................................................................................................... 4
Descripción del problema a resolver ....................................................................... 4
Problema a Resolver: ............................................................................................... 4
Requerimientos .......................................................................................................... 4
Abstraccion: .................................................................................................................... 5
Especificación del Programa ................................................................................. 5
Arquitectura del Programa .......................................................................................... 5
Implementación .............................................................................................................. 6
Compilador Utilizado ................................................................................................ 6
Como compilar el programa?................................................................................. 6
Guía de uso del programa ......................................................................................... 11
2
Introducción
Esta tarea consiste en generar mediante una herramienta automatizada un
analizador sintáctico para reconocer gramáticas LALR. La sintaxis de la entrada
va a ser una gramática escrita en el formato que emplea el libro de texto del curso
(Aho, Alfred V & Sethi, Ravi & Ullman, Jeffrey D.: Compiladores principios,
técnicas y herramientas, Addison Wesley. 1979.).
El programa generado debe de recibir una gramática escrita en el formato del libro
de texto y producir una gramática con el formato valido para Bison/Yacc. Luego
de producir esta gramática se invoca a Bison/Yacc y se le pasa la gramática recién
generada para que Bison/Yacc analice si es una gramática es LALR.
3
Dirección en Internet
La solución de esta tarea se encuentra alojada en el siguiente sitio:
http://khristtian.angelfire.com/tarea4.htm
Descripción del problema a resolver
Problema a Resolver:
El problema consiste reconocer si una gramática es LALR utilizando Bison/Yacc,
para esto se utiliza una gramática en formato del libro de texto y se traduce
mediante un traductor generado con Bison/Yacc, además después de traducir la
gramática a un formato válido para Bison/Yacc se debe validar que la gramática
sea LALR.
Objetivos
1. Que el estudiante aprenda a utilizar una herramienta automatizada para
generar analizadores sintácticos (Bison/Yacc).
2. Comprender las ventajas que tiene utilizar gramáticas LALR.
3. Conocer la utilizad de y la simplicidad de generar un analizador sintáctico
con Bison/Yacc.
4. Despejar las dudas mediante la práctica.
Requerimientos:
JFlex para crear el analizador léxico
BYacc para crear el analizador sintáctico
4
Un compilador de java
Abstraccion:
Especificación del Programa
El programa traduce una gramática escrita en el formato del libro de texto del
curso a un formato que pueda reconocer BYacc
Arquitectura del Programa
El programa generado es creado automáticamente y esta escrito en forma
secuencial. El programa fue generado con byaccj1.14 para Windows y jflex-1.4.1
El primer paso a realizar es convertir la gramática de entrada en una gramática
con un formato válido para Bison/Yacc. Para esto se creo una gramática que
pudiera reconocer cualquier gramática en el formato del libro de texto.
5
Se establecieron los siguientes tokens para una gramática de entrada:
TERMINAL = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" |
"s" | "t" | "u" | "v" | "w" | "x" | "y" | "z" | "+" | "-" | "*" | "/" | "(" | ")"
EPSILON = "epsilon"
DERIVA = "-->"
OR = "|"
NO_TERMINAL = "A" |"B" |"C" |"D" |"E" |"F" |"G" |"H" |"I" |"J" |"K" |"L" |"M" |"N" |"O" |"P" |"Q" |"R"
|"S" |"T" |"U" |"V" |"W" |"X" |"Y" |"Z"
NL = \n | \r | \r\n
Las gramáticas de entrada en el formato del libro de texto van a tener la forma:
A-->Aq |epsilon
B-->q|w|p
Cuando una gramatica es reconocida se va almacenado en un String donde los
tokens TERMINAL se encierran entre comillas simples (‘a’). Los tokens
NO_TERMINAL y los tokens OR se guardan igual, cuando se encuentra un token
DERIVA (-->) se guarda “:” y para un token EPSILON se guarda un String vacío.
Al final de la gramatica se agrega “;”.
El analizador sintáctico generado por Bison/Yacc en base a esta gramática genera
su resultado (traducción a la gramática reconocida por Bison/Yacc) a la salida
estandar.
Implementación
Compilador Utilizado
Los archivos generados por JFlex y por BYacc fueron incluidos en un proyecto
netbeans 6.1 y compilados con javac de la plataforma JDK 1.6
¿Como compilar el programa?
Para compilar el programa es necesario compilar juntos los archivos .java
generados por JFlex y por Byacc.
6
Archivo “analizadorLexico.flex”
%%
%byaccj
%{
private Parser yyparser;
public Yylex(java.io.Reader r, Parser yyparser) {
this(r);
this.yyparser = yyparser;
}
%}
TERMINAL = "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" |
"k" | "l" | "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" |
"w" | "x" | "y" | "z" | "+" | "-" | "*" | "/" | "(" | ")"
EPSILON = "epsilon"
DERIVA = "-->"
OR = "|"
NO_TERMINAL = "A" |"B" |"C" |"D" |"E" |"F" |"G" |"H" |"I" |"J" |"K" |"L"
|"M" |"N" |"O" |"P" |"Q" |"R" |"S" |"T" |"U" |"V" |"W" |"X" |"Y" |"Z"
NL = \n | \r | \r\n
%%
/* cambio de linea */
{NL}
{ return Parser.NL; }
{TERMINAL} { yyparser.yylval = new ParserVal(yytext());
return Parser.TERMINAL; }
{EPSILON} { yyparser.yylval = new ParserVal(yytext());
return Parser.EPSILON; }
{DERIVA} { yyparser.yylval = new ParserVal(yytext());
return Parser.DERIVA; }
{OR} { yyparser.yylval = new ParserVal(yytext());
return Parser.OR; }
{NO_TERMINAL} { yyparser.yylval = new ParserVal(yytext());
return Parser.NO_TERMINAL; }
[ \t]+ { } //no hace nada
\b
{ System.err.println("Caracter invalido"); }
/* error fallback */
[^]
{ System.err.println("Error: Caracter invalido '"+yytext()+"'");
return -1; }
El archivo analizadorLexico.flex es procesado por JFlex 1.4.1 y produce un
archivo Yylex.java
7
Archivo “analizadorSintáctico.y”
%{
import java.io.*;
%}
%token <sval> NL
/* cambio de linea
%token <sval> TERMINAL
%token <sval> EPSILON
%token <sval> DERIVA
%token <sval> OR
%token <sval> NO_TERMINAL
%type <sval> Gramatica
%type <sval> Produccion
%type <sval> Producciones
%type <sval> Cuerpo
%type <sval> Mas_Cuerpo
%%
input:
*/
/* empty string */
| input line
;
NL
line:
{
if (interactive)
System.out.print("Introduzca la Gramatica: ");
}
| Gramatica NL
{
System.out.println("La gramatica es : ");
8
int tam = traduccion.length();
char [] temp = traduccion.toCharArray();
for(int i = tam-1; i>=0; i--)
System.out.print(temp[i]);
System.out.println(";"); //fin de gramatica en Yacc
traduccion ="";//limpia el string
if (interactive) System.out.print("Introduzca la Gramatica: ");
};
Gramatica: Produccion Producciones ; //al menos una produccion
Producciones: Produccion Producciones |; //esto es epsilon
Produccion: NO_TERMINAL DERIVA Cuerpo
{
traduccion += " :";
traduccion += $1;
};
Cuerpo: NO_TERMINAL Mas_Cuerpo
{
traduccion += " "+$1;
}
| TERMINAL Mas_Cuerpo
{
traduccion += "'"+$1+"'";
};
| EPSILON;
Mas_Cuerpo: TERMINAL Mas_Cuerpo
{
traduccion += " '"+$1+"'";
}
| NO_TERMINAL Mas_Cuerpo{
traduccion += " "+$1;
}
|OR Cuerpo{
traduccion += " " + $1 + " ";
}
| ; //esto es epsilon
%%
private Yylex lexer;
static String traduccion = ""; //limpia el string
private int yylex () {
int yyl_return = -1;
try {
yylval = new ParserVal(0);
9
yyl_return = lexer.yylex();
}
catch (IOException e) {
System.err.println("IO error :"+e);
}
return yyl_return;
}
public void yyerror (String error) {
System.err.println ("Error: " + error);
}
public Parser(Reader r) {
lexer = new Yylex(r, this);
}
static boolean interactive;
public static void main(String args[]) throws IOException {
System.out.println("Traductor de Gramaticas");
Parser yyparser;
if ( args.length > 0 ) {
// parse a file
yyparser = new Parser(new FileReader(args[0]));
}
else {
// interactive mode
System.out.println("[Para salir presione CTRL-D]");
System.out.print("Introduzca la Gramatica: ");
interactive = true;
yyparser = new Parser(new InputStreamReader(System.in));
}
yyparser.yyparse();
if (interactive) {
System.out.println();
System.out.println("Gracias por usar este programa");
}
}
El archivo analizadorSintactico.y es procesador por Yacc.exe y produce los
archivos:
ParserVal.java
Parser.java
10
Para compilar el programa es necesario compilar los archivos Yylex.java
Parser.java, ParserVal.java ultilizando un compilador de java. En nuestro caso
estos archivos fueron incluidos en un proyecto netbeans 6.1 y compilados
utilizando el javac de la plataforma JDK 1.6
En la carpeta adjunta Herramientas se proporcionan los programas necesarios
para realizar las acciones descritas anteriormente.
Guía de uso del programa
El programa se ejecuta en la plataforma Windows y acepta un archivo de entrada
con una gramática en el formato del libro de texto para esto debe colocar un
archivo de nombre “entrada.txt” con la gramática en el mismo directorio donde se
encuentre traductor.jar, yacc.exe.
Hay dos archivos de procesamiento por lotes:
1. Resultado: llama al traductor.jar le pasa como parámetro “entrada.txt”
produce un archivo intermedio llamado “salida.txt”, este archivo contiene la
gramática traducida a formato yacc. Luego se llama a yacc con la opción –
v que genera en un archivo llamado y.output la especificación de lo que
realizó, este archivo se muestra en pantalla. Para finalizar se borran todos
los archivos intermedios.
11
2. Resultado_sin_borrar: realiza la misma acción que Resultado.bat pero no
borra los archivos intermedios.
12