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:
El proyecto completo de este ejemplo puede descargarse del siguiente enlace:
Diseño utilizado para el desarrollo de este ejemplo
Para este ejemplo se crea un objeto por cada una de las sentencias que reconoce nuestra gramática, cada objeto implementa la interfaz instruccion que representa un nodo en nuestro árbol. Esto nos permite tratar todas las sentencias como nodos y asignarle acciones específicas a cada uno según su tipo. Se puede entender nuestra gramática de la siguiente forma:
El lenguaje de entrada
Dentro de la carpeta del proyecto podremos acceder a /bin/Debug y allí encontraremos un archivo de entrada llamado “entrada.txt”, en él se muestran ejemplos de todas las funciones del lenguaje diseñado para esta aplicación, al leerlo se puede tener una idea clara de las funciones con las que el lenguaje cuenta, este archivo contiene lo siguiente:
- Comentarios simples, es decir de una sola línea (//)
- Comentarios múltiples, es decir de más de una línea (/ /)
- Concatenación de cadenas, mediante el operador &
- Función Imprimir: Recibe como parámetro una cadena e imprime su valor en consola.
- Declaración de variables: Únicamente se acepta definición de variables de tipo numero incluyendo enteros y decimales.
- Asignación de variables: A cualquier variable se le puede asignar cualquier expresión que tenga como resultado un número.
- Instrucción Mientras: Tiene el comportamiento clásico del ciclo while, ejecuta el ciclo mientras la expresión booleana que recibe sea verdadera. Esta instrucción soporta anidamiento.
- Instrucción If e If-Else: Tiene el comportamiento clásico de las sentencias de selección If e If-Else, evalúa la expresión booleana y ejecuta el bloque de instrucciones en If si es verdadera. En caso contrario y si existe un bloque Else se ejecuta este bloque de instrucciones. Estas instrucciones también soportan anidamiento.
- Expresiones aritméticas: Se soportan las expresiones aritméticas binarias: suma, resta, multiplicación y división. También la expresión unaria: negación. Adicionalmente se soporta expresiones agrupadas en paréntesis. Se maneja la precedencia habitual de las expresiones aritméticas.
- Expresiones booleanas: Comparan dos expresiones que tengan como resultado un número y soportan unicamente los operados mayor que y menor que (<, >).
La gramatica utilizada para este ejemplo puede encontrarse en la carpeta Gramatica, en el archivo Gramatica.grm. Gold Parser permite la definición de expresiones regulares con las que podremos definir algunos tokens del programa, tales como:
- Entero acepta todos los numero que no poseen punto decimal
- Decimal acepta todo tipo de números decimales
- Car Acepta todos los caracteres imprimibles que pueden venir dentro de una cadena con la excepción de las comillas dobles
- Cadena Acepta un conjunto de caracteres delimitados por comillas dobles
- ID Head Acepta todas las letras del alfabeto además del guien bajo, se utiliza para la primera letra de los identificadores.
- ID Tail Acepta Todos los caracteres alfanuméricos además del guion bajo, se utiliza para todos los caracteres del identificador con la excepción de la primera letra
- ID Agrupa ID Head e ID Tail para poder conformar un identificador valido para nuestro lenguaje
De igual manera, Gold Parser posee palabras reservadas para definir los comentarios, por lo que no tendremos que escribir una expresión regular personalizada.
El resultado de la ejecución
Al ejecutar la entrada mostrada en nuestro ejemplo, esta fue la salida obtenida:
Sobre la tabla de símbolos
La tabla de símbolos es una parte importante en el proceso de ejecución del código, es en esta estructura de datos en donde guardamos información de las variables como su tipo, identificador y valor. En esta estructura podemos agregar variables, modificar los valores de las variables existentes, así como obtener sus valores. Otra alternativa más detallada es utilizar entornos, un ejemplo de esto se puede encontrar en el libro del curso (Ver Referencias) en la página 87, en donde se habla sobre tablas de símbolos por alcance, a través de entornos anidados.
El manejo de entornos es sumamente importante ya que deberíamos de crear un nuevo entorno por cada alcance, de manera que los entornos superiores no tengan acceso a las variables declaradas en entornos inferiores pero los entornos inferiores puedan acceder tanto a sus variables como a las de los entornos superiores, esto funciona de manera muy similar a una pila, ya que el ultimo entorno creado debería ser el primero en ser eliminado.
En este ejemplo, esto se logra mediante el método AddAll de la clase TablaSimbolos.vb, que agrega todos los símbolos del entorno anterior al final del nuevo entorno.
La magia detrás de todo esto: Árbol de sintaxis abstracta (AST)
Un árbol de sintaxis abstracta (AST) es una representación simplificada de la estructura sintáctica del código fuente. A nivel de programación un AST es una estructura de datos que se genera durante el proceso de análisis sintáctico.
Gold Parser nos genera un árbol de análisis sintáctico, sin embargo, es mucho más práctico generar el nuestro que nos permita poder ejecutar las acciones al mismo tiempo que visitamos los nodos. Si creamos nuestro propio árbol tendremos completo control sobre nuestra gramática, tendremos código más entendible, reportes de errores más detallados y menos dolores de cabeza al tratar de encontrar un error.
Como se observa en el código fuente, las únicas acciones que realizamos en el árbol de Gold Parser es retornar nodos que nos permitan generar nuestro árbol. En la producción inicial debemos crear nuestro AST, que funcionara como raíz desde la cual debemos comenzar la ejecución de nuestro programa.
En este ejemplo el AST es la pieza más importante, porque al recorrerlo pueden ejecutarse las acciones del código de entrada y ese es el principal objetivo de la aplicación. Esta se conforma únicamente de dos paquetes:
- Análisis: Este paquete únicamente contiene la clase SkeletonProgram, que es el que nos genera Gold Parser por defecto y sobre el archivo que crearemos nuestro AST.
- Árbol: Posee todas las clases necesarias que nos permiten crear nuestro AST, así como la interfaz operación que es la que permite tratar a todos los nodos del árbol como uno mismo.
Además, es importante destacar que existe un archivo más que se encuentra en la carpeta raíz de nuestro programa, es la clase principal que visual nos crea por defecto y en este caso se denomina Module1.Vb. Desde este archivo comienza toda la ejecución del programa y es desde donde debemos de configurar nuestro parser con el método setup (método por defecto de Gold Parser) y también donde deberemos de mandar a ejecutar las acciones de nuestro árbol con el método ejecutar una vez que estemos seguros que la entrada fue aceptada.
Acerca del autor:
Este tutorial fue elaborado por el Auxiliar de Cátedra Luis Lizama, como contribución al curso de Organización de Lenguajes y Compiladores 2 de la Universidad de San Carlos de Guatemala.
Fuentes consultadas:
- Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.
- Documentación de Gold Parser
