Jison toma una gramática libre de contexto como entrada y produce código JavaScript capaz de parsear el lenguaje descrito por dicha gramática. Una vez se tenga el script generado podemos usarlo para parsear la entrada y aceptarla, rechazarla o ejecutar acciones con base en la entrada. Si se está familiarizado con Bison, Yacc o algún otro similar ya se está listo para iniciar. Jison genera tanto el analizador léxico como el analizador sintáctico.
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.
El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generarse 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.
En Jison se definen tanto el analizador léxico como el sintáctico. Esto es una gran ventaja pues podemos trabajar en una sola herramienta.
Pre-requisitos
Para este ejemplo hace falta que tengamos instalado:
La bandera -g nos sirve para indicar que instalaremos Jison de manera global, es decir, estará disponible en cualquier directorio del sistema.
Crear nuestro proyecto
Usaremos npm para crear nuestro proyecto. Primero crearemos un nuevo folder, en este caso lo llamaremos ProyectoJisonUbuntu. Para esto abrimos una nueva terminal, nos ubicamos donde queremos crear el proyecto y ejecutamos el siguiente comando:
1
$ mkdir ProyectoJisonUbuntu
Y luego ingresamos al directorio con el siguiente comando:
1
$ cd ProyectoJisonUbuntu
Ahora procedemos a iniciar el proyecto con npm. Para esto ejecutamos el siguiente comando:
1
$ npm init -y
Con esto habremos iniciado el proyecto. La bandera -y sirve para seleccionar valores por defecto en los parámetros de inicialización.
Ahora nos pasamos a nuestro editor de texto, en este caso usaremos Visual Studio Code. Ejecutamos el siguiente comando para abrir Code con nuestro proyecto directamente.
1
$ code .
Code se desplegará con nuestro proyecto llamado ProyectoJisonUbuntu
Nótese que únicamente contiene el archivo package.json el cual fue creado por el comando npm init.
Procedemos a crear un nuevo archivo llamado gramatica.jison
Código Fuente para el analizador léxico y sintáctico
En el archivo gramática.jison le indicamos a Jison la descripción de nuestra gramática.
Explicación del código fuente para el analizador léxico
Iniciamos indicando que queremos iniciar con la definición léxica, posteriormente agregamos las opciones que deseamos. En este caso indicamos que nuestro analizador no distinguirá diferencias entre mayúsculas y minúsculas.
1 2 3 4
/* Definición Léxica */ %lex
%options case-insensitive
A diferencia de otras herramientas, Jison por defecto cuenta la posición de línea y columna de los caracteres y acepta el conjunto de caracteres unicode.
Luego escribimos los patrones para los tokens que deseamos reconocer. Para cada uno de ellos debemos retornar el nombre asociado al token.
Jison también soporta el uso de expresiones regulares para identificar patrones. En las siguientes instrucciones escribimos una expresión regular para identificar espacios en blanco e indicamos que al ser reconocidos no hacemos nada. Esto se hace a través de un par de llaves vacíos.
1 2 3
/* Espacios en blanco */ [ \r\t]+ {} \n {}
Escribimos expresiones regulares para identificar enteros y decimales.
Las últimas dos expresiones son para reconocer el fin de la entrada y caracteres no válidos.
1 2 3 4
<<EOF>> return'EOF';
. { console.error('Este es un error léxico: ' + yytext + ', en la linea: ' + yylloc.first_line + ', en la columna: ' + yylloc.first_column); } /lex
En caso de encontrarse con un error léxico lo desplegamos en consola.
Explicación del código fuente para el analizador sintáctico
Otra de las ventajas de Jison es que en el mismo archivo podemos definir nuestro análisis sintáctico haciendo uso de los tokens previamente definidos en la sección del analizador léxico.
Primeramente definimos la asociatividad y 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
Debemos indicarle a Jison cual será nuestro símbolo Inicial.
1
%start ini
Finalmente escribimos nuestras producciones, aquí vemos otra de las ventajas de Jison, cada No Terminal no debe definirse previamente, esto lo hace más práctico pero a la vez se debe de tener más cuidado con errores de escritura.
Al final de cada producción se puede incluir código javascript entre llaves “{ <código javascript> }”. Para sintetizar un valor asociado al no terminal de lado izquierdo de la producción hacemos uso de la variable $$. Esta variable es propia de Jison. Como podemos ver, para cada producción del no terminal “expresion” sintetizamos el valor de la operación aritmética o el valor del token aceptado.
La variable $$ puede tomar cualquier valor, recordemos que Jison al estar basado en javascript el tipo puede ser dinámico.
Nótese el terminal EOF, que indica el fin de la entrada, debe agregarse en nuestra gramática luego de haber reconocido nuestra entrada, esto indicará que hemos terminado. Si se omite este terminal obtendremos una excepción cuando nuestro analizador alcance el final del archivo.
Por último, podemos manejar también las producciones de error para el manejo de errores sintácticos.
El archivo de compilación
Para facilitar la compilación de nuestra gramática y poder obtener el script para nuestro parser procedemos a escribir un archivo sh.
Para esto creamos un nuevo archivo en Code llamado compilar.sh con el siguiente contenido:
1 2 3 4 5 6 7
#!/bin/bash
echo"Procesando gramática..."
jison gramatica.jison
echo"Gramática procesada..."
Para ejecutar nuestro script ejecutamos el siguiente comando en la terminal:
1
$ sh compilar.sh
Nos debe aparecer el siguiente resultado:
Si hubiese algún error debemos revisar que nuestra gramática esté correcta.
El comando nos generará el script en un archivo llamado gramatica.js en nuestro proyecto. Este es el script que utilizaremos para procesar nuestros archivos de entrada.
Creando un archivo de entrada para nuestro analizador
Creamos un nuevo archivo de texto utilizando nuestro editor llamado entrada.txt. El contenido de este archivo es el siguiente:
Necesitamos de un script que nos ayude a leer el archivo de entrada e invocar a nuestro parser con su contenido. Para esto creamos un nuevo archivo de texto y lo nombramos parser.js.
Su contenido es el siguiente:
1 2 3 4 5 6 7 8
var fs = require('fs'); var parser = require('./gramatica');
Hacemos uso de la librería fs de Nodejs para leer archivos y también de nuestro parser. Esto lo hacemos a través de la función require.
Luego invocamos al método readFile el cual lee nuestro archivo de entrada ‘entrdata.txt’. Este método devuelve dos parámetros, err el cual indica si hubo algún error y data, que almacena el contenido del archivo.
Validamos que no haya ocurrido error y con el contenido de nuestro archivo de entrada invocamos a nuestro parser.
Para ejecutar este script corremos el siguiente comando:
1
$ node parser
Como podemos ver, obtenemos la salida esperada.
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Rainman Sián, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.
Fuentes consultadas:
Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.
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:
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.
En esta publicación se muestra un ejemplo sencillo de la implementación de un analizador sintáctico a partir de una gramática independiente del contexto. Este proyecto se desarrolló utilizando Visual Studio 2013. El proyecto completo puede descargarse del siguiente enlace:
Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.
Funcionamiento del proyecto
Este ejemplo ilustra la implementación de un analizador sintáctico a partir de una gramática independiente del contexto. No se utiliza ningún generador de analizadores sintácticos que genere el analizador, ni se realiza el proceso de análisis sintáctico con ninguna librería. Los errores identificados en el proceso de análisis sintáctico se muestran en consola, si en el entorno de Visual Studio no aparece la consola, esta puede abrirse desde el menú ver, en la opción resultados o con Ctrl+Alt+O. Inicialmente se muestra una expresión aritmética de ejemplo que puede utilizarse como entrada, esta entrada contiene una expresión incompleta que léxicamente es correcta pero sintácticamente no, su estructura es incorrecta porque le hace falta un numero y un paréntesis derecho al final.
Al presionar el botón Analizar se ejecuta el análisis de la entrada y en consola se despliegan los mensajes de error.
El fundamento teórico que sirvió de soporte para el desarrollo de este ejemplo es el descrito en la sección 4.4.1 titulada Análisis sintáctico de descenso recursivo del libro: Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.
Gramática independiente del contexto utilizada
La gramática utilizada, reconoce expresiones aritméticas respetando la precedencia de operadores, no es ambigua y no tiene recursividad por la izquierda. La gramática es la siguiente:
1 2 3 4 5 6 7 8 9 10
E → T E' E' → + T E' E' → - T E' E' → ε T → F T' T' → * F T' T' → / F T' T' → ε F → ( E ) F → numero
Método utilizado para el desarrollo del analizador
Se desarrolló un analizador sintáctico predictivo recursivo. Los analizadores predictivos o descendentes consisten en la construcción de un árbol de análisis sintáctico para la cadena de entrada, partiendo desde la raíz y creando los nodos del árbol de análisis sintáctico en pre-orden. En este caso no se construye un árbol en memoria, ya que no es necesario guardar lo que se analiza, pero las llamadas recursivas a los diferentes métodos del analizador crean un árbol en pila mientras se ejecutan. La construcción de este analizador sintáctico predictivo recursivo sigue los siguientes principios:
Consiste en un conjunto de procedimientos, uno para cada no terminal.
La ejecución empieza con el procedimiento para el símbolo inicial.
Se detiene y anuncia que tuvo éxito si el cuerpo de su procedimiento explora la cadena completa de entrada.
Para cada no terminal del lado derecho de las producciones se hace una llamada al método que le corresponde.
Para cada terminal del lado derecho de las producciones se hace una llamada al método match enviando como parámetro el terminal.
El método match valida si el terminal que se recibe es el que se esperaba, de no ser así despliega un mensaje de error.
La gramática a utilizar reconoce expresiones aritméticas y cumple con lo siguiente:
No es ambigua
No tiene recursividad por la izquierda
Sobre la recuperación de errores sintácticos Este ejemplo es bastante básico, por lo que no tiene implementado un sistema de recuperación de errores sintácticos, para hacerlo existen muchas estrategias, como las siguientes:
Recuperación en modo pánico
Recuperación a nivel de frase
Producción de errores
Corrección global
Se recomienda la recuperación en modo pánico por ser la más sencilla de implementar
Fuentes consultadas:
Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición. Sección 4.4.1.
En esta publicación se muestra un ejemplo sencillo de la implementación de un analizador léxico a partir de un autómata finito determinista. Este proyecto se desarrolló utilizando Visual Studio 2013. 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.
Funcionamiento del proyecto
Este ejemplo ilustra la implementación de un analizador léxico a partir de un Autómata Finito Determinista (AFD). No se utiliza ningún generador de analizadores léxicos que genere el analizador, ni se realiza el proceso de análisis léxico con ninguna librería. Los errores identificados en el proceso de análisis léxico se muestran en consola, si en el entorno de Visual Studio no aparece la consola, esta pueden abrirse desde el menú ver, en la opción resultados o con Ctrl+Alt+O.
Inicialmente se muestra una expresión aritmética de ejemplo que puede utilizarse como entrada, del lado izquierdo.
Al presionar el botón Realizar Análisis Léxico se ejecuta el análisis de la entrada y del lado derecho se despliega la lista de tokens identificada, en la que se indica el tipo de token y el valor específico que este tiene.
Si existiera algún error léxico en la entrada, por ejemplo, si pusiéramos al final de la expresión una arroba en lugar del uno, entonces se desplegaría en consola un mensaje de error y se mostraría en la lista de tokens todos aquellos tokens válidos.
Autómata Finito Determinista utilizado
En este ejemplo se reconocen los componentes léxicos propios de una expresión aritmética, por ello el ejemplo se realizó a partir del siguiente autómata finito determinista:
El estado inicial del autómata es E_0. En el autómata podemos observar que existen tres estados de aceptación, el primero (EA_1) reconoce todos los componentes léxicos de un carácter y a nivel programación se clasifican los tokens según el carácter que se haya reconocido, el segundo estado de aceptación (EA_2) reconoce los números enteros y el tercero (EA_3) reconoce los números reales, es decir, los números con punto decimal. Se pueden desplegar dos tipos de mensajes de error, ya que se cuentan con dos estados de error, el primero es cuando se reconoce un carácter desconocido estando en el estado 1, el segundo se da cuando estando en el estado 2, correspondiente a los números reales, se esperaban más dígitos después del punto decimal, pero se obtiene un carácter que no es un dígito.
A un lado de algunos estados se coloca un asterisco (*), que indica que debe retrocederse la entrada en una posición, esto se hace porque los tokens se dan como aceptados con el primer carácter del siguiente token, entonces para que no se pierda ese carácter del siguiente token en el análisis debe retrocederse una posición en la entrada, esta notación es la misma que se utiliza en el libro de Aho, Lam, Sethi y Ullman.
El secreto tras la implementación del autómata
El secreto es encontrar la forma de ejecutar en código las acciones que un reconocedor haría basado en el autómata finito determinista, es lógico que la función core del analizador léxico debe estar dentro de un ciclo ya que deben recorrerse los caracteres de izquierda a derecha y agruparse en componentes léxicos. Este ciclo se encuentra en la función escanear de la clase AnalizadorLexico, dentro de dicho ciclo debe haber un select case en el que cada caso representa a uno de los estados del conjunto de estados para cada caso (o estado) hay un if elseif elseif … else que representan el conjunto de transiciones que salen de dicho estado.
Fuentes consultadas:
Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición. Págs. 111, 130 y 131
Teoría de la computación. Lenguajes formales, autómatas y complejidad. J. Glenn Brookshear. Pág. 24
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.
