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.

En este tutorial se desarrolla un intérprete sencillo que permite ejecutar un archivo de entrada que contiene sentencias tales como declaración de variables, sentencias de control, impresiones en consola, etc. El lenguaje de programación fue diseñado especialmente para este ejemplo. El proyecto cuenta con comentarios que explican su funcionamiento.

Las tecnologías a utilizar son:

• Irony: Generador de analizadores léxicos y sintácticos que retorna un AST (Abstract Syntax Tree).
• Visual Studio 2017: Entorno de desarrollo integrado utilizado para programar en C#.
• Windows 10: Sistema Operativo.
• Irony.dll: DLL que permite la integración de Irony con C#.

El proyecto completo de este ejemplo puede descargarse del siguiente enlace:

• Intérprete Sencillo Utilizando Irony

Si desean una pequeña introducción a Irony pueden revisar el post:

• Mi primer proyecto utilizando Irony

En el que se explica paso a paso como utilizar esta herramienta.

El lenguaje de entrada

Dentro de la carpeta del proyecto podremos acceder a /input y allí encontraremos un archivo de entrada llamado “entrada.txt”, en él se muestran ejemplos de todas las funciones del lenguaje diseñado para esta aplicación, al leerlo se puede tener una idea clara de las funciones con las que el lenguaje cuenta, este archivo contiene lo siguiente:

• Comentarios simples, es decir de una sola línea (//)
• Comentarios múltiples, es decir de más de una línea (/ /)
• Concatenación de cadenas, mediante el operador &
• Función Imprimir: Recibe como parámetro una cadena e imprime su valor en consola.
• Declaración de variables: Únicamente se acepta definición de variables de tipo numero incluyendo enteros y decimales.
• Asignación de variables: A cualquier variable se le puede asignar cualquier expresión que tenga como resultado un número.
• Instrucción Mientras: Tiene el comportamiento clásico del ciclo while, ejecuta el ciclo mientras la expresión booleana que recibe sea verdadera. Esta instrucción soporta anidamiento.
• Instrucción If e If-Else: Tiene el comportamiento clásico de las sentencias de selección If e If-Else, evalúa la expresión booleana y ejecuta el bloque de instrucciones en If si es verdadera. En caso contrario y si existe un bloque Else se ejecuta este bloque de instrucciones. Estas instrucciones también soportan anidamiento.
• Expresiones aritméticas: Se soportan las expresiones aritméticas binarias: suma, resta, multiplicación y división. También la expresión unaria: negación. Adicionalmente se soporta expresiones agrupadas en paréntesis. Se maneja la precedencia habitual de las expresiones aritméticas.
• Expresiones booleanas: Comparan dos expresiones que tengan como resultado un número y soportan unicamente los operados mayor que y menor que (<, >).

El resultado de la ejecución
Al ejecutar la entrada mostrada en nuestro ejemplo, esta fue la salida obtenida:

Tabla de símbolos
La tabla de símbolos es una parte importante en el proceso de ejecución del código, es en esta estructura de datos en donde guardamos información de las variables como su tipo, identificador y valor. En esta estructura podemos agregar variables, modificar los valores de las variables existentes, así como obtener sus valores.

Entornos

El manejo de entornos es sumamente importante ya que deberíamos de crear un nuevo entorno por cada alcance, de manera que los entornos superiores no tengan acceso a las variables declaradas en entornos inferiores pero los entornos inferiores puedan acceder tanto a sus variables como a las de los entornos superiores, esto funciona de manera muy similar a una pila, ya que el ultimo entorno creado debería ser el primero en ser eliminado.

En este ejemplo, esto se logra mediante el creando una tabla local para cada sentencia ejecutada que posea un ámbito propio, como el If, While, etc. Luego de crear la tabla local se agregan todos los símbolos de la tabla del ámbioto padre y se utiliza esta tabla local como tabla principal, al terminar de ejecutar la sentencia esta tabla local desaparece, pues fue declarada dentro de la sentencia que se ejecuta.

Árbol de análisis abstracto AST

Un á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.
En el código de Irony lo vamos armando por medio de listas de instrucciones, donde cada sentencia es una instrucción y en el bloque contenido en esta sentencia tendríamos otra lista de instrucciones, armando así un árbol en donde cada nodo es un objeto que implementa la interfaz instrucción y puede contener múltiples hijos que serían otros objetos que implementan la interfaz instrucción, que serían otras instrucciones.

El código de nuestro proyecto está organizado en dos paquetes:

• analizador: que contiene los archivos de Irony.
• arbol: que contiene todas las clases que forman parte del AST, que se utiliza como estructura primaria en la aplicación.

Teniendo únicamente una clase afuera que seria la clase principal de la aplicación Program.cs.

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Julio Arango, 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.

Se desarrollará un intérprete que recibe como entrada varias expresiones aritméticas y presenta como salida el resultado de dichas expresiones evaluadas.

Las tecnologías a utilizar son:

• Irony: Generador de analizadores léxicos y sintácticos que retorna un AST (Abstract Syntax Tree).
• Visual Studio 2017: Entorno de desarrollo integrado utilizado para programar en C#.
• Windows 10: Sistema Operativo.
• Irony.dll: DLL que permite la integración de Irony con C#.

El proyecto completo puede descargarse del siguiente enlace:

• Mi primer proyecto utilizando Irony

Irony

Irony es un kit de desarrollo para implementar lenguajes en la plataforma .NET. A diferencia de la mayoría de las soluciones de estilo yacc / lex existentes, Irony no emplea ninguna generación de scanner (analizador léxico) o parser (analizador sintáctico) a partir de especificaciones gramaticales escritas en un meta-lenguaje especializado. En Irony, la gramática del lenguaje se codifica directamente en C# utilizando la sobrecarga de operadores para expresar construcciones gramaticales. Los módulos de scanner y parser de Irony utilizan la gramática codificada como una clase de C# para controlar el proceso de análisis. En la página principal de Irony, se anuncia que el proyecto se ha movido a un repositorio en GitHub.

Analizador léxico (Scanner)

La principal tarea de un analizador léxico es leer los caracteres de entrada del programa fuente, agruparlos en lexemas y producir como salida una secuencia de tokens.

• Un token es un par que consiste en un nombre de token y un valor de atributo opcional.

• Un lexema es una secuencia de caracteres en el programa fuente, que coinciden con el patrón para un token y que el analizador léxico identifica como una instancia de este tóken.

• Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.

Analizador sintáctico (Parser)

El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generarse con la gramática para el lenguaje fuente. Una gramática proporciona una especificación precisa y fácil de entender de un lenguaje de programación.

Pre-requisitos

• Obtención del archivo Irony.DDL

El proyecto de Irony anteriormente mencionado es un proyecto de C#, el cual contiene la aplicación de Irony, sin embargo, a nosotros únicamente nos interesa las librerías que este proyecto genera, para obtener dichas librerías debemos seguir los siguientes pasos:

1. Descargar el repositorio completo de Irony desde GitHub.

2. Descomprimimos el repositorio e ingresamos a la carpeta Irony.Interpreter

3. Dentro de la carpeta Irony.Interpreter, encontraremos el proyecto 015.Irony.Interpreter.csproj, debemos abrir este proyecto con Visual Studio.

4. Al tener abierto el proyecto en Visual Studio, procedemos a dar click derecho en el nombre del proyecto → “Build Solution” en el nombre del .

5. Luego de haber ejecutado exitosamente la opción “Build Solution” se creará la carpeta bin/Debug dentro de la carpeta del proyecto Irony.Interpreter. Encontraremos en esta carpeta generada dos carpetas: net40, netstandard2.0. Nosotros escogeremos la carpeta net40, que corresponde a .NET Framework 4.0, nosotros escogeremos esta que sería la versión más reciente, que además es compatible con el proyecto que crearemos en Visual Studio 2017.

6. Dentro de la carpeta net40 encontraremos el archivo Irony.dll, que utilizaremos en nuestro proyecto.

• Creación del proyecto en el que utilizaremos Irony

1. Abrimos Visual Studio y seleccionamos la opción “File” → “New” → “Project…”.

2. Una vez abierto el wizard para crear nuevos proyectos seleccionamos el apartado “Visual C#” → “Windows Desktop” → “Console App (.NET Framework)” y le pondremos como nombre ProyectoIronyCS.

3. Posteriormente creamos una carpeta lib dentro de nuestro proyecto, para ello vamos al explorador de soluciones y hacemos click derecho en el nombre del proyecto, “Add” → “New Folder”. En la carpeta lib recién creada, pegamos el archivo Irony.dll anteriormente generado.

4. Luego de pegar el archivo Irony.dll, volvemos al explorador de soluciones y damos click derecho en la carpeta lib, “Add” → “Existing Item…”.

5. Buscamos el archivo Irony.dll que acabamos de pegar en la carpeta lib y lo agregamos.

6. Importamos la librería Irony.dll que acabamos de pegar en nuestra carpeta lib, para hacerlo daremos click derecho en “References” → “Add Reference…”

7. Esto nos desplegara una nueva ventana, seleccionamos la opción “Browse…” y seleccionamos nuestro archivo .dll y daremos click en aceptar.

• Creación de la gramática

1. La creación de la gramática se realiza por medio de un archivo .cs, para ello agregaremos primero una carpeta a la solución con el nombre de analizador, esto no es completamente necesario, lo hacemos para tener el código organizado.
   Para crear la carpeta es clic derecho sobre el nombre de nuestro proyecto en el explorador de soluciones. “Add” → “New Folder”, le asignamos el nombre “analizador”.

2. Dentro de la carpeta creamos una nueva clase de nombre “Gramatica” que contendrá toda la gramática para Irony, para ello hacemos click derecho sobre la carpeta “Add” → “Class”.

3. En la clase “Gramatica” incorporamos el código de la gramática correspondiente a este ejemplo, dicho código puede consultarse en el repositorio.

• Explicación de la gramática creada

A continuación se explican los principales elementos de la clase gramática:

• Se importan las librerías de Irony a utilizar

1
2

using Irony.Ast;
using Irony.Parsing;

• Nos aseguramos de que la clase “Gramatica” herede de la clase “Grammar” de Irony.Parsing.

1

class Gramatica : Grammar

• Una de las principales características de Irony es poder organizar todo en regiones, para crear una región se debe escribir el nombre de la región de la siguiente manera:

  • Se comienza la región con “#region ” seguido del nombre de la región
  • Se finaliza la región con “#endregion”

• Para la gramática anterior se definen las siguientes regiones:

  • ER: Expresiones regulares de los tokens que nuestra gramática reconocerá.
  • Terminales: Conjunto de terminales que serán utilizados en nuestra gramática, que no fueron aceptados por ninguna de las expresiones regulares definidas anteriormente.
  • No terminales: Conjunto de no terminales que serán utilizados en nuestra gramática.
  • Gramática: Región donde se define la gramática.
  • Preferencia: Configuraciones especiales necesarias para el uso de Irony.

• La gramática debe reconocer números enteros y decimales, por lo que creamos las expresiones regulares para reconocer estos tokens. Para ello se crean objetos del tipo “RegexBasedTerminal”, el cual recibirá de parámetros: el nombre con que se va a reducir y la expresión regular a cumplir.

1

var NUMERO = new NumberLiteral("Numero");

• Posteriormente se escriben los terminales, para estos no es necesario escribir expresiones regulares pues son caracteres simples o bien palabras reservadas por esta razón es que no se incluyeron en la región ER. Para definir los terminales se crean variables instanciadas con la función “ToTerm”, que recibe de parámetro el símbolo terminal con el que debe de cumplir, para el ejemplo se definieron los siguientes:

1
2
3
4
5
6
7
8
9
10

var REVALUAR = ToTerm("Evaluar");
var PTCOMA = ToTerm(";");
var PARIZQ = ToTerm("(");
var PARDER = ToTerm(")");
var CORIZQ = ToTerm("[");
var CORDER = ToTerm("]");
var MAS = ToTerm("+");
var MENOS = ToTerm("-");
var POR = ToTerm("*");
var DIVIDIDO = ToTerm("/");

• Se agrega precedencia a los operadores aritméticos, esto se hace con la función “RegisterOperators” que recibe como parámetro el nivel de precedencia y la lista de terminales que corresponde a dicho nivel.

1
2

RegisterOperators(1, MAS, MENOS);
RegisterOperators(2, POR, DIVIDIDO);

• Se crean los No Terminales para nuestra gramática, para esta declaración se deben crear objetos de tipo “NonTerminal” que en su constructor recibe de parámetro el nombre del no terminal.

1
2
3
4

NonTerminal ini = new NonTerminal("ini");
NonTerminal instruccion = new NonTerminal("instruccion");
NonTerminal instrucciones = new NonTerminal("instrucciones");
NonTerminal expresion = new NonTerminal("expresion");

• Con lo anterior definido, se crea la gramática, para ello es importante resaltar los siguientes puntos:

  • Toda producción debe iniciar con el nombre de algún no terminal previamente declarado y el atributo Rule “Produccion.Rule”.
  • Se finalizan las producciones con punto y coma.
  • Se pueden tener diferentes producciones en un solo no terminal, para ello cada una de ellas se separa con un “|”.
  • Para concatenar terminales o no terminales a la producción se debe usar siempre el signo “+”.

• Gramática utilizada:

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

ini.Rule = instrucciones;

instrucciones.Rule = instruccion + instrucciones
    | instruccion;

instruccion.Rule = REVALUAR + CORIZQ + expresion + CORDER + PTCOMA;

expresion.Rule = MENOS + expresion
    | expresion + MAS + expresion
    | expresion + MENOS + expresion
    | expresion + POR + expresion
    | expresion + DIVIDIDO + expresion
    | NUMERO
    | PARIZQ + expresion + PARDER;

Para finalizar, es necesario declarar nuestra producción de inicio, para ello asignamos al atributo Root el no terminal con el cual comenzara nuestra gramática.

1

this.Root = ini;

• Recorrido del AST

Para realizar este recorrido se crea la clase “Sintactico” dentro de la carpeta analizador, tal como creamos la clase “Gramatica”:

El código de la clase “Sintactico”, puede consultarse en el repositorio.

A continuación analizaremos el contenido de la clase “Sintactico”, pero antes de continuar es necesario tener presentes los siguientes conceptos de Irony:

• ParseTree: AST devuelto por Irony que será posteriormente recorrido y analizado.
• ParseTreeNode: Cada uno de los nodos del ParseTree, el atributo mas importante de este nodo es:
  • ChildNodes: Atributo de cada ParseTreeNode, este atributo es de tipo Array y contiene todas las cualidades de una lista, tales como Count, ElementAt, etc. Si esta lista esta vacía significa que el nodo es un nodo hoja, caso contrario es un subárbol.

Como ya hemos mencionado, Irony no acepta acciones entre sus producciones, se limita a devolver el AST (Abstract Syntax Tree) que arma luego de ser aceptada la cadena de entrada.

Dentro de la clase “Sintactico”, podemos encontrar el método analizar para cargar el árbol y disparar el recorrido de dicho árbol a través de una llamada al método instrucciones a la que se le manda el nodo raíz del árbol.

1
2
3
4
5
6
7
8
9
10
11

public void analizar(String cadena)
{
    Gramatica gramatica = new Gramatica();
    LanguageData lenguaje = new LanguageData(gramatica);
    Parser parser = new Parser(lenguaje);
    ParseTree arbol = parser.Parse(cadena);
    ParseTreeNode raiz = arbol.Root;

    instrucciones(raiz.ChildNodes.ElementAt(0));

}

En el método tenemos lo siguiente:

1. Declarar un objeto de la clase que contiene nuestra gramática, en este caso será un objeto de la clase “Gramatica”.
2. Crear un objeto de la clase “LanguageData”, el cual recibirá de parámetro la variable de nuestra gramática.
3. Crear un objeto de la clase “Parser”, el cual recibirá de parámetro la variable de la clase “LenguageData”.
4. Obtener el AST (Abstract Syntax Tree) de la entrada procesada creando un objeto de la clase “ParseTree”.
5. Obtener la raíz del árbol con el atributo “root” del ParseTree, este es un objeto de tipo “ParseTreeNode” y contiene toda la información del nodo, en este caso el nodo raíz.
6. Invocar el método instrucciones enviándole como parámetro el nodo raíz del AST.

Para recorrer el AST (Abstract Syntax Tree) es importante comprender cómo está armado según la gramática definida. Para la entrada: “Evaluar[1+1];”, por ejemplo, el árbol que arma nuestra gramática es:

Analizando la imagen con la estructura del árbol tenemos que:

• Los No terminales se guardan en el nodo únicamente con el nombre que se les dio para reducir al momento de declararlos.
• Los Terminales se guardan junto a un Keyword.
• Los Token dados con expresiones regulares, guardan el valor original con que coincidió la ER, seguido del nombre que se le dio para reducir.

Teniendo lo anterior en cuenta creamos dentro de la clase “Sintactico” un set de funciones representativas para cada producción, estas siempre recibirán como parámetro el nodo padre y usaran la información almacenada en los nodos para ejecutar las acciones correspondientes.

• Para las producciones del no terminal “instrucciones”, tenemos la siguiente función:

1
2
3
4
5
6
7
8
9
10

public void instrucciones(ParseTreeNode actual) {
    if (actual.ChildNodes.Count == 2)
    {
        instruccion(actual.ChildNodes.ElementAt(0));
        instrucciones(actual.ChildNodes.ElementAt(1));
    }
    else {
        instruccion(actual.ChildNodes.ElementAt(0));
    }
}

En nuestra gramática, el no terminal “instrucciones”, contaba con 2 posibles producciones, una en la cual tenia dos hijos y en la otra solamente uno, con esta información y usando la propiedad ChildNodes, hacemos el recorrido de esa producción, haciendo llamadas a otras funciones según el no terminal encontrado.

• Para la producción del no terminal “instruccion”, tendremos la siguiente función:

1
2
3

public void instruccion(ParseTreeNode actual) {
    Console.WriteLine("El valor de la expresion es: " + expresion(actual.ChildNodes.ElementAt(2)));
}

Este no terminal posee solamente una producción, por lo cual no es necesario evaluar condiciones para determinar qué método debe ejecutar posteriormente. Este método imprime “El valor de la expresión es:”, seguido del resultado que nos devuelve la llamada a expresión.

• Para la producción de “expresion”, tendremos la siguiente función:

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

public double expresion(ParseTreeNode actual) {
    if (actual.ChildNodes.Count == 3) {
        string tokenOperador = actual.ChildNodes.ElementAt(1).ToString().Split(' ')[0];
        switch (tokenOperador) {
            case "+":
                return expresion(actual.ChildNodes.ElementAt(0))  + expresion(actual.ChildNodes.ElementAt(2));
            case "-":
                return expresion(actual.ChildNodes.ElementAt(0)) - expresion(actual.ChildNodes.ElementAt(2));
            case "*":
                return expresion(actual.ChildNodes.ElementAt(0)) * expresion(actual.ChildNodes.ElementAt(2));
            case "/":
                return expresion(actual.ChildNodes.ElementAt(0)) / expresion(actual.ChildNodes.ElementAt(2));
            default:
                return expresion(actual.ChildNodes.ElementAt(1));
        }

    }
    else if (actual.ChildNodes.Count == 2)
    {
        return -1 * expresion(actual.ChildNodes.ElementAt(1));
    }
    else
    {
        return Double.Parse(actual.ChildNodes.ElementAt(0).ToString().Split(' ')[0]);
    }
}

Como en los casos anteriores, debemos plantear condiciones para determinar qué producción se está reconociendo, estas condiciones pueden basarse en la cantidad de hijos de la producción.

• Si tiene un hijo se trata de un número entero o decimal, por lo cual retornamos únicamente el valor del número.
• Si tiene dos hijos es la producción de “menos <expresión>” por lo cual multiplicamos el valor de la expresión por menos uno.

• Si tiene 3 hijos puede tratarse de una suma, resta, multiplicación o división, para determinar de cuál se trata, recogemos el valor del hijo de en medio que contiene el operador y ejecutamos según corresponda, esto se hace dentro de la sentencia switch del método.

• Interpretación del archivo de entrada

Esta interpretación se ejecuta dentro del método Main de la clase “Program” que se creo automáticamente en nuestro proyecto.

En esta clase se importa la referencia a la carpeta analizador para poder usar la clase Sintactico recién creada:

1

using ProyectoIronyCS.sol.com.analizador;

Y en el método Main encontramos lo siguiente:

1
2
3

string text = System.IO.File.ReadAllText(Path.Combine(AppDomain.CurrentDomain.BaseDirectory, @"..\..\input", "entrada.txt"));
Sintactico sintac = new Sintactico();
sintac.analizar(text);

Estos comandos realizan las siguientes acciones:

1. Cargar el contenido del archivo “entrada.txt” que debe ser creado dentro de la carpeta /input que también debemos crear dentro de nuestro proyecto.
2. Crear el analizador sintáctico a utilizar
3. Analizar el texto del archivo de entrada

El archivo de “entrada.txt” tiene el siguiente contenido:

1
2
3
4
5

Evaluar[1+1];
Evaluar[1+1*2];
Evaluar[-(1+1*6/3-5+7)];
Evaluar[-(1+1*6/3-5+1*-2)];
Evaluar[-(1+1)];

Y tras analizarlo con nuestra solución genera la siguiente salida:

Como podemos ver, obtenemos la salida esperada.

Y el AST que formaría dicha entrada sería:

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Julio Arango, 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.