GUÍA 26-10-26 Teoría de la Computación

NE111 · lunes 26/10/2026 · 16:00-17:15 · Sesión 22

Análisis léxico

DÓNDE SE USA TODO EL BLOQUE

La primera fase de un compilador convierte texto en tokens, y esa fase es literalmente un autómata finito. Es la aplicación directa de las seis sesiones anteriores y la entrada al bloque de compiladores.

EL ANALIZADOR LÉXICO

Recibe el flujo de caracteres del código fuente y produce una secuencia de tokens: identificadores, palabras reservadas, números, operadores y delimitadores. Descarta espacios y comentarios.

CADA TOKEN ES UN LENGUAJE REGULAR

• Identificador: [a-zA-Z_][a-zA-Z0-9_]*
• Entero: [0-9]+
• Real: [0-9]+\.[0-9]+
• Operador: \+|-|\*|/|==|!=|<=|>=

CÓMO SE CONSTRUYE LA HERRAMIENTA

1. Una expresión regular por cada tipo de token.

2. Se unen todas con el operador de unión.

3. Se convierte a AFN con ε por la construcción de Thompson.

4. Se determiniza con la construcción de subconjuntos.

5. Se minimiza con el llenado de tabla.

6. La tabla de transiciones se emite como código.

Eso es exactamente lo que hacen lex y flex. Los cinco pasos ya se vieron por separado; aquí se ve la cadena completa funcionando.

DOS REGLAS DE DESEMPATE

• Coincidencia más larga — ante «indice» se toma el identificador completo, no la palabra «in».
• Prioridad por orden — si dos patrones empatan en longitud, gana el declarado primero. Así las palabras reservadas ganan a los identificadores.

LA TABLA DE SÍMBOLOS

El analizador léxico registra cada identificador en una tabla de símbolos, que las fases posteriores consultan y enriquecen con tipo y ámbito. Es una tabla hash, como la que estás viendo en Estructuras de Datos.

POR QUÉ EL ANÁLISIS LÉXICO NO BASTA

Los paréntesis balanceados no son un lenguaje regular: se demuestra con el lema del bombeo igual que 0ⁿ1ⁿ. Por eso la sintaxis de un lenguaje de programación no se puede describir con expresiones regulares, y hace falta subir a las gramáticas libres de contexto, que es el tema de la próxima sesión.

EJERCICIO

Diseñar el conjunto de expresiones regulares de un lenguaje pequeño y construir el AFD del analizador léxico.