Arboles de sintaxis abstracta (ASTs)

Árboles de sintaxis abstracta (ASTs)
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
podemosobviar 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 elementointermedio 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))

En esta práctica estudiaremos losmecanismos que proporciona ANTLR para
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 delaná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 elsignificado 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 queservirá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...