Mi primer proyecto utilizando Irony

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.