ANTLR
Los ASTs (Abstract Syntax Trees, o Árboles de Sintaxis Abstracta) sirven para
manejar la información semántica de un código. La forma más eficiente de manejar la
información proveniente de un lenguaje de programación es la forma arbórea; por éso la
estructura de datos elegida es un árbol. Además, construyendo ASTs a partir de un texto
podemos obviar mucha información irrelevante; si un AST se construye bien, no habrá
que tratar con símbolos de puntuación o azúcar sintáctica en el nivel semántico.
Al contrario que los flujos, una estructura en árbol puede especificar la relación
jerárquica entre los símbolos de una gramática.
Los ASTs pueden intervenir en varias fases del análisis: como producto del
análisis sintáctico, como elemento intermedio en sucesivos análisis semánticos y como
entrada para la generación de código.
La forma normal de representar un árbol en ANTLR utiliza una notación basada
en LISP. Por ejemplo:
#(A B C)
Es un árbol con “A” en la raíz, y los hijos B y C.
Esta notación puede anidarse para describir árboles de estructuras más complejas. Así:
#(A B #(C D E))
crear árboles de sintaxis abstracta. Estos aspectos (junto con la notación utilizada para
recorrer dichos árboles) constituyen la parte más original de la herramienta, la solución
aportada para describir dichos árboles a partir de la especificación sintáctica es
realmente imaginativa y da lugar a descripciones bastante claras y compactas.
Construcción del árbol de sintaxis abstracta
ANTLR no requiere de una especificación adicional para definir los árboles de
sintaxis abstracta. En su lugar inserta una serie de símbolos en la propia gramática
concreta que establecen qué elementos merece la pena mantener en árbol de sintaxis
abstracta y a partir de ahí lo genera de forma automática. De esta forma con tan sólo
enriquecer la especificación del análisis sintáctico se tiene resuelta la especificación y
construcción del árbol de sintaxis abstracta. La siguiente especificación construye el
árbol de sintaxis abstracta para el lenguaje de las expresiones que venimos usando como
ejemplo en las prácticas de la asignatura:
///////////////////////////////
// Analizador sintáctico
///////////////////////////////
class Anasint extends Parser;
options
{
buildAST = true;
}
tokens
{
LISTA_INST;
}
instrucciones : (expresion ";"!)* EOF!
{##=#(#[LISTA_INST,"LISTA_INST"],##);}
;
expresion : exp_mult (("+"^
"-"^) exp_mult)* ;
exp_mult : exp_base (("*"^
"/"^) exp_base)* ;
exp_base : NUMERO
"("! expresion ")"!
;
A simple vista la especificación anterior puede parecer un poco críptica, pero
una vez que se comprende el significado de los distintos elementos en juego se descubre
que resulta muy cómodo especificar la construcción de árboles con ellos:
La sección options incluye la instrucción buildAST=true. De esta
forma se activa la construcción automática del árbol de sintaxis abstracta.
La sección tokens permite añadir nuevos tokens a los ya definidos en el
análisis léxico. En este caso serán tokens virtuales que servirán como raíz
a árboles para los que en la gramática no hay ningún token que pueda
desempeñar esta función. Esto suele ser muy común en las listas, como
ocurre en el ejemplo con LISTA_INST.
Cuando un símbolo va seguido del operador ! se considerará no
relevante y no se incluirá en el árbol de sintaxis abstracta.
El operador ^ indica que el símbolo al que acompaña debe ser la raíz del
árbol. Si en una regla no se destaca ningún símbolo como raíz, el árbol
generado será una secuencia de hermanos sin padre.
Se puede deshabilitar la construcción automática y sustituirla por otra.
Esto es lo que se hace en la regla de instrucciones para dotar de un
padre a la secuencia de expresion.
Con el elemento #[LISTA_INST,"LISTA_INST"] se crea un árbol
cuya raíz es el token ficticio LISTA_INST. La operación #(...)
toma una lista de árboles y construye un árbol en el que el primer
elemento hace de raíz.
El elemento ## hace referencia al árbol generado de forma automática
para el símbolo de la parte izquierda de la regla. También se podría
referenciar con el nombre del símbolo precedido de # (en el ejemplo
sería #instrucciones).
¿Qué se puede hacer con el árbol?
En la próxima práctica veremos la notación que ANTLR proporciona para
especificar recorridos de árboles de sintaxis abstracta. Pero antes de llegar a eso
podemos aprovecharnos de distintas facilidades ya implementadas para al menos
comprobar que los árboles construidos se corresponden con los que realmente
queremos.
El comportamiento de los árboles de sintaxis abstracta se establece a través de la
interfaz AST. Por defecto los árboles son objetos de la clase CommonAST que
implementa dicha interfaz, y que a su vez es subclase de BaseAST. La clase BaseAST
implementa todos los métodos de la interfaz AST salvo los relacionados con la
información contenida en las raíces que son implementados en CommonAST (lo que
permite extender esta información con facilidad). Algunos de los métodos de que
disponen los árboles de sintaxis abstracta son:
AST getFirstChild(): devuelve el primer hijo de un nodo interno de
un árbol.
AST getNextSibling(): devuelve el hermano derecho de un árbol.
boolean equals(AST t): comprueba si las raíces de ambos árboles
son iguales.
boolean equalsTree(AST t): comprueba si los árboles son iguales.
boolean equalsTreePartial(AST t): comprueba si t es una
versión ampliada del árbol que llama al método.
boolean equalsList(AST t): igual que equalsTree pero admite
como entrada una lista de árboles (un árbol sin raíz).
boolean equalsListPartial(AST t): igual que el método
equalsTreePartial pero admite como entrada una lista de árboles.
String getText(): obtiene el texto asociado a la raíz.
int getType(): obtiene el tipo asociado a la raíz (habitualmente será un
tipo de token).
String toString(): convierte la raíz del árbol a una cadena.
String toStringTree(): convierte el árbol completo en una cadena.
String toStringList(): igual que toStringTree pero admite
como entrada una lista de árboles.
Con todos estos métodos ya podemos empezar a manipular árboles, lo único que
necesitamos es acceder al árbol construido durante el análisis sintáctico, eso lo
conseguiremos gracias al método getAST de la clase Anasint. Por ejemplo, la
siguiente clase principal recupera el árbol y lo imprime haciendo uso del método
toStringTree:
/////////////////////////////////////
// Procesador.java (clase principal)
/////////////////////////////////////
import java.io.*;
import antlr.collections.AST;
import antlr.*;
public class Procesador {
public static void main(String args[]) {
try {
FileInputStream fis =
new FileInputStream(args[0]);
Analex analex = null;
Anasint anasint = null;
AST arbol = null;
analex = new Analex(fis);
anasint = new Anasint(analex);
anasint.instrucciones();
arbol = anasint.getAST();
System.out.println(arbol.toStringTree());
}catch(ANTLRException re) {
System.err.println(re.getMessage());
}catch(FileNotFoundException fnfe) {
System.err.println("No existe el fichero");
}
}
}
Si ejecutamos este programa tras el reconocimiento se mostrará en pantalla una
versión textual del árbol construido. Por ejemplo para la entrada:
1+2+3;
4*5+6;
La salida sería la siguiente:
( LISTA_INST ( + ( + 1 2 ) 3 ) ( + ( * 4 5 ) 6 ) )
Esto nos puede servir de ayuda cuando los textos reconocidos son pequeños,
pero para entradas de mayor tamaño resulta muy complejo interpretar correctamente la
versión textual del árbol Afortunadamente ANTLR proporciona otra vía para comprobar
el contenido de los árboles. Se trata de la clase ASTFrame incluida en el paquete
antlr.debug.misc, que muestra el árbol en una ventana SWING. Para crear un
objeto de la clase ASTFrame debemos especificar el título de la ventana y el árbol a
representar. Una vez creado el objeto podremos visualizar el árbol con el método
setVisible. Si por ejemplo queremos crear una ventana cuyo título sea el nombre
del fichero que estamos analizando deberíamos hacer algo así:
ASTFrame frame= new ASTFrame(args[0],arbol);
frame.setVisible(true);
Lo que daría lugar a una ventana como la siguiente:
Los distintos árboles y subárboles podrán plegarse y desplegarse, por lo que
puede comprobarse la estructura de un árbol con gran facilidad incluso en el caso de
árboles muy grandes.
Ampliando la clase CommonAST
De la misma forma que en su momento fuimos capaces de extender la clase
CommonToken para incluir más atributos, también está abierta esa posibilidad de
extensión para la clase CommonAST. Por ejemplo, la siguiente clase incluye como
atributo de los árboles la línea en la que se encuentra el token correspondiente:
import antlr.*;
import antlr.collections.*;
public class MiArbol extends CommonAST {
// Nuevo atributo
int linea;
// Constructor vacío
public MiArbol() {
}
// Constructor a partir de un token
public MiArbol(Token t){
initialize(t);
}
// Constructor a partir de un árbol
public MiArbol(AST a) {
initialize(a);
}
// Inicialización a partir de un token
public void initialize(Token t) {
super.initialize(t);
setLinea(t.getLine());
}
// Inicialización a partir de un árbol
public void initialize(AST a)
{
super.initialize(a);
if(a instanceof MiArbol) {
setLinea(((MiArbol)a).getLinea());
}
}
// Métodos de actualización y acceso
// del atributo linea
public void setLinea(int l) {
linea=l;
}
public int getLinea() {
return linea;
}
// Redefinición del método toString
public String toString() {
StringBuffer sb = new StringBuffer("");
String textoCommonAST = super.toString();
sb.append(textoCommonAST);
sb.append( " (línea: ");
sb.append( linea );
sb.append( ")" );
return sb.toString();
}
}
La definición de la clase anterior incluye:
La definición del atributo linea y de los correspondientes métodos
de actualización y consulta.
Tres métodos constructores de la clase MiArbol: sin argumentos, a
partir de un token y a partir de otro árbol.
La redefinición del método initialize que es el encargado de
actualizar los atributos de los árboles en el momento de la creación.
La actualización se puede hacer desde los datos proporcionados por
un token o por un árbol.
La redefinición del método toString para que se incluya el
atributo linea al convertir el árbol a texto.
Una vez hecho esto tan sólo falta indicarle al analizador sintáctico que los
árboles que tiene que crear deben ser de la nueva clase. Esto se consigue con el método
setASTNodeType de la clase Anasint:
/////////////////////////////////////
// Procesador.java (clase principal)
/////////////////////////////////////
...
public class Procesador {
public static void main(String args[]) {
...
anasint = new Anasint(analex);
anasint.setASTNodeClass("MiArbol");
anasint.instrucciones();
...
}
}
Gracias a la redefinición del método toString, la visualización del árbol
también presentará el valor del nuevo atributo:
Cuando la sintaxis abstracta difiere de la concreta
Los operadores ^ y ! son muy potentes y dan lugar a especificaciones muy
compactas, pero no siempre tendremos suficiente con ellos para construir los árboles
que necesitaremos. El siguiente lenguaje nos plantea un problema de construcción de
árboles que no podrá ser resuelto de forma automática con estos operadores y para el
que necesitaremos especificar la manera en que deben tratarse ciertas reglas. Se trata del
lenguaje de las declaraciones de C:
int a,b,c;
char d,e,f;
Una primera solución a la construcción del árbol sería la siguiente:
declaraciones : (declaracion)*
{##=#(#[LISTA_DEC,"LISTA_DEC"],##);};
declaracion : t:tipo i:idents ";"!
{##=#(#t,#i);};
tipo : CHAR
INT ;
idents : IDENT (","! IDENT)*;
La regla asociada a declaraciones introduce el token ficticio LISTA_DEC para
enraizar la lista de la misma forma que se hizo con el token LISTA_INST en el primer
ejemplo del enunciado. La otra regla que no se resuelve con la construcción automática
es la de declaracion, en esta ocasión esto es debido a que el operador ^ sólo puede
aplicarse a símbolos terminales, de manera que si queremos que el árbol devuelto por
tipo sea la raíz debemos especificarlo directamente con el constructor #(...). Para
ello se utilizan las etiquetas t e i que, precedidas del operador #, dan acceso a los
árboles de tipo e idents. Con esta especificación el árbol para el ejemplo anterior
sería:
Puede que nos interese asociar a cada identificador el tipo, de manera que nos
quedase el mismo árbol que si la entrada hubiese sido:
int a;
int b;
int c;
char d;
char e;
char f;
De hecho es esto último lo que queremos expresar, pero el lenguaje nos permite
compartir una única aparición del tipo con varios identificadores para ahorrarnos
escritura. Si quisiésemos generar este tipo de árboles la especificación sería la siguiente:
declaracion : t:tipo! idents[#t] ";"!
;
tipo : CHAR
INT
;
idents[AST t] : ident[t] (","! ident[t])*
;
ident[AST t]: i:IDENT
{AST ct= astFactory.dupTree(t);
##=#(#[DECLAR,"DECLAR"],ct,#i);}
;
Lo más destacable de la especificación anterior es:
El árbol asociado al símbolo tipo se desactiva ya que vendrá integrado en el
devuelto por el símbolo idents.
El símbolo idents recibe como atributo heredado el tipo a través de la
etiqueta #t, este árbol es a su vez propagado al símbolo ident.
En la regla ident se hace una copia al árbol del tipo (con el método
dupTree del objeto astFactory declarado en la clase Anasint) y se
utiliza como raíz el token ficticio DECLAR.
El árbol resultante quedaría ahora así:
