jueves, octubre 07, 2010

Ejemplo de antlr - Campeonato de fútbol

En el siguiente ejemplo en antlr se va a trabajar el problema de generar una tabla de puntuación para un torneo de fútbol. Se han utilizado solamente 4 equipos de fútbol, pero el ejemplo se puede modificar para permitir más equipos, bien sea determinados con anterioridad o no.

Tanto las reglas léxicas como sintácticas son relativamente sencillas, pues solo hay dos componentes léxicos principales: el equipo y el número de goles anotado; en el caso de las reglas sintácticas, también son dos: la que define el torneo como una secuencia de partidos, y la que define el partido como una combinación de dos equipos con dos números.

Las reglas semánticas implementadas en la gramática son tres: una para inicializar la tabla de resultados; la segunda para registrar en la tabla el resultado de un partido; la tercera para ordenar y mostrar la tabla de resultados al final del proceso.

En el ejemplo se muestra la forma de importar librerias de clase desde java y la definición de elementos del lenguaje: la clase Equipo con sus atributos y métodos, así como los métodos que implementan las acciones semánticas: crearTabla, registrarPartido y mostrarTabla.

grammar Campeonato;
// Codigo en lenguaje anfitrion
@header{
 import java.util.Vector;
 import java.util.Collections;
}
@members{
 class Equipo implements Comparable<Equipo> {
  String nombre;
  int  pj;
  int  pg;
  int  pe;
  int  pp;
  int  gf;
  int  gc;
  int  ptos;
  int dif() { return gf-gc; }
  Equipo(String n) { nombre = n;}
  public String toString() { 
   return String.format("\%-20s \%2d \%2d \%2d \%2d \%2d \%2d \%2d \%4d", 
                         nombre, pj, pg, pe, pp, gf, gc, dif(), ptos); 
  }
  public boolean equals(Object o) {
   Equipo tmp = (Equipo) o;
   if(this.nombre.equals(tmp.nombre)) return true;
   else return false;
  }
  public int compareTo(Equipo tmp) {
   if(this.ptos < tmp.ptos) return -1;
   else if(this.ptos > tmp.ptos) return 1;
   else if(this.dif() < tmp.dif()) return -1;
   else if(this.dif() > tmp.dif()) return 1;
   else if(this.pg < tmp.pg) return -1;
   else if(this.pg > tmp.pg) return 1;
   else return 0;
  }
 }
  
 Vector<Equipo> tabla = new Vector<Equipo>();
  
 void crearTabla() {
  tabla.add(new Equipo("Arsenal"));
  tabla.add(new Equipo("Chelsea"));
  tabla.add(new Equipo("Liverpool"));
  tabla.add(new Equipo("Manchester City"));
 }
  
 void registrarPartido(String ne1, String ge1, String ne2, String ge2) {
  int ng1 = Integer.parseInt(ge1);
  int ng2 = Integer.parseInt(ge2);
  Equipo e1 = new Equipo(ne1);
  Equipo e2 = new Equipo(ne2);
  e1=tabla.get(tabla.indexOf(e1));
  e2=tabla.get(tabla.indexOf(e2));
  e1.pj++;  e2.pj++  ;
  e1.gf+=ng1; e2.gf+=ng2;
  e1.gc+=ng2; e2.gc+=ng1;
  if(ng1>ng2)   { e1.pg++; e2.pp++; e1.ptos+=3; }
  else if(ng1<ng2) { e1.pp++; e2.pg++; e2.ptos+=3; }
  else     { e1.pe++; e2.pe++; e1.ptos++; e2.ptos++; }
 }
  
 void mostrarTabla() {
  Collections.sort(tabla);
  Collections.reverse(tabla);
  System.out.println("Equipo               PJ PG PE PP GF GC DG PTOS");
  System.out.println("-------------------- -- -- -- -- -- -- -- ----");
  for(Equipo e: tabla) System.out.println(e);
 }
}
 
// Componente lexicos
fragment DIGITO  : '0'..'9' ;
fragment LETRA   : 'A'..'Z'|'a'..'z';
NUMERO  : DIGITO DIGITO? ;
EQUIPO  : LETRA+ ((' ' LETRA) => ' ' LETRA+)*;
ESPACIO  : (' '|'\t'|'\n') { skip(); };
 
// Componentes sintacticos
torneo : { crearTabla(); } 
    partido+ 
    { mostrarTabla(); }
        ;
         
partido  : a=EQUIPO b=NUMERO c=EQUIPO d=NUMERO
          { registrarPartido($a.text, $b.text, $c.text, $d.text); }
        ;

8 comentarios:

  1. Creería conveniente cambiar la regla
    EQUIPO : LETRA (' ' LETRA )*;
    por
    EQUIPO : LETRA (LETRA ' '?)*;
    Pues con esta se aceptan nombres con espacios, pero Al correr este programa en AntLr aparece el siguiente error Cannot Launch the debugger Tab. Time-out waiting to connect to the remote parser. Me gustaría saber por qué se da esto.

    -Cesar

    ResponderBorrar
  2. Hola, muchas gracias por el comentario. Realmente acabo de leerlo y notar que hay un error en mi código debido al programa que uso para convertirlo a HTML, y ya lo corregí. La idea es que la regla de equipo deberia ser
    EQUIPO: LETRA+ (' ' LETRA+)* teniendo en cuenta que hay nombres de equipos que tienen más de una palabra (por ejemplo: "Real Madrid", "Estudiantes de la Plata", etc).

    En el caso de tu error, a mi me ha pasado lo mismo cuando he intentado volver a lanzar el debugger sin haber regenerado el código en java, y la única solución que me ha funcionado es la de cerrar AntlrWorks y volverlo a cargar.

    En la regla de EQUIPO hay un cambio adicional, y es debido a que el hecho de que después de una secuencia de letras el encontrar un espacio en blanco no es garantía de que siga otra secuencia de letras, entonces se deben usar predicados sintácticos para que revise antes de entrar a esa parte de la regla si después del espacio viene una letra o no. La regla queda entonces asi:

    EQUIPO : LETRA+ ( (' ' LETRA)=> ' ' LETRA+)*

    Muchas gracias por el comentario

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...