Graficar expresiones aritméticas con Graphviz, Java, Jlex y Cup

En este tutorial se desarrolla un ejemplo sencillo de un intérprete que recibe como entrada un archivo de texto que contiene varias expresiones aritméticas que son evaluadas y posteriormente graficadas por Graphviz, para ello se hace análisis léxico y sintáctico de dicha entrada, los analizadores se generan con Jlex y Cup. Es importante mencionar que para que el ejemplo funcione correctamente debe estar instalado Graphviz. Para desarrollar el proyecto se utilizó Ubuntu 14.04 y Netbeans 8.0. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Graficar expresiones aritméticas con Graphviz, Java, Jlex y Cup

Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.

Si desean, una pequeña introducción al uso de Jlex y Cup pueden visitar mi post: Mi primer proyecto utilizando Jlex y Cup.

Instalación de Graphviz

Lo primero que haremos será instalar Graphviz, para ello abrimos una terminal, en Ubuntu puede hacerse con la combinación de teclas Ctrl+Alt+t o en Aplicaciones → Accesorios → Terminal, una vez abierta la terminal ingresamos el comando “sudo apt-get install graphviz”, autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Graphviz. 

 

Funcionamiento del proyecto

La aplicación recibe como entrada un archivo que se encuentra en la carpeta del proyecto, dicho archivo se llama “entrada.txt” y contiene lo siguiente:

Evaluar[1+1];
Evaluar[1+1*2];
Evaluar[1.5+1.25*6.4/3.3-5.2+7.1];
Evaluar[1.1+1.2*6.3/3.4-5+1*-2.12345];
Evaluar[(2+2)*3+(1-1)];

Al ejecutar la aplicación, esta le hace análisis léxico y sintáctico al archivo de entrada, evalúa las expresiones aritméticas e indica el resultado de la expresión y el nombre del archivo en el que se generó la imagen. 
 

Veremos que se generan una serie de archivos .dot y una serie de archivos .jpg, los archivos dot, contienen el código con el que Graphviz genera la imagen jpg correspondiente.

A continuación se muestra el detalle de las imágenes que se generaron para cada línea del archivo de entrada.

Evaluar[1+1];

Evaluar[1+1*2];

Evaluar[1.5+1.25*6.4/3.3-5.2+7.1];

Evaluar[1.1+1.2*6.3/3.4-5+1*-2.12345];

Evaluar[(2+2)*3+(1-1)];

La magia detrás de todo esto: Árbol de sintaxis abstracta (AST)

Un árbol de sintaxis abstracta (AST) es una representación simplificada de la estructura sintáctica del código fuente. A nivel de programación un AST es una estructura de datos que se genera durante el proceso de análisis sintáctico.

En este ejemplo el AST es la pieza más importante porque con él pueden ejecutarse las principales funciones que son: evaluar la expresión y graficar la expresión.

En este ejemplo el AST se construye al hacer análisis sintáctico al archivo de entrada, esta estructura es un árbol binario, ya que cada nodo puede tener como máximo dos hijos y modela bien el funcionamiento de las expresiones aritméticas porque todas sus operaciones tienen dos operandos y el caso del operador “-” de las expresiones negativas que tiene un solo operando.

Hacemos análisis sintáctico una sola vez para cargar el árbol, posteriormente podemos recorrer ese árbol las veces que deseemos, podemos manipularlo y hacer muchas cosas sin necesidad de hacer nuevamente análisis sintáctico al archivo de entrada.

En este caso, el árbol se carga y posteriormente se recorre para evaluar la expresión aritmética y mostrar en consola el resultado. Se recorre nuevamente el árbol para generar el código de Graphviz y guardarlo en un archivo .dot, con el archivo .dot podemos pedirle a Graphviz que cree el diagrama de la expresión aritmética.

Todos los métodos que realizan estas acciones luego de cargar el árbol se encuentran en la clase “Nodo”, del paquete “arbol”. El método getValor, devuelve el resultado de la expresión aritmética evaluada. El método graficar, genera el diagrama de la expresión aritmética y devuelve el nombre del archivo generado.

Si les gusto este tutorial, puede que también estén interesados en este otro: Intérprete sencillo utilizando Java, Jlex y Cup.

Para tener acceso a más temas como este, pueden unirse a este blog, solo tienen que hacer clic en el botón “Participar en este sitio” que se encuentra del lado derecho de esta página.

Fuentes consultadas:

Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición