¿Qué es y cómo funciona ANTLR?ANTLR es un programa está escrito en java, por lo que se necesita alguna máquina virtual de java para poder ejecutarlo. Es software libre, lo que quiere decir que al descargarlo de la página oficial (http://www.antlr.org) obtendremos tanto los ficheros compilados *.class como el código fuente en forma de ficheros *.java. ANTLR es un generador de analizadores. Mucha gente llama a estas herramientas compiladores de compiladores15, dado que ayudar a implementar compiladores es su uso más popular. Sin embargo tienen otros usos. ANTLR, por ejemplo, podría servir para implementar el intérprete de un fichero de configuración
ANTLR es capaz de generar un analizador léxico, sintáctico o semántico en varios lenguajes (java, C++ y C# en su versión 2.7.2) a partir de unos ficheros escritos en un lenguaje propio. Dicho lenguaje es básicamente una serie de reglas EBNF y un conjunto de construcciones auxiliares.
ANTLR genera analizadores pred-LL(k), y él mismo utiliza un analizador pred-LL(k) para leer los ficheros en los que están escritas las reglas EBNF. ANTLR admite acciones en sus reglas, además de otras prestaciones como paso de parámetros, devolución de valores o herencia de gramática
Especificación de gramáticas con ANTLRLos ficheros con los que trabaja ANTLR tienen la terminación *.g, y en adelante los llamaremos ficheros de especificación de gramáticas o, directamente, ficheros de gramáticas.
Un fichero de gramática contiene la definición de uno o varios analizadores. Cada uno de estos analizadores se traducirá a código nativo (java, C++ o C#, dependiendo de ciertas opciones) en forma de clases. Es decir, por cada analizador descrito en el fichero de gramáticas se generará una clase.
Todo fichero de gramática tiene la siguiente estructura:
header{
/* opciones de cabecera */
}
options
{
/* opciones generales a todo el fichero */
}
// A continuación la definición de el(los) analizadore(s).
Cabecera: Esta zona es opcional (puede aparecer o no). Delimitada por las partículas “header {” y “}”, en esta zona incluimos elementos en código nativo (java, C++ o C#) que deben preceder a la definición de las diferentes clases de los analizadores. Esta sección se utiliza para incluir otros ficheros (import e #include), definir el paquete al que pertenecerá la clase del analizador (package) etc.
Opciones generales del fichero: Esta zona es opcional. Permite controlar algunos parámetros de ANTLR mediante “opciones”. Las opciones se representan como asignaciones : nombreOpcion=valor;. Se utilizan mucho en ANTLR. Las opción más importante de esta zona es la que permite elegir el lenguaje nativo en el que se generarán los analizadores (java,C++,C#). Su valor por defecto es “java”. Dado que vamos a generar reconocedores en java, no necesitaremos esta zona. En el manual de ANTLR aparecen todas las opciones que se pueden incluir en esta zona.
Tras las opciones generales del fichero vienen las definiciones de analizadores. Es muy común que en un mismo fichero se especifiquen varios analizadores (en la mayoría de los ejemplos que acompañan a ANTLR se utiliza esta técnica). Sin embargo también es posible definir cada analizador en un fichero, sobre todo cuando se trata de analizadores extensos16. Dado que nuestro lenguaje en este capítulo será muy sencillo, definiremos los tres analizadores en el mismo fichero.
En ANTLR, cada analizador tiene la siguiente estructura:
class nombreAnalizador extends tipoAnalizador; // definición del analizador
options {
/* Zona de opciones del analizador*/
}
tokens {
/* Zona de definición de tokens */
}
{
/* Zona de código nativo */
}
/* Zona de reglas */
Definición del analizador: En la primera línea definimos el nombre del analizador (nombreAnalizador) y su tipo (tipoAnalizador). El tipo puede será Lexer para analizadores léxicos, Parser para analizadores sintácticos y TreeParser para analizadores semánticos.
Zona de opciones: Esta zona es opcional, aunque casi siempre interesa utilizarla. En esta zona se definen propiedades muy importantes del analizador: se define el lookahead (k), si se va a generar un AST o no, en el caso de Parsers y TreeParsers, la importación/exportación de vocabulario, la activación/desactivación del tratamiento automático de errores etc. Para más información consúltese el manual de ANTLR.
Zona de definición de tokens: Esta zona es opcional. Permite definir nuevos tokens, que se añaden a los que se hayan importado en la zona de opciones del analizador.
Zona de código nativo:
Zona de definición de reglas: En esta zona se encontrarán las reglas que definirán la gramática.
Se admiten reglas EBNF extendidas (para más información sobre las reglas EBNF extendidas,
ANTLR utiliza un tipo de reglas que llamaremos EBNF extendidas. Las reglas EBNF extendidas se diferencian de las reglas EBNF en los siguientes aspectos:
• Pueden tener acciones
• Pueden tener predicados sintácticos y semánticos
• Pueden empezar con una acción, para declaración de variables locales.
• Los elementos de la regla son utilizables en el cuerpo de las acciones, y para ello se utilizan
“etiquetas”.
• Pueden devolver valores
• Pueden tomar parámetros
• Pueden codificar rangos de caracteres en el analizador léxico
• Pueden codificar patrones árbol en el analizador semántico
La zona de código nativoNo hay que olvidar que para ANTLR cualquier analizador es una instancia de una clase. En ocasiones es muy útil declarar métodos y atributos para dicha clase.
Para añadir métodos y variables a una clase de un analizador basta con escribirlos, entre la zona de opciones y la zona de reglas, entre llaves. Por ejemplo,
class MyParser extends Parser; // definición de un analizador sintáctico
options {...}
tokens {...}
{
private String a= “Hola ”; // atributo privado
public void imprimir(String s) // método público
{ System.out.println(s); }
}
regla1 : i:IDENT { imprimir(i.getText()); } ;
regla2 : e:ENTERO { imprimir(a+e.getText()); } ;
Los flujos de información
Flujo de caracteresEl primer flujo que voy a explicar es el que modela la entrada de datos desde el exterior hasta la primera fase del compilador, es decir, al analizador léxico. En otras palabras, voy a explicar qué es para ANTLR el flujo que en el primer capítulo llamé “Caracteres”.
Para ANTLR el flujo caracteres es, simplemente “cualquier subclase de java.io.InputStream”.
Lo más normal es utilizar un flujo de caracteres provinentes de un fichero (con un FileInputStream) pero pueden utilizarse otras fuentes, como una cadena (StringBufferStream) o una página web (URL.openStream). El InputStream que proporciona los caracteres al analizador léxico se le pasa como parámetro en su constructor.
Un pequeño inconveniente de utilizar éste método es que se pierde el concepto de “fichero”; los datos del fichero de texto perduran en forma de flujo FileInputStream, pero no ocurre así con el nombre del fichero. Éste puede ser especificado con la función setFilename:
// Convertir el nombre de fichero en un flujo
FileInputStream fis = newFileInputStream(fileName);
// Crear el lexer utilizando dicho flujo
LeLiLexer lexer = new LeLiLexer(fis);
// Proporcionar además el nombre de fichero al analizador
lexer.setFilename(f);Flujo de TokensEn éste caso estamos hablando del flujo de información existente entre el nivel léxico y sintáctico, es decir, el flujo que anteriormente hemos llamado “Tokens”.
La clase antlr.TokenLos tokens se representan en ANTLR utilizando una clase llamada antlr.Token. He aquí el código íntegro de dicha clase (salvo por algunos comentarios):
public class Token {
// constants
public static final int MIN_USER_TYPE = 3;
public static final int INVALID_TYPE = 0;
public static final int EOF_TYPE = 1;
public static final int SKIP = -1;
// each Token has at least a token type
int type=INVALID_TYPE;
// the illegal token object
public static Token badToken =
new Token(INVALID_TYPE, "");
public Token() {;}
public Token(int t) { type = t; }
public Token(int t, String txt) {
type = t; setText(txt);
}
public void setType(int t) { type = t; }
public void setLine(int l) {;}
public void setColumn(int c) {;}
public void setText(String t) {;}
public int getType() { return type; }
public int getLine() { return 0; }
public int getColumn() { return 0; }
public String getText() {...}
}Esta clase está “casi vacía”; no hay una verdadera implementación de los métodos – están ahí para ser sobreescritos por una subclase.
A pesar de ser casi una interfaz, esta clase nos da una idea de cómo se tratan los tokens en ANTLR: un token es un “tipo” (un entero) un texto (una cadena) y una línea y columna (sendos enteros). Esta clase base garantiza que siempre que utilicemos un token en ANTLR podremos obtener estas informaciones.
La clase antlr.CommonTokenLa clase antlr.Token por sí misma no es muy práctica debido a sus “métodos vacíos”. El analizador sintáctico no la utilizará directamente para representar los tokens; en su lugar se utiliza una subclase de antlr.Token llamada antlr.CommonToken. Su código es el siguiente:
public class CommonToken extends Token {
// most tokens will want line, text information
int line;
String text = null;
public CommonToken() {}
public CommonToken(String s) { text = s; }
public CommonToken(int t, String txt) {
type = t;
setText(txt);
}
public void setLine(int l) { line = l; }
public int getLine() { return line; }
public void setText(String s) { text = s; }
public String getText() { return text; }
}Esta clase no hace más que rellenar los “huecos” que faltan en su superclase.
Uno de los “huecos” que CommonToken no implementa es la conservación del nombre de fichero (filename) en el token (CommonToken no tiene ningún atributo llamado “filename”, y los métodos getFilename y setFilename no hacen nada o devuelven null).
La interfaz antlr.TokenStreamLa clase antlr.CharScanner (de la que heredan los analizadores léxicos que hacemos en ANTLR) implementa la interfaz antlr.TokenStream. El código completo de esta interfaz es el siguiente:
package antlr;
/* ANTLR Translator Generator
* Project led by Terence Parr at http://www.jGuru.com
* Software rights: http://www.antlr.org/RIGHTS.html
*
* $Id: //depot/code/org.antlr/main/main/antlr/TokenStream.java
*/
public interface TokenStream {
public Token nextToken() throws TokenStreamException;
}Así que lo único que tiene que hacer el analizador sintáctico es ir llamando al método nextToken del analizador léxico.
Construyendo y ejecutando el analizadorPor eso el constructor principal de cualquier analizador sintáctico generado por ANTLR toma como único parámetro un objeto que cumpla la interfaz antlr.TokenStream. Por ejemplo, nuestro analizador léxico:
// Crear un analizador sintáctico utilizando el léxico
LeLiParser parser = new LeLiParser(lexer);Como ocurría anteriormente, el nombre del fichero es irrecuperable por el Ç analizador, con lo que de nuevo es necesario pasárselo al analizador:
// Proporcionar el nombre del fichero al analizador sintáctico
parser.setFilename(fileName);Una consecuencia muy interesante de esta arquitectura es que podemos utilizar cualquier clase que implemente la interfaz antlr.TokenStream como analizador léxico; si no nos gusta la implementación con autómatas LL del analizador léxico, podemos utilizar nuestra propia implementación. Bastará que cumpla la interfaz para poder pasársela al analizador sintáctico en la construcción.
Para que un analizador sintáctico comience a analizar una entrada, es necesario llamar explícitamente al método de la primera clase que se ha declarado. A dicha clase también se le llama “regla inicial” o “regla raíz”.
Si la regla raíz de nuestro compilador se llama “programa”, entonces para iniciar el análisis sintáctico sobre una entrada será necesario escribir algo así:
parser.programa();En ese momento el analizador sintáctico comenzará a pedir tokens al analizador léxico, haciendo que éste a su vez comience a consumir caracteres de la entrada.
CONCLUSIONESSobre ANTLRAl comenzar a trabajar con ANTLR pensaba que las principales dificultades que tendría serían derivadas de implementar un analizador léxico con un autómata recursivo descendente. Más tarde constaté que la mayoría de las dificultades que pueden presentarse durante el análisis léxico se resolvían bastante bien con las “ayudas” que ANTLR proporciona en el análisis léxico: reglas EBNF, tratamiento de literales, tratamiento de mayúsculas y minúsculas, rangos de caracteres...
Incluso superaba a flex en algunos aspectos, como la compatibilidad con Unicode y la posibilidad de generar código para varios lenguajes.
El análisis sintáctico, por su parte, resultó muy cómodo: habiendo comprendido el fundamento de pred-LL(k) durante el análisis léxico, resultó muy sencillo adaptarse a los flujos de tokens.
La recuperación de errores, por su parte, fue un poco más complicada de comprender. Cuando uno ha trabajado con Bison, adaptarse a que “solamente se puede reconocer una regla cada vez” es complicado. Finalmente dominé la recuperación de errores con un enfoque práctico: observando los cambios que se producían en el código generado, a la sazón bastante inteligible.
Aprender a crear el AST fue aproximadamente tan complicado como implementar la recuperación de errores; después hubo que implementar la creación del AST, con lo que podemos concluir que la mayor parte del tiempo de desarrollo con ANTLR se emplea en la creación y manejo del AST.
¿Merece la pena ANTLR?
¡Sí!A pesar de las carencias, el balance total es muy positivo. El código que genera, aunque no es el más rápido, es muy robusto y comprensible. Es una solución más avanzada que el binomio bison+flex (permite crear y recorrer ASTs).
Quizás queda un poco atrás en el apartado de la eficiencia. Conforme aumente la velocidad de los procesadores esta diferencia se irá haciendo cada vez más pequeña, pero en algunos casos en los que se necesite procesar rápidamente una cantidad alta de datos podría resultar insuficiente.
En el ámbito académico, sin duda ANTLR es muy adecuado: su sencillez facilita el aprendizaje.
http://www.worldlingo.com/ma/enwiki/es/ANTLRhttp://www.lsi.us.es/~troyano/documentos/guia.pdfhttp://www.worldlingo.com/ma/enwiki/es/ANTLR
JAVACC
El generador JavaCC (Java Compiler Compiler) es una herramienta para generar analizadores de lengua¬jes; acepta como entrada una especificación de un determinado lenguaje y produce como salida un analiza¬dor para ese lenguaje; el analizador generado está escrito en Java. La especificación proporcionada al gene¬rador JavaCC puede contemplar distintos aspectos del lenguaje para el que se quiere obtener el analizador.
CARACTERÍSTICAS DE JAVACCJavaCC integra las funciones de análisis léxico y análisis sintáctico en una sola herramienta, obteniendo a la salida código java –a diferencia de lex/yacc cuya salida es código C-.
- Características lexicográficas y sintácticases la forma más frecuente de uso del generador; la especificación proporcionada define las característi¬cas sintácticas y lexicográficas de un lenguaje y se genera un analizador léxico-sintáctico del lenguaje especificado.
- Características lexicográficasen la especificación proporcionada al generador sólo se definen características lexicográficas del lengua¬je; con el código generado se puede obtener un analizador lexicográfico.
- Características lexicográficas y sintácticas y comprobaciones semánticasTambién es posible completar una especificación léxico-sintáctica con la inclusión de código Java com¬plementario para que el programa generado (que incorpora adecuadamente ese código auxiliar) pueda hacer un análisis completo (léxico, sintáctico y semántico) del lenguaje especificado.
FUNCIONAMIENTO:El funcionamiento de la herramienta consiste en analizar un fichero de entrada, que contiene la descripción de una gramática, y generar un conjunto de ficheros de salida, escritos en Java, que contienen la especificación de un analizador léxico y de un analizador sintáctico para la gramática especificada.
Estructura de un programa en JavaCC
Como puede verse en el ejemplo propuesto, la estructura básica de un programa JavaCC es:
options {
Área de opciones
}
PARSER_BEGIN(NombreClase)
Unidad de compilación Java con la clase de nombre Nombreclase
PARSER_END(NombreClase)
Área de tokens
Área de funciones BNFEl área de opciones permite especificar algunas directrices que ayuden a JavaCC a generar analizadores léxico-sintácticos bien más eficientes, bien más adaptados a las necesidades concretas del desarrollador.
En el ejemplo se ha indicado que, por defecto, la gramática indicada es de tipo LL(1), excepto si, en algún punto, se indica otra cosa.
Las cláusulas PARSER_BEGIN y PARSER_END sirven para indicarle a JavaCC el nombre de nuestra clase principal, así como para englobar tanto a ésta como a cualesquiera otras que se quieran incluir de apoyo, como pueda ser p.ej. un gestor de tablas de símbolos. En el ejemplo puede observarse que la clase principal constituye el analizador sintáctico en sí ya que la función main() crea un objeto de tipo Ejemplo a la vez que le pasa como parámetro en el constructor la fuente de la que se desea consumir la entrada: el teclado (System.in).
La clase creada por JavaCC incorporará una función por cada no terminal del área de reglas. Cada función se encargará de consumir la parte de la entrada que subyace debajo de su no terminal asociado en el árbol sintáctico de reconocimiento. Por tanto, asumiendo que el axioma inicial es listaExpr, una llamada de la forma miParser.listaExpr() consumirá toda la entrada, si ésta es aceptable.
Las siguientes dos áreas pueden mezclarse, aunque lo más usual suele ser indicar primero los tokens y finalmente las reglas en BNF, especialmente por motivos de claridad en el código.
En el ejemplo se han indicado tokens de dos tipos. Los tokens agrupados bajo la cláusula SKIP son aquellos que serán consumidos sin ser pasados al analizador sintáctico; en nuestro caso son: el espacio, el tabulador, el retorno de carro (CR-Carry Return) y la alimentación de línea (LF-Line Feed). Los tokens bajo la cláusula TOKEN constituyen los tokens normales, aunque el desarrollador también puede indicar este tipo de tokens en las propias reglas BNF, como ocurre con los patrones "(", ")", ";", etc. La declaración de cada token se agrupa entre paréntesis angulares y está formada por el nombre del token seguido por el patrón asociado y separado de éste por dos puntos. Los patrones lexicográficos se describen de forma parecida a PCLex. El ejemplo ilustra el reconocimiento de un identificador formado sólo por letras (ya sean mayúsculas o minúsculas merced al modificador
[IGNORE_CASE] de la cláusula TOKEN) y de un número entero.
La última área del ejemplo ilustra la creación de tres no terminales y sus reglas BNF asociadas. Dado que cada no terminal va a ser convertido por JavaCC en una función Java, su declaración es idéntica a la de dicha función y está sujeta a las mismas restricciones que cualquier otra función en Java. El cuerpo de cada una de estas funciones será construido por JavaCC y tendrá como propósito el consumo adecuado de tokens en base a la expresión BNF que se indique en la especificación.
La notación BNF empleada hace uso del símbolo * que representa repetición 0 ó más veces, + para la repetición 1 ó más veces, | para la opcionalidad, paréntesis para agrupar, etc. Los terminales pueden indicarse de dos formas, bien colocando entre paréntesis angulares alguno de los declarados en la fase anterior, o bien indicando su patrón directamente si éste está formado por una cadena constante de caracteres (realmente, JavaCC permite cualquier expresión regular, pero ello no resulta útil para nuestros propósitos). En el ejemplo es de notar la inclusión del carácter "@" en los terminales ad hoc NEW y ALGO, ya que, en caso contrario serían considerados identificadores al encajar por el patrón del token ID. Los patrones "NEW" y "ALGO" habrían sido correctamente reconocidos si el token ID se hubiera declarado después de la aparición de éstos en las reglas BNF.
http://www.lcc.uma.es/~galvez/theme/IntroduccionAJavaCC.pdfhttp://www.giaa.inf.uc3m.es/docencia/II/PL2/herramientas/JFlex_JavaCC.pdf
