Unidad 5: Análisis léxico.
Un analizador léxico o analizador lexicográfico (en inglés scanner) es la primera fase de un compilador consistente en un programa que recibe como entrada el código fuente de otro programa (secuencia de caracteres) y produce una salida compuesta de tokens (componentes léxicos) o símbolos.
5.1 Funciones del analizador léxico.
El analizador léxico opera bajo petición del analizador
sintáctico devolviendo un componente léxico conforme el analizador sintáctico
lo va necesitando para avanzar en la gramática. Los componentes léxicos son los
símbolos terminales de la gramática.
Suele implementarse como una subrutina del analizador
sintáctico. Cuando recibe la orden obtén el siguiente componente léxico, el
analizador léxico lee los caracteres de entrada hasta identificar el siguiente
componente léxico.
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 estos 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
porque 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).
El compilador tiene que:
- Un error que produce un token erróneo
- 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.
Las etiquetas pueden guardarse mediante dispersión para producir un sistema de
firmas que acelere sus búsquedas
Como las tablas de transiciones son muy escasas, se pueden guardar en una lista
corta que se consulte cada vez que se necesite hacer una transición a partir de
un estado
Estas listas no suelen tener más de tres o cuatro elementos, así que su
búsqueda será razonablemente rápida
Símbolos terminales de una gramátic
Identificadores, palabras reservadas, operadores,...
Varios signos pueden forman el mismo token
Atributos:
Información adicional que tiene el token, de utilidad para
el análisis sintáctico y semántico.
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.
Descripción de la forma que han de tomarlos lexemas para
ajustarse a un componente léxico.
5.2 Componentes léxicos, patrones y lexemas.
Componente léxico (token).
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:
Representan cadenas de caracteres en el programa fuente que se pueden tratar
juntos como una unidad léxica. Un lexema es una secuencia de caracteres en el
programa fuente con la que concuerda el patrón para un componente léxico. 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. Atributos de los
componentes léxicos: El analizador léxico recoge información sobre los
componentes léxicos en sus atributos asociados. Los componentes léxicos influyen
en las decisiones del análisis sintáctico y los atributos en la traducción de
los componentes léxicos:
- operadores aritméticos
- operadores
- relacionales
- operadores lógicos
- operador de asignación
- identificadores
- constantes
- cadenas
- literales
- signos de puntuación
- librerías
Lexema:
Apuntador a la entrada de la Tabla de símbolos donde se
guarda la información sobre el componente léxico.
El lexema para un identificador
El número de línea en que se encontró por primera vez.
5.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).
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.
5.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.
Reportar clara y exactamente la presencia de errores
Recuperarse de cada error lo suficientemente rápido para
poder detectar errores subsiguientes:
Tratar de evitar mensajes
falsos de error
5.5 Generadores de analizadores Léxicos
Se pueden usar varias técnicas para acelerar el algoritmo y
ahorrar espacio
Comentarios
Publicar un comentario