Analizador léxico en Visual Basic

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