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

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.

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

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

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

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

1
2
3
4
5

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

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.

En esta publicación se muestra un ejemplo sencillo de la implementación de un analizador sintáctico a partir de una gramática independiente del contexto. Este proyecto se desarrolló utilizando Visual Studio 2013. El proyecto completo puede descargarse del siguiente enlace:

Analizador sintáctico en Visual Basic.

Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.

Funcionamiento del proyecto

Este ejemplo ilustra la implementación de un analizador sintáctico a partir de una gramática independiente del contexto. No se utiliza ningún generador de analizadores sintácticos que genere el analizador, ni se realiza el proceso de análisis sintáctico con ninguna librería. Los errores identificados en el proceso de análisis sintáctico se muestran en consola, si en el entorno de Visual Studio no aparece la consola, esta puede abrirse desde el menú ver, en la opción resultados o con Ctrl+Alt+O. Inicialmente se muestra una expresión aritmética de ejemplo que puede utilizarse como entrada, esta entrada contiene una expresión incompleta que léxicamente es correcta pero sintácticamente no, su estructura es incorrecta porque le hace falta un numero y un paréntesis derecho al final.

Al presionar el botón Analizar se ejecuta el análisis de la entrada y en consola se despliegan los mensajes de error.

El fundamento teórico que sirvió de soporte para el desarrollo de este ejemplo es el descrito en la sección 4.4.1 titulada Análisis sintáctico de descenso recursivo del libro: Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición.

Gramática independiente del contexto utilizada

La gramática utilizada, reconoce expresiones aritméticas respetando la precedencia de operadores, no es ambigua y no tiene recursividad por la izquierda. La gramática es la siguiente:

1
2
3
4
5
6
7
8
9
10

E  → T E'
E' → + T E'
E' → - T E'
E' → ε
T  → F T'
T' → * F T'
T' → / F T'
T' → ε
F  → ( E )
F  → numero

Método utilizado para el desarrollo del analizador

Se desarrolló un analizador sintáctico predictivo recursivo. Los analizadores predictivos o descendentes consisten en la construcción de un árbol de análisis sintáctico para la cadena de entrada, partiendo desde la raíz y creando los nodos del árbol de análisis sintáctico en pre-orden. En este caso no se construye un árbol en memoria, ya que no es necesario guardar lo que se analiza, pero las llamadas recursivas a los diferentes métodos del analizador crean un árbol en pila mientras se ejecutan. La construcción de este analizador sintáctico predictivo recursivo sigue los siguientes principios:

• Consiste en un conjunto de procedimientos, uno para cada no terminal.

• La ejecución empieza con el procedimiento para el símbolo inicial.

• Se detiene y anuncia que tuvo éxito si el cuerpo de su procedimiento explora la cadena completa de entrada.

• Para cada no terminal del lado derecho de las producciones se hace una llamada al método que le corresponde.

• Para cada terminal del lado derecho de las producciones se hace una llamada al método match enviando como parámetro el terminal.

• El método match valida si el terminal que se recibe es el que se esperaba, de no ser así despliega un mensaje de error.

• La gramática a utilizar reconoce expresiones aritméticas y cumple con lo siguiente:

• No es ambigua

• No tiene recursividad por la izquierda

Sobre la recuperación de errores sintácticos Este ejemplo es bastante básico, por lo que no tiene implementado un sistema de recuperación de errores sintácticos, para hacerlo existen muchas estrategias, como las siguientes:

• Recuperación en modo pánico

• Recuperación a nivel de frase

• Producción de errores

• Corrección global

Se recomienda la recuperación en modo pánico por ser la más sencilla de implementar

Fuentes consultadas:

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

En esta publicación se muestra un ejemplo sencillo de la implementación de un analizador léxico a partir de un autómata finito determinista. Este proyecto se desarrolló utilizando Visual Studio 2013. El proyecto completo del ejemplo puede descargarse del siguiente enlace:

Analizador léxico en Visual Basic.

Todo el código dentro del proyecto está documentado con comentarios que contienen explicaciones sobre su funcionamiento.

Funcionamiento del proyecto

Este ejemplo ilustra la implementación de un analizador léxico a partir de un Autómata Finito Determinista (AFD). No se utiliza ningún generador de analizadores léxicos que genere el analizador, ni se realiza el proceso de análisis léxico con ninguna librería. Los errores identificados en el proceso de análisis léxico se muestran en consola, si en el entorno de Visual Studio no aparece la consola, esta pueden abrirse desde el menú ver, en la opción resultados o con Ctrl+Alt+O.

Inicialmente se muestra una expresión aritmética de ejemplo que puede utilizarse como entrada, del lado izquierdo.

Al presionar el botón Realizar Análisis Léxico se ejecuta el análisis de la entrada y del lado derecho se despliega la lista de tokens identificada, en la que se indica el tipo de token y el valor específico que este tiene.

Si existiera algún error léxico en la entrada, por ejemplo, si pusiéramos al final de la expresión una arroba en lugar del uno, entonces se desplegaría en consola un mensaje de error y se mostraría en la lista de tokens todos aquellos tokens válidos.

Autómata Finito Determinista utilizado

En este ejemplo se reconocen los componentes léxicos propios de una expresión aritmética, por ello el ejemplo se realizó a partir del siguiente autómata finito determinista:

El estado inicial del autómata es E_0. En el autómata podemos observar que existen tres estados de aceptación, el primero (EA_1) reconoce todos los componentes léxicos de un carácter y a nivel programación se clasifican los tokens según el carácter que se haya reconocido, el segundo estado de aceptación (EA_2) reconoce los números enteros y el tercero (EA_3) reconoce los números reales, es decir, los números con punto decimal. Se pueden desplegar dos tipos de mensajes de error, ya que se cuentan con dos estados de error, el primero es cuando se reconoce un carácter desconocido estando en el estado 1, el segundo se da cuando estando en el estado 2, correspondiente a los números reales, se esperaban más dígitos después del punto decimal, pero se obtiene un carácter que no es un dígito.

A un lado de algunos estados se coloca un asterisco (*), que indica que debe retrocederse la entrada en una posición, esto se hace porque los tokens se dan como aceptados con el primer carácter del siguiente token, entonces para que no se pierda ese carácter del siguiente token en el análisis debe retrocederse una posición en la entrada, esta notación es la misma que se utiliza en el libro de Aho, Lam, Sethi y Ullman.

El secreto tras la implementación del autómata

El secreto es encontrar la forma de ejecutar en código las acciones que un reconocedor haría basado en el autómata finito determinista, es lógico que la función core del analizador léxico debe estar dentro de un ciclo ya que deben recorrerse los caracteres de izquierda a derecha y agruparse en componentes léxicos. Este ciclo se encuentra en la función escanear de la clase AnalizadorLexico, dentro de dicho ciclo debe haber un select case en el que cada caso representa a uno de los estados del conjunto de estados para cada caso (o estado) hay un if elseif elseif … else que representan el conjunto de transiciones que salen de dicho estado.

Fuentes consultadas:

• Compiladores, principios, técnicas y herramientas. Aho, Lam, Sethi y Ullman. Segunda Edición. Págs. 111, 130 y 131

• Teoría de la computación. Lenguajes formales, autómatas y complejidad. J. Glenn Brookshear. Pág. 24