Análisis léxico

Nota: Antes de profundizar en la primera fase de un compilador, es fundamental repasar tus conocimientos sobre lenguajes formales, en particular el tema de autómatas. Estos conceptos son esenciales para entender cómo se verifican los tokens y cómo se aplican las expresiones regulares.

El análisis Léxico es la primera fase de un compilador, y toma el programa fuente de los pre-procesadores que está escrito en forma de declaraciones.La primera fase del compilador se caracteriza por ser la que lee el flujo de caracteres que conforman el programa fuente y los agrupa en tokens. Un token es la unidad mínima de información de un lenguaje de programación; esta puede ser un carácter, un número, una palabra clave, un operador u otro símbolo.

En la Tabla1 se muestra la clasificación que puede haber dentro de la fase de tokenización y ejemplos de ellos. 

La clasificación de tokens que pueden encontrarse en un programa durante el análisis léxico. 

1. Categoría: Indica el tipo de token que se clasifica según su función o rol dentro del lenguaje de programación.
2. Descripción: Proporciona una breve explicación del propósito o uso de cada categoría.
3. Ejemplos: Presenta ejemplos específicos de cada categoría para ilustrar su uso.

Detalle de cada categoría:

1. Palabras clave

Descripción: Son elementos reservados del lenguaje de programación que tienen un significado específico y no pueden usarse como identificadores (nombres de variables o funciones).

Ejemplos: if, for, return.

2.      Identificadores

Descripción: Representan nombres definidos por el programador, como nombres de variables, funciones o clases.

Ejemplos: x, miFuncion.

3.       Números

Descripción: Se refieren a literales numéricos, tanto enteros como decimales, que son usados en cálculos o asignaciones.

Ejemplos: 10, 3.14.

4 .      Operadores

Descripción: Son símbolos utilizados para realizar operaciones matemáticas, lógicas o relacionales.

Ejemplos: +, -, =.

5.       Delimitadores

Descripción: Caracteres que marcan límites o separaciones en la estructura del código, como en listas, bloques o instrucciones.

Ejemplos: ;, {, }.

En un lenguaje de programación, palabras reservadas, constantes, identificadores, cadenas de texto, números, operadores y signos de puntuación pueden ser considerados como tokens.  

El propósito principal del analizador léxico es transformar una secuencia de caracteres del código fuente en una secuencia de tokens, que son elementos básicos que el compilador puede interpretar y procesar en etapas posteriores.

Generalmente, el analizador léxico omite los espacios en blanco, las tabulaciones y los comentarios, ya que estos no tienen importancia para la sintaxis del programa, aunque son fundamentales para la legibilidad del código.
En la Figura3 se muestra un programa de una calculadora básica que acepta dos números y un operador, que pueda realizar ya sea una (suma, resta, multiplicación, división) como entrada del usuario y devuelve el resultado. En la Tabla2 se clasifican los tokens de dicho lenguaje.

En la imagen anterios se presenta un programa escrito en el lenguaje de programación C que implementa una calculadora básica capaz de realizar operaciones como suma, resta, multiplicación y división. Este lenguaje sigue un conjunto de reglas que el analizador léxico reconoce y verifica al escanear cada línea del código. Durante este proceso, el código se divide en unidades mínimas de información, conocidas como tokens, las cuales son clasificadas según su tipo en la Tabla2. 

Escanear nuestros tokens:

Línea 1: #include <stdio.h>

• #include: Palabra clave del preprocesador de C para incluir librerías.
• <stdio.h>: Identificador que indica la librería estándar de entrada/salida.

Línea 3: int main()

• int: Palabra clave que especifica el tipo de dato que devuelve la función main (en este caso, un entero).
• main: Identificador que nombra la función principal del programa.
• (): Delimitadores que indican que es una función.

Línea 4: char operador;

• char: Palabra clave que indica el tipo de dato (un carácter).
• operador: Identificador que define el nombre de la variable.

Línea 5: double num1, num2, resultado;

• double: Palabra clave que indica el tipo de dato (números de punto flotante de doble precisión).
• num1, num2, resultado: Identificadores de las variables.
• ;: Delimitador que marca el final de la declaración.

Línea 7-8: printf y scanf

• printf: Identificador de una función de salida (imprime texto en la consola).
• scanf: Identificador de una función de entrada (lee datos desde la consola).
• ": Delimitador que encierra cadenas de texto.
• %c y %lf: Especificadores de formato para caracteres y números de tipo double, respectivamente.
• ,: Separador para argumentos de las funciones.
• ;: Finaliza cada instrucción.

Línea 19: switch (operador)

• switch: Palabra clave para el control condicional múltiple.
• ( y ): Delimitadores que encierran la variable a evaluar (operador).
• operador: Identificador (la variable sobre la que se basa el switch).

Líneas 20-43: case, default, break

• case: Palabra clave que indica una opción dentro del switch.
• '+' y demás operadores (-, *, /): Literales que representan los casos posibles.
• break: Palabra clave que finaliza la ejecución de un caso.
• default: Caso por defecto si ningún case coincide.

Operaciones y lógica en el switch  

• resultado = num1 + num2;
• resultado, num1, num2: Identificadores de variables.
• =: Operador de asignación.
• +: Operador aritmético.
• ;: Delimitador que cierra la instrucción.
• if (num2 != 0) (en la división):
• if: Palabra clave para el control condicional.
• ( y ): Delimitadores que encierran la condición lógica.
• num2 != 0: Expresión lógica (comprueba que num2 no sea cero).!=: Operador de comparación "distinto de".

Salida: printf

• El resultado de %.2lf ...: Cadena de texto que utiliza especificadores de formato (%.2lf) para mostrar el resultado con dos decimales.

Línea 45: return 0;

• return: Palabra clave que indica el valor de retorno de la función.
• 0: Literal numérico (valor de retorno para indicar que el programa finalizó correctamente).
• ;: Delimitador que cierra la instrucción.

En la Tabla2 se muestran dichas clasificaciones, lo que facilita la identificación y comprensión de los elementos del programa. 

 Si el compilador detecta un elemento que no tiene sentido o no cumple con las reglas del lenguaje, como un símbolo desconocido, genera un mensaje de error. Esto permite al programador identificar y corregir los errores en el código desde las primeras etapas del desarrollo. 

Comprobación de los tokens con los lenguajes formales, autómatas y el uso de expresiones regulares. 

Para poder empezar, primero hay que recordar qué son los términos de autómatas y cómo se utilizan para comprobar los tokens y sus expresiones regulares.

Expresiones Regulares: Una expresión regular es una notación importante para la especificación de patrones. Cada patrón coincide con un conjunto de cadenas, de modo que las expresiones regulares se utilizan como nombres para un conjunto de cadenas. Se emplean para definir los patrones de los tokens.

En la Tabla3 se representan las diferentes expresiones regulares que se pueden utilizar con la calculadora básica. También se muestran algunos errores que no serán validados por las expresiones.

Lo que se muestra en tabla es que relaciona funciones del análisis léxico con expresiones regulares , descripciones y ejemplos. 

1. Reconocer números

• Expresión Regular: ^[0-9]+(\.[0-9]+)?$
• ^[0-9]+: Busca números enteros que comienzan con uno o más dígitos (0-9).
• (\.[0-9]+)?: De manera opcional, puede contener un punto (.) seguido de uno o más dígitos decimales.
• $: Asegura que toda la cadena cumple con este patrón.
• Descripción: Detecta números enteros o decimales.
• Ejemplos Válidos: 123, 45.67.
• Ejemplos Inválidos: .45, 123., abc (porque no son números válidos en este contexto).

2. Reconocer operadores

• Expresión Regular: ^[\+\-\*\/]$

• [\+\-\*\/]: Reconoce cualquiera de los símbolos de los operadores aritméticos básicos: +, -, *, /.

• ^ y $: Indican que debe ser un operador único en toda la cadena.

• Descripción: Identifica operadores aritméticos.

• Ejemplos Válidos: +, -, *, /.

• Ejemplos Inválidos: ++, %, a (porque no son operadores básicos válidos).

3. Detectar entradas inválidas

• Expresión Regular: [^0-9.\+\-\*\/]

• [^...]: Indica un conjunto de caracteres que no son válidos. En este caso, cualquier carácter que no sea un dígito (0-9), un punto (.) o un operador (+, -, *, /).

• Descripción: Detecta caracteres fuera del rango permitido.

• Ejemplos Válidos: Ninguno (esta expresión se usa para invalidar entradas, no para validarlas).

• Ejemplos Inválidos: abc, 1a2, 12+34 (porque incluyen caracteres no válidos como letras).

El análisis léxico se puede representar como un autómata, específicamente un autómata finito determinista (AFD), que pasa por una serie de estados mientras lee los caracteres y reconoce los tokens. Cada estado representa una parte del patrón que se está reconociendo. 

Autómatas Finitos Deterministas: El AFD se utiliza para representar y procesar secuencias de caracteres (o entradas) de manera sistemática, evaluando si cumplen con ciertas reglas definidas.

Una vez que se tiene el AFD, este puede procesar el código fuente carácter por carácter, siguiendo las transiciones de estado. Si el AFD llega a un estado final (de aceptación) después de procesar una secuencia, esa secuencia es un token válido.

Si quieres saber más a detalle sobre el uso de los autómatas, te estoy proporcionando el siguiente video donde se detalla mucho más su uso.

Piñeiro, M. A. (@matematicamaravillosa). (s.f.). Autómatas finitos y máquinas de estados [Video]. YouTube. https://youtu.be/ScR1T1DME14 

En la Figura4 se muestra un ejemplo de un autómata que puede validar expresiones aritméticas y determinar si una cadena de caracteres dada corresponde a una expresión matemática válida, según las reglas que hemos definido. También se muestra su tabla de transiciones para validar cada movimiento del estado inicial al final. 

El autómata de la Figura4 compone de:

Validacion de los tokens:

Este AFD reconoce expresiones aritméticas simples que consisten en una secuencia de dígitos, seguida de un operador, y luego otra secuencia de dígitos.  

Otro ejemplo representado en la Figura5 es un autómata que solo está validando los operadores básicos de nuestra calculadora. 

Esta se compone de los siguientes elementos:

Proceso de validación:

 Inicio: El autómata comienza en el estado S0.

Lectura de entrada: El autómata lee un símbolo de la entrada.

Transición: Si el símbolo leído pertenece al conjunto {+, -, *, /}, el autómata realiza una transición del estado S0 al estado S1.

Aceptación: Si el autómata llega al estado S1 al final de la entrada, la entrada es aceptada. De lo contrario, la entrada es rechazada.

Este AFD en particular es muy simple y reconoce cualquier secuencia de símbolos que contenga al menos un operador aritmético (+, -, *, /). En otras palabras, este autómata acepta cualquier cadena que tenga al menos uno de estos símbolos.

Referencias:

Autómatas, L. Y. (s. f.). Lenguajes y autómatas I. https://lenguajesyautomatas1998.blogspot.com/2019/04/unidad-4-4.html

Compilador Diseño - expresiones regulares. (s. f.). https://www.tutorialspoint.com/es/compiler_design/compiler_design_regular_expressions.htm