Fase léxica (Primera fase)
La fase léxica en el proceso de compilación es muy importante, ya que es la que se hacer cargo de convertir la entrada de código fuente en una secuencia de tokens, que serán utilizados posteriormente por las fases siguientes del compilador. A este primer paso en el proceso de compilación se le denomina como "análisis léxico" o "escaneo".
Durante esta fase el compilador utiliza un analizador léxico para leer el código fuente carácter por carácter y agruparlos en unidades mínimas denominadas tokens. Estos tokens representan las diferentes construcciones del lenguaje de programación, como palabras reservadas, identificadores, operadores, signos de puntuación, etc.
Token
Es una agrupación de caracteres reconocidos por el analizador léxico que constituyen los símbolos con los que se forman las sentencias del lenguaje y también se les denomina componentes léxicos.
En la siguiente Figura tenemos la especificación de nuestros tokens para nuestro mini lenguaje en español:
 |
| Figura 3. Definición de tokens. |
Tokens del mini lenguaje de C en español
Palabras clave
si→ para condicionales (equivalente aif)sino→ paraelsemientras→ para bucles (equivalente awhile)hacer→ para buclesdo-whileimprime→ para imprimir en consola (equivalente aprintf)regresa→ para funciones (equivalente areturn)
Operadores
- Aritméticos:
+,-,*,/ - Relacionales:
<,>,<=,>=,==,!= - Asignación:
=
- Aritméticos:
Símbolos especiales
{,},(,),;,,
Identificadores y literales
- Identificadores: nombres de variables y funciones (
[a-zA-Z_][a-zA-Z0-9_]*) - Literales numéricos: enteros y reales (
[0-9]+(\.[0-9]+)?) - Literales de cadena: texto entre comillas dobles (
"[^"]*")
- Identificadores: nombres de variables y funciones (
Comentarios
- Una línea:
// comentario - Multilínea:
/* comentario */
- Una línea:
Autómatas para los tokens
Un autómata finito determinista (abreviado AFD) es un autómata finito que además es un sistema determinista; es decir, para cada estado en que se encuentre el autómata, y con cualquier símbolo del alfabeto leído, existe siempre no más de una transición posible desde ese estado y con ese símbolo.(colaboradores de Wikipedia, 2019b)
En la Figura 4 tenemos el autómata para reconocer los identificadores de nuestro lenguaje:
 |
| Figura 4. Autómata de identificadores. |
El ejemplo de la Figura 4 es el autómata para identificadores:
- Estado inicial: leer una letra o guión bajo (
[a-zA-Z_]). - Estado de aceptación: seguir leyendo letras, números o guion bajo (
[a-zA-Z0-9_]*). - Estado de rechazo: cualquier otro carácter.
 |
| Figura 5. Tabla de transiciones. |
1abc), el autómata termina en el estado , indicando un error.Reconocimientos de identificadores
Un identificador está formado por al menos una letra mayúscula o minúscula. La forma de representar mediante expresiones regulares cualquier letra mayúscula o minúscula es: [a-z][A-Z] y le denominamos letra. La forma de representar un número cualquiera es [0-9] y le denominamos número. Para finalizar se define como [otro]cualquier otro símbolo, indicando que ya ha terminado de definirse el identificador. Se encuentra un ejemplo en la figura (3)
¿Qué son las expresiones regulares?
Las expresiones regulares son una
forma de especificar patrones, entendiendo por patrón la forma de describir
cadenas de caracteres. Es la forma de definir los tokens o componentes léxicos
y, como veremos, cada patrón concuerda con una serie de cadenas.
De esta forma, utilizamos las
expresiones regulares para darle nombre a estos patrones.
El lenguaje que se reconoce mediante estas expresiones regulares (r), se denomina lenguaje generado por la expresión regular L(r) (Louden, 2004)
Una expresión regular se puede construir a partir de otras expresiones regulares más simples. Cuando definamos los símbolos mediante los que se especifican las expresiones regulares veremos ejemplos de estos, definiendo letras y dígitos y como un identificador es una combinación de ambos.
Comprobación de tokens de nuestro analizador
En esta parte mostraremos el código de nuestro analizador léxico,este fue implementado en java:
import java.util.*;
import java.util.regex.*;
public class AnalizadorLexico {
// Definición de tokens con sus expresiones regulares
private static final Map<String, String> TOKENS = Map.of(
"PALABRA_CLAVE", "(si|sino|mientras|hacer|imprime|regresa)\\b",
"IDENTIFICADOR", "[a-zA-Z_][a-zA-Z0-9_]*",
"NUMERO", "[0-9]+(\\.[0-9]+)?",
"CADENA", "\"[^\"]*\"",
"OPERADOR", "(\\+|\\-|\\*|\\/|==|!=|<=|>=|<|>)",
"SIMBOLO", "[\\{\\}\\(\\);,]",
"COMENTARIO_LINEA", "//.*",
"COMENTARIO_BLOQUE", "/\\*[\\s\\S]*?\\*/"
);
public static List<Token> analizar(String codigo) {
List<Token> tokens = new ArrayList<>();
String patronGeneral = construirPatronGeneral();
Pattern pattern = Pattern.compile(patronGeneral);
Matcher matcher = pattern.matcher(codigo);
while (matcher.find()) {
for (String tipo : TOKENS.keySet()) {
if (matcher.group(tipo) != null) {
tokens.add(new Token(tipo, matcher.group(tipo)));
break;
}
}
}
return tokens;
}
private static String construirPatronGeneral() {
StringBuilder patron = new StringBuilder();
for (Map.Entry<String, String> entry : TOKENS.entrySet()) {
if (patron.length() > 0) patron.append("|");
patron.append("(?<").append(entry.getKey()).append(">").append(entry.getValue()).append(")");
}
return patron.toString();
}
public static void main(String[] args) {
String codigoEjemplo = """
si (x > 0) {
imprime("Hola mundo");
} // Fin del bloque
""";
List<Token> tokens = analizar(codigoEjemplo);
for (Token token : tokens) {
System.out.println(token);
}
}
}
class Token {
private final String tipo;
private final String valor;
public Token(String tipo, String valor) {
this.tipo = tipo;
this.valor = valor;
}
@Override
public String toString() {
return "Token{" + "tipo='" + tipo + '\'' + ", valor='" + valor + '\'' + '}';
}
}
Ejemplo de entrada:
si (x > 0) {
imprime("Hola mundo");
x = x + 1;
}
Salida esperada de tokens:
Como vemos nuestra entrada de código fuente fue perfectamente analizada y separada por sus tokens por nuestro analizador léxico, de esta manera vemos su funcionamiento
Se comparte el link de un video para entender más a detalle sobre este tema:
Iraic. (2020, 7 mayo). Lenguajes y Autómatas i T4 Análisis Léxico [Vídeo]. YouTube. https://www.youtube.com/watch?v=XZSC9_3qDpU
Lenguajes y Autómatas 1. (2022, 9 julio). 07 1 Análisis Léxico [Vídeo]. YouTube. https://www.youtube.com/watch?v=NYfL9fbORo8
Referencias
Cartagena99. (s.f.). Unidad 2: Análisis léxico. Recuperado de https://www.cartagena99.com/recursos/alumnos/apuntes/ININF2_M4_U2_T2.pdf
Invarato, R. (2019, 20 enero). Expresiones regulares - Regexp - Pattern matching. Jarroba. https://jarroba.com/busqueda-de-patrones-expresiones-regulares/#google_vignette
Comentarios
Publicar un comentario