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:
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:
1
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:
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.
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.
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.
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 “$$”.
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.
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.
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.
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.
1
./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.
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:
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
# 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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
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. '''
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
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
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. '''
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. '''
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. '''
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.
1 2 3 4 5 6 7 8 9 10 11 12 13
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.
1 2 3 4
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 '''
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 '''
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
1 2 3 4 5 6 7 8 9 10
class ExpresionLogica() : ''' Esta clase representa la expresión lógica. Esta clase recibe los operandos y el operador '''
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.
1 2 3 4
# 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).
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.
1 2 3 4
from enum import Enum
class TIPO_DATO(Enum) : NUMERO = 1
Definimos una clase para los Símbolos.
1 2 3 4 5 6 7
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.
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.
1 2 3 4
import gramatica as g import ts as TS from expresiones import * from instrucciones import *
Seguidamente, obtenemos el AST a partir del archivo de entrada.
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.
1 2 3 4 5 6 7 8 9 10
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_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_definicion(instr, ts) : simbolo = TS.Simbolo(instr.id, TS.TIPO_DATO.NUMERO, 0) # inicializamos con 0 como valor por defecto ts.agregar(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
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.
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.
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.
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: 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.
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.
Sección more Sección utilizada para la creación de estados.
1 2 3 4 5 6 7 8 9
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.
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
@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:
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()); } elseif (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()); } } });
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:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
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.
