Please enable JavaScript.
Coggle requires JavaScript to display documents.
Procesadores del lenguaje image, image, image, image, image, image, image…
Procesadores del lenguaje
Alfabetos y lenguajes
Dependiendo de la aplicación que tengamos en mente, estos pueden ser: caracteres, letras o palabras, si queremos trabajar con lenguaje natural
Una cadena es una secuencia de símbolos del alfabeto. Nuevamente, no estamos interesados en la naturaleza precisa de las cadenas.
La cadena puede ser una pregunta a una base de datos
Para el analizador léxico, una cadena es el programa una evz pasado por el analizador léxico
En OCR, una cadena es la descripción de una letra manuscrita, etc.
Un alfabeto Σ es un conjunto finito de símbolos. No nos interesa la naturaleza de los símbolos.
Un
lenguaje formal
es un subconjunto de Σ*. Tal como está definido, puede ser finito infinito.
Las especificaciones serán de dos tipos
Expresiones regulares que se emplean en el análisis léxico
Gramáticas incontextuales en el análisis sintáctico
Categorías léxicas
Categorías léxicas más usuales
Palabras clave.
Palabras con un significado concreto en el lenguaje
Identificadores.
Nombres de variables, nombres de función, nombres de tipos definidos por el usuario, etc.
Operadores.
Símbolos que especifican operaciones aritméticas, lógicas, de cadena, etc.
Constantes numéricas.
Literales que especifican valores numéricos enteros, en coma flotante, etc.
Constantes de caracter o de cadena.
Literales que especifican caracteres o cadenas de caracteres
Símbolos especiales. Separadores, delimitadores, terminadores, etc.
Comentarios.
Información destinada al lector de programa.
Blancos.
Espacios en blanco, tabuladores y saltos de línea.
Fin de entrada.
Se trata de una categoría ficticia emitida por el analizador léxico para indicar que no queda ningún componente pendiente en la entrada
Conceptos básicos
De forma natural, surge el concepto de
categoría léxica
, que es un tipo de símbolo elemental del lenguaje de programación
Los componentes léxicos (
tokens
en inglés) So elementos de las categorías léxicas.
Para que el analizador léxico consiga el objetivo de dividir la entrada en partes, tiene que poder decidir por cada una de esas partes si es un componente separado
Para algunos componentes, fases posteriores del análisis necesitan información adicional a la categoría a la que pertenece
Lexema
. Es la secuencia concreta de caracteres que corresponde a un componente léxico
Especificación de las categorías léxicas
Expresiones regulares
Antes de describir las expresiones regulares, recomendaremos dos operaciones sobre lenguajes
La concatenación de dos lenguajes L y M.
Clausura. Conjunto de cadenas que se pueden obtener mediante la concatenación de un numero arbitrario de cadenas
Expresiones regulares básicas
La expresión regular 0 denota el lenguaje vacío-
La expresión regular lambda denota el lenguaje que únicamente contiene la cadena vacía
Dada una expresión regular r, utilizaremos L(r) para referirnos al lenguaje que representa.
La expresión regular a, donde a pertenece a Σ.
Sea r una expresión regular, la expresión regular (r
) representa el lenguaje L((r)
) = (L(r))*.
La expresión regular (rs) representa el lenguaje L((rs)) = L(r)L(s)
La expresión regular (r|s) representa el lenguaje L((r|s)) = L(r) U L(s)
Expresiones regulares extendidas
Agrupaciones de caracteres
. Permite escribir agrupaciones de caracteres de manera más cómoda. En su forma más simple, si queremos representar la elección de uno entre varios caracteres, basta con encerrarlos entre corchetes. También permiten especificar los caracteres que no están en un conjunto.
Nuevos operadores
. Enriquecemos el conjunto básico de operadores regulares con dos nuevos operadores:
clausura positiva
, y la
opcionalidad
.
El primero se representa mediante el signo más e indica una o más repeticiones de la expresión regular a la que afecta.
El segundo operador, representado mediante un interrogante, representa la aparición opcional de la expresión a la que afecta.
Las expresiones regulares básicas pueden considerarse una notación estándar.
Caracter de escape
. Hemos visto una serie de caracteres que tienen un significado especial. A estos caracteres se les llama metacaracteres. Si queremos referirnos a ellos podemos utilizar el caracter de escape, en nuestro caso la barra .
Las extensiones permiten escribir más cómodamente las expresiones regulares sin aumentar su poder descriptivo.
Nombres.
La última extensión que permitiremos es la posibilidad de introducir nombres para las expresiones. Estos nombres podrán utilizarse en lugar de cualquier expresión.
Aún cuando las expresiones regulares resultan más legibles al introducir las prioridades, sigue habiendo construcciones habituales que resultan incómodas de escribir.
El conjunto de lexemas que forman los componentes léxicos que podemos clasificar en una determinada categoría léxica se expresa mediante un patrón.
Autómatas de estados finitos
Autómatas finitos deterministas
Para definir el funcionamiento del AFD debemos empezar por el concepto de
camino
. Un camino en un AFD es una secuencia p1, s1, p2, s2, ... sn-1, pn tal que para todo i entre 1 y n - 1 (pi, si, pi+1) pertenece a E.
Un
autómata finito determinista
es una quíntupla (Q, Σ, E, q0, F) donde
Σ es un alfabeto
E Q x Σ es un conjunto de
arcos
tal que si (p, a, q) y (p, a, q') pertenecen a E, se tiene que q = q' (condición de determinismo).
Q es un conjunto finito de estados
q0 Q es un estado inicial
F Q es el conjunto de estados finales
Los autómatas se pueden representar gráficamente. Para ello se emplea un grafo en el que cada estado esta representado por un nodo y cada arco del autómata se representa mediante un arco en el grafo.
Los estados finales se marcan mediante un doble círculo y el estado inicial mediante una flecha.
Construcción de un AFD a partir de una expresión regular
Formalización
La idea básica de sustituir cada ítem por una serie de transformaciones que se corresponden con los movimientos.
Intentaremos sistematizar lo que hemos ido haciendo. Empezaremos por el proceso de, a partir de un conjunto de ítems, encontrar los ítems básicos que constituirán el estado del autómata.
Una vez sabemos como calcular la clausura de un estado, podemos construir los movimientos del autómata. Si estamos en un estado que contiene una serie de items básicos, el estado al que iremos al consumir un caracter de la entrada será la clausura del conjunto resultante de avanzar el punto una posición en aquellos items que lo tengan delante del caracter.
Podemos construir un AFD a partir de una expresión regular. La idea básica es llevar en cada estado del autómata la cuente de en qué pate de la expresión "estamos".
Para esto emplearemos lo que llamaremos
items
, que serán expresiones regulares con un punto centrado (.).
El punto indicará que parte e la expresión corresponde con la entrada leída hasta alcanzar el estado en el que esta el item.
Los estados de nuestro autómata será conjuntos de items básicos sobre la expresión regular
Compromisos entre espacio y tiempo
Hay por lo menos dos maneras mas de trabajar con las expresiones regulares
Emplear autómatas finitos no deterministas (AFN)
La construcción de un autómata no determinista es mas sencilla que la de uno determinista y proporciona autómatas de menor número de estados que los deterministas
En análisis es más costoso. Esto hace que sea una opción atractiva para situaciones en las que la expresión e vaya a utilizar pocas veces.
Utilizar
backtracking
Cuando se utiliza backtracking, lo que se hace es ir probando a ver qué partes de la expresión se corresponden con la entrada y se vuelve atrás si es necesario.
Podemos ver que el uso de backtracking minimiza la utilización del espacio, pero solo puede aumentar notablemente el tiempo de análisis
Cuando se trabaja con compiladores e intérpretes, las expresiones se utilizan muchas veces, por lo que merece la pena utilizar AFDs e incluso minimizarlos.
En otras aplicaciones por ejemplo facilidades de búsqueda de un procesador de textos, la expresión se empleará pocas veces.
Distinguimos 2 tipos de autómatas según sean sus transiciones.
Si desde cualquier estado hay como mucho una transición por símbolo, el autómata es no determinista
En caso de que haya algún estado tal que con un símbolo pueda transitar a más de un estado, el autómata es no determinista.
Las expresiones regulares permiten describir con cierta comodidad los lenguajes regulares. Sin embargo, no es fácil decidir a partir de una expresión regular si una cadena pertenece al correspondiente lenguaje.
Implementación del analizador léxico
La estrategia avariciosa
Inicialmente puede parecer que podemos especificar completamente el analizador dando una lista de expresiones regulares para las distintas categorías.
Sin embargo, debemos definir algo más: cómo esperamos que se unan estas categorpias para formar la entrada
Lo que se suele emplear es la denominada "estrategia avariciosa": en cada momento se busca en la parte de la entrada no analizada el prefijo más largo que pertenezca al lenguaje asociado a alguna categoría léxica
Máquina discriminadora determinista
El funcionamiento de las MDD es muy similar al de los AFDs, las diferencias son 2:
Aceptan prefijos de entrada
Tienen asociadas acciones a los estados finales
Por construcción, los únicos arcos que pueden llegar a un estado final serán los etiquetados con símbolos especiales. Lo que hacemos ahora es eliminar los estados finales y los arcos con símbolos especiales.
A estos estados asociaremos las acciones correspondientes al reconocimiento de las categorías léxicas.
Para reconocer simultáneamente las distintas categorías léxicas utilizaremos un tipo de autómata muy similar a los AFDs: la
máquina discriminadora determinista (MDD)
Tratamiento de errores
Desafortunadamente, es difícil saber cuál ha sido el error.
Podría suceder que estuviésemos escribiendo un real y hubiésemos sustituido el primer dígito por otro.
Un rango mal escrito
Un punto que sobrase
Una posible estrategia sería definir una "distancia" entre programas y buscar el programa más próximo a la entrada encontrada
Desgraciadamente, esto resulta bastante costoso y las ganancias en la práctica pueden ser mínimas.
La MDD no puede transitar desde un determinado estado y no ha pasado por estado final alguno, se ha detectado un error léxico. Tenemos que tratarlo de alguna manera adecuada,
La estrategia que requeriremos será:
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 detectó el último componente léxico.
Eliminar el primer caracter
Continuar el anállisis
Uso de categorías léxicas para el tratamiento de errores
Un error frecuente es olvidar las comillas de cierre de cadena. Si las cadenas no pueden abarcar varia líneas, es fácil escribir una expresión regular para detectar las cadenas no cerradas.
Categorías
Erroneal.
Informar del error, calcular valor, emitir real
Errorrango
. Informar del error, emitir rango
En muchas ocasiones los mensajes de error que puede emitir son muy poco informativos y puede provocar errores en las fases siguientes del análisis.
La estrategia anterior garantiza que el análisis continúa y finalmente habremos analizado toda la entrada.
Detección de errores en las acciones asociadas
Aquí si que es de esperar un mensaje de error bastante informativo y una buena recuperación: basta con emitir la categoría con un valor predeterminado
Otros errores que se detectan en el nivel léxico son aquellos que sólo pueden encontrarse al ejecutar las acciones asociadas a categorías.
La interfaz del analizado léxico
Además de estas funciones, existen una serie de unciones auxiliares que debe proporcionar el analizador.
Una función o método para averiguar en qué línea del fichero nos encontramos. Esto facilita la emisión de mensajes de error.
Relacionada con la anterior, en algunos analizadores podemos pedir que escriba la línea actual con alguna marca para señalar el error.
Una función o método para especificar cuál serpa el flujo de caracteres de entrada. Generalmente esta función permitirá especificar el fichero desde el que leeremos.
Si el analizador léxico necesita información del sintáctico, puede ser necesario utilizar funciones para comunicarla.
Así pues, lo mínimo que deberá ofrecer el analizador léxico es una función que permita ir recuperando el componente léxico actual. Pude ser cómodo dividir esta lectura en 2 partes.
Una función que indique cuál es el último componente leído. Esta función no avanza la lectura.
Una función que avance la lectura hasta encontrar otro componente y lo devuelva.
Implementación de la MDD
Implementación entre tablas
Esta es la implementación mas directa de la MDD. Se utilizan 3 tablas:
La tabla final contiene por cada estado un booleano que indica si es o no final.
La tabla acción contiene por cada estado las acciones asociadas. Asumiremos que la acción devuelve el token que se tiene que emitir o el valor especial definido para indicar que hay que omitir.
La tabla de movimiento contiene por cada estado y cada numero de entrada el estado siguiente o una marca espacial en cado de que el estado no esté definido.
Cuando no podemos seguir transitando, devolvemos el flujo de entrada la parte del lexema que leímos después de asar por el último final y ejecutamos las acciones pertinentes. Las variables que utilizaremos son
q: el estado de la MDD
l: el lexema del componente actual
uf: ultimo estado final por el que hemos pasado
ul: lexema que teníamos al llegar a uf
Implementación mediante control de flujo
El código asociado a un estado dependerá si este es o no final. En caso se que lo sea, tenemos que guardárnoslo en la variable uf y actualizar ul. Después tenemos que comprobar las transiciones y, si no hay posibles transacciones, devolver c al flujo de entrada y ejecutar las acciones asociadas al estado,
El código para loes estanos no finales es ligeramente más complicado, porque si no ha transiciones debemos retroceder hasta el último final.
En este caso, el propio programa refleja la estructura de la MDD. Lógicamente, aquí solo podemos dar un esquema. La estructura global del program es simplemente un bucle que lee un caracter y ejecuta el código asociado al estado actual.
Ten en cuenta que si se esta implementando a mano el analizador, suele ser muy fácil encontrar mejoras sencillas que aumentarán la eficiencia del código.
El analizador léxico no se utiliza para comprobar si una cadena pertenece o no a un lenguaje. Lo que hace es dividir la entrada en una serie de componentes léxicos, realizando en cada uno de ellos determinadas acciones.
Algunas de estas son: Comprobar alguna restricción adicional, preparar los atributos del componente y emitir u omitir dicho componente.
El flujo de entrada
Para evitar entrar en estos detalles, podemos suponer que existe un módulo u objeto que utiliza el analizador léxico para obtener los caracteres. Este módulo deberá ofrecer al menos los siguientes servicios.
Un método para leer el siguiente caracter
Un método para especificar desde donde se leen los caracteres
Un método para devolver uno o más caracteres a la entrada.
Un aspecto importante es la eficiencia de la lectura del disco. No es raro que una implementación eficiente de las siguientes fases del compilador haga que la lectura de un disco sea el factos determinante para el tiempo total de compilación
Hasta ahora hemos asumido más o menos implícitamente que los caracteres que utilizaba el analizador léxico provenían de algún fichero.
Según las características del lenguaje para el que estemos escribiendo el compilador, la devolución de caracteres será mas o menos complicada. En su forma más simple, bastará una variable para guardar un caracter.
Funcionamiento de la MDD
La idea del funcionamiento es muy similar a la de los AFD, salvo por 2 aspectos:
La MDD no intenta reconocer la entrada, sino segmentarla
La MDD actúa repetidamente sobre la entrada, empezando en cada caso en un unto distinto, pero siempre en su estado inicial.
Algunas categorías especiales
El fin de fichero.
Aunque ha aparecido como un símbolo más al hablar de las expresiones regulares, lo cierto es que el fin de fichero no suele ser un caracter más. Dependiendo del lenguaje en que estemos programando o incluso dependiendo de las rutinas que tengamos, el fin de fichero aparecerá de una manera u otra.
Las palabras clave
. De manera implícita, hemos supuesto que las expresiones regulares que empleamos para especificar las categorías léxicas definen lenguajes disjuntos dos a dos. Aunque esta es la situación ideal, en ocasiones puede suponer una fuente de incomodidades.
Categorías que se suelen omitir.
Los espacios generalmente no tienen significado. Esto hace que sea habitual tener una expresión del tipo [u\t\n]+ con
omitir
como acción asociada. En particular, es bueno llevar la cuenta de los \n para informar de la línea del error. Otra categoría generalmente omitida es el comentario.
Introducción a un generador automático de analizadores léxicos: Flex
Estructura de un programa en Flex
Zona de funciones auxiliares
Esta zona permite incluir código C que se copia literalmente en lex.yy.c.
Zona de declaraciones
En esta zona podemos dar nombres a expresiones regulares. Estos nombres pueden usarse luego en la zona de reglas encerrando su identificador en llaves.
Zona de reglas
Cada regla es de la forma
expresion regular {acción}
Donde acción es un fragmento de código en C
Las expresiones regulares pueden utilizar metasímbolos
Lee de la entrada el prefijo más largo que pertenece a la expresión regular de alguna regla Entonces ejecutan la acción asociada a esa regla.
Si la regla incluye una sentencia
return
, el control es devuelto a la función que invocó el analizador.
En caso contrario, se busca el siguiente componente.
Si la parte de la regla está vacía, la correspondiente entrada es simplemente deshechada.
Compilación de especificaciones
Las especificaciones se pueden emplear para generar un fichero C, que puede actuar como módulo de un programa mayor o compilarse para dar directamente un programa ejecutable.
Una vez hemos escrito la especificación, debemos crear un fichero C que sea capaz de ejecutarla.
Otro ejemplo
El siguiente programa flex cuenta el número de caracteres, palabras y líneas que se proporcinoen por la entrada estandar.
Cómo utilizar diferentes flujos
Otras posibles opciones para la lectura son:
Lectura de varios ficheros.
Cuando yylex() alcanza el final de fichero, llama automáticamente la función yywrap() que devuelve 0 o 1. Si devuelve un 1, el programa a finalizado. Si devuelve un 0, el analizador asume que yywrap() ha asignado a yyin a un nuevo fichero para lectura, con lo que sigue leyendo.
Lectura de una cadena
. Es posible analizar una cadena en lugar de un fichero. Para esto, se puede redefinir la macro Y_INPUT o utilizar funciones YY_scan_string, yy_scan_bytes o yy_scan_buffer.
Flex (Fast Lexical Analyser Generator) es un generador automático de analizadores léxicos para el lenguaje de programacion C: lee un fichero de texto con una descripción del analizador léxico y produce un programa C que implementa el analizador.
Flex es un software GNU creado a partir de lex, un generador de analizadores léxicos muy popularizado porque se distribuye gratuitamente con las versiones más comunes de Unix.
Algunas aplicaciones de los analizador léxicos
Ficheros organizados por columnas
Un ejemplo sencillo de uso de analizadores léxicos sería el trabajo con ficheros organizados en forma de columnas separadas por tabuladores. Supongamos que tenemos un fichero de texto en el que aparecen secuencias de dígitos separadas por tabuladores que definen columnas.
El método que tiene flex para pasar atributos no es muy elegante (y también bison), por eso usamos yyval para el valor del número.
Procesamiento de configuración
Otro ejemplo típido de uso de analizadores léxicos sería la lectura de n fichero de configuración.
Supongamos que 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 caracter # y terminan al final de la línea
Además se permiten líneas vacias.
