En mayo y julio de 2008 publiqué sendos artículos en los que intentaba explicar la utilidad de los generadores de analizadores sintácticos, y su aplicación en uno concreto, JavaCC.
Desde entonces han ocurrido algunos hechos que actualizan este panorama:
Por otro lado, en este artículo quiero hablar de otras herramientas incluidas en JavaCC, denominadas JJTree y Java Tree Builder (JTB). Ambas están incluidas en el plugin para Eclipse.
JJTree es un preprocesador de JavaCC que genera árboles para construir árboles sintácticos abstractos. Como indican en el Libro del Dragón “los árboles sintácticos abstractos (en inglés AST), conocidos simplemente como árboles sintácticos, representan la estructura sintáctica jerárquica del programa fuente… Se parecen en cierto grado a los árboles de análisis sintáctico. No obstante, en el árbol sintáctico los nodos interiores representan construcciones de programación mientras que, en el árbol de análisis sintáctico, los nodos interiores representan no terminales.”
¿Qué ofrece esta utilidad?
Un fichero JJTree, tiene la extensión .jjt. Trabajaremos sólo con este fichero, en el que escribiremos la definición de la gramática, con sus reglas, tokens y acciones. Cuando le digamos a Eclipse que lo compile, automáticamente invocará a JJTree, que generará un fichero fuente de JavaCC, de extensión .jj. Éste será tomado como entrada y generará todos los .java que serán a su vez la entrada del compilador Java (javac) para generar los .class que ejecutaremos.
Para aclararnos:
JTB es un constructor de árboles sintácticos. A partir de un fichero que contenga la definición de una gramática JavaCC genera lo siguiente:
-
Un conjunto de clases que implementan dicho árbol basadas en las producciones de la gramática, utilizando el patrón de diseño Visitor.
-
Dos interfaces: Visitor y GJVisitor. Dos visitors para acceder a los hijos del nodo en el que estramos: DepthFirstVisitor y GJDepthFirst.
-
Una gramática JavaCC, que tiene el nombre jtb.out.jj conteniendo las anotaciones necesarias para constuir el árbol de sintaxis durante el análisis sintáctico de una entrada.
Todo esto puede parecer un auténtico berenjenal y la lectura y comprensión de las opciones que ofrecen estas herramientas puede ser costosa.
Pero os diré que en su día utilicé JavaCC junto con la construcción de árboles para resolver este problema: al ejecutar este tipo de sentencias SQL en Oracle Text (al menos en las versiones 9.*)
SELECT … FROM … WHERE CONTAINS(texto, 'a ; (b or c)') > 0;
ocurría este error:
DRG-50919: NEAR operand not a phrase, equivalence or another NEAR expression
En cambio si ejecutábamos la equivalente:
SELECT … FROM … WHERE CONTAINS(texto, '(a ; b) or (a ; c)') > 0;
no había error alguno.
a ; (b or c) eran los términos de búsqueda que introducía el usuario a través de un formulario en la web.
Una cadena que siga ese patrón podía ser: cotizacion ; (ibex or nasdaq)
que quiere decir que se obtengan los registros donde la cadena cotizacion se encuentre cerca de la cadena ibex o de la cadena nasdaq.
Es decir que es lo mismo que esto:
(cotizacion ; ibex) or (cotizacion ; nasdaq)
Lo que hemos hecho es distribuir algebraicamente el operador ‘;’ sobre los demás operadores, obteniendo una expresión equivalente pero con el ‘;’ anidado entre los demás operadores.
Para ello se realizaron los siguientes pasos:
1. Verificación de la sintaxis de la expresión introducida por el usuario.
2. Creación de un árbol con la estructura de la expresión. El recorrido de dicho árbol en inorden nos daba la expresión de consulta.
3. Transformación de dicho árbol para distribuir los operadores ‘;’ sobre el resto de operadores.
4. Obtención de la expresión final mediante el recorrido del árbol en inorden, colocando los paréntesis pertinentes para señalar el anidamiento de sub-expresiones.
Ejemplos de traducción:
Expresión: a a or b a ; (b or c) (a or b) ; (c and d)
Árbol: a or ; ;
/ \ / \ / \
a b a or or and
/ \ / \ / \
b c a b c d
Trad.: a or or or
/ \ / \ / \
a b ; ; and and
/ \ / \ / \ / \
a b a c ; ; ; ;
/ \ / \ / \ / \
a c a d b c b d
Y os aseguro que hubo usuarios (era un sistema con más de 2000 sesiones abiertas en su momento de mayor uso) que introdujeron cadenas con este patrón:
((d .p b) .o ((e .p b) .o (f .p b))) .p ((d .p c) .o ((e .p c) .o (f .p c)))
que hubo que transformar en la siguiente:
(((D ; B) ; (D ; C)) or ((D ; B) ; E ; (D ; B) ; C) or ((D ; B) ; F ; (D ; B) ; C)) or (((D ; C) ; E ; (D ; C) ; B) or ((D ; C) ; F ; (D ; C) ; B) or ((((E ; B) ; (E ; C)) or ((E ; B) ; (F ; C))) or (((F ; B) ; (E ; C)) or ((F ; B) ; (F ; C)))))
No utilicé ni JTree ni JTB, sí JavaCC… ¿Debería haber dedicado más tiempo a leer y luego empezar a desarrollar? Ésta es la eterna pregunta de los desarrolladores.
Referencias
http://twitter.com/CESNavarra
http://twitter.com/curtasun