UNIDAD 4

4. Analizador lexico

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.

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.

Definiciones.

Tokens:

• Símbolos terminales de una gramática

o    Identificadores, palabras reservadas, operadores,...

o    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.

Patrón:

Descripción de la forma que han de tomarlos lexemas para ajustarse a un componente léxico.

Ejemplo:

Otras Funciones:

• Manejo del fichero de entrada del programa fuente: abrirlo, leer sus caracteres, cerrarlo y gestionar posibles errores de lectura.
• Eliminar comentarios, espacios en blanco, tabuladores y saltos de línea (caracteres no validos para formar un token).
• Inclusión de ficheros: # include...
• La expansión de macros y funciones in line: # define...
• Contabilizar el número de líneas y columnas para emitir mensajes de error.
• Reconocimiento y ejecución de las directivas de compilación (por ejemplo, para depurar u optimizar el código fuente).

Aspectos del Análisis Léxico.

Diseño más sencillo:

• Los símbolos que trata el scanner se describe con una gramática más simple que la del parser, gramática regular

Mejora la eficiencia:

• Gran parte del tiempo de compilación se consume en la lectura y exploración de caracteres

Mejora la portabilidad:

• Se pueden tener varias versiones del scanner una para distintos códigos (EBCDID, ASCII, ...), con el mismo parser

Descarga el análisis sintáctico:

Ejemplo; no puedo distinguir en FORTRAN hasta después del 1

o    DO 5 I=1.25

o    DO 5 I=1,25

4.2 Componentes léxicos, patrones y  lexemas.

• 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 sin tá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, e l 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.

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.

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 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). ¡¡Los programas no siempre son correctos!!

El compilador tiene que:

1.        Reportar clara y exactamente la presencia de errores

2.        Recuperarse de cada error lo suficientemente rápido para poder detectar errores subsiguientes:

                Tratar de evitar mensajes falsos de error
         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.

4.5 Generadores de analizadores Léxicos.

Se pueden usar varias técnicas para acelerar el algoritmo y ahorrar espacio
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

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.