2.7. Herramientas para la Especificación de Analizadores Léxicos

Se han desarrollado algunas herramientas para construir analizadores léxicos a partir de notaciones de propósito especial basadas en expresiones regulares. Ya se ha estudiado el uso de expresiones regulares en la especificación de patrones de componentes léxicos. Antes de considerar los algoritmos para compilar expresiones regulares en programas de concordancia de patrones, se da un ejemplo de una herramienta que pueda ser utilizada por dicho algoritmo.

En esta sección se describe una herramienta concreta, llamada LEX, muy utilizada en la especificación de analizadores léxicos para varios lenguajes. Esa herramienta se denomina compilador LEX, y la especificación de su entrada, lenguaje LEX. El estudio de una herramienta existente permitirá mostrar cómo., utilizando expresiones regulares, se puede combinar la especificación de patrones con acciones, por ejemplo, haciendo entradas en una tabla de símbolos, cuya ejecución se pueda pedir a un analizador léxico. Se pueden utilizar las especificaciones tipo LEX aunque no se disponga de un compilador LEX.

Figura 1.Creación de analizador léxico con LEX

Por lo general, se utiliza el LEX de la forma representada en la figura. Primero, se prepara una especificación del analizador léxico creando un programa lex.l en lenguaje LEX. Después lex . l se pasa por el compilador LEX para producir el programa en C lex.yy.c. El programa lex.yy.c consta de una representación tabular de un diagrama de transiciones construido a partir de las expresiones regulares de lex.l. junto con una rutina estándar que utiliza la tabla para reconocer lexemas. Las acciones asociadas a las expresiones regulares de lex son partes de código en C y se transfieren directamente a lex.yy.c. Por último, lex.yy.e se ejecuta en el compilador de C para producir un programa objeto a. out. Que es el analizador léxico que transforma un archivo de entrada en una secuencia de componentes léxicos.

Especificaciones  en LEX

Un programa en LEX consta de tres partes:

Declaraciones

%%

Reglas de traducción

%%

Funciones auxiliares

La sección de declaraciones incluye declaraciones de variables, constantes manifiestas y definiciones regulares. (Una constante manifiesta es un identificador que se declara para representar una constante)

Las definiciones regulares se utilizan como componentes de las expresiones regulares que aparecen en las reglas de traducción.

Las reglas de traducción de un programa en LEX son proposiciones de la forma

P₁    {acción₁}

P₂   {acción₂}

…            …

P_n   {acción_n} 

donde p_i es una expresión regular y cada acción es un fragmento de programa que describe cuál ha de ser la acción del analizador léxico cuando el patrón p₁ concuerda con un lexema. En LEX, las acciones se escriben en C, en general, sin embargo, pueden estar en cualquier lenguaje de implantación.

La tercera sección contiene todos los procedimientos auxiliares que puedan necesitar las acciones. A veces, estos procedimientos se pueden compilar por separado y cargar con el analizador léxico.

Un analizador léxico creado por LEX se comporta en sincronía con un analizador sintáctico como sigue. Cuando es activado por el analizador sintáctico, el analizador léxico comienza a leer su entrada restante, un carácter a La vez, hasta que encuentre el mayor prefijo de la entrada que concuerde con una de las expresiones regulares p₁. Entonces, ejecuta la acción₁, Generalmente, acción₁ devolverá el control al analizador sintáctico. Sin embargo, si no lo hace, el analizador léxico se dispone a encontrar más lexemas, basta que una acción hace que el control regrese al analizador sintáctico. La búsqueda repetida de lexemas hasta encontrar una instrucción return explícita permite al analizador léxico procesar espacios en blanco y comentarios de manera apropiada.

El analizador léxico devuelve una única cantidad, el componente léxico, al analizador sintáctico. Para pasar un valor de atributo con la información del lexema, se puede asignar una variable global llamada yylval.

Los analizadores léxicos, para ciertas construcciones de lenguajes de programación, necesitan ver adelantadamente más allá del final de un lexema antes de que puedan determinar un token con certeza. En Lex, se puede escribir un patrón de la forma r1/r2, donde r1 y r2 son expresiones regulares, que significa que una cadena se corresponde con r1, pero sólo si está seguida por una cadena que se corresponde con r2. La expresión regular r2, después del operador lookahead "/", indica el contexto derecho para una correspondencia; se usa únicamente para restringir una correspondencia, no para ser parte de la correspondencia.

Recuperación de errores lexicográficos: Los programas pueden contener diversos tipos de errores, que pueden ser:

•             Errores lexicográficos: Que veremos a continuación.

•             Errores sintácticos: Por ejemplo, una expresión aritmética con mayor numero de paréntesis de apertura que de cierre.

•             Errores semánticos: Por ejemplo, la aplicación de un operador a un tipo de datos incompatible con el mismo.

•             Errores lógicos: Por ejemplo, un bucle sin final.

Cuando se detecta un error, un compilador puede detenerse en ese punto e informar al usuario, o bien desechar una serie de caracteres del texto fuente y continuar con el análisis, dando al final una lista completa de todos los errores detectados. En ciertas ocasiones es incluso posible que el compilador corrija el error, haciendo una interpretación coherente de los caracteres leídos. En estos casos, el compilador emite una advertencia, indicando la suposición que ha tomado, y continúa el proceso sin afectar a las sucesivas fases de compilación.

Los errores lexicográficos se producen cuando el analizador no es capaz de generar un token tras leer una determinada secuencia de caracteres. En general, puede decirse que los errores lexicográficos son a los lenguajes de programación lo que las faltas de ortografía a los lenguajes naturales. Las siguientes situaciones producen con frecuencia la aparición de errores lexicográficos:

1.            Lectura de un carácter que no pertenece al vocabulario terminal previsto para el autómata. Lo más normal en este caso es que el autómata ignore estos caracteres extraños y continué el proceso normalmente. Por ejemplo, pueden dar error en la fase de análisis lexicográfico la inclusión de caracteres de control de la impresora en el programa fuente para facilitar su listado.

2.            Omisión de un carácter. Por ejemplo, si se ha escrito ELS en lugar de ELSE.

3.            Se ha introducido un nuevo carácter. Por ejemplo, si escribimos ELSSE en lugar de ELSE.

4.            Han sido permutados dos caracteres en el token analizado. Por ejemplo, si escribiéramos ESLE en lugar de ELSE.

5.            Un carácter ha sido cambiado. Por ejemplo, si se escribiera ELZE en vez de ELSE.

Las técnicas de recuperación de errores lexicográficos se basan, en general, en la obtención de los distintos sinónimos de una determinada cadena que hemos detectado como errónea. Por otra parte, el analizador sintáctico es capaz en muchos casos de avisar al analizador lexicográfico de cuál es el token que espera que éste lea.

Para el ejemplo de borrado de un carácter, tenemos que los sinónimos de ELSE son ELS, ELE, ESE, y LSE. Por tanto, si incluimos en nuestro analizador una rutina de recuperación de errores debidos a omisión de caracteres, cualquiera de estos sinónimos sería aceptado en lugar del lexema ELSE, se emitiría la correspondiente advertencia, y el proceso continuaría asumiendo que se ha leído el token <pal_res_ELSE>.

Análogamente, podemos incluir rutinas para los demás casos. Por ejemplo, si el analizador lee el lexema ESLE, y no puede construir un token correcto para él mismo, procedería a generar los sinónimos por intercambio de caracteres (es decir, SELE, ELSE o ESEL) y comprobaría si alguno de ellos es reconocible. En caso afirmativo, genera el token correspondiente y advierte al usuario del posible error y de su interpretación automática, continuando con el proceso.

Todos los procedimientos para la recuperación de errores lexicográficos son en la práctica métodos específicos, y muy dependientes del lenguaje que se pretende compilar.