sábado, 15 de octubre de 2011

Ejemplo sencillo con JavaCC de un analizador léxico y sintáctico

Java
Hay ocasiones en que necesitamos procesar una determinada expresión, por ejemplo para hacer una búsqueda por una serie de criterios obtenidos de la misma. La forma habitual es hacerlo creando un algoritmo específico más o menos complejo según lo sea la expresión con varios splits, expresiones regulares, condiciones, bucles, etc..., que normalmente resulta en código ofuscado difícil de desarrollar, mantener, entender lo que hace y poco flexible ante cambios. Esta es la primera opción que se nos ocurre pero no es la mejor forma de hacerlo como veremos en esta entrada.

Cuando nos enfrentamos a un problema de procesar una expresión debemos tener en cuenta primeramente dos cosas: cual es su léxico (las palabras que lo forman) y su sintaxis (las reglas que definen el orden del léxico). Más tarde por otra parte para procesar la expresión necesitaremos de acciones léxicas y sintácticas que es código que se ejecutará para realizar las tareas que necesitemos al procesar la expresión.

Para facilitar la tarea existen los compiladores como resultado de la invención de los primeros lenguajes y aunque parecen algo complejo de hacer no lo son tanto como desarrollar un algoritmo específico. JavaCC es una herramienta que nos permite definir el léxico de una expresión o lenguaje, la sintaxis del mismo y las acciones léxicas y sintácticas generando posteriormente con la definción de estas cosas una serie de archivos .java con el código fuente de un analizador léxico, sintáctico y otra serie de archivos .java de utilidad para los mismos.

Supongamos que tenemos una aplicación en la que el usuario tiene una caja de búsqueda en la que puede introducir una serie de palabras separadas por espacios, en la que también puede agrupar varias palabas rodeándolas con " y también puede introducir fechas en varios formatos y con distintos separadores para el día, mes y año pudiendo especificar día, mes y año, solo mes y año, solo el mes o solo el año, por ejemplo dd.MMM.yyyy, dd/MMMM/yyyy, MMMM-dd-yyyy, MMM.yyyy, MMM, yyyy, ... Para complicarlo aún más los meses pueden estar en diferentes idiomas. Un ejemplo de expresión podría ser: «"real madrid" enero.2012 febrero.2012 fútbol» en la que intenta buscar elementos relacionados con el real madrid y fútbol y en los meses de enero o febrero de 2012.

Veamos el código fuente de nuestro pequeño compilador cuya misión sera interpretar la expresión de la mejor de las formas y devolver un objeto org.hibernate.criterion.Criterion con el que podremos hacer una búsqueda en Hibernate según los criterios de la expresión. El compilador está dividido en varias partes:

PARSER_BEGIN y PARSE_END: define el nombre de nuestro analizador e incluye métodos de utilidad (en perfecto código Java) que será incluidos en el analizador sintático sin modificar y que podremos usar desde las acciones sintácticas. Los métodos importantes de esta primera parte son los constructores (JavaCC inserta unos pero como vemos podemos definir más), el método main, buildCriterionTermino y buildCriterionFecha que construirán un Criterion cuando el analizador sintáctico detecte un término o fecha respectivamente, la misión principal de nuestro compilador. Estos métodos no tienen mayor complicación son puro código Java. (en azul).

SKIP y TOKEN: esta parte es la que define el analizador léxico con las palabras de nuestra expresión o lenguaje. Ahí están la forma de las fechas, los términos, el día, mes y año, los separadores. Básicamente son una forma de expresiones regulares para definir cada uno de ellos (en morado).

procesarQuery, procesar, termino, fecha: Son propiamente los métodos del analizador sintáctico y van a definir la sintáxis de nuestro lenguaje. procesar contiene una de las partes más importantes ya que es el punto de partida, va cogiendo los tokens proporcionados por el analizador léxico (que genera JavaCC) y determina si es una fecha, término o algo desconocido. Según lo detectado se ejecuta el bloque de código posterior que va entre {} y que constituye una acción sintáctica. Como se ve la acción sintáctica es perfecto código Java y puede usar las variables definidas en el bloque procesar como ct, ft y r. Después de procesar todos los términos de la expresión se ejecuta otra acción sintáctica que agrupa todos los Criterion recogidos en ct, cf en uno solo y que será lo que devuelve el analizador (en verde).

En la acción sintáctica de termino tenemos que tener en cuenta que el término puede ser un mes (enero, ...) por lo que se intenta procesar como una fecha con buildCriterionFecha y si devuelve algo es que se trataba de un mes sino se procesará como un termino con buildCriterionTermino.

¿Por qué se trata un elemento DESCONOCIDO? Porque sino el analizador sintáctico daría un excepción al no saber lo que es, teminaría y no devolvería nada. De esta forma conseguimos que si una expresión que no se entiende se ignore y se devuelvan al menos el resto de expresiones en el Criterion. Este será el caso de un término fecha mal expresado como «01.enero/2012» donde mezcla diferentes separadores en la misma fecha. Tal como están definidos los tokens, el analizador léxico no sabría que es.

Y eso es lo principal de nuestro compilador. No es tan complicado hacer uno como podría parecer a priori, sin duda mucho más fácil que hacer un algoritmo específico para ello incluso para una expresión tan simple como la tratada, ahora imagínate una que pueda ser como «(<expr> or (<expr>and (<expr>or <expr>) or <expr>))».

Esta es una de esas herramientas muy útilies y con la cual sabiendo usarla o al menos tener conocimiento de ella nos puede ahorrar mucho tiempo y conseguir hacer las cosas mejor. Además y dado que lo que genera como resultado son una serie de archivos .java podremos utilizarlos en cualquier entorno, como en alguna administración pública cuyo nombre no citaré aquí y en la que no esta permitido usar librerías no homologadas por ellos, dado que se trata de código fuente y que no tiene dependencias sobre otras librerías no tendremos ningún problema en usar JavaCC en casos como este.

Para compilar el compilador podemos hacerlo con ant con la siguiente tarea (también podemos utilizar los propios comandos de JavaCC):


<javacc target="src/main/java/com/blogspot/elblogdepicodev/jj/Buscador.jj"
 outputdirectory="src/main/java/com/blogspot/elblogdepicodev/jj/buscador"
    javacchome="/home/[user]/javacc-5.0"/>

Los archivos generados serían:

  • Buscador.java
  • BuscadorConstants.java
  • BuscadorTokenManager.java
  • ParseException.java
  • SimpleCharStream.java
  • Token.java
  • TokenMgrError.java


// Buscador.jj
options {
 STATIC = false;
}

PARSER_BEGIN(Buscador)
package com.blogspot.elblogdepicodev.jj.buscador;

import java.io.InputStream;
import java.io.Reader;
import java.io.StringReader;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.List;
import java.util.Locale;

import org.hibernate.criterion.Criterion;
import org.hibernate.criterion.Restrictions;
import org.hibernate.type.IntegerType;
import org.hibernate.type.Type;

public class Buscador {
 private static final String[] FORMATOS_FECHAS = new String[] { 
  "d/MMM/yyyy", "d/MMMM/yyyy", "MMM/d/yyyy", "MMMM/d/yyyy", "MMM/yyyy", "MMMM/yyyy",
  "d.MMM.yyyy", "d.MMMM.yyyy", "MMM.d.yyyy", "MMMM.d.yyyy", "MMM.yyyy", "MMMM.yyyy",
  "d-MMM-yyyy", "d-MMMM-yyyy", "MMM-d-yyyy", "MMMM-d-yyyy", "MMM-yyyy", "MMMM-yyyy",
  "MMM", "MMMM", "yyyy" 
 };

 private Locale locale;

 public Buscador(Locale locale) {
  this(new StringReader(""), locale);
 }
 
    public Buscador(InputStream is, String encoding, Locale locale) {
  this(is, encoding);
                this.locale = locale;
 }
 
 public Buscador(Reader r, Locale locale) {
  this(r);
        this.locale = locale;
 }

    public static void main(String[] args) throws ParseException, TokenMgrError {
     StringBuffer sb = new StringBuffer();
     for(int i = 0; i < args.length; ++i) {
   if (i > 0) {
    sb.append(" ");
      }
   sb.append(args[i]);
     }

     Buscador parser = new Buscador(new Locale("es"));
     Criterion criterion = parser.procesarQuery(sb.toString());
     System.out.println(criterion);
 }
 
 // Utilidades
 private Criterion or(List<Criterion> criterions) {
  Criterion lhs = null;
  for (Criterion criterion : criterions) {
   if (lhs == null) {
    lhs = criterion;
   } else {
    lhs = Restrictions.or(lhs, criterion);
   }
  }
  return lhs;
 }

 private Criterion and(List<criterion> criterions) {
  Criterion lhs = null;
  for (Criterion criterion : criterions) {
   if (lhs == null) {
    lhs = criterion;
   } else {
    lhs = Restrictions.and(lhs, criterion);
   }
  }
  return lhs;
 }
 
 private Criterion buildCriterionTermino(String term) {
  List<Criterion> coincidencias = new ArrayList<Criterion>();
  
  String t = "%" + term + "%";

  coincidencias.add(Restrictions.ilike("nombre", t));
  coincidencias.add(Restrictions.ilike("ciudad", t));
  coincidencias.add(Restrictions.ilike("direccion", t));

  Criterion criterio = or(coincidencias);
  
  return criterio; 
 }
 
 private Criterion buildCriterionFecha(String term) {
  Criterion criterio = null;
  
  for (int i = 0; i < FORMATOS_FECHAS.length; ++i) {
   String formatoFecha = FORMATOS_FECHAS[i];
   SimpleDateFormat sdf = new SimpleDateFormat(formatoFecha, locale);

   // Fecha
   try {
    Date fecha = sdf.parse(term);

    Calendar calendario = Calendar.getInstance(locale);
    calendario.setTime(fecha);

    switch (i) {
    case 0:
    case 1:
    case 2:
    case 3:
    case 6:
    case 7:
    case 8:
    case 9:
    case 12:
    case 13:
    case 14:
    case 15:
     // Día, mes, año
     criterio = Restrictions.sqlRestriction("(day({alias}.fecha) = ? and month({alias}.fecha) = ? and year({alias}.fecha) = ?)", new Object[] {
       calendario.get(Calendar.DAY_OF_MONTH), calendario.get(Calendar.MONTH) + 1, calendario.get(Calendar.YEAR) }, new Type[] { IntegerType.INSTANCE,
       IntegerType.INSTANCE, IntegerType.INSTANCE });
     break;
    case 4:
    case 5:
    case 10:
    case 11:
    case 16:
    case 17:
     // Mes, año
     criterio = Restrictions.sqlRestriction("(month({alias}.fecha) = ? and year({alias}.fecha) = ?)", new Object[] {
       calendario.get(Calendar.MONTH) + 1, calendario.get(Calendar.YEAR) }, new Type[] { IntegerType.INSTANCE, IntegerType.INSTANCE });
     break;
    case 18:
    case 19:
     // Mes
     criterio = Restrictions.sqlRestriction("month({alias}.fecha) = ?", calendario.get(Calendar.MONTH) + 1, IntegerType.INSTANCE);
     break;
    case 20:
     // Año
     criterio = Restrictions.sqlRestriction("year({alias}.fecha) = ?", calendario.get(Calendar.YEAR), IntegerType.INSTANCE);
     break;
    default:
     assert (false);
     break;
    }
   } catch (java.text.ParseException e) {
   }
   
   if (criterio != null) {
    break;
   }
  }

  return criterio;
 }
 
 private class CriterionInfo {
  public boolean isFecha;
  public Criterion criterio; 
 }
}
PARSER_END(Buscador)

SKIP : { " " | "\t" | "\n" | "\r" | "\r\n" }

TOKEN : { < #NO_SKIP : ~[" ", "\t", "\r", "\n"] > }
TOKEN : { < #SEP1 : "/" > }
TOKEN : { < #SEP2 : "." > }
TOKEN : { < #SEP3 : "-" > }
TOKEN : { < #SEP : (<sep1> | <sep2> | <sep3>) > }
TOKEN : { < #LETRA : ~[" ", "\t", "\r", "\n", "/", ".", "-"] > }
TOKEN : { < #NUM : ["0"-"9"] > }
TOKEN : { < #MES : (<letra>)+ > }
TOKEN : { < #DIA : (<num> | <num><num>) > }
TOKEN : { < #ANO : (<num><num><num><num>) > }

TOKEN : { < FECHA : (
 <dia><sep1><mes><sep1><ano> | <mes><sep1><dia><sep1><ano> | <mes><sep1><ano> | 
 <dia><sep2><mes><sep2><ano> | <mes><sep2><dia><sep2><ano> | <mes><sep2><ano> |
 <dia><sep3><mes><sep3><ano> | <mes><sep3><dia><sep3><ano> | <mes><sep3><ano> |
 <num><num><num><num>) > }
TOKEN : { < TERMINO : ("\""(~["\""])+"\"" | (<letra>)+) > }
TOKEN : { < DESCONOCIDO : (<no_skip>)+ > }

Criterion procesarQuery(String query) :
{
 Criterion criterio = null;

 ReInit(new StringReader(query));
}
{
 criterio = procesar()
 {
  return criterio;
 }
}

Criterion procesar() :
{
 List<Criterion> ct = new ArrayList<Criterion<();
 List<Criterion> cf = new ArrayList<Criterion<();

 Criterion criterio = null;
 CriterionInfo criterioInfo = null;
 Token t = null;
}
{
 (
  criterio = fecha()
  {
   if (criterio != null) {
    cf.add(criterio);
   }
   //System.out.println(criterio);
  }
 |
  criterioInfo = termino() 
  {
   criterio = criterioInfo.criterio;
   if (criterio != null) {
    if (criterioInfo.isFecha) {
     cf.add(criterio);
    } else {
     ct.add(criterio);
    }
   }
   //System.out.println(criterio);
  }
 |
  t = <desconocido>
  {
   //System.out.println(t.image);
  }
 )*
 <eof>
 {
  List<Criterion> r = new ArrayList<Criterion>();
  if (!ct.isEmpty()) {
   r.addAll(ct);
  }
  if (!cf.isEmpty()) {
   r.add(or(cf));
  }
  return (r.isEmpty())?null:and(r);
 } 
}

CriterionInfo termino() :
{
 Token t = null;
}
{
 t = <termino>
 { 
  //System.out.println(t.image);
  String term = t.image;
  CriterionInfo ci = new CriterionInfo();
   
  // Comprobar si se trata de un mes
  ci.criterio = buildCriterionFecha(term);
  
  if (ci.criterio != null) {
   ci.isFecha = true;
  } else {
   ci.isFecha = false;

   if (term.startsWith("\"") && term.endsWith("\"")) {
    term = term.substring(1, term.length() - 1);
   }
   ci.criterio = buildCriterionTermino(term);
  } 
  return ci;
 }
}

Criterion fecha() :
{
 Token t = null;
}
{
 t = <fecha>
 { 
  String term = t.image;
  return buildCriterionFecha(term);
 }
}

Referencia:
http://javacc.java.net/
http://www.lpsi.eui.upm.es/webcomp/jgperez/java/IntrodJavaCC.pdf
Etiquetas: , , , , ,
Compartir: