2.1. Análisis Léxico

Actividad 2.1 Análisis Léxico

Primera fase de un programa traductor. Parte del compilador que lee caracteres del programa fuente y construye simbolos intermedios de posterior uso para el analizador sintáctico.

índice

Conjuntos regulares

Introducción

Algoritmos de reconocimiento léxico

Estructura básica

Expresiones regulares

Herramientas generadora de analizadores léxicos

Diagrama de transición

Es parte del compilador que lee los caracteres del programa fuente y que construye unos símbolos intermedios (elementos léxicos, que llamaremos "tokens") que serán posteriormente utilizados por el analizador sintáctico como entrada. La principal función del analizador léxico es procesar la cadena de caracteres y devolver pares (token, lexema). La funciones que realiza el analizador léxico es:

• Procesado de léxico del programa fuente.
• Manejo de fichero del programa fuente.
• Ingora comentarios y, lenguajes de formato libre e ignora los separadores.
• Cuando se produce una situación de error, será el analizador léxico que situe el error en el programa fuente.
• Preproceso de macros, definiciones, constantes y órdenes de otros ficheros.

INTRODUCCIÓN

El analizador léxico (AL) es la primera fase de un programa traductor. Es, por otra parte, el único que gesitona el fichero de entrada.

Estructura básica

Y funciones

El analizador léxico, también conocido como scanner o tokenizador, es un componente fundamental de un compilador o intérprete. Se encarga de leer el código fuente, caracter por caracter, y transformarlo en una secuencia de tokens, que son unidades léxicas significativas (como palabras clave, identificadores, operadores, literales, etc.).

Modulo de lectura y reconocimiento (Scanner Engine)

Generador de tokens (Token Generator)

Es el núcleo del analizador léxico, encargado de recorrer la entrada y reconocer patrones de caracteres que coincidan con expresiones regulares definidas por el lenguaje.Aquí se aplican autómatas finitos deterministas (AFD) o no deterministas (AFN) para identificar tokens.

• Una vez reconocido un patrón, esta parte genera el token correspondiente y lo envía al analizador sintáctico.

• Cada token contiene información: tipo, lexema, y a veces posición en el código.

Entrada (Input Buffer)

• Es el área donde se almacena el código fuente que va a ser procesado
• Su función es facilitar la lectura eficiente del código, usualmente mediante técnicas como el buffer doble para minimizar el acceso al disco.

Tabla de simbolos

Manejador de errores léxicos (Error Handler)

• Estructura que guarda información sobre los identificadores (como variables, funciones) reconocidos, junto con sus atributos.

• Detecta caracteres o secuencias que no pertenecen al lenguaje y lanza mensajes de error claros.
• En ocasiones, permite la recuperación del error para continuar el análisis.

Para crear una expresión regular debes utilizar una sintaxis específica, es decir, caracteres especiales y reglas de construcción. Por ejemplo, esta es una expresión regular simple que coincide con cualquier número de teléfono de diez cifras con el patrón nnn-nnn-nnnn:

\d{3}-\d{3}-\d{4}

Sintaxis de expresiones regulares

Diagrama de transición

Un diagrama de transición es una representación gráfica del comportamiento de un autómata finito determinista (AFD) o autómata finito no determinista (AFN), que es utilizado en la fase de análisis léxico del compilador.

En un compilador, el analizador léxico usa estos diagramas para identificar patrones (tokens) en el código fuente, como identificadores, números, palabras clave o símbolos.

Este diagrama ilustra los estados, las transiciones entre esos estados (según los caracteres de entrada), y los estados de aceptación o rechazo.

Cada estado representa una etapa en el reconocimiento de un token, y cada transición está definida por un carácter o conjunto de caracteres válidos.

Ayuda a la construcción de analizadores léxicos automáticos (por ejemplo, usando herramientas como Lex o Flex).

Permite diseñar y visualizar cómo un compilador procesa la entrada carácter por carácter.

Facilita la validación de expresiones regulares que definen tokens.

Conjuntos regulares

Conjunto de cadenas que se puede formar mediante operaciones

Un lenguaje regular sobre un alfabeto Σ dado se define recursivamente como:

• El lenguaje vacío ∅ es un lenguaje regular
• El lenguaje cadena vacía {ε} es un lenguaje regular
• Para todo símbolo a ∈ Σ {a} es un lenguaje regular
• Si A y B son lenguajes regulares entonces A ∪ B (unión), A•B (concatenación) y A* (clausura o estrella de Kleene) son lenguajes regulares
• Si A es un lenguaje regular entonces (A) es el mismo lenguaje regular
• No existen más lenguajes regulares sobre Σ

Los conjuntos representados por expresiones regulares son llamados conjuntos regulares. Un lenguaje regular es un lenguaje formal que puede ser definido por una expresión regular, generado por una gramática regular, y reconocido por un autómata finito. Un subconjunto especial de los lenguajes regulares es el de los lenguajes finitos, aquellos que solo contienen un número finito de palabras. Estos son lenguajes obviamente regulares y uno podría crear expresiones regulares que serían la unión de todas las palabras del lenguaje que definirían dicho lenguaje.

Análisis léxico mediante tabla de transiciones

Reconocimiento basado en autómatas finitos (AFD/AFN)

• El autómata determinista resultante se implementa con una tabla de transiciones, donde filas son estados y columnas son símbolos de entrada.
• Se recorre la cadena de entrada carácter por carácter, moviéndose entre estados hasta llegar a un estado de aceptación.
• Este es un algoritmo eficiente y muy utilizado en compiladores industriales.

• Utiliza autómatas construidos a partir de expresiones regulares que describen los tokens.
• El analizador léxico convierte las expresiones regulares en autómatas (deterministas o no deterministas) y recorre el texto para reconocer patrones.

Maximal Munch (Máximo consumo)

Algoritmo de retroceso (Backtracking)

• Algunos analizadores léxicos emplean retroceso cuando no es posible determinar de inmediato el token.
• Se consume caracteres hasta que no se encuentra una transición válida y luego retrocede al último estado aceptable.
• Se usa menos en compiladores de alto rendimiento porque es más costoso, pero es útil en situaciones ambiguas.

Es una estrategia implementada sobre el reconocimiento léxico: el analizador consume la mayor cantidad posible de caracteres hasta que no pueda avanzar más y haya reconocido el token más largo posible. Por ejemplo, si puede reconocer <= o solo <, elegirá <=.

Flex (Generador de analizador léxico rápido)

Lex

Lex es un programa para generar analizadores léxicos (en inglés scanners o lexers). Lex se utiliza comúnmente con el programa yacc que se utiliza para generar análisis sintáctico. 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.

• Flex (generador rápido de analizadores léxicos ) es una alternativa de software libre y de código abierto a lex.
• Se utiliza frecuentemente como implementación de lex junto con el generador de analizadores sintácticos Berkeley Yacc en sistemas operativos derivados de Base de Datos.

JTLex

JFlex

Permite generar un analizador léxico traductor a partir de la especificación mediante ETL´s de los símbolos del lenguaje al que está destinado y sus correpondientes semánticas, según se muestra en la figura 2.

Es un generador de analizador léxico (también conocido como generador de escáner) para Java, escrito en Java. JFlex está diseñado para funcionar con el generador de analizadores LALR CUP de Scott Hudson y la modificación de Java de Berkeley Yacc BYacc/J de Bob Jamison. También puede utilizarse con otros generadores de analizadores como ANTLR o como herramienta independiente.

resultados

bibliografía/publicaciones

• Clase digital 2. Herramientas de software: Lex/Flex. (2022, 16 julio). Nodo Universitario - Universidad de Guanajuato. https://blogs.ugto.mx/rea/clase-digital-2-herramientas-de-software-lex-flex/#:~:text=Las%20ventajas%20de%20usar%20esas,%C2%A1Empecemos%20con%20mucho%20%C3%A1nimo!
• colaboradores de Wikipedia. (2019, 14 julio). Compilers: Principles, Techniques, and Tools. Wikipedia, la Enciclopedia Libre. https://es.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools
• colaboradores de Wikipedia. (2024, 16 julio). Lex (informática). Wikipedia, la Enciclopedia Libre. https://es.wikipedia.org/wiki/Lex_(inform%C3%A1tica)
• Compiladores. (s. f.). Google Books. https://books.google.com.gt/books?id=yG6qJBAnE9UC&printsec=frontcover#v=onepage&q&f=false
• Diseño de compiladores. (s. f.). Google Books. https://books.google.com.mx/books/about/Dise%C3%B1o_de_compiladores.html?id=GnyqPAAACAAJ&redir_esc=y
• Expresiones regulares COMOS (HOWTO). (s. f.). Python Documentation. https://docs.python.org/es/3.13/howto/regex.html GeeksforGeeks. (2024, 17 septiembre). FLEX (Fast Lexical Analyzer Generator).
• GeeksforGeeks. https://www-geeksforgeeks-org.translate.goog/flex-fast-lexical-analyzer-generator/?_x_tr_sl=en&_x_tr_tl=es&_x_tr_hl=es&_x_tr_pto=sge#:~:text=An%C3%A1lisis%20l%C3%A9xico,-Introducci%C3%B3n%20al%20an%C3%A1lisis&text=analizador%20l%C3%A9xico%20r%C3%A1pido)-,Flex%20(Fast%20Lexical%20Analyzer%20Generator)%2C%20o%20simplemente%20Flex%2C,menudo%20junto%20con%20Berkeley%20Yacc.
• Klein, G. (s. f.). JFlex - JFlex The Fast Scanner Generator for Java. https://www.jflex.de/
• Sintaxis de las expresiones regulares - Ayuda de Administrador de Google Workspace. (s. f.). https://support.google.com/a/answer/1371415?hl=es
• The Theory of Parsing, Translation, and Compiling: An introduction to compiling. (s. f.). Google Books. https://books.google.com.mx/books/about/The_Theory_of_Parsing_Translation_and_Co.html?id=45VQAAAAMAAJ&redir_esc=y
• Wikipedia contributors. (2025, 15 marzo). Flex (lexical analyser generator). Wikipedia. https://en.wikipedia.org/wiki/Flex_(lexical_analyser_generator)