domingo, 13 de noviembre de 2011

Un analizador léxico sintáctico con lógica de Sudoku

Cuando me tocó llevar el curso de Autómatas en la Universidad, me pidieron un analizador léxico sintáctico en JAVA, que analizara un determinado lenguaje, sin utilizar jLex, así que me estuve quebrando la cabeza acerca de que lógica utilizar, se me hacía muy difícil ya que no es lo mismo hacerlo a piecito, que con un analizador ya hecho asi como jLex, así que aca muestro la lógica que utilicé y también dejo el código fuente en Pastebin y tambien el proyecto en Netbeans, lo hago porque desde que hice este proyectito ha rolado mas veces que la amigocha buena onda de la U y del Bachillerato, y siempre me llaman para preguntarme como funciona.

El lenguaje a analizar:
Pues como nos dijeron hagan un analizador de cualquier lenguaje de cualquier tipo, incluso pueden inventarse el suyo propio, entonces me inventé un lenguaje estructural, fácil de analizar (nada de ciclos, ni cosas que requieran recursividad para analizar, muy loco), y esto fue lo que me fumé:
  1. GeneraExpresiones ( "PatronExpresion" , "EncajadorExpresión" )
  2. ExpresionGenerada 
  3. O = ( "marrón" , "castaño" ) ;
  4. N  = ( * , "a" ) ;
  5. N = ( + , "b" ) ;
  6. N = ( ? , "b" ) ;
  7. ExpresionEvalua
  8. Evaluar =  "marronaaaaaaaaaaa" ;
Se trata de un lenguaje propuesta para el analisis y generación de expresiones regulares, algo que según para mi en ese tiempo era la mejor solución para la creación de expresiones regulares (aclaro que viendolo bien la definición o propuesta de mi lenguaje es una completa tontera, ya que yo me centré en el analisis de este). Asi que paso a explicarlo linea por linea:

1: Se encuentra el token o palabra reservada GeneraExpresiones, es una palabra que se encuentra definida dentro del lenguaje, asi tambien dentro de los parentesis se encuentran dos parametros, los cuales son "PatronExpresion", "EncajadorExpresion", estos dos parámetros pueden ser pueden ser variables, es decir pueden cambiar por cualquier otro valor que se les pegue la regalada gana, así la primera linea puede quedar:
       GeneraExpresiones ( "no_importa" , "que_sea" )

2: ExpresionGenerada Esta es una palabra parte de la tabla de tokens del lenguaje, es decir ya está predefinida y lo unico que pretende dentro del lenguaje es abrir una serie procedimientos, es como un subencabezado del lenguaje

3 - 6: De estas lineas las unicas expresiones que son parte de la tabla de tokens son:
   N //Variable cuantificador N
   O //Variable alternador O
   = //Simbolo igual
   * //Cuantificador *
   ? //Cuantificador ?
   ( //Simbolo abre paréntesis
   ) //Simbolo cierra paréntesis
 Los que se encuentran entre comillas "a" y  "b" no son parte de la tabla de tokens del lenguaje asi que puede ir lo que sea.

7: ExpresionEvalua Esta palabra tambien es parte de la tabla de tokens, y tambien representa un encabezado.

8: Lo mismo que en las lineas 3-6 solo que en este caso el token que forma parte del lenguaje es Evaluar seguido de una expresion cualquiera entre comillas.

Entonces la expresión mas simple del lenguaje quedaría así:
  1. GeneraExpresiones ( "valorX" , " valorX " )
  2. ExpresionGenerada 
  3. O = ( " valorX " , " valorX " ) ;
  4. N  = ( [+|?|*] , " valorX " ) ;
  5. ExpresionEvalua
  6. Evaluar =  " valorX " ;
Se ve bonito y sencillo vá? pos aqui esta  ,,//,, ..... (jajaja, perdón por la broma), es decir no se trata de un analisis lexico simple, es decir hay que tomar en cuenta los siguientes aspectos:

Hay que corroborar el orden de los tokens: por ejemplo no es lo mismo decir "la niña juega pelota" que "pelota juega la niña", las dos frases están correctamente escritas, es decir todas las palabras estan dentro del diccionario español, pero su significado no es lo mismo.

Después de los encabezados ExpresionGenerada y ExpresionEvalua: los valores de sus contenidos pueden tener el tamaño [1 | ∞] es decir uno o infinitos valores de este.

Los valores en la línea 4 del anterior esquema: pueden tener los valores [+|?|*] es decir pueden ser cualesquiera, y no importando cual sea, aqui ya existe otro problemilla.

Hay que analizar los valores entre comillas: es decir estos valores pueden ser lo que sea, el problema no es tan grave, es sencillo solucionarolo con una funcion que analice la cadena y que tome el primero y último valor de estos y los compare viendo si son comillas.

La solución que propuse:
Pues no me valí de complicados algoritmos, ni tampoco de recursividad, simplemente me basé en el uso de la razón y de las herramientas que ya vienen definida dentro de los lenguajes, y pues me fumé lo siguiente:

1.) Que tal si los valores a lo largo [X] tienen un valor mas compacto, digamos las letras del abecedario en minúsculas.
2.) Que tal si los valores a lo alto [Y] tienen otro valor, digamos también las letras del abecedario solo que en mayúscula.

Entonces mentalmente me vino la siguiente imagen:
Y cual fue mi propuesta para analizar cadenas tanto minúsculas o mayúsculas y que fueran un patrón compacto. Pues las benditas Hashtables, y es aquí donde se basa la mayoría del analizador acá mostrado, y pues si se dan cuenta parece un juego de Sudoku, donde tiene que haber un orden específico para cada fila y cada columna para que el resultado sea correcto. Llámelo burdo o como quiera, la cosa es que esta onda fue la que se me ocurrió, y pues como todo estudiante, cuando tuve la solución, y pues la empecé a echar a andar.

Manos a la obra pues:
Luego de darle a la craneada, comence a echar penca en JAVA, y pues aca está el código fuente de mi proyecto.

<>
<analisis>
<lenguaje>
<manejoArchivos>

No hay comentarios:

Publicar un comentario en la entrada