Please enable JavaScript.
Coggle requires JavaScript to display documents.
Analizador léxico image, image, image, image, image, image,…
Analizador léxico
2.2 Alfabetos y lenguajes
Un alfabeto Σ
Es un conjunto finito de símbolos.
Pueden ser:
Caracteres, como al especificar el analizador léxico.
Letras o palabras, si queremos trabajar con lenguaje natural.
Categorías léxicas, al especificar el analizador sintáctico.
Direcciones en el plano, al hacer OCR, etc.
Una cadena
Es una secuencia finita de símbolos del alfabeto.
En especificación del el analizador léxico, podemos ver la entrada como una cadena.
En lenguaje natural, la cadena puede ser una pregunta a una base de datos.
Para el analizador sintáctico, una cadena es el programa una vez pasado por el analizador léxico.
En OCR, una cadena es la descripción de una letra manuscrita, etc.
La cadena de longitud cero
Se denomina cadena vacía y se denota con λ.
Para referirnos al conjunto de cadenas de longitud k, utilizamos Σk.
Para referimos al conjunto de todas las cadenas que se pueden escribir con símbolos del alfabeto, usamos Σ∗.
Un lenguaje formal
Es un subconjunto de Σ∗. Puede ser finito o infinito.
Simplemente un conjunto de cadenas.
Nos enfrentaremos a dos problemas: especificarlo y reconocerlo.
3. Categorías léxicas
3.1 Conceptos básicos
Categoría léxica
Es un tipo de símbolo elemental
del lenguaje de programación.
Por ejemplo: identificadores, palabras clave, números enteros, etc.
Componentes léxicos
Son los elementos de las categorías léxicas.
El analizador léxico ir ́a leyendo de la entrada y dividiéndola en componentes léxicos.
En fases posteriores del análisis necesitan información adicional a la categoría a la que pertenece.
Utilizamos los atributos de los componentes para guardar esta información.
Lexema
Secuencia concreta de caracteres que corresponde a un componente léxico.
3.2. Categorías léxicas más usuales
Palabras clave
Son palabras con un significado concreto en el lenguaje. Ejemplos en C son while, if, return.
Si no son reservadas, el analizador léxico necesitara información del sintáctico para resolver la ambigüedad.
Cada palabra clave corresponde a una categoría léxica.
Identificadores
Nombres de variables, de función, de tipos definidos por el
usuario, etc. Ejemplos en C son i, x10, valor leído.
Operadores
Símbolos que especifican operaciones aritméticas, lógicas, de cadena, etc. Ejemplos en C son +, *, /, %, ==, !=, &&. ...
Constantes numéricas
Literales que especifican valores numéricos enteros, en coma flotante, etc. Ejemplos en C son 928, 0xF6A5, 83.3E+2. . .
Constantes de carácter o de cadena
Literales que especifican caracteres o cadenas de caracteres. Ejemplo en C es "una cadena", son ’x’, ’\0’. . .
Símbolos especiales
Separadores, delimitadores, terminadores, etc.
Ejemplos en C son {, }, ;. . . Suelen pertenecer cada uno a una categoría léxica separada.
Categorías léxicas especiales:
Comentarios
Información destinada al lector del programa. El analizador léxico los elimina.
Blancos
Los espacios en blanco, tabuladores y saltos de línea solo sirven para separar componentes léxicos, el analizador léxico se limita a suprimirlos.
Fin de entrada
Una categoría ficticia emitida por el analizador léxico para indicar que no queda ningún componente pendiente en la entrada.
4. Especificación de las categorías léxicas
El conjunto de lexemas que forman los componentes léxicos que podemos clasificar en una categoría léxica se expresa mediante un patrón.
4.1. Expresiones regulares
Concatenación de dos lenguajes L y M
Es el conjunto de cadenas que se forman al tomar una del primero, otra del segundo y concatenarlas.
Clausura de un lenguaje L
Representada como L* y es el conjunto de las cadenas que se pueden obtener mediante la concatenación de un número arbitrario de cadenas de L.
4.2. Expresiones regulares básicas
Dada una expresión regular r, utilizaremos L(r) para referirnos al lenguaje que representa.
Su utilidad es cuando se combinan entre si. Disponemos de operadores de clausura, unión y concatenación.
Podemos simplificar la escritura de expresiones regulares si establecemos prioridades y asociatividades.
Disyunción y concatenación son asociativas por la izquierda.
4.3. Expresiones regulares extendidas
Agrupaciones de caracteres
Nos permite escribir agrupaciones de caracteres de manera cómoda.
Si queremos representar la elección de uno entre varios caracteres, basta con encerrarlos entre corchetes.
Los operadores aritméticos son [-+*/].
El punto (.) representa cualquier carácter, incluyendo el fin de línea.
Nuevos operadores
Clausura positiva
Se representa por el signo mas e indica una o mas repeticiones de la expresión regular a la que afecta.
Representado por un interrogante, representa la aparición opcional de la expresión a la que afecta.
Carácter de escape
En nuestro caso la barra .
Para representar la propia barra utilizaremos \.
Nombres
La ́única restricción es que no deben provocar ninguna recursividad, ni directa ni indirectamente.
5. Autómatas de estados finitos
Son maquinas formales que consisten en un conjunto de estados y una serie de transiciones entre ellos.
5.1. Autómatas finitos deterministas
Es una quíntupla (Q, Σ, E, q0, F)
Camino
Es una secuencia p1, s1, p2, s2, . . . , sn−1, pn.
Se pueden representar gráficamente.
Con un grafo, cada estado es representado por un nodo y cada arco se representa por un arco en el grafo. Los estados finales se marcan mediante un doble círculo y el estado inicial mediante una flecha.
Reconocimiento con AFDs
Se necesita llevar la cuenta del estado en que estamos y ver como podemos movernos
5.2 Construcción de un AFD a partir de una expresión regular
La idea básica es llevar en cada estado del autómata la cuenta de en que parte de la expresión “estamos”.
El punto indicara que parte de la expresión corresponde con la entrada leída hasta alcanzar el estado en el que esta el ítem.
Formalización
A partir de un conjunto de ítems, encontrar los ítems básicos que constituirán el estado del autómata.
El estado inicial será la clausura del ítem formado anteponiendo el punto a la expresión regular.
5.3. Compromisos entre espacio y tiempo
Construcción de un autómata no determinista
Es mas sencilla, proporciona autómatas de menor numero de estados que los deterministas. El análisis es mas costoso.
Backtracking
Va probando a ver que partes de la expresión se corresponden con la entrada y se vuelve atrás si es necesario.
6. Implementación del analizador léxico
Lo que hace es dividir la entrada en una serie de componente léxicos, realizando en cada uno de ellos determinadas acciones.
Algunas acciones son: comprobar alguna restricción adicional, preparar los atributos del componente y emitir u omitir dicho componente.
6.1. La estrategia avariciosa
Se busca en la parte de la entrada no analizada el prefijo mas largo que pertenezca al lenguaje asociado a alguna categoría léxica. La división de la entrada coincide con la que esperamos.
6.2. Máquina discriminadora determinista
Además de cadenas completas, aceptan prefijos de la entrada y tienen asociadas acciones a los estados finales.
6.2.1. Funcionamiento de la MDD
No intenta reconocer la entrada sino segmentarla.
Actúa sobre la entrada, empezando en cada caso en un punto distinto, pero siempre en su estado inicial.
6.3. Tratamiento de errores
Emitir un mensaje de error y detener la generación de código.
Devolver al flujo de entrada todos los caracteres leídos desde que se detecto el ́ultimo componente léxico.
Eliminar el primer carácter.
Continuar el análisis.
6.3.1. Uso de categorías léxicas para el tratamiento de errores
Un error frecuente es olvidar las comillas de cierre de una cadena.
Si las cadenas no pueden abarcar varias líneas, es fácil escribir una expresión regular para detectar las cadenas no cerradas.
6.3.2. Detección de errores en las acciones asociadas
Aquí si es de esperar un mensaje de error bastante informativo y una buena recuperación: basta con emitir la categoría con un valor predeterminado.
6.4. Algunas categorías especiales
Categorías que se suelen omitir
El analizador léxico suele analizar los comentarios para comprobar cuantos fines de línea están incluidos en ellos y poder informar de la posición de los errores.
El fin de fichero
En algunos casos es un valor especial, en otros debe consultarse explícitamente y en otros consiste en la devolución de la cadena vacía.
Las palabras clave
El caso mas claro es el que sucede con las palabras clave y su relación con los identificadores.
Este sistema no solo es incomodo para escribir, facilitando la aparición de errores, también hace que añadir una nueva palabra clave sea una pesadilla.
6.5. El interfaz del analizador léxico
Lo mínimo que deberá ofrecer el analizador léxico es una función que permita ir recuperando el componente léxico actual.
Una función que indique cual es el ultimo componente leído. Esta función no avanza la lectura.
Una función que avance la lectura hasta encontrar otro componente y lo devuelva.
6.6. El flujo de entrada
Un método para especificar desde donde se leen los caracteres.
Un método para leer el siguiente carácter.
Un método para devolver uno o mas caracteres a la entrada.
6.7. Implementación de la MDD
6.7.1. Implementación mediante tablas
De diseña una función que es independiente de la MDD que se este utilizando. Se codifica en una tabla que se pasa como parámetro a la función.
Se utilizan tres tablas: La tabla movimiento, la tabla final y la tabla acción.
6.7.2. Implementación mediante control de flujo
Genera un código que simula el funcionamiento del autómata. Es menos flexible pero suele ser mas eficiente.
La estructura global del programa es un bucle que lee un carácter y ejecuta el código asociado al estado actual.
7. Introducción a un generador automático de analizadores léxicos: flex
Flex es un generador automático de analizadores léxicos para el lenguaje de programación C: lee un fichero de texto con una descripción del analizador léxico y produce un programa C que implementa el analizador.
Esta diseñado para usarse conjuntamente con bison (yacc), un metacompilador.
7.1. Estructura de un programa flex
Una especificación flex es un fichero compuesto por tres partes separadas por %%:
7.1.1. La zona de reglas
Cada regla es de la forma: expresión regular {acción} donde acción es un fragmento de código en C.
7.1.2. La zona de funciones auxiliares
Permite incluir código C que se copia literalmente en lex.yy.c.
7.1.3. La zona de declaraciones
Nombres a expresiones regulares, estos pueden usarse en la zona de reglas encerrando su identificador entre llaves.
7.2. Compilación de las especificaciones
Se pueden emplear para generar un fichero C, que puede actuar como modulo de un programa mayor o compilarse para dar un programa ejecutable.
7.3. Como utilizar diferentes flujos de entrada
Lectura de varios ficheros.
Cuando yylex() alcanza el final de fichero, llama automáticamente a la función yywrap(), que devuelve 0 o 1.
Si devuelve un 1, el programa ha finalizado. Si devuelve un 0, el analizador asume que yywrap() ha asignado a yyin un nuevo fichero para lectura, con lo que sigue leyendo.
Lectura de una cadena.
Es posible analizar una cadena en lugar de un fichero. Se puede redefinir la macro YY_INPUT o utilizar las funciones yy_scan_string, yy_scan_bytes o yy_scan_buffer.
8. Algunas aplicaciones de los analizadores léxicos
Se pueden emplear para muchos programas convencionales.
Un analizador léxico simplifica la interfaz y si se dispone de un generador automático, el problema se resuelve en pocas líneas de código.
8.1. Ficheros organizados por columnas
Supongamos que tenemos un fichero de texto en el que aparecen secuencias de dígitos separadas por tabuladores que definen columnas.
8.2. Procesamiento de ficheros de configuración
En este fichero se tienen líneas con el formato: variable = valor.
Los nombres de variable son secuencias de letras y dígitos que comienzan por una letra.
Los valores pueden ser cadenas entre comillas o números enteros.
Se permiten comentarios que comienzan por el carácter # y terminan al final de la línea.
Se permiten líneas vacías.
