UNIDAD 4
4.1 Funciones del analizador léxico.
Un analizador léxico aísla
el analizador sintáctico de la representación de lexemas de los componentes
léxicos.
Funciones:
1- Eliminación de espacios
en blanco
2-reconocimiento de
identificadores y palabras claves
3- Analizador léxico
”scanner” lee la secuencia de los caracteres del programa fuente, y los agrupa
para formar unidades con significado propio.
El analizador léxico es la
primera fase de un compilador.
Esta interacción, suele
aplicarse convirtiendo al analizador léxico en una subrutina o corrutina del
analizador sintáctico. 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.
Funciones secundarias.
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. Otra función es relacionar los mensajes de
error del compilador con el programa fuente. 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 compiladores, el
analizador léxico se encarga de hacer una copia del programa fuente en el que
están marcados los mensajes de error. Si el lenguaje fuente es la base de
algunas funciones de pre procesamiento de macros, entonces esas funciones del
preprocesador también se pueden aplicar al hacer el análisis léxico.
Maigualida Pérez Melgarejo.
Bibliografía:
Louden, K.C. (1997),
Compiler Construction: Principles and Practice, Tema 2, p´aginas: 31-93.
4.2 Componentes léxicos
patrones y lexemas
· Léxico:
Son las unidades lógicas que genera el analizador léxico. Formar
caracteres en tokens es muy parecido a formar palabras en un
lenguaje natural.
Es el conjunto de cadenas de entrada que produce como salida el mismo
componente léxico. Cada token es una secuencia de
caracteres que representa una unidad de información en el programa fuente.
Los componentes léxicos más comunes son los siguientes:
Ø palabras clave o reservadas
Ø palabras clave o reservadas
Ø Operadores aritméticos
Ø Operadores relacionales
Ø Operadores lógicos
Ø Operador de asignación
Ø Identificadores
Ø Constantes
Ø Cadenas
Ø Literales
Ø Signos de puntuación
Ø Librerías
Patrón:
Regla que describe el conjunto de lexemas que pueden
representar a un determinado componente léxico en los programas fuente.
En otras palabras, es la descripción del componente léxico mediante una
regla.
· Lexema:
Edgarda Santiago Reyes
Bibliografia:
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.
Componentes léxicos (tokens): unidad mínima de
información que significa algo a la hora de compilar; concepto de palabra; las
fases de un lenguaje constan de cadenas de componentes léxicos.
Lexema: Una secuencia de caracteres
de entrada que comprenden un solo componente léxico se llama lexema; cadena de
caracteres que extrae el componente abstracto del componente léxico.
Patrón: Descripción de la forma que
han de tomarlos lexemas para ajustarse a un componente léxico.
Ejemplo.
4.4 Errores léxicos
El análisis léxico constituye la
primera fase, aquí se lee el programa fuente de izquierda a derecha y se agrupa
en componentes léxicos (tokens), que son secuencias de caracteres que tienen un
significado. Además, todos los espacios en blanco, líneas en blanco,
comentarios y demás información innecesaria se elimina del programa fuente.
También se comprueba que los símbolos del lenguaje (palabras
clave, operadores,...) se han escrito correctamente.
Como la tarea que realiza el analizador léxico es un caso especial de coincidencia de patrones, se necesitan los métodos de especificación y reconocimiento de patrones, y éstos métodos son principalmente las expresiones regulares y los autómatas finitos. Sin embargo, un analizador léxico también es la parte del traductor que maneja la entrada del código fuente, y puesto que esta entrada a menudo involucra un importante gasto de tiempo, el analizador léxico debe funcionar de manera tan eficiente como sea posible.
Son pocos los errores simplemente en el nivel léxico ya que tiene una visión muy restringida de un programa fuente. El analizador léxico debe devolver el componente léxico de un identificador y dejar a otra fase se ocupe de los errores.
Suponga que una situación en la cual el analizador léxico no puede continuar por que ninguno de los patrones concuerda con un prefijo de la entrada. Tal vez la estrategia de recuperación más sencilla sea recuperación “EN MODO PANICO” (este método de recuperación es donde se borra caracteres sucesivos de la entrada hasta que el analizador léxico pueda encontrar un componente léxico bien formado). ¡¡Los programas no siempre son correctos!!
El compilador tiene que:
- Reportar clara y exactamente la presencia de errores
- Recuperarse de cada error lo suficientemete rápido para poder
detectar errores subsiguientes:
- Tratar de evitar mensajes falsos de error
- Un error que produce un token erroneo
- Errores léxicos posibles
Un token o componente léxico es una cadena de caracteres que tiene un significado coherente en cierto lenguaje de programación. Ejemplos de tokens, podrían ser palabras clave (if, while, int), identificadores, números, signos, o un operador de varios caracteres. Son los elementos más básicos sobre los cuales se desarrolla toda traducción de un programa, surgen en la primera fase, llamada análisis léxico.
Rodolfo Rodríguez Medina
Bibliografía.
4.5.-Generadores de analizadores Léxicos.
Un analizador léxico es un modo destinado a leer caracteres del archivo
de entrada, donde se encuentra la cadena a analizar, reconocer subcadenas que
correspondan a símbolos del lenguaje y retornar los tokens correspondientes y
sus atributos.
o Generador LEX:
Es un programa para generar analizadores léxicos, se utiliza comúnmente
con el programa yacc que se utiliza para generar análisis sintáctico, escrito
originalmente por Eric Schmidt y Mike Lesk, es el analizador léxico estándar de
POSIX. Lex toma como entrada una especificación de analizador léxico y devuelve
como salida el código fuente implementando el analizador léxico en C.
Esquema general: un programa fuente de LEX tiene el siguiente aspecto.
De estas tres secciones, solo la
segunda es obligatoria, y cualquiera de ellas pueden estar vacia.
o Generador FLEX
Es una herramienta para la generación
de programas que realizan corcondancia de patrones en texto, es una herramienta
para generar escanes. FLEX lee los archivos de entrada dados, o la entrada
estándar si no se ha indicado ningún nombre de archivo, con la descripción de
un escáner a generar. La descripción se encuentra en forma de parejas de
expresiones regulares y código C, denominadas reglas.
o Generador JTLexx
Permite expresar conjuntamente sintaxis
y semántica al estilo de los esquemas de traducción. A su vez el proceso
de conjunto de atributos es implementado por JTLex por un autómata finito
traductor con las ventajas de eficiencia que esto supone. Una especificación
JTLex permite no solo asociar procedimiento, o acción a cada expresión regular,
sino también a cada ocurrencia de un símbolo dentro de la expresión.
Esquema de funcionamiento:
Gramática:
Blanca
Estela Reyes Castillo
Bibliografia.
https://prezi.com/mghu3fnrdwd7/generador-de-analizadores-lexicos/
4.6 Aplicaciones (caso de estudio)
Además de para
construir compiladores e intérpretes, los analizadores léxicos se pueden
emplear para muchos programas \convencionales”. Los ejemplos más claros son
aquellos programas que tienen algún tipo de entrada de texto donde hay un
formato razonablemente libre en cuantos espacios y comentarios. En estos casos
es bastante engorroso controlar donde empieza y termina cada componente y es
fácil liarse con los punteros a char. Un analizador léxico simplifica
notablemente la interfaz y si se dispone de un generador automático, el
problema se resuelve en pocas líneas de código.
Edgarda Santiago Reyes
Bibliografia:
