Intérprete sencillo utilizando JavaCC

De no estar familiarizado con la herramienta JavaCC, se recomienda al lector seguir el siguiente tutorial:

• Mi primer proyecto utilizando JavaCC

El desarrollo con JavaCC resulta sencillo, pero la legibilidad de la gramática puede llegar a ser un inconveniente si no se trata con la atención debida, sin embargo, el resto de las funcionalidades que nos ofrece JavaCC son un buen aliciente para utilizarlo, por lo tanto en esta ocasión vamos a desarrollar un intérprete, este contendrá la ejecución de sentencias básicas, como declaraciones de variables, asignaciones, sentencias de control, funciones y demás. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

• Intérprete sencillo utilizando JavaCC

Conceptos básicos

• Intérprete: Es un tipo común de procesador de lenguaje. En vez de producir un programa destino como una traducción, el intérprete ejecuta directamente las operaciones especificadas en el programa de origen (fuente) con las entradas proporcionadas por el usuario.
• Árbol de sintaxis abstracta (AST): es una representación simplificada de la estructura sintáctica del código fuente. A nivel de programación un AST es una estructura de datos que se genera durante el proceso de análisis sintáctico.

Lenguaje de entrada

En la raíz del proyecto hay un archivo llamado entrada.txt, este contiene un ejemplo con las instrucciones que el lenguaje soporta.

Listado instrucciones soportadas

• Declaración de variables
• Asignación de variables
• Evaluación de expresiones aritméticas, lógicas y relaciones
• If…elseif…else
• While
• Continue
• Break
• Return
• Declaración de funciones
• Llamadas a funciones
• Recursividad
• Funciones nativas: pie, toUpper. Pie genera una gráfica pie, y toUpper convierte a mayúsculas cierta cadena.
• Comentarios de una línea y multilínea
• Control de excepciones semánticas

Estructura del archivo Gramatica.jj de JavaCC

La extensión para los archivos JavaCC es .jj, a continuación vamos a describir la estructura del archivo de JavaCC utilizado para este ejemplo.

Sección de opciones
Aquí vamos a indicar que no haga distinción entre mayúsculas y minúsculas, además de indicar que los métodos de nuestro archivo luego de compilados no sean estáticos.

Sección de parserBegin y parserEnd
Aquí vamos a definir el nombre de nuestro paquete, adicionalmente y muy importante todos los import de archivos que vayamos a utilizar en las acciones para generar nuestro AST. Por último vamos a crear una clase vacía, esta es la que vamos a utilizar para invocar a nuestra gramática.

Sección de análisis léxico
En este punto vamos a definir todos los tokens que vamos a utilizar en el lenguaje:

• Sección skip
  Contendrá todos los tokens que javacc va a ignorar cuando los reconozca, por ejemplo los comentarios o saltos de línea, espacios en blanco, etc.

1
2
3
4
5
6
7

SKIP : {
      " "
    | "\t"
    | "\r"
    | "\n"
    | <"//" (~["\n", "\r"])*>
}

• Sección de token
  En esta sección cada vez que se reconozca un lexema este generará un nuevo objeto de tipo token.

1
2
3
4
5

TOKEN : {
      <NUMERO: (["0"-"9"])+>
    | <DECIMAL: (["0"-"9"])+"."(["0"-"9"])+>
    | <ENTERO: "Numero">
}

• Sección more
  Sección utilizada para la creación de estados.

1
2
3
4
5
6
7
8
9

MORE :
{
    "\"" :STRING_STATE
}

<STRING_STATE> MORE:
{
    <~["\""]>
}

Sección de análisis sintáctico
Aquí vamos a definir la gramática y agregar las acciones correspondientes para generar nuestro AST. Ciertas producciones van a generar una clase que tiene cierta funcionalidad donde se indica lo que la ejecución deberá hacer.

Veamos el caso del while

1
2
3
4
5
6
7

/** While -> while(condicion) instrucciones */
AST Mientras() :
{AST e; ArrayList<AST> ins;}
{
    <MIENTRAS> <PARENI> e=Expresion() <PAREND> ins=Bloque() 
    {return new Mientras(e, ins, token.beginLine, token.beginColumn);}
}

Con esta gramática observamos lo siguiente, tenemos dos variables:

• AST e
• ArrayList ins

AST es nuestra clase abstracta asociada con la variable e que contendrá la condición de nuestro while, y el arraylist contendrá una lista de estas clases, esto con el fin de tener una lista de instrucciones.
Como sabemos un while necesita de una condición y una lista de instrucciones, lo cual se cumple en el diseño planteado, por lo tanto vamos a retornar una instancia de la clase Mientras.

Luego de retornar nuestra clase Mientras, el analizador se encarga de continuar la reducción nuestras producciones, y agregar esta clase a una lista de instrucciones ya que la clase Mientras es una instrucción en sí misma.
Al finalizar el análisis de la entrada se debería generar un árbol, que básicamente contiene una lista de instrucciones, y estas instrucciones pueden ser mientras, imprimir, llamadas, etc.
Esta es la idea general detrás de las acciones del análisis sintáctico, retornar clases que van a formar un AST, que nos servirá para el análisis semántico y para la ejecución de nuestras instrucciones.

Análisis semántico y ejecución de código

Aquí nos vamos a encargar de verificar que lo que ejecutemos tenga sentido, vamos a retomar el ejemplo de la clase Mientras, específicamente la sobre-escritura del método interpretar:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

@Override
public Object interpretar(Tabla tabla, Arbol tree) {
    Object valorCondicion = false;
    do {
        Tabla t = new Tabla(tabla);
        valorCondicion = condicion.interpretar(t, tree);
        if (valorCondicion instanceof Excepcion) {
            return valorCondicion;
        }

        if (!(valorCondicion instanceof Boolean)) {
            Excepcion ex = new Excepcion("Semantico", "Se esperaba un valor booleano para la condicion", fila, columna);
            tree.getExcepciones().add(ex);
            return ex;
        }
        Object result = null;
        if ((Boolean) valorCondicion) {
            for (AST m : instrucciones) {
                result = m.interpretar(t, tree);
                if (result instanceof Retorno || result instanceof Excepcion) {
                    return result;
                }
                if(result instanceof Detener){
                    return null;
                }
                if(result instanceof Continue){
                    break;
                }
            }
        }
    } while ((Boolean) valorCondicion);
    return null;
}

Se sobre-escribe la función interpretar que viene desde nuestra clase abstracta AST, cada clase que herede de AST le dará un distinto comportamiento a este método en base a lo que se quiere realizar.

En este caso necesitamos darle el comportamiento de un while, haciendo lo siguiente:

• Declaramos una variable que almacenara nuestra condición
• Iniciamos un ciclo doWhile con la condición establecida en la variable creada anteriormente
• En las instrucciones del do, crearemos un nuevo ámbito para nuestro mientras
• Obtenemos el valor de la condición y lo asignamos a la variable creada al inicio
• Si el valor obtenido es una excepción vamos a retornar este valor para que sea reportado.
• Si continua la ejecución vamos ahora a verificar que el valor obtenido sea de tipo booleano, sino fuera un booleano vamos a generar una nueva excepción y la vamos a retornar para que sea reportada.
• Si la condición fuera valida vamos a tener un if con esta condición y si el valor fuera true inicia la ejecución de cada instrucción en nuestra lista
• Si fuera false, simplemente ignora el if y nuestro doWhile termina
• Dentro del for para recorrer las instrucciones nos encontramos que en cada iteración debemos verificar que lo que obtenemos de valor no sea una excepción ya que si lo fuera la debemos retornar para que sea reportada.
• Además verificamos si fuera un break, continue o return para saber que hacer en cada caso.
• Por ejemplo si fuera retorno vamos a devolver el valor como tal, si fuera un continue únicamente tenemos que ir a la siguiente iteración por lo que cortamos la iteración del ciclo interno donde estamos para que no se sigan ejecutando el resto de las instrucciones y si fuera un break debemos terminar la ejecución del mientras por lo tanto terminamos la ejecución de nuestro doWhile.
  Esta sería la lógica para un ciclo while, y así lo haremos con todas las instrucciones, cada una tendrá una implementación distinta.

Clases importantes del proyecto
Estas clases son clave para el desarrollo de nuestro intérprete y se explicarán a continuación

• Clase abstracta AST
  Contiene los atributos y métodos que tendrán las instrucciones en común, además el método interpretar que será sobre-escrito en cada implementación, la finalidad de esta clase es poder modelar clases de distintos tipos que comparten un comportamiento cómun que en este caso sería que se pueden interpretar.
• Clase símbolo
  Esta clase nos sirve como nodo para crear nuestras variables, vemos que contiene tipo, identificador y valor, aunque esto puede variar dependiendo del tipo de interprete que estemos construyendo.
• Clase tabla
  Esta a tener la función de tabla de símbolos, aquí vamos a almacenar nuestras variables y funciones, nuestras variables las vamos a almacenar en un hashmap y las funciones en un arraylist. Contamos con métodos que nos ayudaran a obtener, guardar variables, obtener y guardar funciones.
• Clase árbol
  Es la clase que nos devuelve el análisis sintáctico contiene las instrucciones que deberán ser ejecutadas, la lista de excepción que vamos a reportar y la tabla global para cuando ejecutemos las llamadas a funciones.
• Clase tipo
  Aquí es donde vamos a definir los tipos que contendrá nuestro interprete.
• Clase función
  Como cualquier otra instrucción, extiende de la clase AST, y recibe una lista de parámetros y el nombre de la función y una lista de instrucciones.
  Y para la ejecución únicamente necesitamos recorrer la lista de instrucciones ejecutando el método interpretar asociado a cada una de estas.

Creación de funciones nativas

Para funciones nativas es muy sencillo, únicamente debemos extender de la clase función y modificar el comportamiento por cualquier otro que deseemos. Tomamos de ejemplo la función nativa aMayuscula, esta recibe en su constructor los mismos datos que la funciones y únicamente se va a diferenciar en el método interpretar donde le daremos una lógica distinta.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

@Override
public Object interpretar(Tabla tabla, Arbol tree) {
    Simbolo simbolo = tabla.getVariable("toUpper%%parametro1");
    if (simbolo == null) {
        Excepcion ex = new Excepcion("Semantico", "No se ha encontrado la variable " + this.nombre + ".", fila, columna);
        tree.getExcepciones().add(ex);
        return ex;
    }
    if (!simbolo.getTipo().equals(new Tipo(Tipo.Tipos.CADENA))) {
        Excepcion ex = new Excepcion("Semantico", "El tipo de los parametros no coinciden.", fila, columna);
        tree.getExcepciones().add(ex);
        return ex;
    }
    return (simbolo.getValor() + "").toUpperCase();
}

Ejecución de la entrada
Para ejecutar la entrada debemos instanciar nuestra gramática, esto sucede en la clase UIController, específicamente dentro del método Ejecutar:

1
2
3

Gramatica parser = new Gramatica(new BufferedReader(new StringReader(entrada.getText())));
Arbol arbol = parser.Analizar();
EjecutarInstrucciones(arbol);

Como mencionamos el resultado de ejecutar nuestra gramática nos devolverá un objeto de tipo Arbol, lo enviamos a un método para tratarlo.
En este método pasamos la consola de la interfaz a nuestro árbol para imprimir cosas, crear la tabla global y asignarla a nuestro árbol, crear las funciones nativas.
Luego recorremos por primera vez nuestras instrucciones en búsqueda de funciones para declararlas, pero solamente funciones no otra instrucción.
Luego recorremos por segunda vez nuestras instrucciones y las ejecutamos utilizando el siempre confiable método interpretar obtenido gracias a nuestra clase abstracta AST. Específicamente con el método EjecutarInstrucciones, de la clase UIController:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

private void EjecutarInstrucciones(Arbol tree) {
    tree.setConsola(consola);
    tree.setGrupo(groupChart);
    Tabla tabla = new Tabla(null);
    tree.setGlobal(tabla);
    crearNativas(tabla);
    // Recorrido 1 para insertar funciones
    tree.getInstrucciones().forEach(m -> {
        if (m instanceof Funcion) {
            tabla.setFuncion((Funcion) m);
        }
    });
    tree.getInstrucciones().forEach(m -> {
        if (!(m instanceof Funcion)) {
            Object result = m.interpretar(tabla, tree);

            if (result instanceof Excepcion) {
                ((Excepcion) result).imprimir(tree.getConsola());
            }
            if (result instanceof Detener) {
                Excepcion ex = new Excepcion("Semantico", "Sentencia break fuera de ciclo.", m.fila, m.columna);
                tree.getExcepciones().add(ex);
                ex.imprimir(tree.getConsola());
            } else if (result instanceof Retorno) {
                Excepcion ex = new Excepcion("Semantico", "Sentencia retorno fuera de funcion.", m.fila, m.columna);
                tree.getExcepciones().add(ex);
                ex.imprimir(tree.getConsola());
            }
        }
    });

    tree.getExcepciones().forEach(m -> {
        System.out.println("" + m.toString());
    });
}

Iniciando funciones nativas
Para las funciones nativas recordemos deben ser creadas antes de iniciar la ejecución de nuestro interprete. Esta creación de las funciones nativas se encuentra en clase UIController, específicamente en el método crearNativas:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public void crearNativas(Tabla t){
    Tipo tipo = new Tipo(Tipo.Tipos.CADENA);
    String nombre = "toUpper";
    ArrayList<AST> parametros = new ArrayList<>();
    parametros.add(new Declaracion(tipo, "toUpper%%parametro1", null, -1, -1));
    ArrayList<AST> instrucciones = new ArrayList<>();
    aMayuscula am = new aMayuscula(tipo, nombre, parametros, instrucciones, -1, -1);
    t.setFuncion(am);
    
    tipo = new Tipo(Tipo.Tipos.CADENA);
    nombre = "pie";
    parametros = new ArrayList<>();
    parametros.add(new Declaracion(new Tipo(Tipos.LISTA), "pie%%parametro1", null, -1, -1));
    parametros.add(new Declaracion(new Tipo(Tipos.LISTA), "pie%%parametro2", null, -1, -1));
    parametros.add(new Declaracion(new Tipo(Tipos.CADENA), "pie%%parametro3", null, -1, -1));
    instrucciones = new ArrayList<>();
    pieChart pc = new pieChart(tipo, nombre, parametros, instrucciones, -1, -1);
    t.setFuncion(pc);
}

Como observamos aquí creamos las funciones nativas de toUpper y pie que mencionamos al inicio. Además los parámetros tienen un nombre especial para que no se confundan con otras variables, al terminar de crearlas las agregamos a nuestra lista de funciones.

Una vez explicado esto procedemos a ejecutar nuestro programa, vemos que contamos con un boton para ejecutar y 2 pestañas, 1 de consola y la otra donde se muestran nuestras graficas:

Agregamos y ejecutamos la entrada proporcionada que produce lo siguiente en la sección de la consola:

Y en la sección de grafica:

Con esto damos por finalizado la explicación de este pequeño proyecto.

Conclusiones

• Como pudimos observar el desarrollo de un interprete es largo, pero a su vez es ordenado.
• Las gramáticas en javaCC pueden ser poco legibles pero altamente sencillas de crear.
• Dry, don’t repeat yourself: si usamos esta filosofía podemos reducir la cantidad de código hecho, por ejemplo en nuestra clase abstracta agregamos código común para todas las clases que la heredan, o con las funciones nativas únicamente heredamos de algo que ya existía, hay que tratar en la manera de lo posible reutilizar el código existente.
• Algo que no se explico porque no era parte del tutorial, pero que es muy útil fue que la interfaz esta hecha en JavaFX, esta nos proporciona una manera más sencilla de utilizar los componentes de la interfaz con nuestra lógica utilizando el modelo MVC.
• La utilización de estados en JavaCC nos puede ayudar en casos donde necesitemos crear tokens más complejos.

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Pavel Vásquez, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.

Fuentes consultadas:

• Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.