Mi primer proyecto utilizando Jison (Linux)

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

Las tecnologías a utilizar son:

• Jison: Generador de analizadores léxicos y sintácticos.
• Nodejs: Es un entorno en tiempo de ejecución, multiplataforma, capaz de ejecutar javascript fuera de un explorador.
• Ubuntu 18.04: Sistema operativo.
• Visual Studio Code: Es un editor de código ligero pero poderoso. Viene con soporte integrado para JavaScript, Nodejs, entre otros.

El proyecto completo lo pueden descargar del siguiente enlace:

• Mi primer proyecto utilizando Jison con Nodejs (Ubuntu)

Jison

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:

• Nodejs
• npm

Para instalar Nodejs en Ubuntu basta con ejecutar el siguiente comando:

1

$ sudo apt install nodejs

Para verificar que la instalación haya sido correcta ejecutamos el siguiente comando:

1

$ nodejs --version

Luego procedemos a instalar npm. Para esto ejecutamos el siguiente comando:

1

$ sudo apt install npm

Y verificamos la instalación con el siguiente comando:

1

$ npm --version

Instalar Jison

Instalamos Jison con el siguiente comando:

1

$ sudo npm install jison -g

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/**
 * Ejemplo mi primer proyecto con Jison utilizando Nodejs en Ubuntu
 */

/* Definición Léxica */
%lex

%options case-insensitive

%%

"Evaluar"           return 'REVALUAR';
";"                 return 'PTCOMA';
"("                 return 'PARIZQ';
")"                 return 'PARDER';
"["                 return 'CORIZQ';
"]"                 return 'CORDER';

"+"                 return 'MAS';
"-"                 return 'MENOS';
"*"                 return 'POR';
"/"                 return 'DIVIDIDO';

/* Espacios en blanco */
[ \r\t]+            {}
\n                  {}

[0-9]+("."[0-9]+)?\b    return 'DECIMAL';
[0-9]+\b                return 'ENTERO';

<<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

/* Asociación de operadores y precedencia */

%left 'MAS' 'MENOS'
%left 'POR' 'DIVIDIDO'
%left UMENOS

%start ini

%% /* Definición de la gramática */

ini
	: instrucciones EOF
;

instrucciones
	: instruccion instrucciones
	| instruccion
	| error { console.error('Este es un error sintáctico: ' + yytext + ', en la linea: ' + this._$.first_line + ', en la columna: ' + this._$.first_column); }
;

instruccion
	: REVALUAR CORIZQ expresion CORDER PTCOMA {
		console.log('El valor de la expresión es: ' + $3);
	}
;

expresion
	: MENOS expresion %prec UMENOS  { $$ = $2 *-1; }
	| expresion MAS expresion       { $$ = $1 + $3; }
	| expresion MENOS expresion     { $$ = $1 - $3; }
	| expresion POR expresion       { $$ = $1 * $3; }
	| expresion DIVIDIDO expresion  { $$ = $1 / $3; }
	| ENTERO                        { $$ = Number($1); }
	| DECIMAL                       { $$ = Number($1); }
	| PARIZQ expresion PARDER       { $$ = $2; }
;

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.

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

%%

"Evaluar"           return 'REVALUAR';
";"                 return 'PTCOMA';
"("                 return 'PARIZQ';
")"                 return 'PARDER';
"["                 return 'CORIZQ';
"]"                 return 'CORDER';

"+"                 return 'MAS';
"-"                 return 'MENOS';
"*"                 return 'POR';
"/"                 return 'DIVIDIDO';

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.

1
2

[0-9]+("."[0-9]+)?\b    return 'DECIMAL';
[0-9]+\b                return 'ENTERO';

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

1
2
3
4
5

/* Asociación de operadores y precedencia */

%left 'MAS' 'MENOS'
%left 'POR' 'DIVIDIDO'
%left UMENOS

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.

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

%% /* Definición de la gramática */

ini
	: instrucciones EOF
;

instrucciones
	: instruccion instrucciones
	| instruccion
	| error { console.error('Este es un error sintáctico: ' + yytext + ', en la linea: ' + this._$.first_line + ', en la columna: ' + this._$.first_column); }
;

instruccion
	: REVALUAR CORIZQ expresion CORDER PTCOMA {
		console.log('El valor de la expresión es: ' + $3);
	}
;

expresion
	: MENOS expresion %prec UMENOS  { $$ = $2 *-1; }
	| expresion MAS expresion       { $$ = $1 + $3; }
	| expresion MENOS expresion     { $$ = $1 - $3; }
	| expresion POR expresion       { $$ = $1 * $3; }
	| expresion DIVIDIDO expresion  { $$ = $1 / $3; }
	| ENTERO                        { $$ = Number($1); }
	| DECIMAL                       { $$ = Number($1); }
	| PARIZQ expresion PARDER       { $$ = $2; }
;

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:

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.6+1.45)];

Script Principal

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');


fs.readFile('./entrada.txt', (err, data) => {
    if (err) throw err;
    parser.parse(data.toString());
});

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.