Java Compiler Compiler es un generador de analizadores para utilizar en java. Este generador es una herramienta que lee la especificación gramatical y la convierte en un programa de java que puede reconocer coincidencias con la gramática. Además del generador de analizadores en sí, JavaCC proporciona otras capacidades estándar relacionadas con la generación de analizadores, como la construcción de árboles (a través de una herramienta llamada JJTree incluida con JavaCC), acciones y depuración. Todo lo que se necesita para ejecutar un analizador JavaCC, una vez generado, es Java Runtime Environment (JRE).
Características
JavaCC utiliza un analizador descendente lo que permite el uso de gramáticas más generales.
Por defecto JavaCC genera un analizador LL(1), aunque JavaCC ofrece capacidades de anticipación sintáctica para resolver ambigüedades.
JavaCC permite la utilización de BNF Extendido, o lo que vendría siendo utilizar expresiones regulares tanto en la parte léxica como gramatical.
JavaCC permite la utilización de estados para manejar de mejor forma las expresiones regulares.
Para más información visitar la página oficial de JavaCC.
Prerrequisitos
Para este este ejemplo necesitamos las siguientes herramientas
Debemos asegurarnos de que la carpeta bin del JDK haya sido agregada a nuestra variable de entorno Path, para ello vamos a la configuración de dicha variable de entorno
Clic derecho en Este equipo
Propiedades
Configuración avanzada del sistema
Variables de entorno
Variable Path
Editar
y si no existe agregamos la ruta a la carpeta bin del JDK, que en mi caso es:
1
C:\Program Files\Java\jdk1.8.0_211\bin
Descarga e instalación de JavaCC
Nos dirigimos a la página oficial de JavaCC, al ingresar hacemos clic sobre el botón de Download[Version].zip
Una vez descargado el archivo, lo extraemos y podremos ver el siguiente contenido:
El archivo que nos interesa es javacc.jar que se encuentra en la carpeta bootstrap:
Por conveniencia, vamos a trasladar el archivo .jar a la carpeta C:/javacc, sin embargo, podría guardarse en otra ubicación.
Mas adelante le daremos uso a nuestro archivo javacc.jar.
Crear el proyecto utilizando NetBeans
Como mencionamos vamos a utilizar NetBeans, sin embargo podría usarse cualquier otro IDE. Vamos a mostrar la creación del proyecto y su estructura.
Seleccionamos la opción de nuevo proyecto.
Ahora seleccionamos el tipo de proyecto, en este caso Java Application y damos clic en siguiente.
Por último, agregamos el nombre del proyecto y finalizamos.
Vemos el resultado de la creación del proyecto.
A continuación, creamos un nuevo paquete llamado Analizador, produciendo el siguiente resultado.
Dentro de este paquete vamos a crear un nuevo archivo llamado Gramatica.jj, este archivo contendrá la gramática para reconocer el lenguaje que vamos a realizar.
Para facilitar la compilación de la gramática vamos a crear un archivo compilarGramatica.bat, con el siguiente contenido, siempre en el paquete Analizador.
Agregar el archivo jar al classpath mediante el argumento -cp (classpath) – -cp C:\javacc\javacc.jar (o la ubicación de nuestro archivo javacc.jar)
Ejecutar java – java
Pasar el main del archivo jar – javacc
Pasar la gramática a compilar – Gramatica.jj
Evitar que se cierre la ventana de comando para ver el resultado – pause
Nota: utilizamos el argumento classpath para indicarle a java donde debe buscar los paquetes y clases a ejecutar, mas información en el siguiente link.
Construcción del lenguaje en JavaCC
Luego de esta introducción vamos a construir una programa que reconozca un lenguaje compuesto por una lista de instrucciones Evaluar que reciben una expresión aritmética para ser evaluada, por ejemplo:
1
Evaluar [3*4-2*9]
Explicación de la estructura del archivo Gramatica.jj
Sección de opciones: Esta sección es opcional, el área de opciones permite especificar algunas directrices que ayuden a JavaCC a generar analizadores léxico-sintácticos más eficientes y adaptados a las necesidades concretas del desarrollador. Existen muchas, si quieres conocerlas mejor puedes verificar la página 132 del libro Compiladores, de Sergio Gálvez Rojas Y Miguel Ángel Mora Mata. En este caso particular utilizamos solamente dos:
Ignore_Case = true, para no hacer distinción entre mayúsculas y minúsculas.
Static = false, para que los métodos que genere la compilación no sean estáticos.
1 2 3 4
options { IGNORE_CASE = true; STATIC = false; }
Clausulas PARSER_BEGIN – PARSER_END: Sirven para indicarle a JavaCC el nombre de nuestra clase principal, así como para englobar tanto a esta como a cualquier otra que se quiera incluir de apoyo. En este ejemplo no definimos ningun método main, solo una clase llamada gramática para nuestro parser, por supuesto que esta clase gramática es la que debemos utilizar para invocar a nuestro parser, y el main lo incluimos fuera de este para tener un código más claro.
1 2 3 4 5 6
PARSER_BEGIN(Gramatica) /** Analizador de expresiones aritmeticas sencillas. */ package Analizador; public class Gramatica { } PARSER_END(Gramatica)
Sección para definición léxica: Esta sección contendrá los tokens permitidos por nuestro lenguaje, contiene distintas clausulas, pero las que utilizamos son:
Token: Constituyen los tokens que nuestro analizador va a reconocer, generalmente aquí se incluyen todos los terminales de nuestro lenguaje, aunque también se pueden utilizar tokens en la definición sintáctica sin haberlos definido en esta sección.
Skip: En esta sección se incluyen los tokens que se van a ignorar durante el análisis, por ejemplo, los espacios o saltos de línea.
Sección para definición sintáctica: Aquí vamos a definir las producciones para nuestro analizador, estas están definidas como funciones. A continuación explicamos la estructura:
Como buena práctica es recomendable agregar en un comentario la producción en formato BNF para que sea más fácil entender la producción actual, ya que las reglas sintácticas en JavaCC pueden ser un poco confusas.
La definición de un método incluye:
1 2 3
<TIPO> <NOMBRE> () : {Sección para código de java, generalmente para declaraciones} {Producciones, estas pueden incluir notación de expresiones regulares}
Si quisiéramos invocar a otra producción, agregamos su llamada a método y para obtener su valor lo hacemos de la siguiente manera
1 2 3 4 5 6
/** Instruccion -> evaluar [ Expresion ]; */ void Instruccion() : {double e;} { <EVALUAR> <CORI> e=Expresion() <CORD> <PCOMA> {System.out.println("El valor de la expresion es: "+e);} }
En tal caso necesitásemos obtener el valor de un terminal, debemos utilizar el atributo image, ya que cada terminal es un objeto de tipo Token, para obtenerlo hacemos lo siguiente
Algo a tomar en cuenta es que, podemos declarar variables de tipo Token y asignarlas al terminal, esto es por si tuviéramos varios terminales en una misma producción y así sepamos diferenciar cada uno.
Compilación de la gramática
Una vez finalizado nuestro archivo Gramatica.jj, vamos a compilar este para generar los archivos necesarios para su ejecución, vamos a utilizar el archivo compilarGramatica.bat creado al inicio. Al ejecutar el archivo veremos lo siguiente:
Como resultado de esto, en nuestro paquete analizador se crearon los siguientes archivos
Gramatica.java: Este archivo contiene las funciones de cada no terminal de la sección sintáctica
GramaticaConstanst.java: Esta interfaz contiene las constantes de tipo entero que identifican a cada token de nuestro lenguaje y son asignadas a las variables kind.
Token.java: Representa cada token definido en nuestra sección léxica.
Clase Principal
Por último, vamos a invocar a nuestro parser en el método main, para utilizar nuestro parser basta con crear la clase Gramatica y pasar por parámetro nuestro archivo de entrada, luego de crear la instancia invocamos al método inicial que en nuestro caso sería el método analizar.
Ejecutamos nuestro programa y vemos la siguiente salida:
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Pavel Vásquez, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.
En este tutorial se desarrolla un ejemplo sencillo en el que se grafica un árbol binario de búsqueda con ayuda de la herramienta Graphviz. Es importante mencionar que para que ejemplo funcione correctamente debe estar instalado Graphviz. Este proyecto se desarrolló utilizando Ubuntu 14.04 y Netbeans 8.0. El proyecto completo del ejemplo puede descargarse del siguiente enlace:
Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.
Instalación de Graphviz
Lo primero que haremos será instalar Graphviz, en caso de que no lo hayamos instalado todavía, 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
El proyecto cuenta con la clase ArbolBinarioBusqueda, en el método principal de la aplicación, se instancian dos objetos de esta clase, es decir, dos árboles binarios de búsqueda, el primero almacena únicamente texto y el segundo únicamente números. El código de la clase principal de la aplicación es el siguiente:
/* * Ejemplo desarrollado por Erick Navarro * Blog: e-navarro.blogspot.com * Octubre - 2015 */
package abbgraphviz;
import abb.ArbolBinarioBusqueda;
/** * Clase principal de la aplicación. * @author Erick Navarro */ public class ABBGraphviz {
/** * Método principal de la aplicación * @param args los argumentos de la línea de comando */ public static void main(String[] args) { //Creamos un árbol cuyos nodos contendrán solamente texto ArbolBinarioBusqueda arbol_texto=new ArbolBinarioBusqueda(); //Llenamos con información el árbol arbol_texto.insertar("Juan"); arbol_texto.insertar("Pedro"); arbol_texto.insertar("María"); arbol_texto.insertar("Roberto"); arbol_texto.insertar("Teodoro"); arbol_texto.insertar("Manuel"); arbol_texto.insertar("Diego"); arbol_texto.insertar("Alejandro"); //Graficamos el árbol generando la imagen arbol_texto.jpg arbol_texto.graficar("arbol_texto.jpg"); //Imprimimos el contenido del árbol ordenado arbol_texto.inorden(); System.out.println(); //Creamos un árbol cuyos nodos contendrán solamente numeros ArbolBinarioBusqueda arbol_numeros=new ArbolBinarioBusqueda(); //Llenamos con información el árbol arbol_numeros.insertar(12); arbol_numeros.insertar(5); arbol_numeros.insertar(26); arbol_numeros.insertar(33); arbol_numeros.insertar(59); arbol_numeros.insertar(27); arbol_numeros.insertar(15); //Graficamos el árbol generando la imagen arbol_numeros.jpg arbol_numeros.graficar("arbol_numeros.jpg"); //Imprimimos el contenido del árbol ordenado arbol_numeros.inorden(); } }
Al ser ejecutada la aplicación, se generan dos imagenes, una para cada árbol la primera arbol_texto.jpg corresponde al árbol que solo almacena texto en sus nodos.
La segunda arbol_numeros.jpg corresponde al árbol que solo almacena números.
En la consola se verán los elementos de ambos árboles impresos en orden, esto se logra haciendo un recorrido enorden de los arboles binarios de búsqueda.
Árbol binario de búsqueda
En un árbol binario, todos los nodos tienen como máximo dos hijos.
“Un árbol binario de búsqueda es aquel que dado un nodo, todos los datos del subárbol izquierdo son menores que los datos de ese nodo, mientras que todos los datos del subárbol derecho son mayores que sus propios datos.”
Fuente: Programación en Java 2. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.
En este árbol únicamente se desarrolla el método para insertar nodos, porque el objetivo de la aplicación es únicamente graficar el árbol, adicionalmente, podrían desarrollarse métodos para eliminar nodos, buscar nodos, vaciar el árbol, calcular la profundidad del árbol, etc. El único recorrido que se hace del árbol es el enorden, que muestra los nodos del árbol ordenados, pero existen otros recorridos que también podrían implementarse como el recorrido preorden, postorden o el recorrido por anchura.
Interfaz Comparable: El secreto tras la flexibilidad de este árbol
La razón por la cual este árbol puede utilizarse para almacenar cadenas o bien para almacenar números es la interfaz Comparable. Lo que almacena el nodo es la instancia de una clase que implementa la interfaz Comparable, por supuesto que todos los nodos tienen que poder compararse satisfactoriamente, por ejemplo no se podrían almacenar números enteros y también cadenas de caracteres en un mismo árbol, ya que no podrían comparase satisfactoriamente porque se daría un problema de tipos. Pero si todos los nodos almacenan números, el árbol funciona sin problemas, al igual cuando todos los nodos almacenan cadenas.
Si deseáramos almacenar otro tipo de información podríamos programar una clase que contenga los atributos que deseamos y que implemente la interfaz Comparable, entonces sin modificar el árbol podríamos almacenar esta información.
Fuentes consultadas:
Programación en Java 2. Algoritmos, estructuras de datos y programación orientada a objetos. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.
En este tutorial se desarrolla un ejemplo sencillo en el que se grafica un árbol AVL con ayuda de la herramienta Graphviz. Es importante mencionar que para que ejemplo funcione correctamente debe estar instalado Graphviz. Este proyecto se desarrolló utilizando Ubuntu 14.04 y Netbeans 8.0. El proyecto completo del ejemplo puede descargarse del siguiente enlace:
Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.
Instalación de Graphviz
Lo primero que haremos será instalar Graphviz, en caso de que no lo hayamos instalado todavía, 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
El proyecto cuenta con la clase ArbolAVL, en el método principal de la aplicación, se instancian dos objetos de esta clase, es decir, dos árboles AVL, el primero almacena únicamente texto y el segundo únicamente números. El código de la clase principal de la aplicación es el siguiente:
/* * Ejemplo desarrollado por Erick Navarro * Blog: e-navarro.blogspot.com * Octubre - 2015 */
package avlgraphviz;
import avl.ArbolAVL;
/** * Clase principal de la aplicación. * @author Erick Navarro */ public class AVLGraphviz {
/** * Método principal de la aplicación * @param args los argumentos de la línea de comando. */ public static void main(String[] args) { //Creamos un árbol cuyos nodos contendrán solamente texto ArbolAVL arbol_texto=new ArbolAVL(); //Llenamos con información el árbol arbol_texto.insertar("Juan"); arbol_texto.insertar("Pedro"); arbol_texto.insertar("María"); arbol_texto.insertar("Roberto"); arbol_texto.insertar("Teodoro"); arbol_texto.insertar("Manuel"); arbol_texto.insertar("Diego"); arbol_texto.insertar("Alejandro"); arbol_texto.insertar("Margarita"); arbol_texto.insertar("Luis"); arbol_texto.insertar("Hernán"); arbol_texto.insertar("Jaime"); arbol_texto.insertar("Ana"); arbol_texto.insertar("Francisco"); arbol_texto.insertar("Andrea"); //Graficamos el árbol generando la imagen arbol_texto.jpg arbol_texto.graficar("arbol_texto.jpg"); //Imprimimos el contenido del árbol ordenado arbol_texto.inorden(); System.out.println(); //Creamos un árbol cuyos nodos contendrán solamente numeros ArbolAVL arbol_numeros=new ArbolAVL(); //Llenamos con información el árbol arbol_numeros.insertar(12); arbol_numeros.insertar(5); arbol_numeros.insertar(26); arbol_numeros.insertar(33); arbol_numeros.insertar(59); arbol_numeros.insertar(27); arbol_numeros.insertar(15); arbol_numeros.insertar(47); arbol_numeros.insertar(74); arbol_numeros.insertar(84); arbol_numeros.insertar(88); arbol_numeros.insertar(90); arbol_numeros.insertar(124); arbol_numeros.insertar(612); //Graficamos el árbol generando la imagen arbol_numeros.jpg arbol_numeros.graficar("arbol_numeros.jpg"); //Imprimimos el contenido del árbol ordenado arbol_numeros.inorden(); } }
Al ser ejecutada la aplicación, se generan dos imagenes, una para cada árbol la primera arbol_texto.jpg corresponde al árbol que solo almacena texto en sus nodos.
La segunda arbol_numeros.jpg corresponde al árbol que solo almacena números.
En la consola se verán los elementos de ambos árboles impresos en orden, esto se logra haciendo un recorrido enorden de los arboles AVL.
Árbol AVL
El árbol AVL es un árbol binario de búsqueda equilibrado. Recibió el nombre del árbol AVL en honor de Adelson, Velskii y Landis, que fueron los primeros científicos en estudiar esta estructura de datos. “Un árbol AVL es un árbol binario de búsqueda en el que las alturas de los subárboles izquierdo y derecho de cualquier nodo difieren como máximo en 1.”
Fuente: Algoritmos y estructuras de datos, una perspectiva en C. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.
En este árbol únicamente se desarrolla el método para insertar nodos, porque el objetivo de la aplicación es únicamente graficar el árbol, adicionalmente, podrían desarrollarse métodos para eliminar nodos, buscar nodos, vaciar el árbol, calcular la profundidad del árbol, etc. El único recorrido que se hace del árbol es el enorden, que muestra los nodos del árbol ordenados, pero existen otros recorridos que también podrían implementarse como el recorrido preorden, postorden o el recorrido por anchura.
Interfaz Comparable: El secreto tras la flexibilidad de este árbol
La razón por la cual este árbol puede utilizarse para almacenar cadenas o bien para almacenar números es la interfaz Comparable. Lo que almacena el nodo es la instancia de una clase que implementa la interfaz Comparable, por supuesto que todos los nodos tienen que poder compararse satisfactoriamente, por ejemplo no se podrían almacenar números enteros y también cadenas de caracteres en un mismo árbol, ya que no podrían comparase satisfactoriamente porque se daría un problema de tipos. Pero si todos los nodos almacenan números, el árbol funciona sin problemas, al igual cuando todos los nodos almacenan cadenas. Si deseáramos almacenar otro tipo de información podríamos programar una clase que contenga los atributos que deseamos y que implemente la interfaz Comparable, entonces sin modificar el árbol podríamos almacenar esta información.
Fuentes consultadas
Algoritmos y estructuras de datos, una perspectiva en C. Luis Joyanes Aguilar, Ignacio Zahonero Martínez.
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:
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:
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.
1
Evaluar[1+1];
1
Evaluar[1+1*2];
1
Evaluar[1.5+1.25*6.4/3.3-5.2+7.1];
1
Evaluar[1.1+1.2*6.3/3.4-5+1*-2.12345];
1
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:
El chat que se muestra en esta publicación utiliza sockets para la comunicación, se desarrolló utilizando Java 1.8 y NetBeans 8.0. El ejemplo está formado por dos aplicaciones, el cliente y el servidor, ambas pueden descargarse de los siguientes enlaces:
Todo el código dentro ambos proyectos está documentado con comentarios que explican su funcionamiento.
Funcionamiento del chat
Para que el chat funcione correctamente, debe ejecutarse primero la aplicación servidor, en la que el cliente debe ingresar el puerto por el cual el servidor escuchara las conexiones de los clientes que participen en el chat. Puede dejarse el puerto por defecto o puede indicarse uno diferente, que no esté siendo utilizado por ninguna otra aplicación.
Si el servidor inicia correctamente se mostrará una ventana como la siguiente.
En este punto ya podremos ejecutar aplicaciones cliente que se conecten al chat, al ejecutar la aplicación cliente nos pedirá la IP de la máquina en la que se ejecuta la aplicación servidor, por defecto tiene la dirección de localhost, en este caso se utiliza esta porque el servidor y todos los clientes se están ejecutando en la misma máquina. Además de la dirección IP, se debe ingresar el puerto por el que el servidor escucha las conexiones de los clientes y el nombre del usuario que se desea conectar.
Si la conexión es correcta, entonces se muestra una ventana que tiene una JTextArea en la que se muestra el historial de las conversaciones, un JComboBox que muestra el listado de los usuarios conectados a los que se puede enviar mensajes, un JTextField en el que se puede ingresar los mensajes a enviar y un JButton para enviar el mensaje.
Si solamente está conectado un cliente, no habrá nadie a quien se le pueda enviar mensajes, si el cliente intentara enviar uno se mostraría el siguiente mensaje de información.
Al ejecutar más de un cliente estos ya podrán comunicarse entre sí.
Luego de que los clientes envíen y reciban múltiples mensajes se tiene algo como lo siguiente.
Si se cierran las ventanas, la aplicación cliente considerará que el usuario está cerrando sesión y enviará una notificación al servidor para elimine a este cliente de la lista de clientes y notifique al resto de los usuarios conectados que deben eliminarlo de su lista de contactos.
En la aplicación servidor se muestra un log, en el que se informa cuando un usuario inicia o cierra sesión.
Si el servidor se cierra repentinamente, mientras aún hay clientes conectados, estas aplicaciones cliente se cerrarán luego de mostrar el siguiente mensaje.
Si se intenta ejecutar una aplicación cliente sin haber ejecutado antes la aplicación servidor o se ingresa una dirección IP o un puerto equivocado se mostrará el siguiente mensaje.
Lógica del chat
El chat consiste de dos aplicaciones, el cliente y el servidor, el servidor se ejecuta una vez y el cliente se ejecuta N veces, donde N es el número de usuarios que participarán en el chat, todos los mensajes que los usuarios del chat se envían entre sí pasan a través del servidor, cuando un cliente quiere enviar un mensaje a otro, le envía el mensaje al servidor indicándole su destinatario y el servidor se encarga de reenviar este mensaje, el servidor también se encarga de indicarle a todos los usuarios cuando un usuario nuevo se conecta al chat, para que puedan incluirlo en su lista de contactos y por ende en la conversación. Asimismo, cuando un cliente se desconecta, el servidor se encarga de informar a todos los usuarios que deben eliminar al cliente que cerró su sesión de la lista de contactos porque ya no podrán enviarle mensajes. No hay comunicación directa entre clientes, el servidor siempre es intermediario entre la comunicación de los clientes. Si se ejecutara el servidor y luego se ejecutaran cuatro clientes que se conectaran a dicho servidor, la comunicación sería como se muestra en la siguiente imagen.
Funcionamiento del servidor
El servidor tiene tres clases, que se describen a continuación:
VentanaS: esta clase gestiona la interfaz gráfica del servidor, que básicamente muestra un log de las principales acciones del servidor (conexión y desconexión de clientes).
Servidor: Esta clase gestiona a los clientes que se conectan al servidor, es un hilo que tiene como principal función escuchar constantemente en caso de que algún nuevo cliente quiera conectarse al chat.
HiloCliente: Cada vez que un nuevo cliente se conecta, dentro de la clase servidor se instancia un nuevo HiloCliente y se agrega a la lista de clientes. Este hilo cuenta con un socket con el que puede enviar y recibir mensajes del cliente con el que está conectado y tiene como principal función escuchar constantemente en caso de que el cliente envíe mensajes.
A continuación se muestra una imagen que ilustra el funcionamiento de la aplicación servidor.
Funcionamiento del cliente
El cliente tiene dos clases, que se describen a continuación:
VentanaC: esta clase gestiona la interfaz gráfica del servidor, que básicamente muestra una lista de contactos, un historial de conversación, una caja de texto para ingresar nuevos mensajes y un botón que permite enviar mensajes.
Cliente: Cuando el cliente se instancia y se conecta con el servidor, se crea un hilo que está escuchar constantemente en caso de que el servidor envíe mensajes. Este cliente cuenta con un socket con el que puede enviar y recibir mensajes del servidor con el que está conectado.
A continuación se muestra una imagen que ilustra el funcionamiento de la aplicación cliente.
En los cursos de compiladores de la universidad, es bastante común que se solicite al estudiante desarrollar un intérprete, una herramienta que reciba como entrada cierto lenguaje de programación y lo ejecute, pero la mayoría de documentación al respecto solo muestra ejemplos de cosas sencillas, como una calculadora o un lenguaje que imprime cadenas en consola. Pero qué pasa si lo que deseamos es que se ejecuten sentencias de control como el IF o ciclos como la sentencia WHILE y que además estas sentencias soporten muchos niveles de anidamiento, que se declaren variables y se asigne valores a estas variables, que se tenga control de los ámbitos de las variables, en fin, que tenga las funciones básicas de un lenguaje de programación. No es común encontrar este tipo de ejemplos, en lo personal, puedo asegurar que nunca encontré un tutorial en el que se mostrara un ejemplo documentado y bien explicado sobre esto. Es por eso que les traigo este ejemplo, espero que les sea útil.
Funcionamiento de la aplicación
En este tutorial se desarrolla un intérprete que recibe como entrada un archivo de texto que contiene varias sentencias en un lenguaje programación diseñado especialmente para esta aplicación, primero se hace análisis léxico y sintáctico de dicha entrada, durante el análisis sintáctico se carga en memoria un Árbol de Sintaxis Abstracta (AST) que se utiliza posteriormente para ejecutar las sentencias. Los analizadores se generan con Jlex y Cup. Se desarrollaron dos versiones del proyecto, una utilizando Windows 10 y otra utilizando Ubuntu 14.04. El proyecto completo del ejemplo puede descargarse de los siguientes enlaces:
Dentro de la carpeta del proyecto, hay un archivo de entrada llamado “entrada.txt”, en él se muestran ejemplos de todas las funciones del lenguaje diseñado para esta aplicación, al leerlo se puede tener una idea clara de las funciones con las que el lenguaje cuenta, este archivo contiene lo siguiente:
/****************************************** * Ejemplo desarrollado por Erick Navarro * * Blog: e-navarro.blogspot.com * * Septiembre - 2015 * ******************************************/
//Se imprime el encabezado imprimir("Tablas de" & " multiplicar");
//Se declara la variable a, de tipo numero numero a; //Se asigna a la variable a el valor 0 a=0; //Se declara la variable c, de tipo numero numero c; //Se asigna a la variable c el valor 0 c=1; //Se imprime un separador imprimir("----------------"); /** * Se imprimen las tablas del 1 al 5 y * para cada tabla, se imprimen los resultados * desde el uno hasta el 5, esto se hace con * dos ciclos while anidados. **/ mientras(a<4+c){ a=a+1; numero b; b=0; mientras(b<4+c){ b=b+1; imprimir(a & " * " & b & " = " & a * b); } imprimir("----------------"); }
//Se asigna a la variable a el valor de 11 a=11; /** * La variable b ya había sido declarada pero * dentro del ámbito del primer ciclo while, * entonces no existe en este ámbito por lo que * debe declararse. **/ numero b; //Se asigna valor de 12 a b y valor de 13 a c b=12; c=13; /** * Se evalua si el valor de la variable a es * mayor que 10, si el b es mayor que 11 y si * el de c es mayor que 12. **/ If(a>10){ imprimir("a es mayor que 10."); if(b>11){ imprimir("a es mayor que 10 y b es mayor que 11."); if(c>12){ imprimir("a es mayor que 10, b es mayor que 11 y c es mayor que 12."); } } }else{ imprimir("a es menor o igual que 10."); }
Como se puede observar, el lenguaje acepta:
Comentarios de muchas líneas (//).
Comentarios de una línea (//).
Concatenación de cadenas, mediante el operador “&”.
Función “imprimir”: que recibe como parámetro una cadena e imprime en consola dicha cadena.
Declaración de variables: el único tipo de variables que el lenguaje soporta es “numero”, que es una variable de tipo numérico que suporta números enteros o con punto decimal (Dentro del rango del tipo Double de Java).
Asignación de variables, a cualquier variable se le puede asignar cualquier expresión que tenga como resultado un número.
Instrucción “mientras”: tiene el comportamiento clásico del ciclo while, ejecuta el ciclo mientras la expresión booleana que recibe sea verdadera. Esta instrucción soporta anidamiento.
Instrucción “if” e instrucción “if-else”: si la expresión booleana que recibe es verdadera entonces ejecuta las instrucciones contenidas en el “if”, si es falsa y la instrucción tiene un “else” entonces se ejecutan las instrucciones contenidas en el “else”. Esta instrucción soporta anidamiento.
Expresiones aritméticas: Estas expresiones soportan sumas, restas, divisiones, multiplicaciones, expresiones negativas y paréntesis para agrupar operaciones. Tiene la precedencia habitual de las expresiones aritméticas.
Expresiones booleanas: comparan dos expresiones que tengan como resultado un número y soportan únicamente los operadores mayor que y menor que (<, >).
El resultado de la ejecución
Al ejecutar el archivo de entrada mostrado anteriormente se obtiene el siguiente resultado en consola:
run: Tablas de multiplicar ---------------- 1.0 * 1.0 = 1.0 1.0 * 2.0 = 2.0 1.0 * 3.0 = 3.0 1.0 * 4.0 = 4.0 1.0 * 5.0 = 5.0 ---------------- 2.0 * 1.0 = 2.0 2.0 * 2.0 = 4.0 2.0 * 3.0 = 6.0 2.0 * 4.0 = 8.0 2.0 * 5.0 = 10.0 ---------------- 3.0 * 1.0 = 3.0 3.0 * 2.0 = 6.0 3.0 * 3.0 = 9.0 3.0 * 4.0 = 12.0 3.0 * 5.0 = 15.0 ---------------- 4.0 * 1.0 = 4.0 4.0 * 2.0 = 8.0 4.0 * 3.0 = 12.0 4.0 * 4.0 = 16.0 4.0 * 5.0 = 20.0 ---------------- 5.0 * 1.0 = 5.0 5.0 * 2.0 = 10.0 5.0 * 3.0 = 15.0 5.0 * 4.0 = 20.0 5.0 * 5.0 = 25.0 ---------------- a es mayor que 10. a es mayor que 10 y b es mayor que 11. a es mayor que 10, b es mayor que 11 y c es mayor que 12. BUILD SUCCESSFUL (total time: 0 seconds)
Sobre la tabla de símbolos
La tabla de símbolos es una parte importante en el proceso de ejecución del código, es en esta estructura de datos en donde guardamos información de las variables como su tipo, identificador y valor. A esta estructura podemos pedirle el valor de una variable, o pedirle que le asigne cierto valor a una variable.
Es importante mencionar que en el proceso de ejecución la tabla de símbolos va cambiando de forma dinámica, esto con el objetivo de manejar los ámbitos, por ejemplo, la instrucción WHILE tiene su propio ámbito, lo que significa que su tabla de símbolos contiene información de las variables declaradas en ámbitos superiores y la información de las variables declaradas en el ámbito local de la instrucción, al terminar de ejecutar la instrucción, todas las variables declaradas en el ámbito local se eliminan de la tabla de símbolos que almacena la información de los ámbitos superiores, de tal manera que los ámbitos superiores no tendrán acceso a las variables declaradas dentro del WHILE.
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 al recorrerlo pueden ejecutarse las acciones del código de entrada y ese es el principal objetivo de la aplicación.
En el código fuente de Cup se observa que la mayoría de las acciones se enfocan en cargar el AST, básicamente es lo único que hace el analizador, además de verificar que la sintaxis de la entrada sea correcta
La estructura en este caso es un tanto compleja ya que cada nodo puede tener muchos hijos, en el caso de las instrucciones IF-ELSE y WHILE, el número de hijos es incierto ya que estas instrucciones pueden contener muchas otras instrucciones dentro, lo cierto es que el árbol se acopla muy bien al lenguaje de programación porque en el árbol se tiene bien claro qué instrucciones están contenidas dentro de otras instrucciones, porque cada nodo esta directamente ligado a sus hijos, entonces la ejecución de instrucciones anidadas no representa mayor problema.
Hacemos análisis sintáctico una sola vez para cargar el árbol, posteriormente recorremos ese árbol para ejecutar el código.
El árbol es una representación exacta de lo que el código de entrada contiene. Las únicos tres paquetes del proyecto son:
analizadores: que contiene los archivos de Cup y JLex y los analizadores que con estas herramientas se generaron.
arbol: que contiene todas las clases que forman parte del AST, que se utiliza como estructura primaria en la aplicación.
interpretesencillo: que contiene la clase principal de la aplicación.
Fuentes consultadas:
Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.
JLex es un generador de analizadores léxicos, escrito en Java, para Java. JLex fue desarrollado por Elliot Berk en la Universidad de Princeton. Para más información visitar la página oficial de JLex.
La principal tarea de un analizador léxico es leer los caracteres de entrada del programa fuente, agruparlos en lexemas y producir como salida una secuencia de tokens.
Un token es un par que consiste en un nombre de token y un valor de atributo opcional.
Un lexema es una secuencia de caracteres en el programa fuente, que coinciden con el patrón para un token y que el analizador léxico identifica como una instancia de este tóken.
Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.
En JLex se definen los patrones de los diferentes tokens que se desean reconocer, estos patrones pueden definirse a través de expresiones regulares. Además JLex cuenta con múltiples opciones, una muy imporante es su capacidad para integrarse con generadores de analizadores sintácticos como Cup.
Cup
Cup es un generador de analizadores sintácticos de tipo LALR para Java.
El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generase con la gramática para el lenguaje fuente. Una gramática proporciona una especificación precisa y fácil de entender de un lenguaje de programación.
Pre-requisitos
Para este ejemplo hace falta que tengamos instalado:
Debemos asegurarnos que la carpeta bin del JDK haya sido agregada a nuestra variable de entorno Path, para ello vamos a la configuración de dicha variable de entorno (Clic derecho en This PC → Properties → Advanced system settings → Environment Variables → Variable Path → Edit) y si no existe agregamos la ruta a la carpeta bin del JDK, que en mi caso es: C:\Program Files\Java\jdk1.8.0_152\bin
Descargar JLex
Lo primero que haremos será descargar JLex, para ello vamos a la página oficial y descargamos la versión actual del software:
Vamos a obtener el archivo Main.java:
Descargar Cup
Para descargar Cup, vamos a la página oficial y descargamos la última versión del software:
Descomprimimos el archivo descargado, para ello se recomienda la herramienta PeaZip y vamos a obtener los siguientes archivos:
Crear nuestro proyecto
Abrimos Netbeans y creamos un nuevo proyecto de Java (File → New Project).
Creamos un paquete llamado analizadores, este almacenará todo el código fuente relacionado con el analizador léxico y sintáctico (Clic derecho en Source Packages → New → Java Package).
Creamos tres archivos en el paquete analizadores, el primero “Lexico”, que almacenará el código fuente con el cual JLex generará el analizador léxico que queremos, el segundo “Sintactico”, que almacenará el código fuente con el cual Cup generará el analizador sintáctico que queremos y el tercero “compilar.sh”, que guardará los comandos que deben ejecutarse para solicitarle a JLex y a Cup que generen los analizadores. Para crear cada uno de los archivos hacemos clic derecho en el paquete analizadores → New → Other → en la ventana que despliegue, seleccionar Categories: Other y File Types: Empty File, seleccionamos siguiente, indicamos el nombre para el archivo y finalizamos. De tal modo que al final tendremos los tres archivos archivos.
Importar la librería de Cup en nuestro proyecto para poder ejecutar el analizador sintáctico que generemos
Para ello creamos una carpeta lib dentro de la carpeta de nuestro proyecto.
Dentro de la carpeta lib pegamos el archivo “java-cup-11b-runtime.jar” que descargamos anteriormente.
Para importar el archivo jar, vamos a Netbeans y damos clic derecho en la pestaña Libraries de nuestro proyecto → Add JAR/Folder… luego buscamos el archivo jar en la carpeta lib que acabamos de copiar en la carpeta lib y lo seleccionamos.
Código fuente para el analizador léxico
En el archivo “Lexico” incluiremos todo el código que le indicará a Jlex lo que debe hacer. El código se muestra a continuación:
"Evaluar" {return new Symbol(sym.REVALUAR,yyline,yychar, yytext());}
";" {return new Symbol(sym.PTCOMA,yyline,yychar, yytext());} "(" {return new Symbol(sym.PARIZQ,yyline,yychar, yytext());} ")" {return new Symbol(sym.PARDER,yyline,yychar, yytext());} "[" {return new Symbol(sym.CORIZQ,yyline,yychar, yytext());} "]" {return new Symbol(sym.CORDER,yyline,yychar, yytext());}
"+" {return new Symbol(sym.MAS,yyline,yychar, yytext());} "-" {return new Symbol(sym.MENOS,yyline,yychar, yytext());} "*" {return new Symbol(sym.POR,yyline,yychar, yytext());} "/" {return new Symbol(sym.DIVIDIDO,yyline,yychar, yytext());}
\n {yychar=1;}
{BLANCOS} {} {D} {return new Symbol(sym.ENTERO,yyline,yychar, yytext());} {DD} {return new Symbol(sym.DECIMAL,yyline,yychar, yytext());}
. { System.out.println("Este es un error lexico: "+yytext()+ ", en la linea: "+yyline+", en la columna: "+yychar); }
Explicación del código fuente para el analizador léxico
En las primeras líneas indicamos a Jlex que la clase estará en el paquete analizadores y que es necesario que se importe la clase Symbol.
Luego viene el bloque init, dentro del init, se ejecutan las acciones de inicialización, es decir, lo que va dentro del constructor del analizador léxico.En este caso indicamos dentro del init que:
La variable yyline, que lleva la cuenta del número de linea por el que va el analizador valdrá inicialmente 1.
La variable yychar, que lleva la cuenta del número de carácter por el que va el analizador valdrá inicialmente 1.
1 2 3 4
%init{ yyline = 1; yychar = 1; %init}
Luego se escriben algunas expresiones regulares que son almacenadas en macros, que básicamente son variables que almacenan los patrones, en este caso se definen las macros: BLANCOS, D y DD. Los patrones para cada una son los siguientes:
BLANCOS: Expresión regular que reconoce uno o muchos espacios en blanco, retornos de carro o tabuladores.
D: Expresión regular que reconoce números enteros.
DD: Expresión regular que reconoce números con punto decimal.
Por último se definen todas las reglas léxicas, en las que indicamos el patrón que reconocerá y dentro de llaves lo que debe hacer cuando lo reconozca. En la mayoría de los casos se retorna un objeto de tipo Symbol, que vendría siendo un token, este se instancia con el tipo, la fila en la que se encontró, la columna en la que se encontró y el lexema en específico que se reconoció, este se obtiene mediante yytext(). Dentro de las llaves podríamos incluir el código java que quisiéramos. Vemos que al reconocer el patrón BLANCOS no se hace nada porque esperamos que ignore los espacios en blanco. También vemos que al encontrar un salto de linea reinicia la variable yychar, es decir, reinicia el conteo de caracteres para que se lleve la cuenta del número de columna en cada fila.
"Evaluar" {return new Symbol(sym.REVALUAR,yyline,yychar, yytext());}
";" {return new Symbol(sym.PTCOMA,yyline,yychar, yytext());} "(" {return new Symbol(sym.PARIZQ,yyline,yychar, yytext());} ")" {return new Symbol(sym.PARDER,yyline,yychar, yytext());} "[" {return new Symbol(sym.CORIZQ,yyline,yychar, yytext());} "]" {return new Symbol(sym.CORDER,yyline,yychar, yytext());}
"+" {return new Symbol(sym.MAS,yyline,yychar, yytext());} "-" {return new Symbol(sym.MENOS,yyline,yychar, yytext());} "*" {return new Symbol(sym.POR,yyline,yychar, yytext());} "/" {return new Symbol(sym.DIVIDIDO,yyline,yychar, yytext());}
\n {yychar=1;}
{BLANCOS} {} {D} {return new Symbol(sym.ENTERO,yyline,yychar, yytext());} {DD} {return new Symbol(sym.DECIMAL,yyline,yychar, yytext());}
. { System.out.println("Este es un error lexico: "+yytext()+ ", en la linea: "+yyline+", en la columna: "+yychar); }
Código fuente para el analizador sintáctico
En el archivo “Sintáctico” incluiremos todo el código que le indicará a Cup lo que debe hacer. El código se muestra a continuación:
/* * Ejemplo desarrollado por Erick Navarro * Blog: e-navarro.blogspot.com * Julio - 2018 */
package analizadores; import java_cup.runtime.*;
parser code {: /** * Método al que se llama automáticamente ante algún error sintactico. **/ public void syntax_error(Symbol s){ System.out.println("Error Sintáctico en la Línea " + (s.left) + " Columna "+s.right+ ". No se esperaba este componente: " +s.value+"."); }
/** * Método al que se llama automáticamente ante algún error sintáctico * en el que ya no es posible una recuperación de errores. **/ public void unrecovered_syntax_error(Symbol s) throws java.lang.Exception{ System.out.println("Error síntactico irrecuperable en la Línea " + (s.left)+ " Columna "+s.right+". Componente " + s.value + " no reconocido."); } :}
instruccion ::= REVALUAR CORIZQ expresion:a CORDER PTCOMA{:System.out.println("El valor de la expresión es: "+a);:} ;
expresion ::= MENOS expresion:a {:RESULT=a*-1;:}%prec UMENOS | expresion:a MAS expresion:b {:RESULT=a+b;:} | expresion:a MENOS expresion:b {:RESULT=a-b;:} | expresion:a POR expresion:b {:RESULT=a*b;:} | expresion:a DIVIDIDO expresion:b {:RESULT=a/b;:} | ENTERO:a {:RESULT=new Double(a);:} | DECIMAL:a {:RESULT=new Double(a);:} | PARIZQ expresion:a PARDER {:RESULT=a;:} ;
Explicación del código fuente para el analizador sintáctico
En las primeras líneas indicamos a Cup que la clase estará en el paquete analizadores y que es necesario que se importe todo el contenido de “java_cup.runtime”.
1 2
package analizadores; import java_cup.runtime.*;
Luego viene la sección “parser code”, en la que se programan acciones propias del parser o analizador sintáctico que se va a generar, en este caso se programa lo que se debe hacer ante un error sintáctico y ante un error sintáctico irrecuperable.
parser code {: /** * Método al que se llama automáticamente ante algún error sintactico. **/ public void syntax_error(Symbol s){ System.out.println("Error Sintáctico en la Línea " + (s.left) + " Columna "+s.right+ ". No se esperaba este componente: " +s.value+"."); }
/** * Método al que se llama automáticamente ante algún error sintáctico * en el que ya no es posible una recuperación de errores. **/ public void unrecovered_syntax_error(Symbol s) throws java.lang.Exception{ System.out.println("Error síntactico irrecuperable en la Línea " + (s.left)+ " Columna "+s.right+". Componente " + s.value + " no reconocido."); } :}
Luego se definen los terminales, a estos se les puede indicar un tipo, en este caso todos son de tipo String, si no se indicara un tipo, los terminales serían por defecto de tipo Object.
Existe un terminal por cada tipo de token que el analizador léxico devuelve. Todos estos tipos estarán definidos en la clase “sym”, que se genera automáticamente y de la que se hablará más adelante.
Luego viene la declaración de los no terminales, a los que también se les puede indicar un tipo específico, si no se les indica un tipo, estos son por defecto de tipo Object.
1 2 3 4
non terminal ini; non terminal instrucciones; non terminal instruccion; non terminal Double expresion;
Posteriormente podemos indicar la precedencia de los operadores, ya que la gramática escrita es ambigua, es necesario definir una precedencia para que el analizador no entre en conflicto al analizar, en este caso la precedencia es la misma que la de los operadores aritméticos, la precedencia más baja la tienen la suma y la resta, luego están la multiplicación y la división que tienen una precedencia más alta y por último está el signo menos de las expresiones negativas que tendría la precedencia más alta.
1 2 3
precedence left MAS,MENOS; precedence left POR,DIVIDIDO; precedence right UMENOS;
Por último viene el conjunto de reglas de escritura de la gramática o producciones, al final de cada producción puede incluirse código java entre llaves y dos puntos “{:<código java>:}”. Podemos ver que en las producciones del no terminal “expresion”, se utiliza la variable RESULT, esta variable es propia de Cup y nos permite sintetizar cierto atributo para ese no terminal que se encuentra del lado izquierdo de la producción, recordemos que Cup trabaja con analizadores LALR, que son de tipo ascendente, lo que significa que nos permiten manipular atributos sintetizados. Básicamente eso es RESULT, un atributo sintetizado.
RESULT puede ser cualquier objeto, por ejemplo si quisiéramos que RESULT almacenara varios números enteros hacemos una clase Nodo que contenga muchas variables de tipo entero y declaramos los no terminales para que sean de tipo Nodo, entonces el RESULT que sintetizarán dichos no terminales serán de tipo Nodo.
instruccion ::= REVALUAR CORIZQ expresion:a CORDER PTCOMA{:System.out.println("El valor de la expresión es: "+a);:} ;
expresion ::= MENOS expresion:a {:RESULT=a*-1;:}%prec UMENOS | expresion:a MAS expresion:b {:RESULT=a+b;:} | expresion:a MENOS expresion:b {:RESULT=a-b;:} | expresion:a POR expresion:b {:RESULT=a*b;:} | expresion:a DIVIDIDO expresion:b {:RESULT=a/b;:} | ENTERO:a {:RESULT=new Double(a);:} | DECIMAL:a {:RESULT=new Double(a);:} | PARIZQ expresion:a PARDER {:RESULT=a;:} ;
Incluír JLex para generar el analizador léxico de nuestro proyecto
Creamos un paquete llamado JLex dentro del paquete analizadores, este almacenará la herramienta JLex (Clic derecho en el paquete analizadores → New → Java Package).
En la carpeta del paquete JLex copiamos el archivo Main.java que descargamos de la página oficial de JLex.
Incluír Cup para generar el analizador sintáctico de nuestro proyecto
Creamos un paquete llamado Cup dentro del paquete analizadores, este almacenará la herramienta Cup (Clic derecho en el paquete analizadores → New → Java Package).
En la carpeta del paquete Cup copiamos el archivo “java-cup-11b-runtime.jar” que descargamos de la página oficial de Cup.
El archivo de compilación
En el archivo “compilar.bat”, ejecutamos tres líneas, la primera indica a compila Main.java para poder disponer de la herramienta para generar nuestro analizador léxico, la segunda le indica a la herramienta Jlex que debe generar un analizador léxico en base al código fuente que se encuentra en el archivo “Lexico”, la tercera indica a Cup que la clase que debe generar para el analizador sintáctico se llamará “Sintactico” y que debe generarse en base al código fuente que se encuentra en el archivo “Sintactico”.
Para ejecutarlo solo vamos a Netbeans, damos clic derecho sobre el archivo y seleccionamos la opción Run. Al finalizar la ejecución del archivo, veremos en la consola de Netbeans una salida como la siguiente:
C:\Users\erick\OneDrive\Documentos\NetBeansProjects\ProyectoCupJlexWindows\src\analizadores>javac JLex/Main.java Note: JLex\Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
C:\Users\erick\OneDrive\Documentos\NetBeansProjects\ProyectoCupJlexWindows\src\analizadores>java JLex.Main Lexico Processing first section -- user code. Processing second section -- JLex declarations. Processing third section -- lexical rules. Creating NFA machine representation. NFA comprised of 67 states. Working on character classes.:::::.:::::::::::::.:::. NFA has 24 distinct character classes. Creating DFA transition table. Working on DFA states........................... Minimizing DFA transition table. 24 states after removal of redundant states. Outputting lexical analyzer code.
C:\Users\erick\OneDrive\Documentos\NetBeansProjects\ProyectoCupJlexWindows\src\analizadores>java -jar Cup/java-cup-11b.jar -parser Sintactico Sintactico ------- CUP v0.11b 20160615 (GIT 4ac7450) Parser Generation Summary ------- 0 errors and 0 warnings 15 terminals, 4 non-terminals, and 14 productions declared, producing 28 unique parse states. 0 terminals declared but not used. 0 non-terminals declared but not used. 0 productions never reduced. 0 conflicts detected (0 expected). Code written to "Sintactico.java", and "sym.java". ---------------------------------------------------- (CUP v0.11b 20160615 (GIT 4ac7450))
RUN SUCCESSFUL (total time: 3s)
Que nos confirma que la generación del analizador léxico fue exitosa y que la del analizador sintáctico también. Veremos que se han creado tres nuevos archivos en el paquete analizadores. Estos archivos son las clases: Lexico.java, Sintactico.java y sym.java.
La clase sym.java, sirve como puente entre la clase Lexico.java y Sintactico.java, por ejemplo, cuando el analizador léxico reconoce un número entero, instancia un objeto de la clase Symbol e indica que es de tipo número entero por medio de la constante “sym.ENTERO”, que se genera dentro de la clase sym.java y esta constante se genera porque en el archivo de entrada para Cup se indicó que existe un terminal llamado ENTERO. Entonces tanto el analizador léxico como el sintáctico hacen referencia a los tokens de tipo número entero con la constante “sym.ENTERO”. Básicamente eso es sym.java, una clase con muchas constantes estáticas a las que acceden ambos analizadores para poder integrarse y ejecutar sus tareas exitosamente.
Creando un archivo de entrada para nuestros analizadores
Dentro de la carpeta del proyecto crearé un archivo de entrada llamado “entrada.txt”. Que contendrá el archivo de entrada que reconocerán nuestros analizadores.
El archivo de “entrada.txt” contiene lo siguiente:
Dentro de la clase principal solo tenemos el método main y el método interpretar que lee el contenido del archivo que se encuentra en el path que se le indica y ejecuta análisis léxico y análisis sintáctico, en el transcurso del analisis sintáctico se mandan a imprimir en consola los resultados de las expresiones aritméticas analizadas, por lo que al final del análisis tendremos todos los resultados de las operaciones en consola. A continuación se muestra el código de la clase principal.
/* * Ejemplo desarrollado por Erick Navarro * Blog: e-navarro.blogspot.com * Julio - 2018 */
package proyectocupjlexwindows;
import java.io.FileInputStream;
/** * Clase principal de la aplicación * @author Erick */ public class ProyectoCupJlexWindows {
/** * @param args argumentos de la linea de comando */ public static void main(String[] args) { interpretar("entrada.txt"); } /** * Método que interpreta el contenido del archivo que se encuentra en el path * que recibe como parámentro * @param path ruta del archivo a interpretar */ private static void interpretar(String path) { analizadores.Sintactico pars; try { pars=new analizadores.Sintactico(new analizadores.Lexico(new FileInputStream(path))); pars.parse(); } catch (Exception ex) { System.out.println("Error fatal en compilación de entrada."); System.out.println("Causa: "+ex.getCause()); } } }
Ejecutando nuestra aplicación
Al ejecutar la aplicación obtenemos los resultados de las operaciones evaluadas en consola.
JLex es un generador de analizadores léxicos, escrito en Java, para Java. JLex fue desarrollado por Elliot Berk en la Universidad de Princeton. Para más información visitar la página oficial de JLex. La principal tarea de un analizador léxico es leer los caracteres de entrada del programa fuente, agruparlos en lexemas y producir como salida una secuencia de tokens.
Un token es un par que consiste en un nombre de token y un valor de atributo opcional.
Un lexema es una secuencia de caracteres en el programa fuente, que coinciden con el patrón para un token y que el analizador léxico identifica como una instancia de este tóken.
Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.
En JLex se definen los patrones de los diferentes tokens que se desean reconocer, estos patrones pueden definirse a través de expresiones regulares. Además JLex cuenta con múltiples opciones, una muy imporante es su capacidad para integrarse con generadores de analizadores sintácticos como Cup.
Cup
Cup es un generador de analizadores sintácticos de tipo LALR para Java.
El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generase con la gramática para el lenguaje fuente. Una gramática proporciona una especificación precisa y fácil de entender de un lenguaje de programación.
Pre-requisitos
Para este ejemplo hace falta que tengamos instalado:
Lo primero que haremos será instalar JLex, 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 jlex”, autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado JLex.
Luego instalamos cup, ejecutando en la terminal el comando “sudo apt-get install cup”, autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Cup.
Abrimos Netbeans y creamos un nuevo proyecto de Java (File → New Project).
Creamos un paquete llamado analizadores, este almacenará todo el código fuente relacionado con el analizador léxico y sintáctico (Clic derecho en Source Packages → New → Java Package).
Creamos tres archivos en el paquete analizadores, el primero “Lexico”, que almacenará el código fuente con el cual JLex generará el analizador léxico que queremos, el segundo “Sintactico”, que almacenará el código fuente con el cual Cup generará el analizador sintáctico que queremos y el tercero “compilar.sh”, que guardará los comandos que deben ejecutarse para solicitarle a JLex y a Cup que generen los analizadores. Para crear cada uno de los archivos hacemos clic derecho en el paquete analizadores → New → Other → en la ventana que despliegue, seleccionar Categories: Other y File Types: Empty File, seleccionamos siguiente, indicamos el nombre para el archivo y finalizamos. De tal modo que al final tendremos los tres archivos archivos.
Ahora importaremos la llibrería de Cup a nuestro proyecto de netbeans, para ello descargamos el archivo “java-cup-bin-11b-<versión>.tar.gz” de la página oficial de Cup. En este caso el archivo descargado fue el “java-cup-bin-11b-20150326.tar.gz”.
Lo descomprimimos y veremos que contiene dos archivos .jar, el que nos interesa es el archivo “java-cup-11b-runtime.jar”.
Creamos una carpeta lib dentro de la carpeta de nuestro proyecto.
Dentro de la carpeta lib pegamos el archivo “java-cup-11b-runtime.jar”.
Para importar el archivo jar, vamos a Netbeans y damos clic derecho en la pestaña Libraries de nuestro proyecto → Add JAR/Folder… luego buscamos el archivo jar en la carpeta lib que acabamos de crear y lo seleccionamos.
Código fuente para el analizador léxico
En el archivo “Lexico” incluiremos todo el código que le indicará a Jlex lo que debe hacer. El código se muestra a continuación:
"Evaluar" {return new Symbol(sym.REVALUAR,yyline,yychar, yytext());}
";" {return new Symbol(sym.PTCOMA,yyline,yychar, yytext());} "(" {return new Symbol(sym.PARIZQ,yyline,yychar, yytext());} ")" {return new Symbol(sym.PARDER,yyline,yychar, yytext());} "[" {return new Symbol(sym.CORIZQ,yyline,yychar, yytext());} "]" {return new Symbol(sym.CORDER,yyline,yychar, yytext());}
"+" {return new Symbol(sym.MAS,yyline,yychar, yytext());} "-" {return new Symbol(sym.MENOS,yyline,yychar, yytext());} "*" {return new Symbol(sym.POR,yyline,yychar, yytext());} "/" {return new Symbol(sym.DIVIDIDO,yyline,yychar, yytext());}
\n {yychar=1;}
{BLANCOS} {} {D} {return new Symbol(sym.ENTERO,yyline,yychar, yytext());} {DD} {return new Symbol(sym.DECIMAL,yyline,yychar, yytext());}
. { System.out.println("Este es un error lexico: "+yytext()+ ", en la linea: "+yyline+", en la columna: "+yychar); }
Explicación del código fuente para el analizador léxico
En las primeras líneas indicamos a Jlex que la clase estará en el paquete analizadores y que es necesario que se importe la clase Symbol.
Luego viene el bloque init, dentro del init, se ejecutan las acciones de inicialización, es decir, lo que va dentro del constructor del analizador léxico.En este caso indicamos dentro del init que:
La variable yyline, que lleva la cuenta del número de linea por el que va el analizador valdrá inicialmente 1.
La variable yychar, que lleva la cuenta del número de carácter por el que va el analizador valdrá inicialmente 1.
1 2 3 4
%init{ yyline = 1; yychar = 1; %init}
Luego se escriben algunas expresiones regulares que son almacenadas en macros, que básicamente son variables que almacenan los patrones, en este caso se definen las macros: BLANCOS, D y DD. Los patrones para cada una son los siguientes:
BLANCOS: Expresión regular que reconoce uno o muchos espacios en blanco, retornos de carro o tabuladores.
D: Expresión regular que reconoce números enteros.
DD: Expresión regular que reconoce números con punto decimal.
Por último se definen todas las reglas léxicas, en las que indicamos los patrones que reconocerá y dentro de llaves lo que debe hacer cuando los reconozca. En la mayoría de los casos se retorna un objeto de tipo Symbol, que vendría siendo un token, este se instancia con el tipo, la fila en la que se encontró, la columna en la que se encontró y el lexema en específico que se reconoció, este se obtiene mediante yytext(). Dentro de las llaves podríamos incluir el código java que quisiéramos. Vemos que al reconocer el patrón BLANCOS no se hace nada porque esperamos que ignore los espacios en blanco. También vemos que al encontrar un salto de linea reinicia la variable yychar, es decir, reinicia el conteo de caracteres para que se lleve la cuenta del número de columna en cada fila.
"Evaluar" {return new Symbol(sym.REVALUAR,yyline,yychar, yytext());}
";" {return new Symbol(sym.PTCOMA,yyline,yychar, yytext());} "(" {return new Symbol(sym.PARIZQ,yyline,yychar, yytext());} ")" {return new Symbol(sym.PARDER,yyline,yychar, yytext());} "[" {return new Symbol(sym.CORIZQ,yyline,yychar, yytext());} "]" {return new Symbol(sym.CORDER,yyline,yychar, yytext());}
"+" {return new Symbol(sym.MAS,yyline,yychar, yytext());} "-" {return new Symbol(sym.MENOS,yyline,yychar, yytext());} "*" {return new Symbol(sym.POR,yyline,yychar, yytext());} "/" {return new Symbol(sym.DIVIDIDO,yyline,yychar, yytext());}
\n {yychar=1;}
{BLANCOS} {} {D} {return new Symbol(sym.ENTERO,yyline,yychar, yytext());} {DD} {return new Symbol(sym.DECIMAL,yyline,yychar, yytext());}
. { System.out.println("Este es un error lexico: "+yytext()+ ", en la linea: "+yyline+", en la columna: "+yychar); }
Código fuente para el analizador sintáctico
En el archivo “Sintáctico” incluiremos todo el código que le indicará a Cup lo que debe hacer. El código se muestra a continuación:
/* * Ejemplo desarrollado por Erick Navarro * Blog: e-navarro.blogspot.com * Septiembre - 2015 */
package analizadores; import java_cup.runtime.*;
parser code {: /** * Método al que se llama automáticamente ante algún error sintactico. **/ public void syntax_error(Symbol s){ System.out.println("Error Sintáctico en la Línea " + (s.left) + " Columna "+s.right+ ". No se esperaba este componente: " +s.value+"."); }
/** * Método al que se llama automáticamente ante algún error sintáctico * en el que ya no es posible una recuperación de errores. **/ public void unrecovered_syntax_error(Symbol s) throws java.lang.Exception{ System.out.println("Error síntactico irrecuperable en la Línea " + (s.left)+ " Columna "+s.right+". Componente " + s.value + " no reconocido."); } :}
instruccion ::= REVALUAR CORIZQ expresion:a CORDER PTCOMA{:System.out.println("El valor de la expresión es: "+a);:} ;
expresion ::= MENOS expresion:a {:RESULT=a*-1;:}%prec UMENOS | expresion:a MAS expresion:b {:RESULT=a+b;:} | expresion:a MENOS expresion:b {:RESULT=a-b;:} | expresion:a POR expresion:b {:RESULT=a*b;:} | expresion:a DIVIDIDO expresion:b {:RESULT=a/b;:} | ENTERO:a {:RESULT=new Double(a);:} | DECIMAL:a {:RESULT=new Double(a);:} | PARIZQ expresion:a PARDER {:RESULT=a;:} ;
Explicación del código fuente para el analizador sintáctico
En las primeras líneas indicamos a Cup que la clase estará en el paquete analizadores y que es necesario que se importe todo el contenido de “java_cup.runtime”.
1 2
package analizadores; import java_cup.runtime.*;
Luego viene la sección “parser code”, en la que se programan acciones propias del parser o analizador sintáctico que se va a generar, en este caso se programa lo que se debe hacer ante un error sintáctico y ante un error sintáctico irrecuperable.
parser code {: /** * Método al que se llama automáticamente ante algún error sintactico. **/ public void syntax_error(Symbol s){ System.out.println("Error Sintáctico en la Línea " + (s.left) + " Columna "+s.right+ ". No se esperaba este componente: " +s.value+"."); }
/** * Método al que se llama automáticamente ante algún error sintáctico * en el que ya no es posible una recuperación de errores. **/ public void unrecovered_syntax_error(Symbol s) throws java.lang.Exception{ System.out.println("Error síntactico irrecuperable en la Línea " + (s.left)+ " Columna "+s.right+". Componente " + s.value + " no reconocido."); } :}
Luego se definen los terminales, a estos se les puede indicar un tipo, en este caso todos son de tipo String, si no se indicara un tipo, los terminales serían por defecto de tipo Object.
Existe un terminal por cada tipo de token que el analizador léxico devuelve. Todos estos tipos estarán definidos en la clase “sym”, que se genera automáticamente y de la que se hablará más adelante.
Luego viene la declaración de los no terminales, a los que también se les puede indicar un tipo específico, si no se les indica un tipo, estos son por defecto de tipo Object.
1 2 3 4
non terminal ini; non terminal instrucciones; non terminal instruccion; non terminal Double expresion;
Posteriormente podemos indicar la precedencia de los operadores, ya que la gramática escrita es ambigua, es necesario definir una precedencia para que el analizador no entre en conflicto al analizar, en este caso la precedencia es la misma que la de los operadores aritméticos, la precedencia más baja la tienen la suma y la resta, luego están la multiplicación y la división que tienen una precedencia más alta y por último está el signo menos de las expresiones negativas que tendría la precedencia más alta.
1 2 3
precedence left MAS,MENOS; precedence left POR,DIVIDIDO; precedence right UMENOS;
Por último viene el conjunto de reglas de escritura de la gramática o producciones, al final de cada producción puede incluirse código java entre llaves y dos puntos “{:<código java>:}”. Podemos ver que en las producciones del no terminal “expresion”, se utiliza la variable RESULT, esta variable es propia de Cup y nos permite sintetizar cierto atributo para ese no terminal que se encuentra del lado izquierdo de la producción, recordemos que Cup trabaja con analizadores LALR, que son de tipo ascendente, lo que significa que nos permiten manipular atributos sintetizados. Básicamente eso es RESULT, un atributo sintetizado.
RESULT puede ser cualquier objeto, por ejemplo si quisiéramos que RESULT almacenara varios números enteros hacemos una clase Nodo que contenga muchas variables de tipo entero y declaramos los no terminales para que sean de tipo Nodo, entonces el RESULT que sintetizarán dichos no terminales serán de tipo Nodo.
instruccion ::= REVALUAR CORIZQ expresion:a CORDER PTCOMA{:System.out.println("El valor de la expresión es: "+a);:} ;
expresion ::= MENOS expresion:a {:RESULT=a*-1;:}%prec UMENOS | expresion:a MAS expresion:b {:RESULT=a+b;:} | expresion:a MENOS expresion:b {:RESULT=a-b;:} | expresion:a POR expresion:b {:RESULT=a*b;:} | expresion:a DIVIDIDO expresion:b {:RESULT=a/b;:} | ENTERO:a {:RESULT=new Double(a);:} | DECIMAL:a {:RESULT=new Double(a);:} | PARIZQ expresion:a PARDER {:RESULT=a;:} ;
El archivo de compilación
En el archivo “compilar.sh”, ejecutamos dos líneas, la primera indica a Jlex que debe generar un analizador léxico en base al código fuente que se encuentra en el archivo “Lexico”, la segunda indica a Cup que la clase que debe generar para el analizador sintáctico se llamará “Sintactico” y que debe generarse en base al código fuente que se encuentra en el archivo “Sintactico”.
1 2
jlex Lexico cup -parser Sintactico Sintactico
Para ejecutarlo solo vamos a Netbeans, damos clic derecho sobre el archivo y seleccionamos la opción Run. Al finalizar la ejecución del archivo, veremos en la consola de Netbeans una salida como la siguiente:
Processing first section -- user code. Processing second section -- JLex declarations. Processing third section -- lexical rules. Creating NFA machine representation. NFA comprised of 67 states. Working on character classes.:::::.:::::::::::::.:::. NFA has 24 distinct character classes. Creating DFA transition table. Working on DFA states........................... Minimizing DFA transition table. 24 states after removal of redundant states. Outputting lexical analyzer code. ------- CUP v0.11a beta 20060608 Parser Generation Summary ------- 0 errors and 0 warnings 15 terminals, 4 non-terminals, and 14 productions declared, producing 28 unique parse states. 0 terminals declared but not used. 0 non-terminals declared but not used. 0 productions never reduced. 0 conflicts detected (0 expected). Code written to "Sintactico.java", and "sym.java". ---------------------------------------------------- (v0.11a beta 20060608)
RUN SUCCESSFUL (total time: 757ms)
Que nos confirma que la generación del analizador léxico fue exitosa y que la del analizador sintáctico también. Veremos que se han creado tres nuevos archivos en el paquete analizadores. Estos archivos son las clases: Lexico.java, Sintactico.java y sym.java.
La clase sym.java, sirve como puente entre la clase Lexico.java y Sintactico.java, por ejemplo, cuando el analizador léxico reconoce un número entero, instancia un objeto de la clase Symbol e indica que es de tipo número entero por medio de la constante “sym.ENTERO”, que se genera dentro de la clase sym.java y esta constante se genera porque en el archivo de entrada para Cup se indicó que existe un terminal llamado ENTERO. Entonces tanto el analizador léxico como el sintáctico hacen referencia a los tokens de tipo número entero con la constante “sym.ENTERO”. Básicamente eso es sym.java, una clase con muchas constantes estáticas a las que acceden ambos analizadores para poder integrarse y ejecutar sus tareas exitosamente.
Archivo de entrada
Dentro de la carpeta del proyecto crearé un archivo de entrada llamado “entrada.txt”. Que contendrá el archivo de entrada que reconocerán nuestros analizadores.
El archivo de “entrada.txt” contiene lo siguiente:
Dentro de la clase principal solo tenemos el método main y el método interpretar que lee el contenido del archivo que se encuentra en el path que se le indica y ejecuta análisis léxico y análisis sintáctico, en el transcurso del analisis sintáctico se mandan a imprimir en consola los resultados de las expresiones aritméticas analizadas, por lo que al final del análisis tendremos todos los resultados de las operaciones en consola. A continuación se muestra el código de la clase principal.
/** * Clase principal de la aplicación * @author Erick */ public class ProyectoCupJlex {
/** * @param args argumentos de la linea de comando */ public static void main(String[] args) { interpretar("entrada.txt"); } /** * Método que interpreta el contenido del archivo que se encuentra en el path * que recibe como parámentro * @param path ruta del archivo a interpretar */ private static void interpretar(String path) { analizadores.Sintactico pars; try { pars=new analizadores.Sintactico(new analizadores.Lexico(new FileInputStream(path))); pars.parse(); } catch (Exception ex) { System.out.println("Error fatal en compilación de entrada."); System.out.println("Causa: "+ex.getCause()); } } }
Ejecutando nuestra aplicación
Al ejecutar la aplicación obtenemos los resultados de las operaciones evaluadas en consola.
