Clase 9 — Laboratorio 2: Generador de Analizadores Sintácticos CAP/JavaCC

Resumen Ejecutivo

Sesión de laboratorio centrada en CAP (JavaCC), el generador de analizadores sintácticos para Java, equivalente a lo que JFlex es para el léxico. Se explica la estructura completa de un archivo de especificación CAP (7 bloques), el flujo de integración léxico–sintáctico (el parser dirige, el lexer es subrutina), la comunicación mediante objetos Symbol de la librería javacc_runtime, y el algoritmo LALR(1) que CAP genera internamente. Se revisan errores frecuentes de la práctica 1 (léxico) y se anuncia el retraso de la actividad 2 al 19 de mayo.

Conceptos Clave

CAP (JavaCC): Generador de analizadores sintácticos para Java. Toma una especificación con gramática LC y acciones semánticas y produce una clase Parser en Java. ⚠️ EXAMEN
Relación con JFlex: CAP es al sintáctico lo que JFlex es al léxico. Analogía directa: el archivo .jj de CAP equivale al .flex de JFlex.
LALR(1): Algoritmo que usa CAP por debajo. "LookAhead LR": LR(1) compactado unificando estados con mismo núcleo. Más potente que SLR(1), autómata manejable. ⚠️ EXAMEN
Flujo léxico–sintáctico: El parser es el director. Solicita tokens al lexer mediante next_token(). El lexer es una subrutina del sintáctico, no al revés. ⚠️ EXAMEN
Symbol (javacc_runtime): Clase puente entre lexer y parser. El lexer debe retornar objetos Symbol compatibles con lo que CAP espera. Herencia útil: hacer que tu clase Token extienda Symbol.
Acciones semánticas: Código Java ejecutado al hacer una reducción (al final, cuando se reconoce la producción completa, no en mitad). ⚠️ EXAMEN
Archivo de especificación CAP — 7 bloques:
Código Java embebido (importaciones, clase parser_code)
Action code (variables y funciones auxiliares para acciones semánticas)
Declaración de terminales (tokens del léxico)
Declaración de no terminales (elementos de la gramática)
Declaraciones de precedencia y asociatividad
Símbolo inicial
Producciones con acciones semánticas
parser_code vs action_code: parser_code define métodos dentro de la clase Parser (acceso a sus atributos). action_code define variables/constantes auxiliares solo para acciones semánticas.
Conflicto shift-reduce con else: Caso clásico if-then-else. CAP prioriza el shift (asocia else con el if más cercano). Tolerable. ⚠️ EXAMEN
Conflicto reduce-reduce: Nunca aceptable. Indica gramática ambigua; hay que reescribirla.

Desarrollo del Temario

1. Avisos de inicio

Actividad 2 retrasada al 19 de mayo (antes era el 4 de mayo). El motivo es que el temario necesario para hacerla bien (análisis ascendente, reducciones, CAP) no se había visto completo aún.
Se convoca una clase taller (1h 30min, jueves de 15:00 a 16:30) para resolver dudas sobre CAP de forma más interactiva.

2. Feedback de la práctica 1 (léxico JFlex)

Errores detectados en la corrección que hay que evitar en la práctica 2:

Error	Descripción
Copias entre alumnos	Coincidencias exactas en mensajes de error, formato de memoria, código. En la práctica 2 se vigilará más.
Break al primer error	Parar el análisis léxico en el primer error es ineficiente. Se podía seguir leyendo y reportar todos los errores.
Doble salida contradictoria	Imprimir el error por consola con un mensaje distinto al que se escribe en el archivo de salida. Deben ser consistentes.
Atributos privados de Lexer	Acceder a `yyline`, `yycolumn` desde una clase externa sin métodos accesores. Solo el propio `.flex` tiene visibilidad sobre ellos.
main() dentro del .flex	En la práctica 2 el main desaparece: lo dirige el sintáctico. Separarlo en una clase aparte desde ya.

La primera actividad se puntuó con cierta flexibilidad. En la segunda se mirará la independencia del trabajo y la calidad del reporte de errores.

3. CAP: generador de analizadores sintácticos

CAP (o JavaCC, su implementación) hace para el sintáctico lo que JFlex hace para el léxico:

Entrada: archivo de especificación con gramática independiente del contexto + acciones semánticas.
Salida: clase Parser.java lista para compilar e integrar.
Algoritmo generado: LALR(1). Internamente construye el autómata LR(1) canónico y lo compacta unificando estados con mismo núcleo (técnica idéntica a LALR pero automática).

3.1 Relación con el léxico

Fuente ──► JFlex (.flex) ──► Lexer.java
                                  ▲
                           retorna Symbol
                                  │
Fuente ──► CAP (.jj) ────► Parser.java ──► dirige el análisis

El parser llama a lexer.next_token() cada vez que necesita un token. El lexer ya no tiene main propio. ⚠️ EXAMEN

4. Estructura de la especificación CAP (7 bloques)

/* 1. Importaciones y código Java general */
import java_cup.runtime.*;

/* 2. parser_code — métodos dentro de la clase Parser */
parser code {:
    void imprimir(String msg) { System.out.println(msg); }
:}

/* 3. action_code — variables auxiliares de acciones semánticas */
action code {:
    int contadorReducciones = 0;
:}

/* 4. Terminales (tokens que retorna el léxico) */
terminal       PLUS, MINUS, TIMES, DIVIDE;
terminal       LPAREN, RPAREN;
terminal String IDENT;
terminal Integer ENTERO;

/* 5. No terminales */
non terminal   expr, term, factor;

/* 6. Precedencia y asociatividad */
precedence left PLUS, MINUS;
precedence left TIMES, DIVIDE;

/* 7. Producciones con acciones semánticas */
expr ::= expr:e PLUS term:t
         {: imprimir("Reducción: expr → expr + term"); :}
       | term:t
         {: imprimir("Reducción: expr → term"); :}
       ;

Notas importantes de cada bloque

Terminales: Deben coincidir exactamente con los tokens que retorna JFlex. Los nombres los decides tú (puedes cambiarlos para mayor legibilidad, solo tiene que ser consistente entre .flex y .jj).

parser_code: El código aquí se copia dentro de la clase Parser. Tiene acceso a los atributos de la clase. Útil para métodos de reporte o inicialización.

action_code: Variables o constantes auxiliares solo para usar dentro de las acciones semánticas {: ... :}. No es código de la clase Parser, es código auxiliar de las acciones.

Producciones: Las acciones semánticas se ejecutan al completar la reducción (al reconocer la parte derecha entera). Si pones código en mitad de una producción (técnica avanzada), genera conflictos shift-reduce en cascada. Evitarlo. ⚠️ EXAMEN

5. Objetos Symbol: puente léxico–sintáctico

CAP espera que el lexer devuelva objetos compatibles con java_cup.runtime.Symbol. Opciones:

Devolver Symbol directamente: return new Symbol(TokenIds.PLUS);
Herencia (recomendada): Crear tu clase MiToken extends Symbol con atributos propios (lexema, línea, columna). Aprovecha compatibilidad de tipos Java. ⚠️ EXAMEN

// En el .flex, en la sección de acciones:
{identificador} {
    return new MiToken(sym.IDENT, yytext(), yyline, yycolumn);
}

El problema de devolver un int pelado o un String directamente: Java es fuertemente tipificado, no hay conversión implícita. La clase Symbol es el contrato de interfaz entre ambas fases.

6. LALR(1) — qué genera CAP por debajo

Algoritmo	Lookahead	Autómata	Conflictos
LR(0)	0	Pequeño	Muchos
SLR(1)	1 (SIGUIENTE)	Igual que LR(0)	Bastantes menos
LR(1) canónico	1 (en cada elemento)	Muy grande	Mínimos
LALR(1)	1	LR(1) compactado	Mínimos, autómata manejable

CAP genera LALR(1): compacta estados LR(1) que tienen el mismo núcleo, reduciendo el autómata a un tamaño manejable sin perder casi potencia.

No modificar el código Java que genera CAP. Si descubres un error, corrígelo en la especificación .jj y regenera. Si lo corriges en el .java generado, la próxima regeneración sobreescribe el fix.

7. Conflictos y cómo tratarlos en CAP

Shift-reduce: Caso más común. Si lo provoca el if-then-else (dangling else), CAP lo resuelve priorizando el shift (comportamiento estándar en compiladores). ⚠️ EXAMEN

Reduce-reduce: Siempre indica un problema en la gramática. CAP puede compilar con advertencia pero el comportamiento es impredecible. Hay que eliminarlos.

Gramática ambigua — ejemplo: La gramática con una sola producción expr ::= expr PLUS expr | expr TIMES expr | NUMBER genera dos árboles distintos para 3 + 5 * 2 (suma primero o producto primero). Es ambigua. La solución no es factorizar la gramática sino declarar precedencia. ⚠️ EXAMEN

Precedencia y asociatividad de operadores: Declarar con precedence left/right/nonassoc. La primera línea tiene menor precedencia, la última tiene mayor precedencia. ⚠️ EXAMEN

precedence left PLUS, MINUS;   // menor precedencia
precedence left TIMES, DIVIDE; // mayor precedencia (declarado después = más abajo = mayor)

La mayoría de operadores son asociativos por la izquierda. Excepción notable: el operador de asignación (=) es asociativo por la derecha (a = b = c equivale a a = (b = c)). ⚠️ EXAMEN

8. Axioma de la gramática

start with expr;

Indica qué no terminal es la raíz del árbol. CAP no requiere que las producciones estén en ningún orden concreto (distinto a JFlex, donde el orden sí importa). El axioma puede escribirse al final. ⚠️ EXAMEN: diferencia con JFlex.

9. Semántica de atributos y paso de valores

Las acciones semánticas usan etiquetas (:nombre) para acceder a los valores de los símbolos hijos, y result para pasar el valor al símbolo padre.

/* Calculadora simple */
expr ::= expr:e1 PLUS expr:e2
         {: RESULT = e1 + e2; :}
       | NUMBER:n
         {: RESULT = n; :}
       ;

Metáfora de la profesora: el árbol se va "decorando con bolas de Navidad" — cada nodo lleva un valor que sube desde las hojas hacia la raíz. ⚠️ EXAMEN: los valores siempre suben por el árbol, de hijos a padres.

Recomendación: Probar primero la gramática sin acciones semánticas. Si no hay conflictos, añadir las acciones. Mezclar la depuración de gramática con la depuración de semántica complica el diagnóstico.

10. Archivos Java generados por CAP

CAP produce varios archivos Java automáticamente:

Archivo	Contenido
`Parser.java`	Clase `Parser extends lr_parser`. Contiene el método `parse()` y el método `do_action()`.
`do_action()`	Gran `switch/case` con una rama por cada reducción. Ejecuta las acciones semánticas. Generado automáticamente, no tocar.
`sym.java`	Codifica cada token como una constante entera. Útil para la interfaz con el lexer.

El código de parser_code se copia como métodos dentro de Parser. El código de action_code se copia como variables auxiliares usadas dentro de do_action().

La regla de oro: si encuentras un bug, corrígelo en la especificación .jj, regenera, y compila. Nunca edites el .java generado directamente.

Sobre sym.java: Algunos usaron los enteros de sym.java directamente para devolver tokens desde JFlex. Es funcional pero primitivo — en la práctica 2 hay que devolver objetos Symbol enriquecidos para que el sintáctico pueda acceder al lexema, línea y columna.

Preguntas de Autoevaluación

¿Qué papel tiene el parser generado por CAP respecto al lexer generado por JFlex? ¿Cuál dirige al otro?
¿Por qué el lexer no puede tener un main() cuando se integra con CAP? ¿Dónde va el programa principal?
Explica la diferencia entre parser_code y action_code en una especificación CAP. ¿A qué tienen acceso cada uno?
¿Cuándo se ejecuta una acción semántica en CAP: al desplazar un token o al hacer una reducción?
¿Por qué es problemático insertar código semántico en mitad de una producción (entre dos símbolos de la parte derecha)?
¿Qué es un objeto Symbol y por qué el lexer debe devolverlo? ¿Qué ventaja tiene usar herencia con Symbol?
Compara LR(1) canónico con LALR(1): misma potencia, ¿qué diferencia el autómata?
¿Qué hace CAP con un conflicto shift-reduce causado por el if-then-else? ¿Es aceptable?
¿Por qué nunca se debe aceptar un conflicto reduce-reduce? ¿Qué indica sobre la gramática?
Si corriges un error en el archivo Parser.java generado por CAP y luego regeneras, ¿qué pasa con tu corrección?
¿Cómo se declaran la precedencia y asociatividad en CAP? ¿Cuál de dos operadores declarados en líneas distintas tiene mayor precedencia?
¿Por qué el operador de asignación es asociativo por la derecha mientras que + y * son por la izquierda?
Explica con la metáfora del árbol cómo fluye la información en las acciones semánticas. ¿En qué dirección viajan los valores?
¿Para qué sirve RESULT en una acción semántica? ¿Qué ocurre si no lo asignas?
¿Qué contiene do_action() en el Parser.java generado? ¿Por qué no debes modificarlo?
¿En qué se diferencia el orden de las reglas en JFlex vs en CAP? ¿Importa el orden de las producciones?
¿Puede un terminal y un no terminal tener el mismo nombre en CAP? ¿Por qué se desaconseja aunque funcione?
Describe el flujo completo de análisis: desde que se lee el carácter fuente hasta que se ejecuta una acción semántica.