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:

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

  [0-9]+

• 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í:

public class Token {

    public Tipos getTipo() {
        return tipo;
    }

    public void setTipo(Tipos tipo) {
        this.tipo = tipo;
    }

    public String getValor() {
        return valor;
    }

    public void setValor(String valor) {
        this.valor = valor;
    }

    private Tipos tipo;
    private String valor;

    enum Tipos {
        NUMERO ("[0-9]+"),
        OPERADOR_BINARIO("[*|/|+|-]");

        public final String patron;
        Tipos(String s) {
            this.patron = s;
        }
    }

}

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í:

    private static ArrayList<Token> lex(String input) {
        final ArrayList<Token> tokens = new ArrayList<Token>();
        final StringTokenizer st = new StringTokenizer(input);

        while(st.hasMoreTokens()) {
            String palabra = st.nextToken();
            boolean matched = false;

            for (Tipos tokenTipo : Tipos.values()) {
                Pattern patron = Pattern.compile(tokenTipo.patron);
                Matcher matcher = patron.matcher(palabra);
                if(matcher.find()) {
                    Token tk = new Token();
                    tk.setTipo(tokenTipo);
                    tk.setValor(palabra);
                    tokens.add(tk);
                    matched = true;
                }
            }

            if (!matched) {
                throw new RuntimeException("Se encontró un token invalido.");
            }
        }

        return tokens;
    }

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:

public static void main(String[] args) {
        String input = "11 + 22 - 33";
        ArrayList<Token> tokens = lex(input);
        for (Token token : tokens) {
            System.out.println("(" + token.getTipo() + ": " + token.getValor() + ")");
        }
    }

Deberíamos obtener una salida así:

(NUMERO: 11)
(OPERADOR_BINARIO: +)
(NUMERO: 22)
(OPERADOR_BINARIO: -)
(NUMERO: 33)

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

 String input = "11 + 22 + a - 33";

Obtendremos un error asi:

Exception in thread "main" java.lang.RuntimeException: Se encontró un token invalido.
	at com.ricardogeek.lexer.Lexer.lex(Lexer.java:41)
	at com.ricardogeek.lexer.Lexer.main(Lexer.java:14)
	at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
	at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:39)
	at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:25)
	at java.lang.reflect.Method.invoke(Method.java:597)
	at com.intellij.rt.execution.application.AppMain.main(AppMain.java:144)

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!