CI-1322
Autómatas y compiladores
Tarea #3
Cálculo del árbol sintáctico
para la calculadora
Realizado por
:
Sharon Amador Vargas A10218
Roberto Hernández Montoya A11727
Tabla de Contenidos
Introducción
En esta tarea se muestra la construcción de un árbol de análisis sintáctico a partir de las definiciones dirigidas por la sintaxis. Los árboles sintácticos funcionan como una representación intermedia que permite separar la traducción del análisis sintáctico.
Los árboles de
análisis sintáctico permiten apreciar como del símbolo inicial de una gramática
deriva una cadena del lenguaje. Formalmente posee las siguientes propiedades:
1.
La raíz está etiquetada con el símbolo inicial.
2.
Cada hoja está etiquetada con un componente léxico o
con épsilon.
3.
Cada nodo interior está etiquetado con un nodo no
terminal.
Las hojas de un árbol de análisis sintáctico, leídas de izquierda a derecha, forman la producción del árbol.
Con
la construcción del árbol para una cadena de componentes se analiza sintácticamente ésta cadena. En esta tarea se muestran
varios ejemplos y se detallan los resultados de los análisis sintácticos.
Descripción del problema
Problema
Modificar
el programa de la tarea #2 (que se encuentra en http://oocities.com/
roberto_hern83/ t2/ t2solA11727.htm) para que calcule el árbol sintáctico de las
expresiones. Una vez que se tiene ese árbol, se imprime mostrando en un renglón
aparte cada nodo del árbol, bien indentado, de
acuerdo a su nivel de anidamiento.
Solución
La solución propuesta se logró mediante la
implementación de dos clases nuevas, la clase nodo y la clase árbol, las cuales
por motivo de reducir el tamaño y la cantidad de archivos a entregar, se
implementaron en el mismo .cpp de la clase
calculadora.
En estas clases se implementan los
procedimientos para insertar, borrar, crear y destruir los nodos que contendrán
las producciones del árbol sintáctico de las expresiones evaluadas por la
calculadora, más adelante se mostrará la especificación de las clases nuevas
insertadas.
Objetivos
h
Crear el árbol de análisis
sintáctico para la expresión que va a evaluar la calculadora.
h
Imprimir el árbol creado de
forma adecuada.
Requerimientos
h
Conocer de la estructura de datos de árbol.
h
Conocer en la programación de procesos recursivos.
Clases creadas
Clase nodo
h
Especificación de la clase:
Clase
que especifica los nodos que va a contener el árbol sintáctico.
h
Métodos y variables
public:
§
nodo(char * val) = constructor de nodo, inserta el string
que recibe en la variable info del nodo.
§
void imprimenodo(fstream&a) =
imprime el valor del nodo y lo guarda en el archivo
§
int eshoja()
= devuelve 1 si el nodo actual es hoja y dos si no.
§
int insertarhijo(nodo
*n) = devuelve 1 si se insertó el hijo al nodo actual y 0 si el vector de hijos
estaba lleno o si no lo pudo insertar por otra razón.
§
nodo * gethijo(int numhijo)
= devuelve el nodo hijo numero numhijo.
private:
§
char info[256]
= información del nodo, hasta 256 caracteres.
§
nodo * hijos[cant] = arreglo de hijos de cantidad cant.
§
nodo * padre = puntero al padre.
§
void insertav(char * val) = inserta el valor
del nodo(solo lo usa el constructor).
§
void inicializahijos()
= inicializa todos los hijos del nodo.
Clase Arbol
h
Especificación de la clase:
Clase que
especifica la implementación del árbol sintáctico
h
Métodos y variables
public:
§
Arbol() = constructor
por defecto.
§
Arbol(nodo * n) = que
recibe un nodo y lo señala como raiz.
§
nodo * getraiz() {return raiz;}
= devuelve un puntero a la raiz.
§
void setraiz(nodo
* n) = establece el nodo que recibe como parámetro como la raiz
del arbol.
§
int insnodo(nodo
* padre, nodo *hijo) = devuelve 1 si lo inserta el nodo y cero si no.
§
void imprimearbol()
= imprime recursivamente todos los nodos del arbol.
private:
§
nodo * raiz = raiz del arbol.
§
void imprimearbolr(int tabulado, nodo * act) =
procedimiento recursivo privado llamado por imprimearbol().
Especificación del programa
El programa de la tarea # 2 era una calculadora que tomaba las expresiones insertadas, las convertía a de infijo a posfijo e imprimía el resultado de la evaluación en posfijo de la misma.
Al modificar el programa se
agregan dos clase nuevas nodo y Arbol, con las cuales
se implementa una estructura de árbol sintáctico ,
para la cual cada nodo contiene una producción de la gramática de la calculadora.
El árbol incluye un método que lo
imprime de forma identada es decir, imprime a los
hijos de un nodo con una tabulación más, con lo que se muestra cual nodo es
hijo de otro, y como está creado el árbol sintáctico.
Implementación
Modelo de la clase
o
Nodo:
o
Árbol:
Compilador Usado
Visual C++ 6.0
Microsoft Compiler.
Cómo compilar el programa
Se proveen tres
archivos necesarios para la compilación del programa: Tarea3.cpp, Astring.cpp y Astring.h.
Para compilar el
programa simplemente se debe crear un nuevo proyecto de consola en Visual C++ y
luego agregar al proyecto los tres archivos proveídos. Por último se compila el
archivo Tarea3.cpp y se construye el ejecutable para
ver así el producto final.
Guía de uso del programa
- EL programa
solicita Introducir la expresión.
- Se despliega
el resultado. Los resultados se
pueden observar en la sección salida del
programa.
Bibliografía
Aho, A. et al. Compiladores: principios,
técnicas y herramientas. Addison Wesley.1990