Construyendo un analizador léxico con java

Como hablamos en el post anterior referente a la parte teórica del análisis léxico de un programa de entrada, ahora construiremos un analizador léxico funcional para un lenguaje formal sencillo, utilizando para ello el lenguaje de programación java.

Para este ejercicio asumimos una gramática formal simple que acepta expresiones aritméticas de suma, resta, multiplicación y división.

El código fuente de este sencillo ejercicio puede ser encontrado completo en mi cuenta de github:

https://github.com/RicardoGeek/java-simple-lexer

Ojo En esta fase solo vamos a identificar los tokens que hay en el codigo fuente de entrada y cada uno de sus tipos, no vamos a verificar la precedencia de operadores ni si la expresión aritmética es válida ya que ese es trabajo del analizador sintáctico.

Entonces asumamos un alfabeto con los siguientes lexemas y sus expresiones regulares:

  • Digito
  • Operador Binario

     

Ahora definamos una clase que nos ayude a almacenar estos lexemas en una estructura de datos. llamaremos a esta clase “Token” y sería así:

Explicación:

La clase Token está compuesta de dos campos:

  • “valor” que nos indica el nombre del token en cuestión
  • “tipo” que nos indica el tipo de token en cuestión

Adicionalmente tenemos un enumerador “Tipos” con todos los tipos posibles para este lexer que en este caso son, como ya dijimos numeros y operadores binarios. El enumerador contiene además contiene en su constructor la expresión regular que sirve para encontrar ese lexema en particular.

Ahora bien, ya que tenemos un objeto almacenable en una estructura de datos, vamos a crear nuestra clase Lexer, esta clase tendría un método protagonista que llamaremos simplemente “lex” y sería así:

Explicación:

El método lex toma como entrada un programa fuente (en nuestro caso una expresión aritmética) y devuelve un arreglo de tokens, para ello en las primeras dos líneas definimos un el arreglo que vamos a devolver y un StringTokenizer que es la clase de java que nos ahorra el trabajo sucio de identificar cada palabra separada por un espacio y las devuelve convenientemente en un arreglo.

Entonces cuando ya tenemos el arreglo de palabras en el programa fuente, es tiempo de identificar que tipo de token son y convertirlas en Tokens de verdad.

Para ello por cada palabra que encontramos recorremos los tipos de Token definidos en la clase Token, y utilizamos las clases Pattern y Matcher para determinar el tipo de token que corresponde.

La variable de control “matched” sirve para determinar si el tipo de token es válido o deberíamos arrojar una excepción porque no existe tal cosa en nuestro alfabeto.

Entonces si corremos este metodo asi:

Deberíamos obtener una salida así:

Y si cambiamos la línea de input a algo asi:

Obtendremos un error asi:

Ya que el carácter “a” no es ni un número ni un operador binario.

No olviden revisar la implementación completa en mi repositorio de github.

Y así es como construyes un lexer muy básico… pero muy educativo 🙂

Manos al código!

Loading Comments…
more
Allowed HTML tags and attributes: <a href="" title=""> <blockquote> <code> <em> <strong>