Unidad IV. Análisis Léxico
4.1 Funciones del Analizador Léxico
El analizador léxico es la primera fase de un compilador.
4.2
Componentes léxicos, patrones y lexemas
Al hablar sobre el análisis léxico, utilizamos tres términos distintos, pero relacionados:
4.4 Errores Léxicos
Investigado por: German David Hernandez Gomez
Investigado por: Arilenne Hernández Plascencia
Investigado por: Jonathan Hernández Antonio
Investigado por: Araceli Martinez Martinez
El analizador léxico es la primera fase de un compilador.
Su principal función consiste en leer los caracteres de
entrada y elaborar como salida una secuencia de componentes léxicos que utiliza
el analizador sintáctico para hacer el análisis. Recibida la orden "obtén
el siguiente componente léxico" del analizador sintáctico, el analizador
léxico lee los caracteres de entrada hasta que pueda identificar el siguiente
componente léxico.
También puede realizar ciertas funciones secundarias en la
interfaz del usuario, como eliminar del programa fuente comentarios y espacios
en blanco en forma de caracteres de espacio en blanco, caracteres TAB y de
línea nueva.
Por ejemplo, el analizador léxico puede tener localizado el
número de caracteres de nueva línea detectados, de modo que se pueda asociar un
número de línea con un mensaje de error.En algunos casos, el analizador
léxico puede leer la información relacionada con el tipo de información de la
tabla de símbolos, como ayuda para determinar el token apropiado que debe pasar
al analizador sintáctico.
En la figura 3.1 se sugieren
estas interacciones. Por lo regular, la interacción se implementa haciendo que
el analizador sintáctico llame al analizador léxico. La llamada, sugerida por
el
comando obtener Siguiente Token, hace que el analizador léxico lea los
caracteres de su entrada hasta que pueda identificar el siguiente lexema y
producirlo para el siguiente token, el cual devuelve al analizador sintáctico.
Al hablar sobre el análisis léxico, utilizamos tres términos distintos, pero relacionados:
Un token es un par que consiste
en un nombre de token y un valor de atributo opcional. El nombre del token es
un símbolo abstracto que representa un tipo de unidad léxica; por ejemplo, una
palabra clave específica o una secuencia de caracteres de entrada que denotan
un identificador. Los nombres de los tokens son los símbolos de entrada que
procesa el analizador sintáctico. A partir de este momento, en general escribiremos
el nombre de un token en negrita. Con frecuencia nos referiremos a un token por
su nombre.
Un patrón es una descripción de
la forma que pueden tomar los lexemas de un token. En el caso de una palabra
clave como token, el patrón es sólo la secuencia de caracteres que forman la
palabra clave. Para los identificadores y algunos otros tokens, el patrón es
una estructura más compleja que se relaciona mediante muchas cadenas.
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 ese token.
La siguiente figura proporciona
algunos tokens comunes, sus patrones descritos de manera informal y algunos
lexemas de ejemplo. La siguiente instrucción en C nos servirá para ver cómo se
utilizan estos conceptos en la práctica:
4.3 Creación de Tabla de tokens
Tabla: conjunto de pares
clave-valor, llamados elementos de la tabla. La tabla de símbolos es una
componente necesaria de un compilador. Al declarar un identificador
(normalmente una sola vez), éste es insertado en la tabla. Cada vez que se
utilice el identificador se realizará una búsqueda en la tabla para obtener la
información asociada (el valor).
Búsqueda: dada la clave de un
elemento, encontrar su valor.
Inserción: Dado un par
clave-valor, añadir un elemento nuevo a la tabla.
Cambio de valor: Buscar el
elemento y cambiar su valor.
Borrado: Eliminar un elemento de
la tabla.
Longitud de búsqueda (o tiempo de
acceso)
De una clave: Li = número de
comparaciones con elementos de la tabla para encontrar esa clave. Máxima: LM =
número máximo de comparaciones para encontrar cualquier clave. Media
(esperada): Lm = número medio de comparaciones para encontrar un valor.
Si la frecuencia de todas las claves
es la misma:
Lm = (S Li)/N
Si la frecuencia de todas las
claves no es la misma:
Lm = S pi.Li
Grado de ocupación:
s = n/N donde n=número de
elementos en la tabla y N=capacidad máxima de la tabla.
Función de búsqueda:
B: K→E asocia a cada clave k un
elemento B(k).
Valor asociado a una clave k:
v(B(k)). Puede ser múltiple, en cuyo caso normalmente se convierte en un
puntero. Si está en la tabla puede almacenarse consecutivamente o en subtablas
paralelas. Tablas de símbolos (identificadores) La clave es el identificador.
El valor está formado por:
Atributos del identificador.
Puntero a la posición de memoria asignada. La clave puede sustituirse por un
puntero. Los identificadores pueden estar empaquetados. La longitud del
identificador puede especificarse en la tabla o delante del nombre, o ser
implícita.
Tablas consecutivas: Todos los elementos
ocupan posiciones de memoria adyacentes. Tablas ligadas: cada elemento apunta
al siguiente. Tablas doblemente ligadas: cada elemento apunta al siguiente y al
anterior. Tablas no ordenadas Inserción: en el primer lugar vacío.
Sin la ayuda de
los demás componentes es difícil para un analizador léxico saber que hay un
error en el código fuente. Por ejemplo, si la cadena fi se encuentra por
primera vez en un programa en C en el siguiente contexto:
fi ( a == f(x))
...
un analizador
léxico no puede saber si fi es una palabra clave if mal escrita, o un
identificador de una función no declarada. Como fi es un lexema válido para el
token id, el analizador léxico debe regresar el token id al analizador sintáctico
y dejar que alguna otra fase del compilador (quizá el analizador sintáctico en
este caso) mande un error debido a la transposición de las letras.
Sin embargo,
suponga que surge una situación en la cual el analizador léxico no puede
proceder, ya que ninguno de los patrones para los tokens coincide con algún
prefijo del resto de la entrada. La estrategia de recuperación más simple es la
recuperación en “modo de pánico”.
Eliminamos
caracteres sucesivos del resto de la entrada, hasta que el analizador léxico
pueda encontrar un token bien formado al principio de lo que haya quedado de
entrada. Esta técnica de recuperación puede confundir al analizador sintáctico,
pero en un entorno de computación interactivo, puede ser bastante adecuado.
Otras de las posibles acciones de recuperación de errores son:
1. Eliminar un
carácter del resto de la entrada.
2. Insertar un
carácter faltante en el resto de la entrada.
3. Sustituir un
carácter por otro.
4. Transponer
dos caracteres adyacentes.
Las transformaciones como éstas pueden probarse en un intento por reparar la entrada. La estrategia más sencilla es ver si un prefijo del resto de la entrada puede transformarse en un lexema válido mediante una transformación simple.
Esta estrategia tiene sentido, ya que en la práctica la mayoría de los errores léxicos involucran a un solo carácter. Una estrategia de corrección más general es encontrar el menor número de transformaciones necesarias para convertir el programa fuente en uno que consista sólo de lexemas válidos, pero este método se considera demasiado costoso en la práctica como para que valga la pena realizarlo.
Las transformaciones como éstas pueden probarse en un intento por reparar la entrada. La estrategia más sencilla es ver si un prefijo del resto de la entrada puede transformarse en un lexema válido mediante una transformación simple.
Esta estrategia tiene sentido, ya que en la práctica la mayoría de los errores léxicos involucran a un solo carácter. Una estrategia de corrección más general es encontrar el menor número de transformaciones necesarias para convertir el programa fuente en uno que consista sólo de lexemas válidos, pero este método se considera demasiado costoso en la práctica como para que valga la pena realizarlo.
4.5 Generadores de Analizadores Léxicos
Flex en una
implementación más reciente, que nos permite especificar un analizador léxico
mediante la especificación de expresiones regulares para describir patrones de
los tokens.
La notación de entrada para la herramienta Lex se conoce como el
lenguaje Lex, y la herramienta en sí es el compilador Lex. El compilador Lex
transforma los patrones de entrada en un diagrama de transición y genera
código, en un archivo llamado lex.yy.c, que simula este diagrama de transición.
Uso de Lex
La figura A
sugiere cómo se utiliza Lex. Un archivo de entrada, al que llamaremos lex.l,
está escrito en el lenguaje Lex y describe el analizador léxico que se va a
generar. El compilador Lex transforma a lex.l en un programa en C, en un
archivo que siempre se llama lex.yy.c. El compilador de C compila este archivo
en un archivo llamado a.out, como de costumbre.
Figura A. Creación
de un analizador léxico con Lex
La salida del
compilador de C es un analizador léxico funcional, que puede recibir un flujo
de caracteres de entrada y producir una cadena de tokens. El uso normal del
programa compilado en C, denominado a.out en la figura A, es como una subrutina
del analizador sintáctico. Es una función en C que devuelve un entero, el cual
representa un código para uno de los posibles nombres de cada token.
El valor del
atributo, ya sea otro código numérico, un apuntador a la tabla de símbolos, o
nada, se coloca en una variable global llamada yylval, la cual se comparte entre el analizador léxico
y el analizador sintáctico, con lo cual se simplifica el proceso de devolver
tanto el nombre como un valor de atributo de un token.
Estructura de
los programas en Lex
Un programa en
Lex tiene la siguiente forma:
Declaraciones
%%
Reglas de
traducción
%%
Funciones
auxiliares
La sección de
declaraciones incluye las declaraciones de variables, constantes de manifiesto
(identificadores que se declaran para representar a una constante; por ejemplo,
el nombre de un token) y definiciones regulares.
Cada una de las
reglas de traducción tiene la siguiente forma:
Patrón { Acción }
Cada patrón es
una expresión regular, la cual puede usar las definiciones regulares de la
sección de declaraciones. Las acciones son fragmentos de código, por lo
general, escritos en C, aunque se han creado muchas variantes de Lex que
utilizan otros lenguajes.
La tercera
sección contiene las funciones adicionales que se utilizan en las acciones. De
manera alternativa, estas funciones pueden compilarse por separado y cargarse
con el analizador léxico. El analizador léxico que crea Lex trabaja en conjunto
con el analizador sintáctico de la siguiente manera.
Cuando el
analizador sintáctico llama al analizador léxico, éste empieza a leer el resto
de su entrada, un carácter a la vez, hasta que encuentra el prefijo más largo
de la entrada que coincide con uno de los patrones Pi. Después
ejecuta la acción asociada Ai. Por lo general, Ai
regresará al analizador sintáctico, pero si no lo hace (tal vez debido a que Pi
describe espacio en blanco o comentarios), entonces el analizador léxico
procede a buscar lexemas adicionales, hasta que una de las acciones
correspondientes provoque un retorno al analizador sintáctico.
El analizador
léxico devuelve un solo valor, el nombre del token, al analizador sintáctico,
pero utiliza la variable entera compartida yylval para pasarle información
adicional sobre el lexema encontrado, si es necesario.
Investigado por: Carlos Martínez Valentin
Resolución de
conflictos en Lex
Nos hemos
referido a las dos reglas que utiliza Lex para decidir acerca del lexema
apropiado a seleccionar, cuando varios prefijos de la entrada coinciden con uno
o más patrones:
1. Preferir
siempre un prefijo más largo a uno más corto.
2. Si el prefijo
más largo posible coincide con dos o más patrones, preferir el patrón que se
lista primero en el programa en Lex
La primera regla
nos dice que debemos continuar leyendo letras y dígitos para buscar el prefijo
más largo de estos caracteres y agruparlos como un identificador. También nos
dice que debemos tratar a <= como un solo lexema, en vez de seleccionar <
como un lexema y = como el siguiente lexema.
La segunda regla
hace a las palabras clave reservadas, si listamos las palabras clave antes que
id en el programa.
El operador
adelantado
Lex lee de
manera automática un carácter adelante del último carácter que forma el lexema
seleccionado, y después regresa la entrada para que sólo se consuma el propio
lexema de la entrada.
No obstante,
algunas veces puede ser conveniente que cierto patrón coincida con la entrada,
sólo cuando vaya seguido de ciertos caracteres más.
De ser así, tal vez podamos
utilizar la barra diagonal en un patrón para indicar el final de la parte del
patrón que coincide con el lexema. Lo que va después de / es un patrón
adicional que se debe relacionar antes de poder decidir que vimos el token en
cuestión, pero que lo que coincide con este segundo patrón no forma parte del
lexema.
Bibliografía
· AHO, ALFRED V., (2008), COMPILADORES.
PRINCIPIOS, TÉCNICAS Y HERRAMIENTAS., PEARS ON EDUCACIÓN, México.
Investigado por: German David Hernandez Gomez
Investigado por: Arilenne Hernández Plascencia
Investigado por: Jonathan Hernández Antonio
Investigado por: Araceli Martinez Martinez
Comentarios
Publicar un comentario