miércoles, 8 de abril de 2009

Analizador Léxico en Java

Hola…

Agradezco a todas las personas que me han ayudado a entender la manera de cómo realizarlo y aquellos que me han apoyado cuando he faltado a clases… y por supuesto a Agustín Froufe por proporcionar todo el material necesario apara aprender Java.

Si ya tienes conocimientos de Java puedes pasar de todo esto e ir directamente a descargarte el código y solo ver la imagen del Árbol de decisiones (Autómata) Si deseas aprender java deberías ir a la página de Agustín Froufe…

yo me he pasado horas bajando toda la información para poder leerla. Si tienes dudas sobre lo que son los autómatas podrías investigar mas en Google, aunque dudo mucho que te interese mas de lo que me intereso a mi (que fue mas bien poco).Si lo que quieres es que te ayude a realizar tu maldito (jaja) Analizador Léxico… sigue leyendo:

Antes que nada quiero decirte que el programa que te proporciono puede ser mejorado y digamos que esta a un 98% de ser terminado, solo faltaría que mandes a escribir los Tokens en un archivo.

Quizás podría simplificarse todo el código con el método stringTokenizer() que ya viene en las librerías de Java, pero he tratado de usar un estilo de programación que pueda aplicarse a los lenguajes que mas practico (C++ y Visual Basic) para que otras personas interesadas en dichos lenguajes puedan usarlo.

En fin… Lo primero que tienes que saber es: ¿que es un Analizador Léxico?, y obviamente yo no te lo pienso explicar. Digamos que como yo tienes muy pocos conocimientos de Java, pero ya debes de saber lo básico de manejo y comparación de cadenas, manejo y comparación de caracteres, Arreglos, Funciones y paso de parámetros.

1. Necesitas crear tu lista de símbolos y palabras reservadas, en particular solo me pidieron algo simple:

IF, THEN, WHILE, DO, PROCEDURE, BEGIN, END, CONST, VAR, NUM, AIF, 1234567890

. , ; : ( ) + - * / \ % < <= > >= # = :=

& ! /n ‘ ‘ /t


2. Posteriormente tienes que diseñar lo que yo llamaría un Árbol de Decisiones otros lo conocen como Autómata Finito Discreto

La manera de diseñarlo para mi fue en un principio muy lenta y no me aclaraba muchas dudas a cerca de cómo trabajaría el programa. En base a este se tiene que diseñar una tabla, que aunque no es muy difícil de crear (si se comprende bien), resulta muy tediosa…

Lo que yo muestro en este escrito, es una alternativa a esta manera de crear el diagrama y olvidarte de crear esa enorme tabla.

Estudiando el trabajo de otros, comencé por dibujar el siguiente diagrama en base a los símbolos y palabras que debe aceptar el Analizador Léxico:


Yo quería que el programa trabajara de una manera recursiva (que la función que extrajera los Tokens se llamara así misma y tomara sus propias decisiones), pero en base a este diseño del árbol, también tendría que crear la tabla.

Puesto que no se trata de crear un potente y nuevo lenguaje de programación (en lo cual el uso de la tabla quizás seria de gran ayuda para la velocidad de ejecución) y solo tenemos que crear un analizador léxico. Decidí olvidarme de la tabla y buscar otra manera para que cualquier persona pudiera entender como hacerlo, además de no usar demasiadas variables (reducir la memoria utilizada) y que sea mas lógico de entender… esperando sea de mucha ayuda para ti que estas leyendo.

Cambie un poco la manera de crear el Árbol de Decisiones, quedando de la siguiente manera:


Explicación

Se entiende que en los puntos rojos la decisión se cicla, porque se esta formando una palabra, o un numero, o se esta leyendo espacios, o tabulaciones, o saltos de línea (esto ultimo nunca ocurrirá en el programa pero era bueno tenerlo en cuenta), etc.

Un ejemplo:

Supongamos que estamos en el nodo 0 y el carácter que leímos es una letra, entonces solo se tendrá que pasar al nodo de decisión 0.1 que esta en rojo, y se mantendrá ese estado siempre que escribamos un numero o una letra, en cualquier otro caso pasaremos al estado de decisión 0.1.0, después haremos algo (escribir en un archivo, guardar el Token, presentarlo en pantalla, etc.) y luego volveremos al nodo 0

Fácil no?

Lo mismo será para cualquier otro carácter…

Otro ejemplo:

De alguna manera estamos en el nodo 0.2 y el carácter leído es un punto, pasaremos al estado 0.2.1, en este estado no podemos hacer nada, así que debemos seguir leyendo el siguiente carácter para poder llegar a un estado final, el cual puede ser 0.2.1.0 o 0.2.1.1.0

Comprendido esto puedes ver la estructura del programa:


3. Programar la función

Solo me resta explicar como trabaja la función para analizar las líneas, además de que he incluido comentarios que pueden ayudar a comprender dicha función.

Pudo haber sido más fácil escribir los tokens directamente en el archivo de salida, conforme fueran encontrándose, pero se me antojo mas devolver un arreglo con los tokens encontrados en la línea, simulando a el método stringTokenizer de java.

A la función se le da una cadena de caracteres, ella va analizando carácter por carácter, calculando cual será el siguiente nodo.

nodo = nodoSiguiente(nodo, car);

En base a dicho nodo se tomara una decisión

“SIEMPRE SE AÑADIRÁ EL CARÁCTER A LA PALABRA QUE SE ESTA FORMANDO, AMENOS QUE SE DESEE VOLVER A ANALIZAR EL CARÁCTER, PORQUE ESE CARÁCTER FUE EL CAUSANTE DEL ESTADO FINAL DEL AUTÓMATA”

Por ejemplo tenemos la siguiente línea:

IF;

Si el estado del autómata es 0.1.0 significa que hemos leído el carácter PuntoyComa así que tendremos que procesar la palabra reservada IF, después tendremos que empezar por el nodo 0 volviendo a leer el carácter PuntoyComa para calcular el siguiente estado 0.6

Cuando se llega al final de la línea simplemente se le añade el estado final .0 (por eso decía que nunca se leerá un salto de línea) quedando 0.6.0 por lo que se tendrá que procesar el token PuntoyComa

Lo mismo ocurrirá para todos los símbolos o palabras reservadas.

C:> Presumido modo on

Solo me tomo un par de horas el realizarlo, aunque me tomo mas horas viendo televisión, escuchando música o matando vampiros, para pensar la manera en que quedara de esta forma… fácil de entender y fácil de modificar.

Pienso que cualquier persona con conocimientos básicos podría modificarlo y la verdad no me importa, pues esa era la idea… yo mismo he necesitado la ayuda de otras personas.

Pues bien aquí esta

C:> Presumido modo off




ver codigo

7 comentarios:

Eric dijo...

emm y el codigo???

Anónimo dijo...

Si es verdad... no escribi un enlace a la siguiente entrada

sorry!

LEINAD dijo...

Disculpen las molestias pero me piden un analizador sintactico para java si alguien lo tiene me podria mandar el codigo a mi correo abdiel_evalizq@hotmail.com si no es mucha la molestia se los agradeceria porfavor!! gracias

Grupo Mensajero dijo...

excelente, una duda como creo el fichero Test.plo, y si es posible leer int x; float x=2.5

Javier dijo...

Gracias

Anónimo dijo...

hola disculpa que es el Test.plo como lo ago ok no tengo idea

ayuda porfavor

Anónimo dijo...

Hay otra entrada donde puedes bajarte el codigo. Lee bien y veras un enlace que dice: ver codigo