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.
Jison toma una gramática libre de contexto como entrada y produce código JavaScript capaz de parsear el lenguaje descrito por dicha gramática. Una vez se tenga el script generado podemos usarlo para parsear la entrada y aceptarla, rechazarla o ejecutar acciones con base en la entrada. Si se está familiarizado con Bison, Yacc o algún otro similar ya se está listo para iniciar. Jison genera tanto el analizador léxico como el analizador sintáctico.
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.
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.
En Jison se definen tanto el analizador léxico como el sintáctico. Esto es una gran ventaja pues podemos trabajar en una sola herramienta.
Pre-requisitos
Para este ejemplo hace falta que tengamos instalado:
La bandera -g nos sirve para indicar que instalaremos Jison de manera global, es decir, estará disponible en cualquier directorio del sistema.
Crear nuestro proyecto
Usaremos npm para crear nuestro proyecto. Primero crearemos un nuevo folder, en este caso lo llamaremos ProyectoJisonUbuntu. Para esto abrimos una nueva terminal, nos ubicamos donde queremos crear el proyecto y ejecutamos el siguiente comando:
1
$ mkdir ProyectoJisonUbuntu
Y luego ingresamos al directorio con el siguiente comando:
1
$ cd ProyectoJisonUbuntu
Ahora procedemos a iniciar el proyecto con npm. Para esto ejecutamos el siguiente comando:
1
$ npm init -y
Con esto habremos iniciado el proyecto. La bandera -y sirve para seleccionar valores por defecto en los parámetros de inicialización.
Ahora nos pasamos a nuestro editor de texto, en este caso usaremos Visual Studio Code. Ejecutamos el siguiente comando para abrir Code con nuestro proyecto directamente.
1
$ code .
Code se desplegará con nuestro proyecto llamado ProyectoJisonUbuntu
Nótese que únicamente contiene el archivo package.json el cual fue creado por el comando npm init.
Procedemos a crear un nuevo archivo llamado gramatica.jison
Código Fuente para el analizador léxico y sintáctico
En el archivo gramática.jison le indicamos a Jison la descripción de nuestra gramática.
Explicación del código fuente para el analizador léxico
Iniciamos indicando que queremos iniciar con la definición léxica, posteriormente agregamos las opciones que deseamos. En este caso indicamos que nuestro analizador no distinguirá diferencias entre mayúsculas y minúsculas.
1 2 3 4
/* Definición Léxica */ %lex
%options case-insensitive
A diferencia de otras herramientas, Jison por defecto cuenta la posición de línea y columna de los caracteres y acepta el conjunto de caracteres unicode.
Luego escribimos los patrones para los tokens que deseamos reconocer. Para cada uno de ellos debemos retornar el nombre asociado al token.
Jison también soporta el uso de expresiones regulares para identificar patrones. En las siguientes instrucciones escribimos una expresión regular para identificar espacios en blanco e indicamos que al ser reconocidos no hacemos nada. Esto se hace a través de un par de llaves vacíos.
1 2 3
/* Espacios en blanco */ [ \r\t]+ {} \n {}
Escribimos expresiones regulares para identificar enteros y decimales.
Las últimas dos expresiones son para reconocer el fin de la entrada y caracteres no válidos.
1 2 3 4
<<EOF>> return'EOF';
. { console.error('Este es un error léxico: ' + yytext + ', en la linea: ' + yylloc.first_line + ', en la columna: ' + yylloc.first_column); } /lex
En caso de encontrarse con un error léxico lo desplegamos en consola.
Explicación del código fuente para el analizador sintáctico
Otra de las ventajas de Jison es que en el mismo archivo podemos definir nuestro análisis sintáctico haciendo uso de los tokens previamente definidos en la sección del analizador léxico.
Primeramente definimos la asociatividad y precedencia de los operadores, ya que la gramática escrita es ambigua, es necesario definir una precedencia para que el analizador no entre en conflicto al analizar, en este caso la precedencia es la misma que la de los operadores aritméticos, la precedencia más baja la tienen la suma y la resta, luego están la multiplicación y la división que tienen una precedencia más alta y por último está el signo menos de las expresiones negativas que tendría la precedencia más alta
Debemos indicarle a Jison cual será nuestro símbolo Inicial.
1
%start ini
Finalmente escribimos nuestras producciones, aquí vemos otra de las ventajas de Jison, cada No Terminal no debe definirse previamente, esto lo hace más práctico pero a la vez se debe de tener más cuidado con errores de escritura.
Al final de cada producción se puede incluir código javascript entre llaves “{ <código javascript> }”. Para sintetizar un valor asociado al no terminal de lado izquierdo de la producción hacemos uso de la variable $$. Esta variable es propia de Jison. Como podemos ver, para cada producción del no terminal “expresion” sintetizamos el valor de la operación aritmética o el valor del token aceptado.
La variable $$ puede tomar cualquier valor, recordemos que Jison al estar basado en javascript el tipo puede ser dinámico.
Nótese el terminal EOF, que indica el fin de la entrada, debe agregarse en nuestra gramática luego de haber reconocido nuestra entrada, esto indicará que hemos terminado. Si se omite este terminal obtendremos una excepción cuando nuestro analizador alcance el final del archivo.
Por último, podemos manejar también las producciones de error para el manejo de errores sintácticos.
El archivo de compilación
Para facilitar la compilación de nuestra gramática y poder obtener el script para nuestro parser procedemos a escribir un archivo sh.
Para esto creamos un nuevo archivo en Code llamado compilar.sh con el siguiente contenido:
1 2 3 4 5 6 7
#!/bin/bash
echo"Procesando gramática..."
jison gramatica.jison
echo"Gramática procesada..."
Para ejecutar nuestro script ejecutamos el siguiente comando en la terminal:
1
$ sh compilar.sh
Nos debe aparecer el siguiente resultado:
Si hubiese algún error debemos revisar que nuestra gramática esté correcta.
El comando nos generará el script en un archivo llamado gramatica.js en nuestro proyecto. Este es el script que utilizaremos para procesar nuestros archivos de entrada.
Creando un archivo de entrada para nuestro analizador
Creamos un nuevo archivo de texto utilizando nuestro editor llamado entrada.txt. El contenido de este archivo es el siguiente:
Necesitamos de un script que nos ayude a leer el archivo de entrada e invocar a nuestro parser con su contenido. Para esto creamos un nuevo archivo de texto y lo nombramos parser.js.
Su contenido es el siguiente:
1 2 3 4 5 6 7 8
var fs = require('fs'); var parser = require('./gramatica');
Hacemos uso de la librería fs de Nodejs para leer archivos y también de nuestro parser. Esto lo hacemos a través de la función require.
Luego invocamos al método readFile el cual lee nuestro archivo de entrada ‘entrdata.txt’. Este método devuelve dos parámetros, err el cual indica si hubo algún error y data, que almacena el contenido del archivo.
Validamos que no haya ocurrido error y con el contenido de nuestro archivo de entrada invocamos a nuestro parser.
Para ejecutar este script corremos el siguiente comando:
1
$ node parser
Como podemos ver, obtenemos la salida esperada.
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.
