Now I'll generate the study guide from this transcription.

Clase 5 — Introducción al Análisis Sintáctico

Resumen Ejecutivo

Esta sesión introdujo el análisis sintáctico (parsing) como el componente central de los compiladores dirigidos por la sintaxis. Se explicó su relación con el analizador léxico, la construcción de árboles de análisis y las diferencias entre análisis descendente (top-down) y ascendente (bottom-up). También se repasaron conceptos de gramáticas independientes del contexto y su aplicación práctica en el diseño de compiladores.

Conceptos Clave

Compilador dirigido por la sintaxis: Arquitectura de compilador donde el analizador sintáctico es el componente central que gobierna al léxico y afecta a la semántica. ⚠️ EXAMEN
Analizador sintáctico (parser): Componente que verifica que el orden de los tokens entregados por el léxico es válido según la gramática del lenguaje.
Árbol de análisis sintáctico: Representación conceptual del análisis; internamente se implementa como una lista de producciones aplicadas. ⚠️ EXAMEN
Analizador predictivo: Analizador que puede decidir qué regla gramatical aplicar con solo conocer un token por adelantado (lookahead de 1). ⚠️ EXAMEN
Gramática independiente del contexto (GIC): Gramática con terminales, no terminales, axioma y producciones donde el antecedente siempre es un único no terminal.
Autómata con pila: Mecanismo formal que utiliza el analizador sintáctico para reconocer las reglas gramaticales (análogo al AFD del léxico).
Tabla de símbolos: Estructura compartida entre léxico, sintáctico y semántico que almacena información sobre identificadores (nombre, tipo, etc.).
CUP (Construction of Useful Parsers): Generador de analizadores sintácticos para Java, equivalente a YACC/Bison. Genera analizadores ascendentes.

Desarrollo del Temario

1. Rol del analizador sintáctico en el compilador

El analizador sintáctico es el corazón del compilador. En la arquitectura de compiladores dirigidos por la sintaxis, el parser dirige al analizador léxico: le pide tokens cuando los necesita. El léxico no lee por su cuenta, solo avanza cuando el sintáctico se lo solicita. ⚠️ EXAMEN

El flujo es: 1. El sintáctico pide un token al léxico. 2. El léxico lee caracteres hasta reconocer un token y lo devuelve. 3. El sintáctico verifica la estructura y puede pedir otro token. 4. El resultado conceptual es un árbol de análisis que sirve de entrada al analizador semántico.

Ejemplo (Java): Al compilar Java, el analizador sintáctico produce como representación intermedia el bytecode. Luego solo se necesita una JVM para ejecutarlo, sin necesidad de fases adicionales de ensamblado.

2. Diferencia entre errores léxicos, sintácticos y semánticos

Léxico: Solo verifica que las "palabras" sean válidas. Tres if seguidos no generan error léxico. Dos asteriscos seguidos (id ** id) tampoco dan error léxico. ⚠️ EXAMEN
Sintáctico: Verifica que las palabras estén bien colocadas (estructura). Detecta paréntesis desbalanceados, delimitadores faltantes, sentencias mal construidas.
Semántico: Verifica que las estructuras correctas tengan significado válido (ej: que los tipos sean compatibles en una suma).

Ejemplo: La expresión 3 + A es léxicamente correcta (todos son tokens válidos) y sintácticamente correcta (expresión + expresión). Pero semánticamente solo será correcta si A es de tipo entero (o compatible). Si A fuera un booleano, habría error semántico.

3. Criterios de eficiencia del análisis sintáctico

El análisis debe cumplir: ⚠️ EXAMEN 1. Una sola pasada por el código fuente (se lee una vez, carácter a carácter). 2. Tiempo proporcional al tamaño del archivo fuente. 3. Sin retrocesos (backtracking): La elección de regla gramatical debe poder decidirse con un número limitado de tokens por adelantado. 4. Predictivo con un solo token de lookahead: Con conocer un componente léxico por adelantado, se debe poder decidir por qué regla continuar. ⚠️ EXAMEN

Ejemplo: Si el analizador lee un número 2 y luego un -, solo con ver el - sabe que debe aplicar la regla \(E \rightarrow E - T\) y no \(E \rightarrow E + T\). No necesita retroceder.

4. Gestión de errores sintácticos

Tres estrategias de recuperación de errores: ⚠️ EXAMEN

Modo pánico: Busca un punto de sincronización (;, }, )) y descarta todo lo intermedio. Es el más fácil de implementar.
Recuperación a nivel de frase: Detecta el tipo de estructura en la que ocurre el error y delimita el problema con mayor precisión.
Producciones de error: Se añaden reglas gramaticales que modelan errores frecuentes (ej: if sin paréntesis izquierdo). Si la gramática entra por una regla de error, la acción semántica asociada informa del error exacto.

Ejemplo de producción de error: Si es muy habitual que en un if se omita un paréntesis, se crea una regla errónea específica para ese caso. Cuando el parser entra por esa regla, sabe exactamente qué error reportar: "falta paréntesis izquierdo en la condición del if".

5. Gramáticas independientes del contexto (repaso)

Una GIC se define como \(G = (T, N, S, P)\): ⚠️ EXAMEN - \(T\): Conjunto de terminales (= componentes léxicos/tokens). - \(N\): Conjunto de no terminales (estructuras gramaticales). - \(S\): Axioma o símbolo inicial. - \(P\): Conjunto de producciones (reglas), donde la parte izquierda es siempre un único no terminal.

Ejemplo de gramática para expresiones aritméticas: - \(E \rightarrow E + T \mid E - T \mid T\) - \(T \rightarrow T * F \mid T / F \mid F\) - \(F \rightarrow (E) \mid id\)

Esta factorización en niveles (E, T, F) garantiza la precedencia de operadores: primero paréntesis, luego multiplicación/división, finalmente suma/resta. Si se usara solo \(E \rightarrow E + E \mid E * E \mid id\), la gramática sería ambigua y no respetaría precedencias.

6. Precedencia de operadores mediante factorización gramatical

Agrupar operadores en distintos niveles de no terminales establece la precedencia: ⚠️ EXAMEN

Nivel	No terminal	Operadores	Precedencia
Más bajo	\(E\) (Expresión)	\(+\), \(-\)	Menor
Medio	\(T\) (Término)	\(*\), \(/\)	Media
Más alto	\(F\) (Factor)	\((\ )\), \(id\)	Mayor

No se puede sumar hasta haber procesado todos los términos (que pueden contener multiplicaciones), y no se puede multiplicar hasta haber procesado los factores (que pueden contener paréntesis).

7. Análisis descendente (Top-Down) vs. ascendente (Bottom-Up)

Descendente (Top-Down): ⚠️ EXAMEN - Construye el árbol desde la raíz hacia las hojas. - Expande siempre el no terminal más a la izquierda primero. - Adecuado para gramáticas sencillas.

Ascendente (Bottom-Up): ⚠️ EXAMEN - Construye el árbol desde las hojas hacia la raíz. - Busca agrupar terminales que coincidan con la parte derecha de una producción para "reducirlos" al no terminal de la parte izquierda. - Utilizado por la mayoría de lenguajes de programación reales. - CUP genera analizadores ascendentes.

Ejemplo descendente para id + id * id: Se parte de \(E\), se expande a \(E + T\), luego \(E\) se reduce a \(T \rightarrow F \rightarrow id\). Después se procesa \(T\) expandiendo a \(T * F\), etc.

Ejemplo ascendente para la misma entrada: Se lee id, se reduce a \(F\), luego a \(T\), luego a \(E\). Se lee +, se lee el siguiente id, se reduce a \(F\), luego a \(T\). Se lee *, se lee id, se reduce a \(F\). Se aplica \(T \rightarrow T * F\), y finalmente \(E \rightarrow E + T\).

8. Relación léxico-sintáctico-semántico y tabla de símbolos

El flujo completo: ⚠️ EXAMEN 1. Léxico: Reconoce tokens. Si encuentra un identificador, lo guarda en la tabla de símbolos (solo el nombre). 2. Sintáctico: Verifica estructura. Cuando lee una declaración (ej: int A), actualiza la tabla añadiendo el tipo al identificador. 3. Semántico: Las acciones semánticas se incorporan a las reglas del sintáctico. Consultan la tabla de símbolos para verificar compatibilidad de tipos, etc. 4. Generación de código: Recupera los identificadores de la tabla para traducir las operaciones al código intermedio.

Ejemplo con Python vs Java: En Java (fuertemente tipado), una variable declarada como int siempre ocupa el mismo espacio en memoria. En Python, al no declararse tipos, la tabla de símbolos debe actualizarse con cada asignación, ya que el tipo puede cambiar dinámicamente.

9. Herramientas: JFlex + CUP

Fase	Herramienta	Formalismo	Autómata
Léxico	JFlex	Expresiones regulares	Autómata Finito Determinista (AFD)
Sintáctico	CUP	Gramática independiente del contexto	Autómata con Pila
Semántico	Código Java manual	Gramáticas de atributos	Acciones en estados finales del autómata con pila

CUP es el equivalente sintáctico de JFlex: se le especifica la gramática y genera automáticamente el analizador. Sin embargo, las acciones semánticas deben programarse manualmente.

Preguntas de Autoevaluación

¿Por qué se dice que los compiladores modernos son "dirigidos por la sintaxis"? ¿Qué papel juega el analizador sintáctico respecto al léxico?
¿Qué significa que un analizador sea "predictivo con un token de lookahead"? ¿Por qué es crucial para la eficiencia del compilador?
Explica las tres estrategias de recuperación de errores sintácticos (modo pánico, nivel de frase, producciones de error) y sus ventajas/desventajas.
Dada la gramática \(E \rightarrow E + E \mid E * E \mid id\), ¿por qué es ambigua? ¿Cómo se factoriza para respetar la precedencia de operadores?
¿Cuál es la diferencia fundamental entre un análisis descendente y uno ascendente? ¿Qué tipo genera CUP?
¿Qué información almacena la tabla de símbolos y en qué fases del compilador se consulta/modifica?
Si el analizador léxico recibe la entrada id ** id, ¿dará error léxico o sintáctico? Justifica tu respuesta.
¿Por qué el análisis sintáctico debe evitar retrocesos (backtracking)? ¿Qué implicaciones tendría en un programa con millones de líneas?

Guía generada automáticamente a partir de transcripción con faster-whisper + Claude Opus 4.6.