Caracteristicas generales:
CUP2 es la versión más moderna del generador de parsers CUP, el cual está escrito completamente en Java y como mejora adicional respecto a CUP, permite utilizar gramaticas LALR(1), LR(0), LR(1) y LARL(1) por citar a unas cuantas.

A diferencia de muchos otros generadores de parsers tradicionales (incluyendo a CUP), CUP2 no crea el código fuente del parser basándose en una definición "separada" de la gramática del lenguaje, en vez de eso utiliza las llamadas de la API de Java, combinado con estructuras de datos para representar la información relacionada con la gramatica. Lo cual significa que todo está hecho en Java puro.

Definición de gramatica:

CUP2 utiliza estructuras de datos en Java para definir la gramatica, para hacer esto una clase de "especificación" ha de ser creada, extendiendo la clase "edu.tum.cup2.spec.CUPSpecification".

public class miClase extends CUPSpecification

Un ejemplo básico de una gramática para expresiones aritméticas simples, con precedencia de operadores:

e ->  e + t
  |   t
f ->  t * f
  |   f
f ->  ( e )
  |   numero
  
Una gramatica consiste de una lista de producciones, las cuales son creadas invocando al método "prod" de CUP2. El método espera a un no terminal del lado izquierdo y una lista de simbolos para cada alternativa del lado derecho, agrupadas por medio del método "rhs". Por último, las producciones creadas de esta forma son declaradas como gramatica al pasarlas como parametros al llamar al método "grammar" del constructor de nuestra clase del parser.

grammar(
  prod(e,       rhs(e, SUMA, t),
                rhs(t)          ), 
  prod(t,       rhs(t, MULTIPLICACION, f),
                rhs(f)          ),
  prod(f,       rhs(PARENTESISABRE, e, PARENTESISCIERRA),
                rhs(numero)     )
);

Acciones semánticas:

Para indicarle al parser como construír un arbol de análisis sintáctico con las producciones dadas en el ejemplo anterior utilizamos las llamadas "acciones semánticas", las cuales se obtienen al extender las producciones, agregandoles las acciones sintacticas. Estas acciones son llamadas cada vez que la producción correspondiente es reducida, el valor que retorna cada acción es relacionado entonces con la producción del lado izquierdo. Debido a que pueden existir variaciones en las producciones del lado derecho, es necesario especificar los diferentes valores de retorno para los no terminales, lo cual se especifica creando clases vacías en el cuerpo de nuestra clase del parser, por ejemplo:

public class numero extends SymbolValue<Integer>{};
public class e extends SymbolValue<Expression>{};
public class f extends SymbolValue<Expression>{};
public class t extends SymbolValue<Expression>{};

Para cada símbolo con valor, creamos una instancia de la clase "edu.tum.cup2.semantics.SymbolValue" parametrizada con el valor apropiado de la clase. El nombre de esta instancia debe de ser exáctamente el mismo que el simbolo.

Creación y utilización del parser:

Para crear y utilizar el parser el primer paso es crear la tabla de parseo para luego inicializar el parser con ella. Esto se logra creando un objeto de tipo LRParsingTable e inicializandolo de la siguiente manera:

LRParsingTable tabla = new LR1Generator(new miClase()).getParsingTable();

Esto nos creara una tabla de parseo utilizando el generador para un analisis LR(1).

Ahora ya podemos darle datos de entrada al parser, ya sea de forma manual o utilizando el analisis léxico proveido por JFlex.

Expression resultado = (Expression)parser.parse(new GeneratedScanner(new FileReader("entrada.txt")));

Declaración de simbolos:

Para usar los simbolos del lenguaje, estos tienen que ser previamente declarados en Java, lo cual se logra creando un nuevo enumerador llamado "Terminals" (de terminales) y otro llamado NonTerminals (no terminales), los cuales implementaran las interfaces Terminal y NonTerminal respectivamente. Cada uno de ellos contendra los nombres de los simbolos correspondientes para cada uno, por ejemplo:

public enum Terminals implements Terminal{
  SUMA, MULTIPLICACION, PARENTESISABRE, PARENTESISCIERRA, NUMERO;
}

public enum NonTerminals implements NonTerminal{
  e, t, f;
}

Definición de reglas gramaticales:

Una gramatica consiste de un conjunto de producciones, las cuales contienen un no terminal de lado izquierdo y una lista de simbolos en el lado derecho, CUP2 provee las clases e interfaces Grammar, Production y Symbol (Terminal y NonTerminal) para representar la gramatica. Por ejemplo:

e ->  e + t
  |   t
f ->  t * f
  |   f
f ->  ( e )
  |   numero
  
grammar(
  prod(e,       rhs(e, SUMA, t),
                rhs(t)          ), 
  prod(t,       rhs(t, MULTIPLICACION, f),
                rhs(f)          ),
  prod(f,       rhs(PARENTESISABRE, e, PARENTESISCIERRA),
                rhs(numero)     )
);

Asignación de acciones semánticas a las reglas gramaticales:

Para calcular cualquier valor o construir una representación de la entrada del parser es necesario equipar al mismo con acciones semanticas, las cuales son métodos de Java que contienen código que es ejecutado cada vez que el parser reduce los simbolos reconocidos hasta el momento siguiento las reglas de la gramatica.

Son subclases anonimas de la clase "Action", utilizando el método "a". Los parametros representan los simbolos del lado derecho de la produccion, el retorno de la funcion representa al lado izquierdo de la producción, además el retorno ha de ser del mismo tipo que el asociado con la producción del lado izquierdo. Las acciones son declaradas como parametros del constructor del método prod, justamente después del simbolo del lado derecho al que pertenecen, por ejemplo:

prod(
  expr,rhs(e,SUMAR,e),
    new Action(){
      public Integer a(Integer a, Integer b){
        System.out.println("e -> e SUMAR e");
        System.out.println("  a = "+a);
        System.out.println("  b = "+b);
        return a+b;
    }}
)

Eliminación de ambiguedad en las producciones:

CUP2 provee un constructor util al momento del parseo con gramaticas ambiguas, el cual permite especificar las precedencias y asociatividades de simbolos terminales en particular. Las precedencias pueden ser consideradas como avisos para el automata, para decirle por donde ha de reducir en el caso de ambiguedad.

En CUP2 se puede definir la asociatividad de 3 formas, left (izuqierda), right (derecha), nonassoc (sin asociatividad).

Para especificar las precedencias y asociatividades en CUP2 es necesario llamar al método "precedences" del constructor de la clase de especificación. Por ejemplo:

precedences(
  left(RESTAUNITARIA),
  left(MULTIPLICACION),
  left(SUMA, RESTA)
);

También es posible definir precedencia exclusiva para un simbolo en una producción dada, la cual sería de la siguiente forma:

grammar(
  prod(res,         rhs(expr, COMA)), 
  prod(expr,        rhs(NUMERO),
                    rhs(expr, MULTIPLICACION, expr),
                    rhs(expr, SUMA, expr),
                    rhs(expr, RESTA, expr),
               prec(rhs(RESTA, expr), RESTAUNITARIA),
                    rhs(PARENTESISABRE, expr, PARENTESISCIERRA))
);

Conexión con JFlex:

Para conectar a un scanner como JFlex con CUP2 es necesario que la clase del scanner implemente la interfaz "edu.tum.cup2.scanner.Scanner", la cual contiene solamente un método:

public ScannerToken<Object> readNextTerminal() throws java.io.IOException;

Este método es invocado cada vez que CUP2 necesita procesar un nuevo simbolo, entonces el scanner retorna el próximo terminal de la secuencia de entrada. Los simbolos son instancias de la clase "edu.tum.cup2.scanner.ScannerToken<T>", parametrizada por la clase T del valor asociado al simbolo (o Object para tokens sin valor).

Después de implementar la clase anterior, la especificación de CUP2 creada está lista pra ser transformada en un parser, para ello necesitamos instanciar un generador de parser con el algoritmo indicado (pueden ser LR1, LR1 a LAL, LALR1 y LR0), se crea la tabla de parseo, se alimenta el manejador del parser con la tabla de parseo y por último se ejecuta el manejador del parser con la entrada del scanner. Por ejemplo

try
  {
    LALR1Generator generador = new LALR1Generator(new miClase());
    LRParsingTable tabla = generador.getParsingTable(); 
    LRParser parser = new LRParser(tabla);
  }
  catch (GeneratorException ex)
  {
//Error en la creacion
  }
  catch(Exception ex)
  {
//Error en el parseo
  }

Manejo y recuperación de errores:


Ejemplo: