En los cursos de compiladores de la universidad, es común que se solicite al estudiante desarrollar un intérprete, una herramienta que reciba como entrada cierto lenguaje de programación y lo ejecute, pero la mayoría de documentación al respecto solo muestra ejemplos de cosas sencillas, como una calculadora o un lenguaje que imprime cadenas en consola. Qué pasa si lo que deseamos es que se ejecuten sentencias de control como el IF o ciclos como la sentencia WHILE y que además estas sentencias soporten muchos niveles de anidamiento, que se declaren variables y se asigne valores a estas variables, que se tenga control de los ámbitos de las variables, en fin, que tenga las funciones básicas de un lenguaje de programación. No es común encontrar este tipo de ejemplos, en lo personal, puedo asegurar que nunca encontré un tutorial en el que se mostrara un ejemplo documentado y bien explicado sobre esto. Por ello es que se elaboró este ejemplo, espero que les sea útil.
Funcionamiento de la aplicación
En este tutorial se desarrolla un intérprete sencillo que permite ejecutar un archivo de entrada que contiene sentencias tales como declaraciones de variables, sentencias de control, impresiones en consola, etc. El lenguaje de programación fue diseñado especialmente para esta aplicación, primero se hace análisis léxico y sintáctico de dicha entrada asistidos por Gold Parser. Una vez Gold Parser genera el árbol de análisis sintáctico, recorreremos dicho árbol para crear nuestro propio árbol. Todo el código se encuentra comentado, por lo que podremos entender la función específica de cada nodo del árbol.
La versión original de este tutorial, realizada con JLex y Cup puede consultarse en el siguiente enlace:
Diseño utilizado para el desarrollo de este ejemplo
Para este ejemplo se crea un objeto por cada una de las sentencias que reconoce nuestra gramática, cada objeto implementa la interfaz instruccion que representa un nodo en nuestro árbol. Esto nos permite tratar todas las sentencias como nodos y asignarle acciones específicas a cada uno según su tipo. Se puede entender nuestra gramática de la siguiente forma:
El lenguaje de entrada
Dentro de la carpeta del proyecto podremos acceder a /bin/Debug 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 (<, >).
La gramatica utilizada para este ejemplo puede encontrarse en la carpeta Gramatica, en el archivo Gramatica.grm. Gold Parser permite la definición de expresiones regulares con las que podremos definir algunos tokens del programa, tales como:
Entero acepta todos los numero que no poseen punto decimal
Decimal acepta todo tipo de números decimales
Car Acepta todos los caracteres imprimibles que pueden venir dentro de una cadena con la excepción de las comillas dobles
Cadena Acepta un conjunto de caracteres delimitados por comillas dobles
ID Head Acepta todas las letras del alfabeto además del guien bajo, se utiliza para la primera letra de los identificadores.
ID Tail Acepta Todos los caracteres alfanuméricos además del guion bajo, se utiliza para todos los caracteres del identificador con la excepción de la primera letra
ID Agrupa ID Head e ID Tail para poder conformar un identificador valido para nuestro lenguaje
De igual manera, Gold Parser posee palabras reservadas para definir los comentarios, por lo que no tendremos que escribir una expresión regular personalizada.
El resultado de la ejecución Al ejecutar la entrada mostrada en nuestro ejemplo, esta fue la salida obtenida:
Sobre la 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. Otra alternativa más detallada es utilizar entornos, un ejemplo de esto se puede encontrar en el libro del curso (Ver Referencias) en la página 87, en donde se habla sobre tablas de símbolos por alcance, a través de entornos anidados. 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 método AddAll de la clase TablaSimbolos.vb, que agrega todos los símbolos del entorno anterior al final del nuevo entorno.
La magia detrás de todo esto: Árbol de sintaxis abstracta (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. Gold Parser nos genera un árbol de análisis sintáctico, sin embargo, es mucho más práctico generar el nuestro que nos permita poder ejecutar las acciones al mismo tiempo que visitamos los nodos. Si creamos nuestro propio árbol tendremos completo control sobre nuestra gramática, tendremos código más entendible, reportes de errores más detallados y menos dolores de cabeza al tratar de encontrar un error. Como se observa en el código fuente, las únicas acciones que realizamos en el árbol de Gold Parser es retornar nodos que nos permitan generar nuestro árbol. En la producción inicial debemos crear nuestro AST, que funcionara como raíz desde la cual debemos comenzar la ejecución de nuestro programa.
En este ejemplo el AST es la pieza más importante, porque al recorrerlo pueden ejecutarse las acciones del código de entrada y ese es el principal objetivo de la aplicación. Esta se conforma únicamente de dos paquetes:
Análisis: Este paquete únicamente contiene la clase SkeletonProgram, que es el que nos genera Gold Parser por defecto y sobre el archivo que crearemos nuestro AST.
Árbol: Posee todas las clases necesarias que nos permiten crear nuestro AST, así como la interfaz operación que es la que permite tratar a todos los nodos del árbol como uno mismo.
Además, es importante destacar que existe un archivo más que se encuentra en la carpeta raíz de nuestro programa, es la clase principal que visual nos crea por defecto y en este caso se denomina Module1.Vb. Desde este archivo comienza toda la ejecución del programa y es desde donde debemos de configurar nuestro parser con el método setup (método por defecto de Gold Parser) y también donde deberemos de mandar a ejecutar las acciones de nuestro árbol con el método ejecutar una vez que estemos seguros que la entrada fue aceptada.
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Luis Lizama, 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 que recibe como entrada un archivo de texto que contiene varias sentencias de un lenguaje de programación diseñado especialmente para esta aplicación. Primero se hace análisis léxico y sintáctico de dicha entrada, durante el análisis sintáctico se carga en memoria un Árbol de Sintaxis Abstracta (AST) que se utiliza posteriormente para ejecutar las sentencias. El analizador se genera con Jison utilizando Nodejs en Ubuntu 18.04. El proyecto completo puede descargarse del siguiente enlace:
Todo el código del proyecto está documentado con comentarios que contienen los detalles de su funcionamiento.
Si se desea una introducción sobre el uso de Jison con Nodejs pueden visitar el post: Mi primer proyecto utilizando Jison (Linux) en el cual se describe los pre-requisitos y cómo crear un proyecto utilizando npm.
El lenguaje de entrada
Dentro de la carpeta del proyecto, hay un archivo de entrada llamado entrada.txt en el cual 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:
/****************************************** * Ejemplo desarrollado por Erick Navarro * * Blog: e-navarro.blogspot.com * * Septiembre - 2015 * ******************************************/
//Se imprime el encabezado imprimir("Tablas de" & " multiplicar");
//Se declara la variable a, de tipo numero numero a; //Se asigna a la variable a el valor 0 a=0; //Se declara la variable c, de tipo numero numero c; //Se asigna a la variable c el valor 0 c=1; //Se imprime un separador imprimir("----------------"); /** * Se imprimen las tablas del 1 al 5 y * para cada tabla, se imprimen los resultados * desde el uno hasta el 5, esto se hace con * dos ciclos while anidados. **/ mientras(a<4+c){ a=a+1; numero b; b=0; mientras(b<4+c){ b=b+1; imprimir(a & " * " & b & " = " & a * b); } imprimir("----------------"); }
//Se asigna a la variable a el valor de 11 a=11; /** * La variable b ya había sido declarada pero * dentro del ámbito del primer ciclo while, * entonces no existe en este ámbito por lo que * debe declararse. **/ numero b; //Se asigna valor de 12 a b y valor de 13 a c b=12; c=13; /** * Se evalua si el valor de la variable a es * mayor que 10, si el b es mayor que 11 y si * el de c es mayor que 12. **/ If(a>10){ imprimir("a es mayor que 10."); if(b>11){ imprimir("a es mayor que 10 y b es mayor que 11."); if(c>12){ imprimir("a es mayor que 10, b es mayor que 11 y c es mayor que 12."); } } }else{ imprimir("a es menor o igual que 10."); }
Como se puede observar, el lenguaje acepta:
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 analizador léxico y sintáctico
En el archivo gramatica.jison detallamos la estructura del lenguaje utilizando Jison. A continuación detallaremos los aspectos más relevantes.
Sobre el analizador léxico
El analizador léxico define los patrones para los tokens que deseamos reconocer. Hacemos uso de expresiones regulares para identificar números, cadenas y comentarios.
Nótese que los comentarios son tratados de la misma manera que los espacios en blanco, no retornamos ningún valor.
1 2 3
\s+ // se ignoran espacios en blanco "//".* // comentario simple línea [/][*][^*]*[*]+([^/*][^*]*[*]+)*[/] // comentario multiple líneas
Sobre el analizador sintáctico
El objetivo principal de nuestro analizador sintáctico es validar que la entrada sea válida y, si lo es, construir el AST (Abstract Syntax Tree). Para lograr esto hacemos uso de funciones utilitarias definidas en un API externa. Esta API contiene toda la lógica necesaria para crear el AST, la idea es centralizar toda esta funcionalidad en un solo lugar, evitando redundancia de funcionalidad y así evitar cometer errores.
Esto también es posible gracias a Nodejs ya que nos permite incluir esta funcionalidad en nuestro script para generar nuestro parser.
La API de Instrucciones
Una de las ventajas de usar Nodejs con Jison es que podemos exportar porciones de scripts de un archivo hacia otro. Para nuestra API definimos constantes y funciones que nos ayudan durante la construcción del AST. Nuestra API se encuentra en el archivo instrucciones.js.
El uso de constantes es altamente recomendado, a través de estos podemos evitar bugs durante el desarrollo. Para este tutorial definimos constantes para los tipos de valores que soporta nuestro lenguaje: números, cadenas e identificadores. También definimos constantes para los tipos de operaciones soportadas y las instrucciones válidas.
// Constantes para los tipos de 'valores' que reconoce nuestra gramática. const TIPO_VALOR = { NUMERO: 'VAL_NUMERO', IDENTIFICADOR: 'VAL_IDENTIFICADOR', CADENA: 'VAL_CADENA', }
// Constantes para los tipos de 'operaciones' que soporta nuestra gramática. const TIPO_OPERACION = { SUMA: 'OP_SUMA', RESTA: 'OP_RESTA', MULTIPLICACION: 'OP_MULTIPLICACION', DIVISION: 'OP_DIVISION', NEGATIVO: 'OP_NEGATIVO', MAYOR_QUE: 'OP_MAYOR_QUE', MENOR_QUE: 'OP_MENOR_QUE', CONCATENACION: 'OP_CONCATENACION' };
// Constantes para los tipos de 'instrucciones' válidas en nuestra gramática. const TIPO_INSTRUCCION = { IMPRIMIR: 'INSTR_IMPRIMIR', MIENTRAS: 'INSTR_MIENTRAS', DECLARACION: 'INSTR_DECLARACION', ASIGNACION: 'INSTR_ASIGANCION', IF: 'INSTR_IF', IF_ELSE: 'INSTR_ELSE' }
Seguidamente, tenemos la definición de una función llamada nuevaOperacion. Nótese que esta función está fuera de nuestra API, es decir no es pública, es para uso interno. Esta función crea objetos genéricos para las operaciones.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
/** * Esta función se encarga de crear objetos tipo Operación. * Recibe como parámetros el operando izquierdo y el operando derecho. * También recibe como parámetro el tipo del operador * @param {*} operandoIzq * @param {*} operandoDer * @param {*} tipo */ function nuevaOperacion(operandoIzq, operandoDer, tipo) { return { operandoIzq: operandoIzq, operandoDer: operandoDer, tipo: tipo } }
La definición de funciones con tareas genéricas también es recomendable para evitar errores.
Finalmente, está la definición de nuestra API. En nuestra API tenemos tres tipos de funciones:
Funciones para Operaciones.
Funciones para Valores
Funciones para Instrucciones.
Cada una de estas funciones representa un Nodo en el AST. Las funciones para operaciones hacen uso de nuestra función privada, de esta forma logramos que nuestros objetos de tipo Operación tengan la misma estructura.
/** * El objetivo de esta API es proveer las funciones necesarias para la construcción de operaciones e instrucciones. */ const instruccionesAPI = {
/** * Crea un nuevo objeto tipo Operación para las operaciones binarias válidas. * @param {*} operandoIzq * @param {*} operandoDer * @param {*} tipo */ nuevoOperacionBinaria: function(operandoIzq, operandoDer, tipo) { return nuevaOperacion(operandoIzq, operandoDer, tipo); },
/** * Crea un nuevo objeto tipo Operación para las operaciones unarias válidas * @param {*} operando * @param {*} tipo */ nuevoOperacionUnaria: function(operando, tipo) { return nuevaOperacion(operando, undefined, tipo); },
/** * Crea un nuevo objeto tipo Valor, esto puede ser una cadena, un número o un identificador * @param {*} valor * @param {*} tipo */ nuevoValor: function(valor, tipo) { return { tipo: tipo, valor: valor } },
/** * Crea un objeto tipo Instrucción para la sentencia Imprimir. * @param {*} expresionCadena */ nuevoImprimir: function(expresionCadena) { return { tipo: TIPO_INSTRUCCION.IMPRIMIR, expresionCadena: expresionCadena }; },
/** * Crea un objeto tipo Instrucción para la sentencia Mientras. * @param {*} expresionLogica * @param {*} instrucciones */ nuevoMientras: function(expresionLogica, instrucciones) { return { tipo: TIPO_INSTRUCCION.MIENTRAS, expresionLogica: expresionLogica, instrucciones: instrucciones }; },
/** * Crea un objeto tipo Instrucción para la sentencia Declaración. * @param {*} identificador */ nuevoDeclaracion: function(identificador) { return { tipo: TIPO_INSTRUCCION.DECLARACION, identificador: identificador } },
/** * Crea un objeto tipo Instrucción para la sentencia Asignación. * @param {*} identificador * @param {*} expresionNumerica */ nuevoAsignacion: function(identificador, expresionNumerica) { return { tipo: TIPO_INSTRUCCION.ASIGNACION, identificador: identificador, expresionNumerica: expresionNumerica } },
/** * Crea un objeto tipo Instrucción para la sentencia If. * @param {*} expresionLogica * @param {*} instrucciones */ nuevoIf: function(expresionLogica, instrucciones) { return { tipo: TIPO_INSTRUCCION.IF, expresionLogica: expresionLogica, instrucciones: instrucciones } },
Para poder utilizar las constantes y el API fuera de este archivo utilizamos la instrucción “module.exports” con el cual exportamos todo lo que deseamos que sea público
Para construir el AST durante nuestro análisis sintáctico importamos nuestra API y las constantes. Esto lo hacemos dentro de los símbolos “%{“ y “}%” en el archivo gramatica.jison
Una vez importemos nuestras constantes y funciones ya podemos hacer uso de ellas en la gramática. Por ejemplo, para la construcción de operaciones aritméticas hacemos uso de la función nuevoOperacionBinaria de nuestra API de Instrucciones, pasamos como parámetros los operandos y el tipo operación (utilizando nuestras constantes).
Para generar el parser ejecutamos el script compilar.sh dentro de nuestro proyecto
1
$ sh compilar.sh
Esto generará el script gramatica.js con el cual ya podremos procesar nuestro archivo de entrada.
La tabla de símbolos
La tabla de símbolos es la que permite el almacenamiento y recuperación de los valores de las variables. Para su implementación hacemos uso de una clase, ya que necesitaremos más de una instancia de tabla de símbolos. Cada ámbito tiene acceso únicamente a su propia tabla de símbolos y a la de los niveles superiores.
Definimos las constantes para los tipos de datos, en este tutorial se hace uso únicamente del tipo de dato numérico.
1 2 3 4
// Constantes para los tipos de datos. const TIPO_DATO = { NUMERO: 'NUMERO' }
Se define una función para crear objetos de tipo Símbolo.
1 2 3 4 5 6 7 8 9 10 11 12 13
/** * Función que crea objetos de tipo Símbolo. * @param {*} id * @param {*} tipo * @param {*} valor */ function crearSimbolo(id, tipo, valor) { return { id: id, tipo: tipo, valor: valor } }
La clase TS define las estructura de una tabla de símbolos y sus funciones para agregar, modificar y obtener símbolos.
/** * Clase que representa una Tabla de Símbolos. */ class TS {
/** * El costructor recibe como parámetro los simbolos de la tabla padre. * @param {*} simbolos */ constructor (simbolos) { this._simbolos = simbolos; }
/** * Función para gregar un nuevo símbolo. * Esta función se usa en la sentencia de Declaración. * @param {*} id * @param {*} tipo */ agregar(id, tipo) { const nuevoSimbolo = crearSimbolo(id, tipo); this._simbolos.push(nuevoSimbolo); }
/** * Función para actualizar el valor de un símbolo existente. * Esta función se usa en la sentencia de Asignación. * @param {*} id * @param {*} valor */ actualizar(id, valor) { const simbolo = this._simbolos.filter(simbolo => simbolo.id === id)[0]; if (simbolo) simbolo.valor = valor; else throw 'ERROR: variable: ' + id + ' no ha sido definida'; }
/** * Función para obtener el valor de un símbolo existente. * @param {*} id */ obtener(id) { const simbolo = this._simbolos.filter(simbolo => simbolo.id === id)[0];
if (simbolo) return simbolo.valor; else throw 'ERROR: variable: ' + id + ' no ha sido definida'; }
/** * Función getter para obtener los símbolos. */ get simbolos() { return this._simbolos; } }
La definición del Intérprete se encuentra en el archivo interprete.js.
Para iniciar con la implementación, primero importamos el parser, las constantes del AST y de la Tabla de Símbolos.
1 2 3 4 5 6 7 8 9 10 11
var fs = require('fs'); var parser = require('./gramatica');
// Constantes para operaciones, instrucciones y valores const TIPO_INSTRUCCION = require('./instrucciones').TIPO_INSTRUCCION; const TIPO_OPERACION = require('./instrucciones').TIPO_OPERACION; const TIPO_VALOR = require('./instrucciones').TIPO_VALOR;
// Tabla de Simbolos const TIPO_DATO = require('./tabla_simbolos').TIPO_DATO; const TS = require('./tabla_simbolos').TS;
Seguidamente, obtenemos el AST a partir del archivo de entrada.
1 2 3 4 5 6 7 8 9 10 11 12 13
let ast; try { // leemos nuestro archivo de entrada const entrada = fs.readFileSync('./entrada.txt'); // invocamos a nuestro parser con el contendio del archivo de entradas ast = parser.parse(entrada.toString());
// imrimimos en un archivo el contendio del AST en formato JSON fs.writeFileSync('./ast.json', JSON.stringify(ast, null, 2)); } catch (e) { console.error(e); return; }
Nótese que se escribe el contenido del AST en un archivo llamado ast.json en formato JSON, esto no es necesario, pero es una forma de ver el contenido del AST en un formato entendible.
El contenido del formato JSON se puede visualizar en cualquier herramienta. Por ejemplo la extensión de Google Chrome JSON Viewer Awesome.
El cual cuenta con una vista gráfica y nos permite visualizar el AST así como también navegar por sus nodos
La función principal del intérprete es de reconocer cada instrucción instrucción y ejecutarla, para esto es necesario recorrer el AST; es por ello que se ha definido la función procesarBloque el cual itera las instrucciones en un ámbito y las ejecuta.
Para iniciar con la ejecución se crea la tabla de símbolos para el ámbito global y se invoca la función procesarBloque con la raíz del AST y la tabla de símbolos del ámbito global.
// Creación de una tabla de simbolos GLOBAL para iniciar con el interprete const tsGlobal = new TS([]);
// Procesamos las instrucciones reconocidas en nuestro AST procesarBloque(ast, tsGlobal);
/** * Este es el método principal. Se encarga de recorrer las instrucciones en un bloque, * identificarlas y procesarlas * @param {*} instrucciones * @param {*} tablaDeSimbolos */ function procesarBloque(instrucciones, tablaDeSimbolos) { instrucciones.forEach(instruccion => { if (instruccion.tipo === TIPO_INSTRUCCION.IMPRIMIR) { // Procesando Instrucción Imprimir procesarImprimir(instruccion, tablaDeSimbolos); } elseif (instruccion.tipo === TIPO_INSTRUCCION.MIENTRAS) { // Procesando Instrucción Mientras procesarMientras(instruccion, tablaDeSimbolos); } elseif (instruccion.tipo === TIPO_INSTRUCCION.DECLARACION) { // Procesando Instrucción Declaración procesarDeclaracion(instruccion, tablaDeSimbolos); } elseif (instruccion.tipo === TIPO_INSTRUCCION.ASIGNACION) { // Procesando Instrucción Asignación procesarAsignacion(instruccion, tablaDeSimbolos); } elseif (instruccion.tipo === TIPO_INSTRUCCION.IF) { // Procesando Instrucción If procesarIf(instruccion, tablaDeSimbolos); } elseif (instruccion.tipo === TIPO_INSTRUCCION.IF_ELSE) { // Procesando Instrucción If Else procesarIfElse(instruccion, tablaDeSimbolos); } else { throw 'ERROR: tipo de instrucción no válido: ' + instruccion; } }); }
Existe una función para procesar cada instrucción.
Las sentencias Mientras, If e If-Else crean nuevas tablas de símbolos antes de procesar las instrucciones dentro de sus bloques de instrucciones. Estas nuevas tablas de símbolos se inicializan con los valores de la tabla de símbolo actual y al terminar la ejecución de la sentencia los valores son eliminados ya que la instancia se crea localmente en el cuerpo de la función.
/** * Función que se encarga de procesar la instrucción Mientras */ function procesarMientras(instruccion, tablaDeSimbolos) { while (procesarExpresionLogica(instruccion.expresionLogica, tablaDeSimbolos)) { const tsMientras = new TS(tablaDeSimbolos.simbolos); procesarBloque(instruccion.instrucciones, tsMientras); } }
/** * Función que se encarga de procesar la instrucción If */ function procesarIf(instruccion, tablaDeSimbolos) { const valorCondicion = procesarExpresionLogica(instruccion.expresionLogica, tablaDeSimbolos);
if (valorCondicion) { const tsIf = new TS(tablaDeSimbolos.simbolos); procesarBloque(instruccion.instrucciones, tsIf); } }
/** * Función que se encarga de procesar la instrucción If-Else * @param {*} instruccion * @param {*} tablaDeSimbolos */ function procesarIfElse(instruccion, tablaDeSimbolos) { const valorCondicion = procesarExpresionLogica(instruccion.expresionLogica, tablaDeSimbolos);
if (valorCondicion) { const tsIf = new TS(tablaDeSimbolos.simbolos); procesarBloque(instruccion.instruccionesIfVerdadero, tsIf); } else { const tsElse = new TS(tablaDeSimbolos.simbolos); procesarBloque(instruccion.instruccionesIfFalso, tsElse); } }
Las sentencias de Declaración y Asignación agregan y modifican valores de la tabla de símbolos. La sentencia Imprimir muestra el valor de una cadena en la consola.
/** * Función que se encarga de procesar la instrucción Imprimir * @param {*} instruccion * @param {*} tablaDeSimbolos */ function procesarImprimir(instruccion, tablaDeSimbolos) { const cadena = procesarExpresionCadena(instruccion.expresionCadena, tablaDeSimbolos); console.log('> ' + cadena); }
/** * Función que se encarga de procesar la instrucción Declaración * @param {*} instruccion * @param {*} tablaDeSimbolos */ function procesarDeclaracion(instruccion, tablaDeSimbolos) { tablaDeSimbolos.agregar(instruccion.identificador, TIPO_DATO.NUMERO); }
/** * Función que se encarga de procesar la instrucción Asignación * @param {*} instruccion * @param {*} tablaDeSimbolos */ function procesarAsignacion(instruccion, tablaDeSimbolos) { const valor = procesarExpresionNumerica(instruccion.expresionNumerica, tablaDeSimbolos) tablaDeSimbolos.actualizar(instruccion.identificador, valor); }
Finalmente, todas las sentencias descritas anteriormente hacen uso de las operaciones numéricas, con cadenas y lógicas las cuales hacen uso de la tabla de símbolos para obtener valores de las variables.
Para las expresiones numéricas evaluamos el tipo de operación y con base en ellos resolvemos el valor apropiado.
/** * De acuerdo con nuestra gramática, aqui, expresión puede ser una operación aritmética binaria (SUMA, RESTA, MULTIPLICACION, DIVISION), * una operación aritmética unaria (NEGATIVO) o un valor correspondiente a un NUMERO o a un IDENTIFICADOR * @param {*} expresion * @param {TS} tablaDeSimbolos * Evaluamos cada caso para resolver a un valor tipo número de acuerdo al tipo de operación. */ function procesarExpresionNumerica(expresion, tablaDeSimbolos) { if (expresion.tipo === TIPO_OPERACION.NEGATIVO) { // Es un valor negado. // En este caso necesitamos procesar el valor del operando para poder negar su valor. // Para esto invocamos (recursivamente) esta función para sesolver el valor del operando. const valor = procesarExpresionNumerica(expresion.operandoIzq, tablaDeSimbolos); // resolvemos el operando // Retornamos el valor negado. return valor * -1; } elseif (expresion.tipo === TIPO_OPERACION.SUMA || expresion.tipo === TIPO_OPERACION.RESTA || expresion.tipo === TIPO_OPERACION.MULTIPLICACION || expresion.tipo === TIPO_OPERACION.DIVISION) { // Es una operación aritmética. // En este caso necesitamos procesar los operandos antes de realizar la operación. // Para esto incovacmos (recursivamente) esta función para resolver los valores de los operandos. const valorIzq = procesarExpresionNumerica(expresion.operandoIzq, tablaDeSimbolos); // resolvemos el operando izquierdo. const valorDer = procesarExpresionNumerica(expresion.operandoDer, tablaDeSimbolos); // resolvemos el operando derecho.
if (expresion.tipo === TIPO_OPERACION.SUMA) return valorIzq + valorDer; if (expresion.tipo === TIPO_OPERACION.RESTA) return valorIzq - valorDer; if (expresion.tipo === TIPO_OPERACION.MULTIPLICACION) return valorIzq * valorDer; if (expresion.tipo === TIPO_OPERACION.DIVISION) return valorIzq / valorDer; } elseif (expresion.tipo === TIPO_VALOR.NUMERO) { // Es un valor numérico. // En este caso únicamente retornamos el valor obtenido por el parser directamente. return expresion.valor; } elseif (expresion.tipo === TIPO_VALOR.IDENTIFICADOR) { // Es un identificador. // Obtenemos el valor de la tabla de simbolos return tablaDeSimbolos.obtener(expresion.valor); } else { throw 'ERROR: expresión numérica no válida: ' + expresion; } }
Para las expresiones con cadenas también validamos el tipo de operación para verificar si es necesario una operación de concatenación. En cualquier caso se resuelve la cadena. También es posible concatenar valores numéricos, para esto resolvemos la expresión apoyándonos de la función para procesar expresiones numéricas.
/** * De acuerdo con nuestra gramática, aqui, expresión puede ser una operacion CONCATENACION, CADENA o una expresión numérica * @param {*} expresion * @param {TS} tablaDeSimbolos * Evaluamos cada caso para resolver a un valor tipo cadena de acuerdo al tipo de operación. */ function procesarExpresionCadena(expresion, tablaDeSimbolos) { if (expresion.tipo === TIPO_OPERACION.CONCATENACION) { // Es una operación de concatenación. // En este caso necesitamos procesar los operandos antes de realizar la concatenación. // Para esto invocamos (recursivamente) esta función para resolver los valores de los operandos. const cadIzq = procesarExpresionCadena(expresion.operandoIzq, tablaDeSimbolos); // resolvemos el operando izquierdo. const cadDer = procesarExpresionCadena(expresion.operandoDer, tablaDeSimbolos); // resolvemos el operando derecho.
// Retornamos el resultado de la operación de concatenación. return cadIzq + cadDer; } elseif (expresion.tipo === TIPO_VALOR.CADENA) { // Es una cadena. // En este caso únicamente retornamos el valor obtenido por el parser directamente. return expresion.valor; } else { // Es una epresión numérica. // En este caso invocamos la función que se encarga de procesar las expresiones numéricas // y retornamos su valor en cadena. return procesarExpresionNumerica(expresion, tablaDeSimbolos).toString() } }
Al igual que las expresiones con cadena, las expresiones lógicas también se apoya en la función que procesa expresiones numéricas para poder evaluar las condiciones booleanas.
1 2 3 4 5 6 7 8 9 10 11 12 13 14
/** * De acuerdo con nuestra gramática, aqui, expresión puede ser una operación lógica MAYOR QUE o MENOR QUE * @param {*} expresion * @param {TS} tablaDeSimbolos * Evaluamos cada caso para resolver a un valor tipo booleando de acuerdo al tipo de operación. */ function procesarExpresionLogica(expresion, tablaDeSimbolos) { // En este caso necesitamos procesar los operandos antes de realizar la comparación. const valorIzq = procesarExpresionNumerica(expresion.operandoIzq, tablaDeSimbolos); // resolvemos el operando izquierdo. const valorDer = procesarExpresionNumerica(expresion.operandoDer, tablaDeSimbolos); // resolvemos el operando derecho.
if (expresion.tipo === TIPO_OPERACION.MAYOR_QUE) return valorIzq > valorDer; if (expresion.tipo === TIPO_OPERACION.MENOR_QUE) return valorIzq < valorDer; }
Para ejecutar nuestro intérprete y procesar el archivo de entrada ejecutamos el siguiente comando:
1
$ node interprete
Y veremos el resultado en consola.
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Rainman Sián, 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:
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.
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:
Descargar el repositorio completo de Irony desde GitHub.
Descomprimimos el repositorio e ingresamos a la carpeta Irony.Interpreter
Dentro de la carpeta Irony.Interpreter, encontraremos el proyecto 015.Irony.Interpreter.csproj, debemos abrir este proyecto con Visual Studio.
Al tener abierto el proyecto en Visual Studio, procedemos a dar click derecho en el nombre del proyecto → “Build Solution” en el nombre del .
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.
Dentro de la carpeta net40 encontraremos el archivo Irony.dll, que utilizaremos en nuestro proyecto.
Creación del proyecto en el que utilizaremos Irony
Abrimos Visual Studio y seleccionamos la opción “File” → “New” → “Project…”.
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.
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.
Luego de pegar el archivo Irony.dll, volvemos al explorador de soluciones y damos click derecho en la carpeta lib, “Add” → “Existing Item…”.
Buscamos el archivo Irony.dll que acabamos de pegar en la carpeta lib y lo agregamos.
Importamos la librería Irony.dll que acabamos de pegar en nuestra carpeta lib, para hacerlo daremos click derecho en “References” → “Add Reference…”
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
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”.
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”.
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.
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 “+”.
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”:
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:
Declarar un objeto de la clase que contiene nuestra gramática, en este caso será un objeto de la clase “Gramatica”.
Crear un objeto de la clase “LanguageData”, el cual recibirá de parámetro la variable de nuestra gramática.
Crear un objeto de la clase “Parser”, el cual recibirá de parámetro la variable de la clase “LenguageData”.
Obtener el AST (Abstract Syntax Tree) de la entrada procesada creando un objeto de la clase “ParseTree”.
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.
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:
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:
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.
Crear el analizador sintáctico a utilizar
Analizar el texto del archivo de entrada
El archivo de “entrada.txt” tiene el siguiente contenido:
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.
