Tarea programada #5
Estudiantes
Nombre: carnet:
Mauricio Ulate 983660
Felipe Umaña 994084
Índice
Planteamiento del Problema a resolver
Guía de uso del programa y Datos de prueba
A la hora de realizar un compilador
con frecuencia, las fases se agrupan en una etapa inicial y una etapa final. La
etapa inicial comprende aquellas fases que dependen principalmente del lenguaje
fuente y que son en gran parte independientes de la máquina objeto. Ahí
normalmente se incluyen los análisis léxico y sintáctico, la creación de la
tabla de símbolos, el análisis semántico y la generación de código intermedio.
La etapa inicial también puede hacer cierta optimación de código. La etapa
inicial incluye, además el manejo de errores correspondiente a cada una de esas
fases.
La etapa final incluye aquellas
partes del compilador que dependen de la máquina objeto y, en general, esas
partes no dependen del lenguaje fuente, sino sólo del lenguaje intermedio. En
la etapa final, se encuentran aspectos de la fase de optimación de código,
además de la generación de código, junto con el manejo de errores necesario y
las operaciones con la tabla de símbolos.
Se nos asignó la implementación del
algoritmo de construcción de un árbol de análisis sintáctico para la calculadora
implementada en la cuarta tarea programada. A través del proyecto daremos
detalle al programador cliente sobre los aspectos más relevantes tanto de la
implementación como de la especificación del programa, también el programador
cliente contará con una guía de uso del programa así como archivos adjuntos de
prueba y el código fuente del mismo.
Usted puede encontrar todo el
trabajo en la siguiente dirección de Internet
Este documento:
https://mauricioulate.tripod.com/Automatas/tarea5/t5sol983660.html
El archivo
.zip con el proyecto
https://mauricioulate.tripod.com/Automatas/tarea5/tarea5.zip
Planteamiento
del Problema a resolver
Modifique el programa
de la tarea anterior
para que, en lugar de evaluar una expresión, calcule el árbol sintáctico de la
expresión. Una vez que ya tenga ese árbol, muestre en un renglón aparte cada
nodo del árbol, con buena indentación, de acuerdo a
su nivel de anidamiento.
1.
Comprender
el funcionamiento de un analizador de léxico.
2.
Estudiar
el algoritmo de construcción de los árboles sintácticos.
3.
Alterar
el proyecto anterior para así usar un árbol de análisis sintáctico en lugar de
un vector posfijo.
4.
Reutilizar
programas anteriores para así ahorrar tiempo y trabajo al programador.
5.
Reafirmar
los conocimientos adquiridos en el amplio campo de la programación orientada a
objetos, al enfrentar este ejercicio de programación.
Programa
principal:
Resultado:
Permite realizar las
principales operaciones aritméticas básicas (+, -, *, / )
de manera simple o de una forma más compleja con expresiones más grandes entre
paréntesis, con números de cualquier tamaño. Además el programa no solo es
capaz de evaluar las expresiones por medio de su lexema si no que también puede
evaluar las expresiones por medio de tokens, como lo
hace un analizador léxico, pero esta vez lo hace LEX
Requiere:
Que el usuario inserte una expresión para ser
analizada
Clase Arbol
Modelo
de la clase
El modelo del ADT es un diagrama de la
estructura de datos usado para implementarlo.
Los hijos de un árbol son en sí árboles, por
lo que el modelo es recursivo.
Cada árbol se forma por un
nodo que contiene aparte de la conexión con los hijos, un Token
con la información del nodo padre (como los hijos son árboles, en sí se
convierte el Token en la información de todo el
nodo).
Operaciones
Operaciones de verificación
y propiedad
Token Raiz();
Retorna el token correspondiente a la raíz del árbol.
bool Vacio();
Retorna
verdadero si el árbol está vacío (sin padre ni hijos).
Arbol HijoIzq();
Retorna el
árbol hijo conectado a la rama izquierda del nodo padre.
Arbol HijoDer();
Retorna el
árbol hijo conectado a la rama derecha del nodo padre.
Operaciones de inserción
void Insertar(Token p);
Analiza el token y lo prepara para su inserción en el árbol.
nodo* Insert(nodo * v);
Agrega el nodo
al árbol.
double Evaluar();
Retorna valor resultante al evalúo de la expresión formada con el árbol
sintáctico.
Clase Token
Modelo
de la clase
El modelo del ADT es un diagrama de la
estructura de datos usado para implementarlo. Los campos del REP de la clase no
es posible modelarlos en un diagrama, por lo que se presenta como cuadro:
Rep
|
_tipo |
Lexema |
El campo _tipo es de tipo Tipo
y el campo lexema es de tipo Astring que son un tipo
de hilera de caracteres
Invariante de la clase
Establece las condiciones que debe cumplir cualquier
instancia de una clase en estado
estable, la invariante general para la clase Token es
que una expresión es una hilera de caracteres de la forma:
(( 60* ( 500 – 400 ) )
/100)
Sólo se procesará si esta bien escrita de acuerdo a las leyes
matemáticas y si no tiene errores de sintaxis.
Operaciones:
En ella se definen los tokens asociados a
los lexemas definidos en el programa por medio de una enumeración, representada
en C++ de la siguiente manera:
enum Tipo {
NUM = 321,
PADRE_VACIO,
OP_SUM,
OP_MUL, // podría ser otro, mientras
no "choque"
P_ABRE, //
con otros valores para tokens
P_CIERRA,
ID,
ERROR
= 666, FIN = 999
};
const Astring&
lexema() const :
Propiedad que retorna la
hilera con el lexema corrspondiente.
const char*
Nombre() const
retorna el nombre del tipo del token correspondiente.
static const char* Nombre(int):
retorna el nombre correspondiente al número de tipo de token pasado como parámetro.
void prpTipo(Tipo s)
Propiedad que permite asignar al token el tipo correspondiente al parámetro.
void prpLexema(Astring s):
Propiedad que permite asignar al lexema el
tipo correspondiente al parámetro.
Clase Astring
Operaciones
Astring& Astring::operator = (const char *str)
Cambia el valor de "*this" para que sea igual a "str".
Astring& Astring::operator += (const char * str)
Le
agrega al final a "*this" el valor de
"str".
Operaciones
Las
operaciones del ADT Compilador se dividen en dos. El primer grupo se encarga de
compilar la expresión y el segundo de evaluarla.
Operaciones de
compilación
Trabaje();
Operación invocada para realizar la
compilación.
void expr(); //
expr ==> term r1
Llama a las operaciones TERM y R1 para poder ir
analizando cada parte de una expresión. TERM
toma términos, es decir un número o números unidos por operandos
de multiplicación o división. Luego R1
busca una suma o resta.
void term(); //
term ==> factor r2
Operación que une número o expresiones a la
izquierda de un operador de suma o resta, lo cual corresponde a un término.
void
r1();
// r1 ==> - term r1 | œ
Operación que se encarga de buscar el final
de un término con el símbolo de una suma o una resta.
void r2();
Operación que se encarga de buscar la unión
entre números de un término de una expresión con el símbolo de multiplicación o
de división.
void factor(); // r2 ==> *
factor r2
Operación que se encarga de revisar si un
factor de una operación es por sí misma
una expresión.
void aparea();
// r2 ==> / factor r2 | œ
Operación que llama a yylex para sacar siguiente token.
error(const char * msg);
Graba un mensaje de
error y cancela el programa.
Operaciones de evaluación
Evaluar()
Evalúa la expresión contenida en _Sintactico.
El programa corresponde a un compilador de
expresiones. Como todo compilador, está separada la etapa de compilación
Cuando
el programa recibe una expresión, la recibe en forma infija,
esto es, la operación está escrita entre los 2 operandos.
Ej.: (2 + 3) * 4 y como resultado la separa token por
token. Esto lo hace un programa en Lex automáticamente. Al analizarlo, devuelve el
primer token que se encuentra, para así ser insertado
en el árbol sintáctico.
El
árbol sintáctico es construido a partir de una gramática LR(1)
para así poder construir el árbol de abajo hacia arriba y de izquierda a
derecha para evitar que se encicle el programa.
A
continuación un ejemplo de cómo se transforma una expresión en un árbol
sintáctico. La expresión a analizar es (2+3) * (3-4+5)
La expresión va a entrar en orden posfijo
gracias a la gramática. Entra 23+34-5+*
El nodo P corresponde a un token llamado PADRE_VACIO que
sirve para conectar partes del árbol que todavía no están terminadas.
Para la evaluación de la expresión formada por el árbol se toma la
recurrencia que se forma con los hijos de cada nodo formando árboles por su
cuenta.
Para un árbol, se toma la evaluación del árbol del hijo izquierdo como
un operando, el árbol del hijo derecho como otro operando y se usa la raíz,
generalmente un operador, para completar la expresión sencilla y evaluarla.
Esta evaluación se da como un retorno por si fue invocada por un árbol padre.
En el caso de que el nodo raíz sea un número (en cuyo caso no tendría hijos),
se retorna este valor como resultado de la evaluación. Se evalúa de izquierda a
derecha, es decir, el hijo izquierdo primero siempre.
Guía de uso del
programa y Datos de prueba
El programa fue implementado en el ambiente
de programación Visual C++ 6.0, su utilización es muy sencilla, basta con
presionar el botón que tiene un icono de un signo de admiración rojo(el botón de la opción run) y
aparecerá la pantalla en modo DOS con lo datos del programa.
A continuación se presenta un ejemplo de salida del programa:
Aho, Alfred V
& Sethi, Ravi & Ullman, Jeffrey D.
Compilers: Principles,
Techniques and Tools, Addison Wesley. 1979.
Liskov, Barbara
& Gutag, John
"Abstraction and Specification
in Program Development"; McGraw-Hill; 1986.
Stroustrup, Bjarne
"The C++ Programming Language"; 3rd edition;
Addison-Wesley;1998.