Mi primer proyecto utilizando Yacc y Lex

2020-10-01

Computer Science / Compilers

14 minutes read (About 2057 words)

Mi primer proyecto utilizando Yacc y Lex

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:

Lex: Generador de analizadores léxicos
Yacc: Generador de analizadores sintácticos
Ubuntu 20.04: Sistema operativo
Visual Studio Code: Editor de código fuente
C: Lenguaje de programación

El proyecto completo del ejemplo puede descargarse en el siguient enlace:

Mi primer proyecto utilizando Yacc y Lex

Lex

Lex es una herramienta que permite generar analizadore léxicos a partir de un conjunto de reglas y expresiones regulares. Desarrollado por Eric Schmidt y Mike Lesk para los sistemas Unix. Escrito en C para C, su implementación para C++ es posible, aunque no es segura ya que está mas enfocado en el trabajo con C.
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 token.
Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.

Para obtener más información de Lex, es recomendable visitar su página oficial.

Yacc

Yacc es un generador de analizadores sintácticos ascendentes escrito en C para C. Las siglas Yacc significan Yet Another Compiler-Compiler. Desarrollado por Stephen C. Jhonson en AT&T para el sistema operativo Unix.

El analizador sintáctico obtiene una cadena de tokens del analizador léxico y verifica que dicha cadena pueda generase 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.

Para obtener más información de Lex, es recomendable visitar su página oficial.

Pre-requisitos

Para este ejemplo neceistamos las siguientes herramientas:

Compilador GCC
Visual Studio Code (o cualquier editor de texto de nuestro agrado)

Instalación y configuración de las herramientas

Lo primero que haremos será instalar Lex, para ello abrimos una terminal, en Ubuntu puede hacerse con la combinación de teclas Ctrl + Alt + t o en Aplicaciones → Accesorios → Terminal, una vez abierta la terminal ingresamos el comando:

1	sudo apt-get install flex

Autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Lex. Como nos pudimos dar cuenta, la instalación de Lex se hace a través Flex que es otra herramienta de analisis léxico.

Luego instalamos Yacc, ejecutando el comando:

1	sudo apt-get install bison

Autenticamos ingresando nuestra contraseña y aceptamos la descarga e instalación, con esto quedará instalado Yacc. Como nos pudimos dar cuenta, la instalación de Yacc se hace a través de Bison que es otra herramienta de análisis sintáctico.

Crear nuestro proyecto
Creamos un nuevo folder el cual será nuestro espacio de trabajo, para crearlo abrimos una terminal y ejecutamos el comando:

1	mkdir ProyectoLexYacc

Luego ingresamos a nuestro folder con el comando:

1	cd ProyectoLexYacc

Ahora nos pasamos a el editor de código, en este caso usaremos Visual Studio Code. Para abrir nuestro directorio de trabajo en Visual Studio Code ejecutamos desde la terminal el comando:

code .

El punto al final es importante, ya que le indica a Visual Studio Code que abra una nueva ventana en el directorio actual.

Esto desplegará una ventana de Visual Studio Code, con nuestro proyecto llamado ProyectoLexYacc.

Definimos la estructura de nuestro espacio de trabajo creando un directorio llamado src en donde estará todo nuestro código fuente. Dentro del directorio src creamos un directorio analizador, en este directorio estará todo el código relacionado con Yacc y Lex.

Código fuente para el analizador léxico

En el archivo lexer.l incluiremos todo el código que le indicará a Lex lo que debe de hacer. El código se muestra a continuación:

%{ 
  #include<stdio.h> 
  #include "y.tab.h" 
  void yyerror(char *);
%} 

%option noyywrap
  
DIGIT   [0-9]
NUM     {DIGIT}+("."{DIGIT}+)?

/* Rule Section */
%% 
{NUM}               { yylval=atoi(yytext); return NUMBER; } 
[-()+*/;]            { return *yytext; }
"evaluar"            { return EVALUAR; }
[[:blank:]] ;
.                     yyerror("Unknown character");
%%

Explicación código fuente para el analizador léxico

En las primeras lineas incluimos stdio.h para la lectura de archivos, luego incluimos la cabecera y.tab.h que es el archivo que genera Yacc para nuestro analizador sintáctico. Por último declaramos la función yyerror, función propia de Lex y Yacc para el manejo de errores léxicos.

%{ 
  #include<stdio.h> 
  #include "y.tab.h" 
  void yyerror(char *);
%}

Establecemos una lista de directivas propias de Lex:

La directiva noyywrap le indica a Lex que unicamente leera un archivo de entrada.

1	%option noyywrap

Luego se escriben algunas expresiones regulares para identificar enteros y decimales.

1 2	DIGIT [0-9] NUM {DIGIT}+("."{DIGIT}+)?

Por último definimos todas las reglas léxicas, en las que indicamos los patrones que reconocerá y dentro de llaves lo que debe hacer cuando los reconozca. Para retornar nuestras reglas como tokens y que puedan ser utilizadas en el analizador sintáctico retornamos un id que le asignaremos a cada token, para los tokens de tipo símbolo retornamos la variable yytext para tener una definición más limpia y corta. En el caso de NUM adicional al token debemos regresar el valor numérico reconocido, por lo que es necesario hacer una conversión con la función atoi que convierte una cadena a un número y lo almacenamos en yyval. Para los espacios en blanco, Lex cuenta con una directiva [[:blank]] donde podemos ver que no retornamos ningún simbolo, ya que ignoramos los espacios en blanco. Luego indicamos con un punto que todo lo que no fue reconocido en las reglas anteriores será un error léxico.

/* Rule Section */
%% 
{NUM}               { yylval=atoi(yytext); return NUMBER; } 
[-()+*/;]            { return *yytext; }
"evaluar"            { return EVALUAR; }
[[:blank:]] ;
.                     yyerror("Unknown character");
%%

Código fuente para el analizador sintáctico

En el archivo parser.y incluiremos todo el código que le indicará a Yacc lo que debe de hacer. El código se muestra a continuación:

%{ 
   #include<stdio.h> 
   int yylex(void);
   void yyerror(char *s);
   FILE *yyin;
%} 
  
%token NUMBER EVALUAR
  
%left '+' '-'
%left '*' '/'
%left NEG

  
/* Rule Section */
%% 
  
Init 
   : Lista {
      return 0;
   }
;

Lista 
   : Lista EVALUAR '(' Expr ')' ';'
   {
      printf("\nResult=%d\n", $4);
   }
   | EVALUAR '(' Expr ')' ';'
   { 
      printf("\nResult=%d\n", $3); 
   }
;

Expr 
   : Expr '+' Expr 
   {
      $$ = $1 + $3; 
   } 
   | Expr '-' Expr 
   {
      $$ = $1 - $3;
   } 
   | Expr '*' Expr 
   {
      $$ = $1 * $3;
   } 
   | Expr '/' Expr 
   {
      $$ = $1/$3;
   }
   | '-' Expr %prec NEG {
      $$ = -$2;
   } 
   |'(' Expr ')' 
   {
      $$ = $2;
   } 
   | NUMBER 
   {
      $$ = $1;
   } 
; 
  
%% 
  
//driver code 
void parse(FILE *file) { 
   yyin = file;
   yyparse();
   fclose(yyin);
} 
  
void yyerror(char *s) { 
   printf("\n%s\n", s); 
}

Explicación código fuente para el analizador sintáctico

En las primeras lineas incluimos el ficherio stdio.h para la lectura de archivos, luego declarramos la función yylex, que es la encargada del analizador léxico, también declaramos la función yyerror, que utiliza Yacc para el manejo de errores sintácticos. Por último declaramos una variable de tipo FILE llamada yyin, en esta indicaremos el archivo de entrada que será analizado.

%{ 
   #include<stdio.h> 
   int yylex(void);
   void yyerror(char *s);
   FILE *yyin;
%}

Luego se definen los no terminales, a estos se les puede indicar o no un tipo, por defecto es de tipo int. Los terminales que son símbolos y no retornan ningún identificador asociado al token en el analizador léxico no se agregan en esta sección.

1 2	/***** TERMINALES ******/ %token NUMBER EVALUAR

Posteriormente podemos indicar la precedencia de operadores, ya que la gramática escrita es ambigua, es necesario definir una precedencia para que el analizador no entre en conflicto. El nivel de precendencia se define del mas bajo al mas alto. La precendencia mas baja la tienen la suma y la resta, seguido por la multiplicación y división y por último tenemos el signo menos de las expresiones negativas.

1
2
3

%left '+' '-'
%left '*' '/'
%left NEG

A continuación tenemos el conjunto de reglas de escritura de la gramática o producciones. Escribimos nuestras producciones, para asignar reglas de producción lo hacemos mediante llaves “{ }”, en esta sección podemos escribir código de C. Ya que los analizadores que utiliza Yacc son ascenentes, nos permiten sintetizar atributos, para sintentizar un atributo lo hacemos a traves del identificador “$$”.

%%
Init 
   : Lista {
      return 0;
   }
;

Lista 
   : Lista EVALUAR '(' Expr ')' ';'
   {
      printf("\nResult=%d\n", $4);
   }
   | EVALUAR '(' Expr ')' ';'
   { 
      printf("\nResult=%d\n", $3); 
   }
;

Expr 
   : Expr '+' Expr 
   {
      $$ = $1 + $3; 
   } 
   | Expr '-' Expr 
   {
      $$ = $1 - $3;
   } 
   | Expr '*' Expr 
   {
      $$ = $1 * $3;
   } 
   | Expr '/' Expr 
   {
      $$ = $1/$3;
   }
   | '-' Expr %prec NEG {
      $$ = -$2;
   } 
   |'(' Expr ')' 
   {
      $$ = $2;
   } 
   | NUMBER 
   {
      $$ = $1;
   } 
;  
%%

Como último paso, definimos la función que será llamada para inciar el análisis sintáctico, que en este caso es la función parse, esta recibe como parámetro un FILE, que será nuestro archivo de entrada a ser analizado. Por último definimos la función yyerror, la cúal será llamada si existiera un error sintáctico, esta función es propia de Yacc.

void parse(FILE *file) { 
   yyin = file;
   yyparse();
   fclose(yyin);
} 
  
void yyerror(char *s) { 
   printf("\n%s\n", s); 
}

El archivo de compilación

En el archivo compilar.sh, ejecutamos dos lineas, la primera indica a Lex que debe generar un analizador léxico en base al código fuente que se encuentra en el archivo Léxico. La segunda linea le indica a Yacc que genere los archivos de compilación para el analizador sintáctico en base al archvio Parser.

1 2	lex lexer.l yacc parser.y -d

Para ejecutar abrimos una terminal sobre el directorio analizador y ejecutamos lo siguiente:

1	./compilar.sh

Nota: Si el comando genera error, asegurese de que el archivo tenga permisos de ejecución.

Este comando genera una serie de archivos que se han mencionado ya anteriormente. Los archivos que genera son los siguientes:

y.tab.c
y.tab.h
lex.yy.c

Archivo de entrada

Dentro de la carpeta src del proyecto, creamos un archivo de entrada llamado entrada.txt, que contendrá el archivo de enetrada que reconocerán nuestros analizadores.

El archivo contiene lo siguiente:

evaluar(1+1);
evaluar(1+1*2);
evaluar(-(1+1*6/3-5+7));
evaluar(-(1+1*6/3-5+1*-2));
evaluar(-(1+1));

Archivo Principal

Dentro del archivo main.c, declaramos el método parse, el cúal fue definido en el analizador sintáctico. Definimos nuestro método main, en este creamos abrimos un archivo a través de FILE, indicamos la ruta del archivo de entrada y por último llamamos a nuestro método parse y le pasamos como parámetro el archivo de entrada.

#include <stdio.h> 
#include "analizador/y.tab.h"
void parse(FILE *file);

void main(){
    FILE *file = fopen("entrada.txt", "r");
    parse(file);   
}

Ejecutando nuestra aplicación

Para ejecutar nuestra aplicación necesitamos compilar todos los archivos y generar el ejecutable. Esto lo realizamos con el compilador GCC ejecutando desde consola el siguiente comando:

1	gcc main.c ./analizador/*.c

Este nos genera un archivo a.out, que es el binario resultante de la compilación, este archivo lo ejecutamos desde consola y obtenemos la salida de nuestro proyecto.

./a.out

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Erik Flores y revisado por el Catedrático Erick Navarro, 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.

Intérprete sencillo utilizando PLY con Python 3

2020-03-15

Computer Science / Compilers

25 minutes read (About 3757 words)

Intérprete sencillo utilizando PLY con Python 3

Funcionamiento de la aplicació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 PLY utilizando Python 3 en Ubuntu 18.04. El proyecto completo puede descargarse del siguiente enlace:

Intérpete sencillo utilizando PLY con Python 3

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 PLY con Python pueden visitar el post: Mi primer proyecto utilizando PLY con Python 3, en el cual se describen los pre-requisitos y los pasos para la creación del proyecto.

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:

//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.py detallamos la estructura del lenguaje utilizando PLY. 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. Para esto hacemos uso del módulo re de Python

reservadas = {
    'numero' : 'NUMERO',
    'imprimir' : 'IMPRIMIR',
    'mientras' : 'MIENTRAS',
    'if' : 'IF',
    'else' : 'ELSE'
}

tokens  = [
    'PTCOMA',
    'LLAVIZQ',
    'LLAVDER',
    'PARIZQ',
    'PARDER',
    'IGUAL',
    'MAS',
    'MENOS',
    'POR',
    'DIVIDIDO',
    'CONCAT',
    'MENQUE',
    'MAYQUE',
    'IGUALQUE',
    'NIGUALQUE',
    'DECIMAL',
    'ENTERO',
    'CADENA',
    'ID'
] + list(reservadas.values())

# Tokens
t_PTCOMA    = r';'
t_LLAVIZQ   = r'{'
t_LLAVDER   = r'}'
t_PARIZQ    = r'\('
t_PARDER    = r'\)'
t_IGUAL     = r'='
t_MAS       = r'\+'
t_MENOS     = r'-'
t_POR       = r'\*'
t_DIVIDIDO  = r'/'
t_CONCAT    = r'&'
t_MENQUE    = r'<'
t_MAYQUE    = r'>'
t_IGUALQUE  = r'=='
t_NIGUALQUE = r'!='

def t_DECIMAL(t):
    r'\d+\.\d+'
    try:
        t.value = float(t.value)
    except ValueError:
        print("Float value too large %d", t.value)
        t.value = 0
    return t

def t_ENTERO(t):
    r'\d+'
    try:
        t.value = int(t.value)
    except ValueError:
        print("Integer value too large %d", t.value)
        t.value = 0
    return t

def t_ID(t):
     r'[a-zA-Z_][a-zA-Z_0-9]*'
     t.type = reservadas.get(t.value.lower(),'ID')    # Check for reserved words
     return t

def t_CADENA(t):
    r'\".*?\"'
    t.value = t.value[1:-1] # remuevo las comillas
    return t 

# Comentario de múltiples líneas /* .. */
def t_COMENTARIO_MULTILINEA(t):
    r'/\*(.|\n)*?\*/'
    t.lexer.lineno += t.value.count('\n')

# Comentario simple // ...
def t_COMENTARIO_SIMPLE(t):
    r'//.*\n'
    t.lexer.lineno += 1

# Caracteres ignorados
t_ignore = " \t"

def t_newline(t):
    r'\n+'
    t.lexer.lineno += t.value.count("\n")
    
def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

# Construyendo el analizador léxico
import ply.lex as lex
lexer = lex.lex()

Nótese que los comentarios, saltos de líneas y espacios en blanco son ignorados (no retornan ningún valor).

Otro aspecto importante a destacar es que las palabras reservadas son tratadas como Identificadores, esto se debe a que PLY da precedencia a las expresiones regulares más generales. Por ejemplo, la palabra reservada “Imprimir” siempre hará match con la expresión regular de Identificador, por lo que si se define de la forma t_IMPRIMIR = r'imprimir' nunca será alcanzado. Esto lo hace con la finalidad de hacer el proceso de parsing más eficiente al tener menos expresiones regulares que evaluar.

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. Para lograr esto hacemos uso de la programación orientada a objetos. Específicamente haremos uso del polimorfismo para la construcción de nuestro árbol. Las clases utilizadas para construir las diferentes instrucciones que componen nuestro AST, están definidas en el archivo instrucciones.py.

Clases para Instrucciones

Primero definimos una clase abstracta Instruccion, esto nos permitirá abstraer las Instrucciones que soporta nuestro lenguaje:

1 2	class Instruccion: '''This is an abstract class'''

Seguidamente, definimos una clase concreta para cada una de las formas posibles que puede tomar Instruccion:

class Imprimir(Instruccion) :
    '''
        Esta clase representa la instrucción imprimir.
        La instrucción imprimir únicamente tiene como parámetro una cadena
    '''

    def __init__(self,  cad) :
        self.cad = cad

class Mientras(Instruccion) :
    '''
        Esta clase representa la instrucción mientras.
        La instrucción mientras recibe como parámetro una expresión lógica y la lista
        de instrucciones a ejecutar si la expresión lógica es verdadera.
    '''

    def __init__(self, expLogica, instrucciones = []) :
        self.expLogica = expLogica
        self.instrucciones = instrucciones

Por ejemplo, para la clase Imprimir vemos que extiende de Instruccion y que su única propiedad es la cadena que se va imprimir. Esta propiedad, cadena, es de tipo ExpresionCadena como veremos más adelante.

De la misma forma, la instrucción Mientras extiende de Instruccion y sus propiedades son la expresión lógica a evaluar y el set de instrucciones a ejecutar mientras la condición sea verdadera. expLogica es de tipo ExpresionLogica e instrucciones es una lista, y sus elementos son de tipo Instrucción.

El proceso es similar para las instrucciones de Definición y Asignación

class Definicion(Instruccion) :
    '''
        Esta clase representa la instrucción de definición de variables.
        Recibe como parámetro el nombre del identificador a definir
    '''

    def __init__(self, id) :
        self.id = id

class Asignacion(Instruccion) :
    '''
        Esta clase representa la instrucción de asignación de variables
        Recibe como parámetro el identificador a asignar y el valor que será asignado.
    '''

    def __init__(self, id, expNumerica) :
        self.id = id
        self.expNumerica = expNumerica

Finalmente, completamos nuestras instrucciones con If e If-Else

class If(Instruccion) : 
    '''
        Esta clase representa la instrucción if.
        La instrucción if recibe como parámetro una expresión lógica y la lista
        de instrucciones a ejecutar si la expresión lógica es verdadera.
    '''

    def __init__(self, expLogica, instrucciones = []) :
        self.expLogica = expLogica
        self.instrucciones = instrucciones

class IfElse(Instruccion) : 
    '''
        Esta clase representa la instrucción if-else.
        La instrucción if-else recibe como parámetro una expresión lógica y la lista
        de instrucciones a ejecutar si la expresión lógica es verdadera y otro lista de instrucciones
        a ejecutar si la expresión lógica es falsa.
    '''

    def __init__(self, expLogica, instrIfVerdadero = [], instrIfFalso = []) :
        self.expLogica = expLogica
        self.instrIfVerdadero = instrIfVerdadero
        self.instrIfFalso = instrIfFalso

Clases para Expresiones

De la misma manera que manejamos las instrucciones manejaremos las expresiones. Definimos 3 clases abstractas que representan los 3 tipos de expresiones soportadas por nuestro lenguaje: Expresiones Aritméticas, Expresiones con Cadenas y Expresiones Lógicas, todas ellas definidas dentro del archivo expresiones.py.

También haremos uso de enumeraciones para definir constantes de nuestras operaciones, esto es altamente recomendado para evitar bugs durante el desarrollo.

from enum import Enum

class OPERACION_ARITMETICA(Enum) :
    MAS = 1
    MENOS = 2
    POR = 3
    DIVIDIDO = 4

class OPERACION_LOGICA(Enum) :
    MAYOR_QUE = 1
    MENOR_QUE = 2
    IGUAL = 3
    DIFERENTE = 4

Iniciamos definiendo nuestra clase ExpresionNumerica de tipo abstracta y será nuestra clase base para las expresiones numéricas.

class ExpresionNumerica:
    '''
        Esta clase representa una expresión numérica
    '''

Las formas que puede tomar nuestra clase ExpresionNumerica son las siguientes:

ExpresionBinaria. Representa una operación aritmética binaria, la clase recibe los 2 operados: exp1 y exp2, ambos de tipos ExpresionNumérica. Y recibe el operador el cual es un calor de nuestro enum definidos anteriormente.
ExpresionNegativo. Representa la operación aritmética unaria de negación. Únicamente recibe como parámetro la expresión que se negara, esta es también de tipo ExpresionNumerica
ExpresionNumero. Representa un valor terminal numérico. El parámetro val contiene el valor extraído por el analizador léxico.
ExpresionIdentificador. Representa un identificador. El parámetro id representa el nombre de la variable que se desea operar.

class ExpresionBinaria(ExpresionNumerica) :
    '''
        Esta clase representa la Expresión Aritmética Binaria.
        Esta clase recibe los operandos y el operador
    '''

    def __init__(self, exp1, exp2, operador) :
        self.exp1 = exp1
        self.exp2 = exp2
        self.operador = operador

class ExpresionNegativo(ExpresionNumerica) :
    '''
        Esta clase representa la Expresión Aritmética Negativa.
        Esta clase recibe la expresion
    '''
    def __init__(self, exp) :
        self.exp = exp


class ExpresionNumero(ExpresionNumerica) :
    '''
        Esta clase representa una expresión numérica entera o decimal.
    '''

    def __init__(self, val = 0) :
        self.val = val

class ExpresionIdentificador(ExpresionNumerica) :
    '''
        Esta clase representa un identificador.
    '''

    def __init__(self, id = "") :
        self.id = id

Ahora, siguiendo el proceso anterior, definimos nuestras expresiones con cadenas.

class ExpresionCadena :
    '''
        Esta clase representa una Expresión de tipo cadena.
    '''

class ExpresionConcatenar(ExpresionCadena) :
    '''
        Esta clase representa una Expresión de tipo cadena.
        Recibe como parámetros las 2 expresiones a concatenar
    '''

    def __init__(self, exp1, exp2) :
        self.exp1 = exp1
        self.exp2 = exp2

class ExpresionDobleComilla(ExpresionCadena) :
    '''
        Esta clase representa una cadena entre comillas doble.
        Recibe como parámetro el valor del token procesado por el analizador léxico
    '''

    def __init__(self, val) :
        self.val = val

class ExpresionCadenaNumerico(ExpresionCadena) :
    '''
        Esta clase representa una expresión numérica tratada como cadena.
        Recibe como parámetro la expresión numérica
    '''
    def __init__(self, exp) :
        self.exp = exp

Y finalmente, definimos nuestras expresiones lógicas

class ExpresionLogica() :
    '''
        Esta clase representa la expresión lógica.
        Esta clase recibe los operandos y el operador
    '''

    def __init__(self, exp1, exp2, operador) :
        self.exp1 = exp1
        self.exp2 = exp2
        self.operador = operador

Construcción del AST

Para construir el AST durante nuestro análisis sintáctico importamos nuestras clases de instrucciones y expresiones. Esto también incluye nuestros enum para las constantes, esto se hará en el archivo gramatica.py.

# Definición de la gramática

from expresiones import *
from instrucciones import *

Una vez importados podemos hacer uso de ellas en la gramática. Por ejemplo, para la construcción de operaciones aritméticas hacemos uso de nuestras clases de tipo ExpresionNumerica, pasamos como parámetros los operandos y el tipo operación (utilizando nuestras constantes).

def p_expresion_binaria(t):
    '''expresion_numerica : expresion_numerica MAS expresion_numerica
                        | expresion_numerica MENOS expresion_numerica
                        | expresion_numerica POR expresion_numerica
                        | expresion_numerica DIVIDIDO expresion_numerica'''
    if t[2] == '+'  : t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.MAS)
    elif t[2] == '-': t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.MENOS)
    elif t[2] == '*': t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.POR)
    elif t[2] == '/': t[0] = ExpresionBinaria(t[1], t[3], OPERACION_ARITMETICA.DIVIDIDO)

def p_expresion_unaria(t):
    'expresion_numerica : MENOS expresion_numerica %prec UMENOS'
    t[0] = ExpresionNegativo(t[2])

def p_expresion_agrupacion(t):
    'expresion_numerica : PARIZQ expresion_numerica PARDER'
    t[0] = t[2]

def p_expresion_number(t):
    '''expresion_numerica : ENTERO
                        | DECIMAL'''
    t[0] = ExpresionNumero(t[1])

def p_expresion_id(t):
    'expresion_numerica   : ID'
    t[0] = ExpresionIdentificador(t[1])

El proceso es el mismo para las Instrucciones, cada producción de tipo Instrucción construye una instancia concreta de la instrucción apropiada.

def p_instruccion_imprimir(t) :
    'imprimir_instr     : IMPRIMIR PARIZQ expresion_cadena PARDER PTCOMA'
    t[0] =Imprimir(t[3])

def p_instruccion_definicion(t) :
    'definicion_instr   : NUMERO ID PTCOMA'
    t[0] =Definicion(t[2])

def p_asignacion_instr(t) :
    'asignacion_instr   : ID IGUAL expresion_numerica PTCOMA'
    t[0] =Asignacion(t[1], t[3])

def p_mientras_instr(t) :
    'mientras_instr     : MIENTRAS PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER'
    t[0] =Mientras(t[3], t[6])

def p_if_instr(t) :
    'if_instr           : IF PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER'
    t[0] =If(t[3], t[6])

def p_if_else_instr(t) :
    'if_else_instr      : IF PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER ELSE LLAVIZQ instrucciones LLAVDER'
    t[0] =IfElse(t[3], t[6], t[10])

Finalmente, una vez que hayamos reconocido toda la entrada, construimos un arreglo con cada uno de los nodos. Este será nuestro AST.

def p_init(t) :
    'init            : instrucciones'
    t[0] = t[1]

def p_instrucciones_lista(t) :
    'instrucciones    : instrucciones instruccion'
    t[1].append(t[2])
    t[0] = t[1]


def p_instrucciones_instruccion(t) :
    'instrucciones    : instruccion '
    t[0] = [t[1]]

def p_instruccion(t) :
    '''instruccion      : imprimir_instr
                        | definicion_instr
                        | asignacion_instr
                        | mientras_instr
                        | if_instr
                        | if_else_instr'''
    t[0] = t[1]

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, la definición de esta clase puede encontrarse en el archivo ts.py.

Definimos las constantes para los tipos de datos, en este tutorial se hace uso únicamente del tipo de dato numérico.

from enum import Enum

class TIPO_DATO(Enum) :
    NUMERO = 1

Definimos una clase para los Símbolos.

class Simbolo() :
    'Esta clase representa un simbolo dentro de nuestra tabla de simbolos'

    def __init__(self, id, tipo, valor) :
        self.id = id
        self.tipo = tipo
        self.valor = valor

La clase TablaDeSimbolos define la estructura de una tabla de símbolos y sus funciones para agregar, modificar y obtener símbolos.

class TablaDeSimbolos() :
    'Esta clase representa la tabla de simbolos'

    def __init__(self, simbolos = {}) :
        self.simbolos = simbolos

    def agregar(self, simbolo) :
        self.simbolos[simbolo.id] = simbolo
    
    def obtener(self, id) :
        if not id in self.simbolos :
            print('Error: variable ', id, ' no definida.')

        return self.simbolos[id]

    def actualizar(self, simbolo) :
        if not simbolo.id in self.simbolos :
            print('Error: variable ', simbolo.id, ' no definida.')
        else :
            self.simbolos[simbolo.id] = simbolo

Construcción del Intérprete

La definición del Intérprete se encuentra en el archivo principal.py

Para iniciar con la implementación, primero importamos nuestra gramática, las constantes y clases de nuestro AST y la Tabla de Símbolos.

import gramatica as g
import ts as TS
from expresiones import *
from instrucciones import *

Seguidamente, obtenemos el AST a partir del archivo de entrada.

f = open("./entrada.txt", "r")
input = f.read()

instrucciones = g.parse(input)
ts_global = TS.TablaDeSimbolos()

procesar_instrucciones(instrucciones, ts_global)

Nótese que el AST está contenido en la variable instrucciones.

La función principal del intérprete es de reconocer cada instrucción y ejecutarla, para esto es necesario recorrer el AST; es por ello que se ha definido la función procesar_instrucciones la 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 procesar_instrucciones con la raíz del AST y la tabla de símbolos del ámbito global.

def procesar_instrucciones(instrucciones, ts) :
    ## lista de instrucciones recolectadas
    for instr in instrucciones :
        if isinstance(instr, Imprimir) : procesar_imprimir(instr, ts)
        elif isinstance(instr, Definicion) : procesar_definicion(instr, ts)
        elif isinstance(instr, Asignacion) : procesar_asignacion(instr, ts)
        elif isinstance(instr, Mientras) : procesar_mientras(instr, ts)
        elif isinstance(instr, If) : procesar_if(instr, ts)
        elif isinstance(instr, IfElse) : procesar_if_else(instr, ts)
        else : print('Error: instrucción no válida')

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.

def procesar_mientras(instr, ts) :
    while resolver_expreision_logica(instr.expLogica, ts) :
        ts_local = TS.TablaDeSimbolos(ts.simbolos)
        procesar_instrucciones(instr.instrucciones, ts_local)

def procesar_if(instr, ts) :
    val = resolver_expreision_logica(instr.expLogica, ts)
    if val :
        ts_local = TS.TablaDeSimbolos(ts.simbolos)
        procesar_instrucciones(instr.instrucciones, ts_local)

def procesar_if_else(instr, ts) :
    val = resolver_expreision_logica(instr.expLogica, ts)
    if val :
        ts_local = TS.TablaDeSimbolos(ts.simbolos)
        procesar_instrucciones(instr.instrIfVerdadero, ts_local)
    else :
        ts_local = TS.TablaDeSimbolos(ts.simbolos)
        procesar_instrucciones(instr.instrIfFalso, ts_local)

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.

def procesar_imprimir(instr, ts) :
    print('> ', resolver_cadena(instr.cad, ts))

def procesar_definicion(instr, ts) :
    simbolo = TS.Simbolo(instr.id, TS.TIPO_DATO.NUMERO, 0)      # inicializamos con 0 como valor por defecto
    ts.agregar(simbolo)

def procesar_asignacion(instr, ts) :
    val = resolver_expresion_aritmetica(instr.expNumerica, ts)
    simbolo = TS.Simbolo(instr.id, TS.TIPO_DATO.NUMERO, val)
    ts.actualizar(simbolo)

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

def resolver_expresion_aritmetica(expNum, ts) :
    if isinstance(expNum, ExpresionBinaria) :
        exp1 = resolver_expresion_aritmetica(expNum.exp1, ts)
        exp2 = resolver_expresion_aritmetica(expNum.exp2, ts)
        if expNum.operador == OPERACION_ARITMETICA.MAS : return exp1 + exp2
        if expNum.operador == OPERACION_ARITMETICA.MENOS : return exp1 - exp2
        if expNum.operador == OPERACION_ARITMETICA.POR : return exp1 * exp2
        if expNum.operador == OPERACION_ARITMETICA.DIVIDIDO : return exp1 / exp2
    elif isinstance(expNum, ExpresionNegativo) :
        exp = resolver_expresion_aritmetica(expNum.exp, ts)
        return exp * -1
    elif isinstance(expNum, ExpresionNumero) :
        return expNum.val
    elif isinstance(expNum, ExpresionIdentificador) :
        return ts.obtener(expNum.id).valor

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.

def resolver_cadena(expCad, ts) :
    if isinstance(expCad, ExpresionConcatenar) :
        exp1 = resolver_cadena(expCad.exp1, ts)
        exp2 = resolver_cadena(expCad.exp2, ts)
        return exp1 + exp2
    elif isinstance(expCad, ExpresionDobleComilla) :
        return expCad.val
    elif isinstance(expCad, ExpresionCadenaNumerico) :
        return str(resolver_expresion_aritmetica(expCad.exp, ts))
    else :
        print('Error: Expresión cadena no válida')

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.

def resolver_expreision_logica(expLog, ts) :
    exp1 = resolver_expresion_aritmetica(expLog.exp1, ts)
    exp2 = resolver_expresion_aritmetica(expLog.exp2, ts)
    if expLog.operador == OPERACION_LOGICA.MAYOR_QUE : return exp1 > exp2
    if expLog.operador == OPERACION_LOGICA.MENOR_QUE : return exp1 < exp2
    if expLog.operador == OPERACION_LOGICA.IGUAL : return exp1 == exp2
    if expLog.operador == OPERACION_LOGICA.DIFERENTE : return exp1 != exp2

Para ejecutar nuestro intérprete y procesar el archivo de entrada ejecutamos el siguiente comando:

1	$ python3 ./principal.py

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.

2020-03-07

Computer Science / Compilers

18 minutes read (About 2674 words)

Intérprete sencillo utilizando JavaCC

De no estar familiarizado con la herramienta JavaCC, se recomienda al lector seguir el siguiente tutorial:

Mi primer proyecto utilizando JavaCC

El desarrollo con JavaCC resulta sencillo, pero la legibilidad de la gramática puede llegar a ser un inconveniente si no se trata con la atención debida, sin embargo, el resto de las funcionalidades que nos ofrece JavaCC son un buen aliciente para utilizarlo, por lo tanto en esta ocasión vamos a desarrollar un intérprete, este contendrá la ejecución de sentencias básicas, como declaraciones de variables, asignaciones, sentencias de control, funciones y demás. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Intérprete sencillo utilizando JavaCC

Conceptos básicos

Intérprete: Es un tipo común de procesador de lenguaje. En vez de producir un programa destino como una traducción, el intérprete ejecuta directamente las operaciones especificadas en el programa de origen (fuente) con las entradas proporcionadas por el usuario.
Árbol de sintaxis abstracta (AST): es una representación simplificada de la estructura sintáctica del código fuente. A nivel de programación un AST es una estructura de datos que se genera durante el proceso de análisis sintáctico.

Lenguaje de entrada

En la raíz del proyecto hay un archivo llamado entrada.txt, este contiene un ejemplo con las instrucciones que el lenguaje soporta.

Listado instrucciones soportadas

Declaración de variables
Asignación de variables
Evaluación de expresiones aritméticas, lógicas y relaciones
If…elseif…else
While
Continue
Break
Return
Declaración de funciones
Llamadas a funciones
Recursividad
Funciones nativas: pie, toUpper. Pie genera una gráfica pie, y toUpper convierte a mayúsculas cierta cadena.
Comentarios de una línea y multilínea
Control de excepciones semánticas

Estructura del archivo Gramatica.jj de JavaCC

La extensión para los archivos JavaCC es .jj, a continuación vamos a describir la estructura del archivo de JavaCC utilizado para este ejemplo.

Sección de opciones
Aquí vamos a indicar que no haga distinción entre mayúsculas y minúsculas, además de indicar que los métodos de nuestro archivo luego de compilados no sean estáticos.

Sección de parserBegin y parserEnd
Aquí vamos a definir el nombre de nuestro paquete, adicionalmente y muy importante todos los import de archivos que vayamos a utilizar en las acciones para generar nuestro AST. Por último vamos a crear una clase vacía, esta es la que vamos a utilizar para invocar a nuestra gramática.

Sección de análisis léxico
En este punto vamos a definir todos los tokens que vamos a utilizar en el lenguaje:

Sección skip
Contendrá todos los tokens que javacc va a ignorar cuando los reconozca, por ejemplo los comentarios o saltos de línea, espacios en blanco, etc.

SKIP : {
      " "
    | "\t"
    | "\r"
    | "\n"
    | <"//" (~["\n", "\r"])*>
}

Sección de token
En esta sección cada vez que se reconozca un lexema este generará un nuevo objeto de tipo token.

TOKEN : {
      <NUMERO: (["0"-"9"])+>
    | <DECIMAL: (["0"-"9"])+"."(["0"-"9"])+>
    | <ENTERO: "Numero">
}

Sección more
Sección utilizada para la creación de estados.

MORE :
{
    "\"" :STRING_STATE
}

<STRING_STATE> MORE:
{
    <~["\""]>
}

Sección de análisis sintáctico
Aquí vamos a definir la gramática y agregar las acciones correspondientes para generar nuestro AST. Ciertas producciones van a generar una clase que tiene cierta funcionalidad donde se indica lo que la ejecución deberá hacer.

Veamos el caso del while

/** While -> while(condicion) instrucciones */
AST Mientras() :
{AST e; ArrayList<AST> ins;}
{
    <MIENTRAS> <PARENI> e=Expresion() <PAREND> ins=Bloque() 
    {return new Mientras(e, ins, token.beginLine, token.beginColumn);}
}

Con esta gramática observamos lo siguiente, tenemos dos variables:

AST e
ArrayList ins

AST es nuestra clase abstracta asociada con la variable e que contendrá la condición de nuestro while, y el arraylist contendrá una lista de estas clases, esto con el fin de tener una lista de instrucciones.
Como sabemos un while necesita de una condición y una lista de instrucciones, lo cual se cumple en el diseño planteado, por lo tanto vamos a retornar una instancia de la clase Mientras.

Luego de retornar nuestra clase Mientras, el analizador se encarga de continuar la reducción nuestras producciones, y agregar esta clase a una lista de instrucciones ya que la clase Mientras es una instrucción en sí misma.
Al finalizar el análisis de la entrada se debería generar un árbol, que básicamente contiene una lista de instrucciones, y estas instrucciones pueden ser mientras, imprimir, llamadas, etc.
Esta es la idea general detrás de las acciones del análisis sintáctico, retornar clases que van a formar un AST, que nos servirá para el análisis semántico y para la ejecución de nuestras instrucciones.

Análisis semántico y ejecución de código

Aquí nos vamos a encargar de verificar que lo que ejecutemos tenga sentido, vamos a retomar el ejemplo de la clase Mientras, específicamente la sobre-escritura del método interpretar:

@Override
public Object interpretar(Tabla tabla, Arbol tree) {
    Object valorCondicion = false;
    do {
        Tabla t = new Tabla(tabla);
        valorCondicion = condicion.interpretar(t, tree);
        if (valorCondicion instanceof Excepcion) {
            return valorCondicion;
        }

        if (!(valorCondicion instanceof Boolean)) {
            Excepcion ex = new Excepcion("Semantico", "Se esperaba un valor booleano para la condicion", fila, columna);
            tree.getExcepciones().add(ex);
            return ex;
        }
        Object result = null;
        if ((Boolean) valorCondicion) {
            for (AST m : instrucciones) {
                result = m.interpretar(t, tree);
                if (result instanceof Retorno || result instanceof Excepcion) {
                    return result;
                }
                if(result instanceof Detener){
                    return null;
                }
                if(result instanceof Continue){
                    break;
                }
            }
        }
    } while ((Boolean) valorCondicion);
    return null;
}

Se sobre-escribe la función interpretar que viene desde nuestra clase abstracta AST, cada clase que herede de AST le dará un distinto comportamiento a este método en base a lo que se quiere realizar.

En este caso necesitamos darle el comportamiento de un while, haciendo lo siguiente:

Declaramos una variable que almacenara nuestra condición
Iniciamos un ciclo doWhile con la condición establecida en la variable creada anteriormente
En las instrucciones del do, crearemos un nuevo ámbito para nuestro mientras
Obtenemos el valor de la condición y lo asignamos a la variable creada al inicio
Si el valor obtenido es una excepción vamos a retornar este valor para que sea reportado.
Si continua la ejecución vamos ahora a verificar que el valor obtenido sea de tipo booleano, sino fuera un booleano vamos a generar una nueva excepción y la vamos a retornar para que sea reportada.
Si la condición fuera valida vamos a tener un if con esta condición y si el valor fuera true inicia la ejecución de cada instrucción en nuestra lista
Si fuera false, simplemente ignora el if y nuestro doWhile termina
Dentro del for para recorrer las instrucciones nos encontramos que en cada iteración debemos verificar que lo que obtenemos de valor no sea una excepción ya que si lo fuera la debemos retornar para que sea reportada.
Además verificamos si fuera un break, continue o return para saber que hacer en cada caso.
Por ejemplo si fuera retorno vamos a devolver el valor como tal, si fuera un continue únicamente tenemos que ir a la siguiente iteración por lo que cortamos la iteración del ciclo interno donde estamos para que no se sigan ejecutando el resto de las instrucciones y si fuera un break debemos terminar la ejecución del mientras por lo tanto terminamos la ejecución de nuestro doWhile.
Esta sería la lógica para un ciclo while, y así lo haremos con todas las instrucciones, cada una tendrá una implementación distinta.

Clases importantes del proyecto
Estas clases son clave para el desarrollo de nuestro intérprete y se explicarán a continuación

Clase abstracta AST
Contiene los atributos y métodos que tendrán las instrucciones en común, además el método interpretar que será sobre-escrito en cada implementación, la finalidad de esta clase es poder modelar clases de distintos tipos que comparten un comportamiento cómun que en este caso sería que se pueden interpretar.
Clase símbolo
Esta clase nos sirve como nodo para crear nuestras variables, vemos que contiene tipo, identificador y valor, aunque esto puede variar dependiendo del tipo de interprete que estemos construyendo.
Clase tabla
Esta a tener la función de tabla de símbolos, aquí vamos a almacenar nuestras variables y funciones, nuestras variables las vamos a almacenar en un hashmap y las funciones en un arraylist. Contamos con métodos que nos ayudaran a obtener, guardar variables, obtener y guardar funciones.
Clase árbol
Es la clase que nos devuelve el análisis sintáctico contiene las instrucciones que deberán ser ejecutadas, la lista de excepción que vamos a reportar y la tabla global para cuando ejecutemos las llamadas a funciones.
Clase tipo
Aquí es donde vamos a definir los tipos que contendrá nuestro interprete.
Clase función
Como cualquier otra instrucción, extiende de la clase AST, y recibe una lista de parámetros y el nombre de la función y una lista de instrucciones.
Y para la ejecución únicamente necesitamos recorrer la lista de instrucciones ejecutando el método interpretar asociado a cada una de estas.

Creación de funciones nativas

Para funciones nativas es muy sencillo, únicamente debemos extender de la clase función y modificar el comportamiento por cualquier otro que deseemos. Tomamos de ejemplo la función nativa aMayuscula, esta recibe en su constructor los mismos datos que la funciones y únicamente se va a diferenciar en el método interpretar donde le daremos una lógica distinta.

@Override
public Object interpretar(Tabla tabla, Arbol tree) {
    Simbolo simbolo = tabla.getVariable("toUpper%%parametro1");
    if (simbolo == null) {
        Excepcion ex = new Excepcion("Semantico", "No se ha encontrado la variable " + this.nombre + ".", fila, columna);
        tree.getExcepciones().add(ex);
        return ex;
    }
    if (!simbolo.getTipo().equals(new Tipo(Tipo.Tipos.CADENA))) {
        Excepcion ex = new Excepcion("Semantico", "El tipo de los parametros no coinciden.", fila, columna);
        tree.getExcepciones().add(ex);
        return ex;
    }
    return (simbolo.getValor() + "").toUpperCase();
}

Ejecución de la entrada
Para ejecutar la entrada debemos instanciar nuestra gramática, esto sucede en la clase UIController, específicamente dentro del método Ejecutar:

1
2
3

Gramatica parser = new Gramatica(new BufferedReader(new StringReader(entrada.getText())));
Arbol arbol = parser.Analizar();
EjecutarInstrucciones(arbol);

Como mencionamos el resultado de ejecutar nuestra gramática nos devolverá un objeto de tipo Arbol, lo enviamos a un método para tratarlo.
En este método pasamos la consola de la interfaz a nuestro árbol para imprimir cosas, crear la tabla global y asignarla a nuestro árbol, crear las funciones nativas.
Luego recorremos por primera vez nuestras instrucciones en búsqueda de funciones para declararlas, pero solamente funciones no otra instrucción.
Luego recorremos por segunda vez nuestras instrucciones y las ejecutamos utilizando el siempre confiable método interpretar obtenido gracias a nuestra clase abstracta AST. Específicamente con el método EjecutarInstrucciones, de la clase UIController:

private void EjecutarInstrucciones(Arbol tree) {
    tree.setConsola(consola);
    tree.setGrupo(groupChart);
    Tabla tabla = new Tabla(null);
    tree.setGlobal(tabla);
    crearNativas(tabla);
    // Recorrido 1 para insertar funciones
    tree.getInstrucciones().forEach(m -> {
        if (m instanceof Funcion) {
            tabla.setFuncion((Funcion) m);
        }
    });
    tree.getInstrucciones().forEach(m -> {
        if (!(m instanceof Funcion)) {
            Object result = m.interpretar(tabla, tree);

            if (result instanceof Excepcion) {
                ((Excepcion) result).imprimir(tree.getConsola());
            }
            if (result instanceof Detener) {
                Excepcion ex = new Excepcion("Semantico", "Sentencia break fuera de ciclo.", m.fila, m.columna);
                tree.getExcepciones().add(ex);
                ex.imprimir(tree.getConsola());
            } else if (result instanceof Retorno) {
                Excepcion ex = new Excepcion("Semantico", "Sentencia retorno fuera de funcion.", m.fila, m.columna);
                tree.getExcepciones().add(ex);
                ex.imprimir(tree.getConsola());
            }
        }
    });

    tree.getExcepciones().forEach(m -> {
        System.out.println("" + m.toString());
    });
}

Iniciando funciones nativas
Para las funciones nativas recordemos deben ser creadas antes de iniciar la ejecución de nuestro interprete. Esta creación de las funciones nativas se encuentra en clase UIController, específicamente en el método crearNativas:

public void crearNativas(Tabla t){
    Tipo tipo = new Tipo(Tipo.Tipos.CADENA);
    String nombre = "toUpper";
    ArrayList<AST> parametros = new ArrayList<>();
    parametros.add(new Declaracion(tipo, "toUpper%%parametro1", null, -1, -1));
    ArrayList<AST> instrucciones = new ArrayList<>();
    aMayuscula am = new aMayuscula(tipo, nombre, parametros, instrucciones, -1, -1);
    t.setFuncion(am);
    
    tipo = new Tipo(Tipo.Tipos.CADENA);
    nombre = "pie";
    parametros = new ArrayList<>();
    parametros.add(new Declaracion(new Tipo(Tipos.LISTA), "pie%%parametro1", null, -1, -1));
    parametros.add(new Declaracion(new Tipo(Tipos.LISTA), "pie%%parametro2", null, -1, -1));
    parametros.add(new Declaracion(new Tipo(Tipos.CADENA), "pie%%parametro3", null, -1, -1));
    instrucciones = new ArrayList<>();
    pieChart pc = new pieChart(tipo, nombre, parametros, instrucciones, -1, -1);
    t.setFuncion(pc);
}

Como observamos aquí creamos las funciones nativas de toUpper y pie que mencionamos al inicio. Además los parámetros tienen un nombre especial para que no se confundan con otras variables, al terminar de crearlas las agregamos a nuestra lista de funciones.

Una vez explicado esto procedemos a ejecutar nuestro programa, vemos que contamos con un boton para ejecutar y 2 pestañas, 1 de consola y la otra donde se muestran nuestras graficas:

Agregamos y ejecutamos la entrada proporcionada que produce lo siguiente en la sección de la consola:

Y en la sección de grafica:

Con esto damos por finalizado la explicación de este pequeño proyecto.

Conclusiones

Como pudimos observar el desarrollo de un interprete es largo, pero a su vez es ordenado.
Las gramáticas en javaCC pueden ser poco legibles pero altamente sencillas de crear.
Dry, don’t repeat yourself: si usamos esta filosofía podemos reducir la cantidad de código hecho, por ejemplo en nuestra clase abstracta agregamos código común para todas las clases que la heredan, o con las funciones nativas únicamente heredamos de algo que ya existía, hay que tratar en la manera de lo posible reutilizar el código existente.
Algo que no se explico porque no era parte del tutorial, pero que es muy útil fue que la interfaz esta hecha en JavaFX, esta nos proporciona una manera más sencilla de utilizar los componentes de la interfaz con nuestra lógica utilizando el modelo MVC.
La utilización de estados en JavaCC nos puede ayudar en casos donde necesitemos crear tokens más complejos.

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Pavel Vásquez, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.

Fuentes consultadas:

Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.

Mi primer proyecto utilizando PLY con Python 3

2020-02-10

Computer Science / Compilers

10 minutes read (About 1505 words)

Mi primer proyecto utilizando PLY con Python 3

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

Las tecnologías a utilizar son:

PLY: Generador de analizadores léxicos y sintácticos.
Python 3: Es un lenguaje de programación interpretado de alto nivel.
Visual Studio Code: Es un editor de código ligero pero poderoso. Existen complementos para trabajar con este lenguaje.

El proyecto completo lo pueden descargar del siguiente enlace

Mi primer proyecto utilizando PLY

PLY

PLY es una implementación en Python de lex y yacc, herramientas populares para la construcción de compiladores.

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 token.
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 PLY se definen los patrones de los diferentes tokens que se desean reconocer, esto se hace a través de expresiones regulares. Mientras que las producciones y acciones para formar la gramática se definen a través de funciones.

Pre-requisitos

Python 3
PLY

Instalamos PLY

Para hacer uso de PLY en nuestro proyecto no hacemos instalación como tal, lo que necesitamos es descargar el archivo ply-3.11.tar.gz (versión 3.11 al momento de escribir este tutorial) de la página oficial de PLY y lo que hacemos es copiar el fólder “ply” a nuestro proyecto.

Crear nuestro proyecto

Primero crearemos un nuevo fólder, en este caso lo llamaremos PROYECTOPLY. Luego lo abrimos en nuestro editor de texto, en este caso usaremos Visual Studio Code. Finalmente procedemos a crear un nuevo archivo llamado gramatica.py donde escribiremos nuestro compilador.

Los directorios “pycache“, al igual que los archivos “parser.out” y “parsetab.py” son generados por Python los cuales pueden ser excluidos en nuestro controlador de versiones. En este caso, los agregamos a nuestro .gitignore.

1
2
3

parser.out
parsetab.py
**/__pycache__/**

El directorio “ply” es el que descargamos y utilizaremos para construir nuestro compilador.

Código Fuente para el analizador léxico y sintáctico

En el archivo gramatica.py tenemos la construcción de nuestro compilador.

Explicación del código fuente para el analizador léxico

Lo primero que debemos hacer es definir el listado de tokens que vamos a reconocer ya asignarlo a la variable tokens

tokens  = (
    'REVALUAR',
    'PARIZQ',
    'PARDER',
    'CORIZQ',
    'CORDER',
    'MAS',
    'MENOS',
    'POR',
    'DIVIDIDO',
    'DECIMAL',
    'ENTERO',
    'PTCOMA'
)

Luego escribimos los patrones para los tokens que definimos. Existen dos formas de definir las reglas de nuestros tokens.

La primera, es con expresiones regulares, agregamos el prefijo “t_” al token que queremos definir y luego le especificamos la expresión regular, para esto se hace uso del módulo re de Python.

# Tokens
t_REVALUAR  = r'Evaluar'
t_PARIZQ    = r'\('
t_PARDER    = r'\)'
t_CORIZQ    = r'\['
t_CORDER    = r'\]'
t_MAS       = r'\+'
t_MENOS     = r'-'
t_POR       = r'\*'
t_DIVIDIDO  = r'/'
t_PTCOMA    = r';'

La otra forma es a través de funciones, esto nos sirve para manipular el valor del token que procesamos. Por ejemplo para los valores numéricos los retornamos con el tipo apropiado, hacer validaciones, etc.

def t_DECIMAL(t):
    r'\d+\.\d+'
    try:
        t.value = float(t.value)
    except ValueError:
        print("Floaat value too large %d", t.value)
        t.value = 0
    return t

def t_ENTERO(t):
    r'\d+'
    try:
        t.value = int(t.value)
    except ValueError:
        print("Integer value too large %d", t.value)
        t.value = 0
    return t

Es importante definir también los caracteres que se van a ignorar.

1 2	# Caracteres ignorados t_ignore = " \t"

Las funciones también llevan el prefijo “t_” antes del nombre del token que queremos procesar. La función recibe un parámetro, “t” en nuestro ejemplo, este contiene el valor del token. Retornamos el valor ya procesado que deseamos, o no retornar nada si lo que deseamos es ignorar el token (por ejemplo: comentarios, contadores, etc.).

def t_newline(t):
    r'\n+'
    t.lexer.lineno += t.value.count("\n")
    
def t_error(t):
    print("Illegal character '%s'" % t.value[0])
    t.lexer.skip(1)

Finalmente construimos el analizador léxico haciendo uso de las librerías de PLY

1
2
3

# Construyendo el analizador léxico
import ply.lex as lex
lexer = lex.lex()

Explicación del código fuente para el analizador sintáctico

Otra de las ventajas de Python 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.

# Asociación de operadores y precedencia
precedence = (
    ('left','MAS','MENOS'),
    ('left','POR','DIVIDIDO'),
    ('right','UMENOS'),
    )

Ahora procedemos a escribir nuestras producciones, aquí vemos otra de las ventajas de Python, las acciones semánticas de nuestras producciones se hacen en forma de funciones. Las características de estas funciones son:

El nombre inicia con el prefijo “_p”. El complemento del nombre queda a nuestra discreción
Tiene un único parámetro “t” el cual es una tupla, en cada posición tiene el valor de los terminales y no terminales de la producción.
Haciendo uso del docstring de las funciones de Python especificamos las producciones que serán procesadas por la función.
En el cuerpo de la función definimos la funcionalidad que deseamos

Por ejemplo:

def p_expresion_evaluar(t):
     'expresion : expresion MAS expresion'
     #   ^            ^      ^    ^
     #  t[0]         t[1]   t[2] t[3]
 
     t[0] = t[1] + t[3]

Sintetizamos en p[0] (expresion) el valor del resultado de sumar loo valores de p[1] (expresion) y p[3].

A continuación el código completo de nuestras producciones:

# Definición de la gramática
def p_instrucciones_lista(t):
    '''instrucciones    : instruccion instrucciones
                        | instruccion '''

def p_instrucciones_evaluar(t):
    'instruccion : REVALUAR CORIZQ expresion CORDER PTCOMA'
    print('El valor de la expresión es: ' + str(t[3]))

def p_expresion_binaria(t):
    '''expresion : expresion MAS expresion
                  | expresion MENOS expresion
                  | expresion POR expresion
                  | expresion DIVIDIDO expresion'''
    if t[2] == '+'  : t[0] = t[1] + t[3]
    elif t[2] == '-': t[0] = t[1] - t[3]
    elif t[2] == '*': t[0] = t[1] * t[3]
    elif t[2] == '/': t[0] = t[1] / t[3]

def p_expresion_unaria(t):
    'expresion : MENOS expresion %prec UMENOS'
    t[0] = -t[2]

def p_expresion_agrupacion(t):
    'expresion : PARIZQ expresion PARDER'
    t[0] = t[2]

def p_expresion_number(t):
    '''expresion    : ENTERO
                    | DECIMAL'''
    t[0] = t[1]

def p_error(t):
    print("Error sintáctico en '%s'" % t.value)

Por último, podemos manejar también las producciones de error para el manejo de errores sintácticos.

Ahora construimos el analizador sintáctico,la funcionalidad para leer el archivo y enviarle su contenido a nuestro compilador.

import ply.yacc as yacc
parser = yacc.yacc()

f = open("./entrada.txt", "r")
input = f.read()
print(input)
parser.parse(input)

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:

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

Ejecución

Para ejecutar este script corremos el siguiente comando:

1	$ python3 .\gramatica.py

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.

2020-02-10

Computer Science / Compilers

13 minutes read (About 1931 words)

Mi primer proyecto utilizando JavaCC

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 para utilizar son:

JavaCC: Generador de analizadores léxicos y sintácticos.
Windows 10: Sistema operativo.
Netbeans 8.2: IDE (entorno de desarrollo integrado)
Java 8: Lenguaje de programación.

El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Mi primer proyecto utilizando JavaCC

JavaCC

Java Compiler Compiler es un generador de analizadores para utilizar en java. Este generador es una herramienta que lee la especificación gramatical y la convierte en un programa de java que puede reconocer coincidencias con la gramática. Además del generador de analizadores en sí, JavaCC proporciona otras capacidades estándar relacionadas con la generación de analizadores, como la construcción de árboles (a través de una herramienta llamada JJTree incluida con JavaCC), acciones y depuración. Todo lo que se necesita para ejecutar un analizador JavaCC, una vez generado, es Java Runtime Environment (JRE).

Características

JavaCC utiliza un analizador descendente lo que permite el uso de gramáticas más generales.
Por defecto JavaCC genera un analizador LL(1), aunque JavaCC ofrece capacidades de anticipación sintáctica para resolver ambigüedades.
JavaCC permite la utilización de BNF Extendido, o lo que vendría siendo utilizar expresiones regulares tanto en la parte léxica como gramatical.
JavaCC permite la utilización de estados para manejar de mejor forma las expresiones regulares.
Para más información visitar la página oficial de JavaCC.

Prerrequisitos

Para este este ejemplo necesitamos las siguientes herramientas

Java Development Kit (JDK)
NetBeans (o cualquier IDE de nuestro agrado)
JavaCC

Agregar jdk a las variables de entorno

Debemos asegurarnos de que la carpeta bin del JDK haya sido agregada a nuestra variable de entorno Path, para ello vamos a la configuración de dicha variable de entorno

Clic derecho en Este equipo
Propiedades

Configuración avanzada del sistema
Variables de entorno
Variable Path
Editar

y si no existe agregamos la ruta a la carpeta bin del JDK, que en mi caso es:

1	C:\Program Files\Java\jdk1.8.0_211\bin

Descarga e instalación de JavaCC

Nos dirigimos a la página oficial de JavaCC, al ingresar hacemos clic sobre el botón de Download[Version].zip

Una vez descargado el archivo, lo extraemos y podremos ver el siguiente contenido:

El archivo que nos interesa es javacc.jar que se encuentra en la carpeta bootstrap:

Por conveniencia, vamos a trasladar el archivo .jar a la carpeta C:/javacc, sin embargo, podría guardarse en otra ubicación.

Mas adelante le daremos uso a nuestro archivo javacc.jar.

Crear el proyecto utilizando NetBeans

Como mencionamos vamos a utilizar NetBeans, sin embargo podría usarse cualquier otro IDE. Vamos a mostrar la creación del proyecto y su estructura.

Seleccionamos la opción de nuevo proyecto.
Ahora seleccionamos el tipo de proyecto, en este caso Java Application y damos clic en siguiente.

Por último, agregamos el nombre del proyecto y finalizamos.

Vemos el resultado de la creación del proyecto.

A continuación, creamos un nuevo paquete llamado Analizador, produciendo el siguiente resultado.

Dentro de este paquete vamos a crear un nuevo archivo llamado Gramatica.jj, este archivo contendrá la gramática para reconocer el lenguaje que vamos a realizar.
Para facilitar la compilación de la gramática vamos a crear un archivo compilarGramatica.bat, con el siguiente contenido, siempre en el paquete Analizador.

1 2	java -cp C:\javacc\javacc.jar javacc Gramatica.jj pause

Lo que indican estas sentencias:

Agregar el archivo jar al classpath mediante el argumento -cp (classpath) – -cp C:\javacc\javacc.jar (o la ubicación de nuestro archivo javacc.jar)
Ejecutar java – java
Pasar el main del archivo jar – javacc
Pasar la gramática a compilar – Gramatica.jj
Evitar que se cierre la ventana de comando para ver el resultado – pause
Nota: utilizamos el argumento classpath para indicarle a java donde debe buscar los paquetes y clases a ejecutar, mas información en el siguiente link.

Construcción del lenguaje en JavaCC

Luego de esta introducción vamos a construir una programa que reconozca un lenguaje compuesto por una lista de instrucciones Evaluar que reciben una expresión aritmética para ser evaluada, por ejemplo:

1	Evaluar [34-29]

Explicación de la estructura del archivo Gramatica.jj

Sección de opciones: Esta sección es opcional, el área de opciones permite especificar algunas directrices que ayuden a JavaCC a generar analizadores léxico-sintácticos más eficientes y adaptados a las necesidades concretas del desarrollador. Existen muchas, si quieres conocerlas mejor puedes verificar la página 132 del libro Compiladores, de Sergio Gálvez Rojas Y Miguel Ángel Mora Mata. En este caso particular utilizamos solamente dos:
- Ignore_Case = true, para no hacer distinción entre mayúsculas y minúsculas.
- Static = false, para que los métodos que genere la compilación no sean estáticos.
  1
  2
  3
  4
  options {
  IGNORE_CASE = true;
  STATIC = false;
  }
Clausulas PARSER_BEGIN – PARSER_END: Sirven para indicarle a JavaCC el nombre de nuestra clase principal, así como para englobar tanto a esta como a cualquier otra que se quiera incluir de apoyo. En este ejemplo no definimos ningun método main, solo una clase llamada gramática para nuestro parser, por supuesto que esta clase gramática es la que debemos utilizar para invocar a nuestro parser, y el main lo incluimos fuera de este para tener un código más claro.
1
2
3
4
5
6
PARSER_BEGIN(Gramatica)
/** Analizador de expresiones aritmeticas sencillas. */
package Analizador;
public class Gramatica {
}
PARSER_END(Gramatica)

Sección para definición léxica: Esta sección contendrá los tokens permitidos por nuestro lenguaje, contiene distintas clausulas, pero las que utilizamos son:

Token: Constituyen los tokens que nuestro analizador va a reconocer, generalmente aquí se incluyen todos los terminales de nuestro lenguaje, aunque también se pueden utilizar tokens en la definición sintáctica sin haberlos definido en esta sección.

Skip: En esta sección se incluyen los tokens que se van a ignorar durante el análisis, por ejemplo, los espacios o saltos de línea.

/** Lexico */
SKIP : {
	" "
	| "\t"
	| "\r"
	| "\n"
}

TOKEN : {
	<NUMERO: (["0"-"9"])+>
	| <DECIMAL: (["0"-"9"])+"."(["0"-"9"])+>
	| <EVALUAR: "Evaluar">
	| <PCOMA: ";">
	| <PARENI: "(">
	| <PAREND: ")">
	| <CORI: "[">
	| <CORD: "]">
	| <MAS: "+">
	| <MENOS: "-">
	| <POR: "*">
	| <DIV: "/">
}
/** Fin Lexico */

Sección para definición sintáctica: Aquí vamos a definir las producciones para nuestro analizador, estas están definidas como funciones. A continuación explicamos la estructura:
- Como buena práctica es recomendable agregar en un comentario la producción en formato BNF para que sea más fácil entender la producción actual, ya que las reglas sintácticas en JavaCC pueden ser un poco confusas.
- La definición de un método incluye:
  1
  2
  3
  <TIPO> <NOMBRE> () :
  {Sección para código de java, generalmente para declaraciones}
  {Producciones, estas pueden incluir notación de expresiones regulares}
- Si quisiéramos invocar a otra producción, agregamos su llamada a método y para obtener su valor lo hacemos de la siguiente manera
  1
  2
  3
  4
  5
  6
  /** Instruccion -> evaluar [ Expresion ]; */
  void Instruccion() :
  {double e;}
  {
  <EVALUAR> <CORI> e=Expresion() <CORD> <PCOMA> {System.out.println("El valor de la expresion es: "+e);}
  }
- En tal caso necesitásemos obtener el valor de un terminal, debemos utilizar el atributo image, ya que cada terminal es un objeto de tipo Token, para obtenerlo hacemos lo siguiente
  1
  2
  3
  4
  5
  6
  7
  8
  9
  double Primitivo() :
  {double e;}
  {
  <NUMERO> {return Double.parseDouble(token.image);}
  |
  <DECIMAL> {return Double.parseDouble(token.image);}
  |
  <PARENI> e=Expresion() <PAREND> {return e;}
  }
- Algo a tomar en cuenta es que, podemos declarar variables de tipo Token y asignarlas al terminal, esto es por si tuviéramos varios terminales en una misma producción y así sepamos diferenciar cada uno.

Compilación de la gramática

Una vez finalizado nuestro archivo Gramatica.jj, vamos a compilar este para generar los archivos necesarios para su ejecución, vamos a utilizar el archivo compilarGramatica.bat creado al inicio. Al ejecutar el archivo veremos lo siguiente:

Como resultado de esto, en nuestro paquete analizador se crearon los siguientes archivos

Gramatica.java: Este archivo contiene las funciones de cada no terminal de la sección sintáctica
GramaticaConstanst.java: Esta interfaz contiene las constantes de tipo entero que identifican a cada token de nuestro lenguaje y son asignadas a las variables kind.
GramaticaTokenManager.java: Se encarga de reconocer los tokens durante el análisis léxico.
ParseException.java: Se utiliza para lanzar los errores durante el análisis sintáctico.
TokenMgrError.java: Se encarga de manejar los errores léxicos.
Token.java: Representa cada token definido en nuestra sección léxica.

Clase Principal

Por último, vamos a invocar a nuestro parser en el método main, para utilizar nuestro parser basta con crear la clase Gramatica y pasar por parámetro nuestro archivo de entrada, luego de crear la instancia invocamos al método inicial que en nuestro caso sería el método analizar.

package proyectojavacc;

import Analizador.Gramatica;
import Analizador.ParseException;
import Analizador.TokenMgrError;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.util.logging.Level;
import java.util.logging.Logger;
/**
 *
 * @author Pavel
 */
public class ProyectoJavaCC {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        try {
            Gramatica parser = new Gramatica(new BufferedReader(new FileReader("./entrada.txt")));
            parser.Analizar();
        } catch (ParseException e) {
            System.err.println(e.getMessage());
        } catch (FileNotFoundException e) {
            Logger.getLogger(ProyectoJavaCC.class.getName()).log(Level.SEVERE, "Error al intentar leer el archivo.", e);
        } catch(TokenMgrError e){
            System.err.println(e.getMessage());
        }
    }
    
}

Ejecución del archivo de entrada

El archivo que vamos a utilizar debe encontrarse dentro de la carpeta de nuestro proyecto.

Y su contenido es el siguiente:

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

Ejecutamos nuestro programa y vemos la siguiente salida:

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Pavel Vásquez, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.

Fuentes consultadas

Intérprete sencillo utilizando Irony y C#

2019-08-07

Computer Science / Compilers

7 minutes read (About 990 words)

Intérprete sencillo utilizando Irony y C#

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

Las tecnologías a utilizar son:

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

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

Intérprete Sencillo Utilizando Irony

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

Mi primer proyecto utilizando Irony

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

El lenguaje de entrada

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

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

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

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

Entornos

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

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

Árbol de análisis abstracto AST

Un árbol de sintaxis abstracta (AST) es una representación simplificada de la estructura sintáctica del código fuente. A nivel de programación un AST es una estructura de datos que se genera durante el proceso de análisis sintáctico.
En el código de Irony lo vamos armando por medio de listas de instrucciones, donde cada sentencia es una instrucción y en el bloque contenido en esta sentencia tendríamos otra lista de instrucciones, armando así un árbol en donde cada nodo es un objeto que implementa la interfaz instrucción y puede contener múltiples hijos que serían otros objetos que implementan la interfaz instrucción, que serían otras instrucciones.

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

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

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

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Julio Arango, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.

Fuentes consultadas:

Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.

Intérprete sencillo utilizando Gold Parser y Visual Basic

2019-08-07

Computer Science / Compilers

11 minutes read (About 1721 words)

Intérprete sencillo utilizando Gold Parser y Visual Basic

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:

Intérprete sencillo utilizando Java, Jlex y Cup

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

Intérprete Sencillo Utilizando Gold Parser

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.
Documentación de Gold Parser

Intérprete sencillo utilizando Jison con Nodejs (Ubuntu)

2019-08-01

Computer Science / Compilers

27 minutes read (About 4031 words)

Intérprete sencillo utilizando Jison con Nodejs (Ubuntu)

Funcionamiento de la aplicació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:

Intérprete sencillo utilizando Jison con Nodejs (Ubuntu)

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

/******************************************
 * 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.

\"[^\"]*\"              { yytext = yytext.substr(1,yyleng-2); return 'CADENA'; }
[0-9]+("."[0-9]+)?\b    return 'DECIMAL';
[0-9]+\b                return 'ENTERO';
([a-zA-Z])[a-zA-Z0-9_]* return 'IDENTIFICADOR';

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.

/**
 * 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
		}
	},

	/**
	 * Crea un objeto tipo Instrucción para la sentencia If-Else.
	 * @param {*} expresionLogica 
	 * @param {*} instruccionesIfVerdadero 
	 * @param {*} instruccionesIfFalso 
	 */
	nuevoIfElse: function(expresionLogica, instruccionesIfVerdadero, instruccionesIfFalso) {
		return {
			tipo: TIPO_INSTRUCCION.IF_ELSE,
			expresionLogica: expresionLogica,
			instruccionesIfVerdadero: instruccionesIfVerdadero,
			instruccionesIfFalso: instruccionesIfFalso
		}
	}
}

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

// Exportamos nuestras constantes y nuestra API

module.exports.TIPO_OPERACION = TIPO_OPERACION;
module.exports.TIPO_INSTRUCCION = TIPO_INSTRUCCION;
module.exports.TIPO_VALOR = TIPO_VALOR;
module.exports.instruccionesAPI = instruccionesAPI;

Construcción del AST

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

%{
	const TIPO_OPERACION	= require('./instrucciones').TIPO_OPERACION;
	const TIPO_VALOR 		= require('./instrucciones').TIPO_VALOR;
	const instruccionesAPI	= require('./instrucciones').instruccionesAPI;
%}

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

expresion_numerica
   : MENOS expresion_numerica %prec UMENOS          { $$ = instruccionesAPI.nuevoOperacionUnaria($2, TIPO_OPERACION.NEGATIVO); }
   | expresion_numerica MAS expresion_numerica      { $$ = instruccionesAPI.nuevoOperacionBinaria($1, $3, TIPO_OPERACION.SUMA); }
   | expresion_numerica MENOS expresion_numerica    { $$ = instruccionesAPI.nuevoOperacionBinaria($1, $3, TIPO_OPERACION.RESTA); }
   | expresion_numerica POR expresion_numerica      { $$ = instruccionesAPI.nuevoOperacionBinaria($1, $3, TIPO_OPERACION.MULTIPLICACION); }
   | expresion_numerica DIVIDIDO expresion_numerica { $$ = instruccionesAPI.nuevoOperacionBinaria($1, $3, TIPO_OPERACION.DIVISION); }
   | PARIZQ expresion_numerica PARDER               { $$ = $2; }
   | ENTERO                                         { $$ = instruccionesAPI.nuevoValor(Number($1), TIPO_VALOR.NUMERO); }
   | DECIMAL                                        { $$ = instruccionesAPI.nuevoValor(Number($1), TIPO_VALOR.NUMERO); }
   | IDENTIFICADOR                                  { $$ = instruccionesAPI.nuevoValor($1, TIPO_VALOR.IDENTIFICADOR); }
;

También hacemos uso de la función nuevoValor para las expresiones con valor.

El proceso es el mismo para las Instrucciones, cada producción de tipo Instrucción invoca a su función designada en nuestra API.

instruccion
   : RIMPRIMIR PARIZQ expresion_cadena PARDER PTCOMA                        { $$ = instruccionesAPI.nuevoImprimir($3); }
   | RMIENTRAS PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER { $$ = instruccionesAPI.nuevoMientras($3, $6); }
   | RNUMERO IDENTIFICADOR PTCOMA                                           { $$ = instruccionesAPI.nuevoDeclaracion($2); }
   | IDENTIFICADOR IGUAL expresion_numerica PTCOMA                          { $$ = instruccionesAPI.nuevoAsignacion($1, $3); }
   | RIF PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER       { $$ = instruccionesAPI.nuevoIf($3, $6); }
   | RIF PARIZQ expresion_logica PARDER LLAVIZQ instrucciones LLAVDER RELSE LLAVIZQ instrucciones LLAVDER
                                                                            { $$ = instruccionesAPI.nuevoIf($3, $6, $10); }
   | error { console.error('Este es un error sintáctico: ' + yytext + ', en la linea: ' + this._$.first_line + ', en la columna: ' + this._$.first_column); }
;

Finalmente, una vez que hayamos reconocido toda la entrada, construimos un arreglo con cada uno de los nodos. Este será nuestro AST.

ini
	: instrucciones EOF {
		// cuado se haya reconocido la entrada completa retornamos el AST
		return $1;
	}
;

instrucciones
	: instrucciones instruccion { $1.push($2); $$ = $1; }
	| instruccion               { $$ = [$1]; }
;

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

Definimos las constantes para los tipos de datos, en este tutorial se hace uso únicamente del tipo de dato numérico.

// Constantes para los tipos de datos.
const TIPO_DATO = {
    NUMERO: 'NUMERO'
}

Se define una función para crear objetos de tipo Símbolo.

/**
 * 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;
    }
}

Finalmente, exportamos las constantes y la clase

// Exportamos las constantes y la clase.

module.exports.TIPO_DATO = TIPO_DATO;
module.exports.TS = TS;

Construcción del Intérprete

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.

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.

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);
        } else if (instruccion.tipo === TIPO_INSTRUCCION.MIENTRAS) {
            // Procesando Instrucción Mientras
            procesarMientras(instruccion, tablaDeSimbolos);
        } else if (instruccion.tipo === TIPO_INSTRUCCION.DECLARACION) {
            // Procesando Instrucción Declaración
            procesarDeclaracion(instruccion, tablaDeSimbolos);
        } else if (instruccion.tipo === TIPO_INSTRUCCION.ASIGNACION) {
            // Procesando Instrucción Asignación
            procesarAsignacion(instruccion, tablaDeSimbolos);
        } else if (instruccion.tipo === TIPO_INSTRUCCION.IF) {
            // Procesando Instrucción If
            procesarIf(instruccion, tablaDeSimbolos);
        } else if (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.

/**
 * 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);
}

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;
    } else if (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;
    } else if (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;
    } else if (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;
    }
}

/**
 * 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;     
    } else if (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.

/**
 * 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.

2019-07-24

Computer Science / Compilers

19 minutes read (About 2848 words)

Mi primer proyecto utilizando Irony

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

Las tecnologías a utilizar son:

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

El proyecto completo puede descargarse del siguiente enlace:

Mi primer proyecto utilizando Irony

Irony

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

Analizador léxico (Scanner)

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

Un token es un par que consiste en un nombre de token y un valor de atributo opcional.
Un lexema es una secuencia de caracteres en el programa fuente, que coinciden con el patrón para un token y que el analizador léxico identifica como una instancia de este tóken.
Un patrón es una descripción de la forma que pueden tomar los lexemas de un token.

Analizador sintáctico (Parser)

Pre-requisitos

Obtención del archivo Irony.DDL

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

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:

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

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

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

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

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

Con lo anterior definido, se crea la gramática, para ello es importante resaltar los siguientes puntos:
- Toda producción debe iniciar con el nombre de algún no terminal previamente declarado y el atributo Rule “Produccion.Rule”.
- Se finalizan las producciones con punto y coma.
- Se pueden tener diferentes producciones en un solo no terminal, para ello cada una de ellas se separa con un “|”.
- Para concatenar terminales o no terminales a la producción se debe usar siempre el signo “+”.
Gramática utilizada:

ini.Rule = instrucciones;

instrucciones.Rule = instruccion + instrucciones
    | instruccion;

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

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

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

1	this.Root = ini;

Recorrido del AST

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

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

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

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

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

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

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:

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:

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

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

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

Si tiene un hijo se trata de un número entero o decimal, por lo cual retornamos únicamente el valor del número.
Si tiene dos hijos es la producción de “menos <expresión>” por lo cual multiplicamos el valor de la expresión por menos uno.
Si tiene 3 hijos puede tratarse de una suma, resta, multiplicación o división, para determinar de cuál se trata, recogemos el valor del hijo de en medio que contiene el operador y ejecutamos según corresponda, esto se hace dentro de la sentencia switch del método.
Interpretación del archivo de entrada

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

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

1	using ProyectoIronyCS.sol.com.analizador;

Y en el método Main encontramos lo siguiente:

1
2
3

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

Estos comandos realizan las siguientes acciones:

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:

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

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

Como podemos ver, obtenemos la salida esperada.

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

Acerca del autor:

Este tutorial fue elaborado por el Auxiliar de Cátedra Julio Arango, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.

Fuentes consultadas:

Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.

Mi primer proyecto utilizando Gold Parser

2019-07-22

Computer Science / Compilers

17 minutes read (About 2524 words)

Mi primer proyecto utilizando Gold Parser

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:

Gold Parser Builder: Generador de analizadores léxicos y sintácticos diseñado para funcionar en múltiples lenguajes de programación.
Visual Studio 2017: Entorno de desarrollo integrado para programar Visual Basic y C#, entre otros.
Windows 10: Sistema operativo

El proyecto completo puede descargarse del siguiente enlace:

Mi primer proyecto utilizando Gold Parser

Gold Parser

Gold Parser es un generador de analizadores léxicos y sintácticos que soporta lenguajes tales como C#, COBOL, DELPHI, Visual Basic, Java entre otros. Este programa realiza de manera conjunta el análisis léxico y sintáctico, por lo que no tenemos la necesidad de recurrir a ningún programa externo.

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.

Pre-requisitos

Gold Parser Builder

Este programa puede descargarse de la página oficial de Gold Parser

Descomprimimos el archivo ZIP descargado y ejecutamos el archivo setup.exe que encontraremos dentro de los files descomprimidos.

Esto nos desplegará el asistente de instalación, en la primera ventana no debemos de seleccionar nada, por lo que únicamente presionaremos el botón de siguiente.

Posteriormente se nos preguntara en que ruta deseamos instalar Gold Parser, en este caso dejaremos la ruta por defecto que es “C:\Program Files (x86)\Gold Parser Builder”, seleccionar si queremos instalarlo para todos los usuarios o solo para nosotros, en este caso seleccionaremos “Everyone” para que todos los usuarios puedan utilizarlo. Damos click en siguiente para continuar con la instalación.

Luego se nos mostrará una ventana que pide nuestra confirmación para continuar con la instalación de Gold Parser, hacemos click en siguiente.

Por último se nos mostrará la ventana de confirmación que indica que Gold Parser fue instalado correctamente.

Generando nuestro analizador léxico y sintáctico con Gold Parser

Hacemos click en el botón de Windows y buscamos “gold parser builder”.

Ejecutamos la aplicación Gold Parser Builder y tendremos un ambiente de trabajo como el que se muestra a continuación.

Lo primero que debemos hacer para comenzar a trabajar con Gold Parser Builder es definir la gramática, el ejemplo que inspiró este tutorial fue realizado con Jlex y Cup:

Mi primer proyecto utilizando Jlex y Cup (Windows)

La gramática planteada para Jlex y Cup era ambigua y dicha ambigüedad se resolvía indicando de forma explicita la precedencia de los operadores aritméticos:

1
2
3

precedence left MAS,MENOS;
precedence left POR,DIVIDIDO;
precedence right UMENOS;

Cup permite definir la precedencia y asociatividad de los operadores de forma explícita, en el caso de Gold Parser, esta opción no está disponible, por lo que es necesario utilizar una gramática no ambigua que respete la precedencia y asociatividad de los operadores.

Tomando en cuenta lo anterior, se propone la siguiente gramática escrita con la sintaxis propia de Gold Parser:

"Name"    = 'Mi Primer Proyecto en Gold Parser'
"Author"  = 'Luis Lizama'
"Version" = '1.0' 
"About"   = 'Ejemplo de una gramática simple que reconoce expresiones aritméticas'

"Case Sensitive" = False 
"Start Symbol"   = <Statements>
    
DECIMAL = {Digit}+'.'{Digit}+
ENTERO = {Digit}+

<Statements> ::= <Statement> <Statements>
               | <Statement>

<Statement>  ::= Evaluar '[' <Expression> ']'';'
               
<Expression>   ::= <Expression> '+' <Mult Exp> 
                 | <Expression> '-' <Mult Exp> 
                 | <Mult Exp> 

<Mult Exp>    ::= <Mult Exp> '*' <Negate Exp> 
                | <Mult Exp> '/' <Negate Exp> 
                | <Negate Exp> 

<Negate Exp>  ::= '-' <Value> 
                | <Value> 

<Value>       ::= ENTERO 
                | DECIMAL 
                | '(' <Expression> ')'

Toda la documentación relacionada con la sintaxis de Gold Parser puede encontrarse en la página oficial.

Una vez tengamos lista nuestra gramática, la ingresamos en la ventana Grammar de la aplicación Gold Parser Builder (para esto basta con copiar y pegar la gramática mostrada anteriormente).

Luego procedemos a guardar la gramática seleccionando la opción “File” → “Save”, el archivo resultante tendrá extensión GRM, que es una extensión propia de Gold Parser.

El archivo GRM con la gramática utilizada para este ejemplo está disponible en la carpeta Gramática del repositorio de este ejemplo.

Posteriormente seleccionamos la opción “Project” → “Analyze the Grammar”, esto analizará la gramática y nos mostrará los conflictos si existieran.

Debemos corregir todos los errores antes de continuar, para este ejemplo no había ninguno. Esto podemos confirmarlo en la parte inferior de nuestro editor de Gold Parser Builder.

Si existiesen errores o notificaciones se nos mostrarán en una ventana emergente de la siguiente manera:

En este caso no teníamos errores, así que podemos proseguir con la creación de las tablas para el análisis LALR. Esto lo hacemos seleccionando la opción “Project” → “Create LALR Parse Tables”

Podemos confirmar que nuestras tablas LALR fueron creadas exitosamente en la parte inferior de nuestro editor de Gold Parser Builder.

Durante la creación de las tablas LALR es posible de que se detecten conflictos de desplazamiento-reducción y el asistente no nos permita continuar, en este caso debemos resolver estos conflictos y luego continuar. Por el contrario, si no tenemos conflictos que resolver, podemos continuar al último paso, crear las tablas del autómata finito determinista que será el encargado de realizar el análisis léxico. Para ello seleccionamos la opción “Project” → “Create DFA Lexer Tables”.

Podemos confirmar que nuestras tablas para el autómata finito determinista fueron creadas exitosamente en la parte inferior de nuestro editor de Gold Parser Builder.

Por último, procedemos a guardar todas las tablas, estas serán importadas posteriormente en nuestro programa para poder realizar el análisis léxico y sintáctico del texto recibido como entrada. Para ello seleccionamos la opción “Project” → “Save the Tables”.

Se nos mostrará una ventana para que indiquemos la ruta en la cual deseamos almacenar las tablas, la seleccionamos y damos click en aceptar, con esto habremos generado un archivo EGT, esta ventana se cerrará y Gold Parser nos mostrará un mensaje diciendo que se guardaron las tablas correctamente.

EGT es una extensión propia de Gold parser.

El archivo EGT con las tablas generado para este ejemplo está disponible en la carpeta Gramática del repositorio de este ejemplo.

Una de las principales ventajas de Gold Parser es que tiene un módulo de test que permite visualizar el proceso de análisis de una forma detallada. Para utilizar el módulo de test, hacemos click en el ícono correspondiente, que tiene un pequeño cheque verde.

O bien seleccionando la opción “Window” → “Test Grammar”

Esto nos desplegará una ventana de test en la que podemos ingresar en el lado izquiero una entrada y posteriormente evaluar paso a paso esta entrada con el botón verde de ejecutar que se encuentra en la parte inferior izquierda, esto nos permitirá ver el progreso del análisis en el panel derecho con el detalle de cada estado.

Luego de este pequeño paréntesis para explorar el módulo de test de Gold Parser continuaremos con nuestro proyecto.

El siguiente paso es crear el esqueleto de un programa, para ello seleccionamos “Project” → “Create a Skeleton Program…”.

Se nos desplegarán varias opciones para generar el esqueleto, para este ejemplo en específico utilizaremos Visual Basic .NET y como motor Cock .NET DLL.

Seleccionaremos la opción de crear y nos mostrará una ventana desde la cual podremos seleccionar la ruta en la cual queremos guardar el esqueleto de nuestro programa. Obtendremos como resultado un archivo con extensión VB.

El archivo VB generado con el esqueleto está disponible en la carpeta Gramática del repositorio de este ejemplo.

Esto es todo lo que haremos en Gold Parser, de acá en adelante utilizaremos Visual Studio.

Abrimos Visual Studio.

Seleccionamos “File” → “New” → “Project”, una vez abierto el wizard para crear nuevos proyectos seleccionamos el apartado “Visual Basic” → “Windows Desktop” → “Console App (.NET Framework)” y le pondremos como nombre Calculadora.

Para poder utilizar el esqueleto que generamos en Gold Parser en el proyecto que acabamos de crear necesitaremos importar la librería .NET DLL que realiza el proceso de análisis, esta libería debe descargarse en la página oficial.

Luego de descargar y descomprimir la librería obtendremos el archivo “Gold Engine.dll” que es el que debemos importar en nuestro proyecto.

Con el proyecto creado debemos de pegar el archivo de las tablas de análisis generadas en Gold Parser (Expresiones aritméticas.egt) y la librería que acabamos de descargar (GOLD Engine.dll) en la carpeta Calculadora/Calculadora/bin/debug de nuestro proyecto.

También debemos de pegar el esqueleto que generamos con Gold Parser (Expresiones aritméticas.vb) en la carpeta principal de nuestro proyecto.

Regresamos a Visual Studio y desde el explorador de soluciones debemos de realizar dos procedimientos.

El primero es importar el archivo que contiene el esqueleto generado en Gold Parser (Expresiones aritméticas.vb), para ello hacemos click derecho sobre el nombre de nuestro proyecto “Add” → “Existing Item…”.

Luego seleccionamos el archivo de nuestro esqueleto.

Veremos que ahora aparece en el explorador de soluciones.

El segundo procedimiento a realizar en el explorador de soluciones es importar la librería que acabamos de pegar en nuestra carpeta debug, 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.

Por último, abrimos el archivo que contiene el esqueleto que generamos con Gold Parser (Expresiones aritméticas.vb) y dentro de las líneas de código buscar el método con el nombre Setup. Es la única instrucción que posee este método, debemos cambiar el nombre del archivo gramar.egt por el nombre de nuestro archivo de tablas (Expresiones aritméticas.egt), es de suma importancia que hayamos pegado nuestras tablas en la carpeta debug, de otra manera nuestro programa no las podrá encontrar y nos arrojará un error en tiempo de ejecución.

Estas son todas las configuraciones que debemos de realizar para poder utilizar Gold Parser, de acá en adelante, el tutorial se enfoca en explicar el funcionamiento de los archivos que se generaron anteriormente.

Creando un archivo de entrada para nuestro analizador

Creamos un nuevo archivo de texto llamado entrada.txt. El contenido de este archivo es el siguiente:

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

Este archivo de entrada será creado en la carpeta Calculadora/Calculadora/bin/debug de nuestro proyecto.

Utilizando el esqueleto generado con Gold Parser

En los pasos anteriores nos enfocamos en la definición de la gramática y las configuraciones que tenemos que realizar para poder utilizar los archivos que generamos con Gold Parser, pero no hemos programado ningún tipo de instrucción dentro de nuestro programa.

Gold Parser se centra en generar un árbol de análisis sintáctico, de esta manera nosotros podremos recorrer este árbol como sea más conveniente, es por ello que no nos permite incrustar acciones semánticas al momento de definir la gramática, debemos de realizarlo directamente en el esqueleto generado, este esqueleto será modificado según convenaga para lograr nuestro objetivo.

El archivo VB generado con el esqueleto (Expresiones aritméticas.vb) modificado con las acciones necesarias para evaluar las expresiones aritméticas, además de estar en la carpeta principal del proyecto dentro del repositorio, está disponible en la carpeta Gramática.

Podremos notar que el esqueleto generado, en su método parse, posee una serie de estados los cuales por defecto tienen comentado su funcionamiento, los estados que alteraremos en este ejemplo son:

LexicalError : Reportar errores léxicos.
SyntaxError : Reportar errores sintácticos.
Accept : Crear la raíz de nuestro árbol de análisis sintáctico.

Definiremos una variable Root de tipo Gold.Reduction que será la raíz de nuestro árbol.

Adicionalmente podremos notar que el archivo también posee una función denominada CreateNewObject que posee una serie de casos los cuales tienen comentado a que producción de la gramática pertenecen, es aquí donde debemos de introducir las acciones semánticas que deseamos que se ejecuten al momento de reducir por cada producción.

Esta función CreateNewObject viene definida únicamente como una plantilla, pero podremos darle la funcionalidad que nosotros deseemos. Para este ejemplo en específico se le cambió el nombre por “GetValue” ya que lo que necesitamos al final es obtener el valor resultante de evaluar cada expresión aritmética.

Los métodos de nuestro parser son estáticos y no es necesario crear una instancia parser, pero si es necesario ejecutar el método Setup para que cargue las tablas de análisis.

El programa por defecto está configurado para leer el archivo entrada.txt en la carpeta Calculadora/Calculadora/bin/debug del proyecto.

A continuación se muestra el resultado de ejecutar el archivo de entrada que preparamos anteriormente.

Como podemos ver, obtenemos la salida esperada.

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.

Erick Navarro

Data Engineering Manager

Guatemala City

Posts

Mi primer proyecto utilizando Yacc y Lex

Código fuente para el analizador léxico

Explicación código fuente para el analizador léxico

Código fuente para el analizador sintáctico

Explicación código fuente para el analizador sintáctico

El archivo de compilación

Archivo de entrada

Archivo Principal

Ejecutando nuestra aplicación

Fuentes Consultadas

Intérprete sencillo utilizando PLY con Python 3

Intérprete sencillo utilizando JavaCC

Mi primer proyecto utilizando PLY con Python 3

Mi primer proyecto utilizando JavaCC

Intérprete sencillo utilizando Irony y C#

Intérprete sencillo utilizando Gold Parser y Visual Basic

Intérprete sencillo utilizando Jison con Nodejs (Ubuntu)

Mi primer proyecto utilizando Irony

Mi primer proyecto utilizando Gold Parser

Links

Categories

Tag Cloud

Recent

Archives

Tags

Recent

Archives

Tags

Your browser is out-of-date!