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:
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.
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.
Pre-requisitos
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:
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 | precedence left MAS,MENOS; |
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:
1 | "Name" = 'Mi Primer Proyecto en Gold Parser' |
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:
1 | Evaluar[1+1]; |
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.
