1. Análisis léxico: Identificando los componentes básicos.

 El análisis léxico es la primera etapa del compilador. Aquí, el código fuente se divide en tokens, que son las unidades más pequeñas del programa. Los tokens incluyen:

  •     Palabras clave → entero, regresa
  •     Identificadores → x, y, suma
  •     Operadores → +, =
  •     Constantes → 10, 20
  •     Delimitadores → {, }, ;

Para el Ejemplo 2 consta de la declaración de una variable de tipo entero llamada x a la cual se le asigna un valor constante 10.

entero x = 10;

Ejemplo 2. Asignación de valor a una variable.
Fuente: Eduardo, O. Q. E. (2024). Ejemplo 2 [Fragmento de código].

El compilador generará los siguientes tokens que se presentan en la Tabla 1, como podemos observar en nuestra tabla, la línea de código del Ejemplo 2 pasa y se dividen los tokens en los siguientes campos:
Tabla 1. Tokens generados.
Fuente: Eduardo, O. Q. E. (2024). Tabla 1 [Imagen]. Excel.

Herramienta utilizada: Autómatas finitos

El análisis léxico se basa en el uso de autómatas finitos deterministas (DFA) para identificar y clasificar los diferentes patrones que aparecen en el código fuente, como palabras clave, identificadores, constantes numéricas, operadores, y delimitadores. Los autómatas finitos son modelos matemáticos que permiten reconocer lenguajes regulares y, por lo tanto, son herramientas ideales para el reconocimiento de patrones en el análisis léxico.

Principios de los autómatas finitos en el análisis léxico:

    1. Definición: Un autómata finito es un sistema formado por:

  •         Un conjunto finito de estados.
  •         Un alfabeto de entrada.
  •         Un estado inicial.
  •         Un conjunto de estados finales o de aceptación.
  •         Transiciones que definen el paso de un estado a otro según el símbolo de entrada.

    2. Aplicación en el análisis léxico: Los autómatas finitos se utilizan para construir analizadores léxicos, que son programas capaces de dividir el código fuente en tokens, los componentes básicos del lenguaje.

    3. Conversión de expresiones regulares a DFA: Generalmente, el proceso inicia con una expresión regular que define el patrón que debe reconocerse (como un identificador o una constante). Esta expresión regular se convierte en un autómata finito determinista que se puede implementar como parte del analizador léxico.

El autómata del Ejemplo 3, reconoce identificadores y está formado de tal forma que solo permite que los identificadores inicien con una letra ya sea minúscula o mayúscula seguido de letras o números:


[Estado inicial] → [A-Za-z] → [Estado válido] → [A-Za-z0-9]* → [Estado válido]

Ejemplo 3. Autómata que valida identificadores.

Fuente: Eduardo, O. Q. E. (2024). Ejemplo 3 [Autómata].

Ventajas de usar autómatas finitos en análisis léxico:
  •     Eficiencia: Los DFA son rápidos porque evalúan cada símbolo de entrada en tiempo constante.
  •     Determinismo: Cada estado tiene una transición definida para cada entrada, lo que facilita su implementación.
  •     Adaptabilidad: Los autómatas finitos pueden modificarse para incluir reglas adicionales según las necesidades del lenguaje de programación.
Limitaciones:
  •     Los DFA no pueden manejar lenguajes no regulares (por ejemplo, cuando el reconocimiento requiere un balance entre símbolos, como paréntesis anidados).
Con esta base, los autómatas finitos forman la columna vertebral de los analizadores léxicos, ayudando a transformar el código fuente en una secuencia de tokens para las etapas posteriores del compilador.

Te comparto algunas páginas para que puedas explorar de mejor forma sobre los autómatas:

1. Autómatas. (n.d.). Autómatas. Retrieved November 27, 2024, from https://posgrados.inaoep.mx/archivos/PosCsComputacionales/Curso_Propedeutico/Automatas/02_Automatas_AutomatasFinitos/Capitulo_2_Automatas_finitos_Curso_Anterior.pdf

2. Autómatas finitos Deterministas. (n.d.). https://cs.famaf.unc.edu.ar/~hoffmann/md20/07.html#/title-slide

En el siguiente video te comparto la explicación más a detalle sobre la fase léxica:

Fuente: Alex Ortega Díaz. (2018, August 13). Fases del compilador Análisis léxico, sintáctico y semántico [Video]. YouTube. https://www.youtube.com/watch?v=7sAU-7z0X1E


Referencia en APA: Alfred, A. V., & Ullman, J. D. (1998). Introducción al análisis léxico. En Principles of compiler design (Capítulo 2). Compiladores. (n.d.). Google Books. https://books.google.com.gt/books?id=yG6qJBAnE9UC&printsec=frontcover#v=onepage&q&f=false

Comentarios

Publicar un comentario