Analizador sintáctico en Visual Basic

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:

Analizador sintáctico en Visual Basic.

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:

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.

Analizador léxico en Visual Basic

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:

Analizador léxico en Visual Basic.

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

Graficar árboles AVL con Graphviz y Java

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:

Graficar árboles AVL con Graphviz y Java.

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.

Graficar árboles binarios de búsqueda con Graphviz y Java

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:

Graficar árboles binarios de búsqueda con Graphviz y Java.

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.