Fase léxica

La fase léxica es una parte muy importante del proceso de compilación siendo esta la primera fase. 

Durante esta etapa, el compilador convierte el código fuente de entrada en una secuencia de unidades conocidas como tokens. Estos tokens representan los diferentes elementos del lenguaje de programación, como palabras reservadas, identificadores, operadores y signos de puntuación.

El responsable de llevar a cabo esta tarea es el analizador léxico, también conocido como "scanner". Este componente lee el código fuente carácter por carácter y los agrupa en tokens siguiendo las reglas definidas en la gramática léxica formal del lenguaje.

Proceso del análisis léxico

1. Lectura del código fuente: El programa analiza el código línea por línea y carácter por carácter.
2. Identificación de patrones: Usando expresiones regulares y autómatas, reconoce palabras clave (keywords), operadores, identificadores, números, etc.
3. Generación de tokens: Cada unidad identificada se convierte en un token con un tipo y un valor asociados.

Ejemplo

Como dijimos en la introducción al blog realizaríamos la construcción de nuestro compilador,para un lenguaje que genere figuras geométricas es por eso que nuestros ejemplo y lo realizado en el blog será hecho en base a eso. 

Primero definiremos los tokens del lenguaje para figuras geométricas:

Figura 2 Definición de tokens.

En la figura 2 definimos los tokens que nuestro analizador léxico podrá reconocer,
vemos en la tabla que de la figura 2 que se especifica el token y se describe lo que hace cada token o lo que significa.

¿Qué son los tokens?

Un token es una unidad de información que tiene significado dentro de un lenguaje de programación. Cada token pertenece a una categoría específica. Por ejemplo:

• Palabras clave como if, while, circle.
• Identificadores como x, y, radio.
• Operadores como +, -, =.
• Números como 5, 3.14.

¿Cómo se identifican los tokens?

El proceso de identificar tokens se basa en expresiones regulares, que son patrones que definen cómo se deben reconocer las distintas categorías de tokens.

Expresiones Regulares

Una expresión regular es un patrón que describe un conjunto de cadenas. Las expresiones regulares permiten identificar secuencias de caracteres que corresponden a ciertos tokens.

Por ejemplo:

Para identificar un número entero, la expresión regular es [0-9]+, que significa "uno o más dígitos" (del 0 al 9).

A continuación,en la figura 3 se presenta una tabla con las expresiones regulares utilizadas para identificar los principales tokens en un lenguaje que genera figuras geométricas (como circle, rectangle):

Figura 3 Tabla de Expresiones regulares.

En la descripción de cada expresión regular que tenemos en la figura 3,se nos da la descripción del lenguaje para entender de mejor manera la expresión regular.

Estas secuencias de caracteres descritas por las expresiones regulares son comprobadas o identificadas por los autómatas.

Autómatas finito determinista (AFD)

Un autómata finito determinista (AFD) es un modelo matemático que nos ayuda a identificar las secuencias de caracteres que coinciden con una expresión regular. A continuación, describiré algunos autómatas básicos para las expresiones regulares más relevantes.

Autómata para Identificadores (expresión regular: [a-zA-Z_][a-zA-Z_0-9]*)

Un identificador es una secuencia de caracteres que comienza con una letra o un guión bajo (_), seguida de letras, números o guiones bajos.

Figura 4 Autómata identificadores.

Descripción del autómata figura 4:

• Estado 0: El primer carácter debe ser una letra o un guión bajo (a-z, A-Z, _).
• Estado 1: Después de que el primer carácter sea válido, pueden seguirse letras, dígitos o guiones bajos.
• Si el autómata encuentra cualquier otro carácter, el proceso termina.

Analizador léxico para un lenguaje que genere figuras geométricas

A continuación, presento el código en C para implementar el analizador léxico que utiliza las expresiones regulares descritas.

Figura 5 1ra parte analizador léxico.

Figura 6 2da parte analizador léxico.

Figura 7 3ra parte analizador léxico.

Este código en C, visto en las figuras 5,6 y 7 implementa un analizador léxico que procesa un código fuente (en este caso, un lenguaje que genera figuras geométricas) para dividirlo en tokens. Utiliza expresiones regulares compiladas para identificar patrones de texto que corresponden a diferentes tipos de tokens, como identificadores, números, operadores y palabras clave. El programa recorre el código fuente carácter por carácter, y cuando encuentra una coincidencia con alguna expresión regular, genera un token con su tipo y valor, que luego se almacena en una lista. El análisis se realiza usando la función regcomp para compilar las expresiones regulares y regexec para verificar si las secuencias de texto coinciden con los patrones. Los tokens se almacenan en una estructura de datos y se imprimen al final del proceso.

Con este analizador ingresamos nuestro código fuente:

circle(x, y, 10); 
rectangle(a, b, 20, 30);

nuestra salida después de analizar nuestro código fuente con nuestro analizador léxico sería la siguiente figura 8:

Figura 8 Salida de token del analizador.

En la figura 8 tenemos la salida que da el analizador léxico después de analizar nuestro código fuente circle(x, y, 10), rectangle(a, b, 20, 30);Vemos que el analizador identificó cada token por su tipo y su valor,esta salida será usada por el analizador sintáctico en la siguiente fase.

Para comprender un poco más el tema dejamos el siguiente video:

https://www.youtube.com/watch?v=P5M5orH6uj8

Referencias:

Compiladores. (s. f.). Google Books. https://books.google.com.gt/books?id=yG6qJBAnE9UC&printsec=frontcover#v=onepage&q&f=false