Compiladores: Analizador Léxico
INTRODUCCION AL ANALIZADOR LÉXICO
La tarea de crear nuestro compilador requerirá de varias cosas: un analizador léxico (que se encargara de identificar las palabras), un analizador sintáctico (que se encargara de las frases) y un analizador semántico (que mirara el sentido de la frase).
El analizador léxico se compone de expresiones regulares, los simbolos que se ignoraran (espacios en blanco, comentarios...) asi como los que acepta (identificadores, numeros...) seguiran las mismas propiedades, y tendran los mismos problemas, como que por ejemplo, no se permite el anidamiento.
OBJETIVO DEL ANALIZADOR LÉXICO
A grandes rasgos identificar que las palabras no tienen simbolos extraños y eliminar aquellas cosas que no nos interesen.
El analizador léxico (AL) lee los caracteres de entrada y elabora una secuencia de tokens (que son las unidades de control y serían los nodos hoja de la ER) de la gramática.
Como lee directamente del texto fuente, hace otras funciones como eliminar comentarios, el exceso de espacios...
Guarda informacion de algunos componentes léxicos en forma de atributos.
Suponiendo la siguiente ER, que validaria el siguiente lenguaje 'x = 23' :
E: E = E | id | num
Podriamos decir que cuando lee x el token sería [id,'1'], cuando lee 23 el token sería [num,'2'] el segundo atributo puede ser dos cosas dependiendo de la implementacion, o bien es una posicion en una tabla de simbolos donde 1 podría ser 'x' y la posicion 2 '23' o directamente aquello que simbolicen.
A la hora de detectar errores, lo mas efectivo es detectarlos, recuperarse del error (ignorando por ejemplo todos los simbolos no existentes y quedandonos con lo importante) y pasar a los siguientes a fin de detectar mas de un error por compilación. Esto se conoce como el módo pánico.
Generalmente relaciona mensajes de error del compilador con el programa fuente, pero no puede detectar muchos errores pues solo ve una palabra particular en un momento concreto, a diferencia del sintáctico que podría ver toda una frase o el semántico.
EXPRESIONES REGULARES Y AUTÓMATAS
A partir de un alfabeto V con las operaciones de union, concatenacion y cierre se cumple:
El simbolo ø es una ER que describe el lenguaje L(ø) = ø.
El simbolo λ es una ER que describe el lenguaje L(λ) = {λ}.
Cualquier simbolo que pertenece al alfabeto es una ER L(a) = {a}
Si R1 y R2 son ER entonces R1|R2 tambien, que describe L(R1|R2) = L(R1)∪L(R2).
Si R1 y R2 sn ER entonces R1·R2 tambien, que describe L(R1·R2) = L(R1)·L(R2)
Si R1 es una ER entonces R1* tambien, que describe L(R*) = L(R)*
Asi mismo, un automata es una quintupla formado por:
Conjunto finito de estados.
Un alfabeto.
Una funcion de transición.
Un estado inicial.
Un conjunto de estados finales.
DISEÑO DE UN ANALIZADOR LÉXICO
Aunque usaremos FLEX para crear un módulo que identifique el léxico, las siguientes tareas han de realizarse, de una forma u otra en un analizador lexico.
Especificacion y reconocimiento de componentes léxicos: Identificando los tokens del lenguaje utilizando ER. Habrá que describir los lexemas que reconoceremos como tokens y los lexemas que ignoraremos.
Tendremos que establecer las cadenas del lenguaje formal con signifificado propio (palabras clave, operadores, signos de puntuación, identificadores, constantes...) para reconocerlas mediante automatas finítos. Cuanto mas sencillos e independientes mejor.
Generalmente, para reconocerlos se suelen llevar dos apuntadores de la frase, el primero para el inicio y el segundo para los caracteres de anticipacion (seguimos avanzando el segundo apuntador hasta que lleguemos a un simbolo que no puede formar parte del anterior) devolvemos dicho simbolo no valido a la entrada y todo lo anterior es un token y dicho token puede ser:
Palabras clave no reservadas: El AL las trata como un identificador y será el sintáctico quien las identifique.
Palabras clave reservadas: Se han de reconocer o mediant euna tabla o un automata.
Comentarios: Reconocidos y eliminarse.
Blancos: Eliminarlos y si no delimitan, agrupar los lexemas.
Token EOF: Para saber cuando se ha terminado es interesante solo para el sintáctico.
Construccion del automata finito que reconozca las ER: O bien pasamos de ER a AFND y luego de AFND a AFD o convertimos la ER directamente a AFD. Una vez tengamos un AFD podemos minimizarlo o simularlo asi como compactar las tablas que tengamos.
Implementacion del automata infinito: Podriamos hacerlo a traves de una tabla de Karnaugh, el diagrama de transicion pero nosotros la haremos con la herramienta FLEX.
Diseño de la interfaz entre la entrada y el AL: Como leeremos desde un fichero, es bastante mas eficiente leer lineas y bloques, como dijimos anteriormente, lo normal serían dos apuntadores pero se puede mejorar con un buffer dividido en dos mitades o con el uso de centinelas pero nos es indiferente.
Manejo de Errores: Han de detectarse los errores e informarse (y si se recupera para detectar otros errores, mejor) con el modo pánico se ignorn los caracteres extraños hasta encontrar un caracter válido para otro nuevo token. No obstante, a veces la recuperación genera mas fallos, lo cual sigue siendonos indiferentes, si detecta mas de uno es mucho mejor.
Al final tendriamos un gran automata que reconoce simbolos en base a los identificadores, las constantes, los numeros, los simbolos especiales y cualquier otro caracter lleva a un estado no final. Las palabras clave no suelen ponerse como estados en el propio autómata.
El código generado empezaría analizando y preguntando si el caracter es diferente del final de fichero, mientras que lo sea, si es un espacio no se hace nada, si encontramos un caracter (letra minuscula, _ ó $ hasta que no encontremos un simbolo que no sea válido lo guardamos en el buffer y al final devolvemos el ultimo caracter no valido a la entrada) si es un digito es un numero y si es un simbolo especial solo tomaremos ese caracter y devolveremos el numero.
EJEMPLO
Supongamos que hemos de analizar la siguiente funcion, ¿como sería el análisis léxico de "float limitedSquare(float x) { return (x<=-10.0 || x>=10.0) ? 100:x*x; }".
Supondremos las palabras reservadas float, ap (abrir parentesis), cp (cerrar parentesis), al (abrir llaves), cl (cerrar llaves). Y operadores como menor, menori (menorigual), mayor, mayori (mayorigual), interr (interrogacion)-
[FLOAT,][ID,1][FLOAT,][AP,][FLOAT,][ID,2][CP,][AL,][RETURN,][AP,][ID,2][MENORI,][MENOS,][CONSTFLOT,3][OR,][ID,2][MAYORI,][CONSTFLOT,3][CP,][INTERR,][CONSTENT,4][DP,][ID,2][POR,][ID,2][PC,][CL,]
Donde las palabras reservadas 'float', 'return' no tienen un numero porque son reservadas ni cosas como 'menorigual' lo tienen porque no varía. Eso si, en una tabla de lexemas tendriamos:
limitedSquare
x
10.0
100
REDUCCION DE TABLAS DE KARNAUGH
A veces tenemos un automata con muchos estados vacios, asi que existe una forma mas sencilla de reducir la tabla (en los ejercicios a mano no tiene mucho sentido pues son manejables, pero suponiendo automatas con miles de estados es bastante adecuado).
El truco consiste en tener una tabla de todos los valores que parten desde todos los estados (tabla de elementos no nulos) y otra (compacta) que diga desde un estado, tomando el elemento numero x hay y transciones.
Si quisieramos saber a que estado vamos con [q0,b] iriamos a la tabla compacta, veriamos que empieza en el numero 1 y tiene 2 transiciones, asi que nos vamos a la tabla de elementos no nulos, miramos la primera, es con a. Pasamos a la siguiente, y vemos que es una transicion con b al estado q2. Conclusion [q0,b] -> [q2].
EJERCICIO 1: Definir una expresión en letras minusculas que reconozca con todos los id salvo aquellos que tengan las letras if:
L=a|b|c|..|z LsinI= a|b|...|h|j|...|z LsinJ= a|b|...|i|j|...|z
i | LsinI·L* | LsinI·LsinF·L* | i·f·L+ | L·LsinF·L*
EJERCICIO2: Definir una expresion regular que con letras, numeros y guion bajo forme los identificadores que, empiezan por letra, numero o guion bajo pero no pueden haber dos guiones bajos o un guion bajo al final
L=a|b|...|z|A|...|Z D=0|1|...|9 LD = LUD
L(_LD+)*