Árboles de sintaxis abstracta (ASTs)Abstract Syntax Trees



Tabla de contenido



Árboles de sintaxis abstracta (ASTs)
Es una representación de árbol de la estructura sintáctica abstracta (simplificada) del código fuente escrito en cierto lenguaje de programación. Cada nodo del árbol denota una construcción que ocurre en el código fuente. Estos difieren de los árboles de análisis sintáctico en que las distinciones superficiales de forma, sinimportancia en la traducción, no aparecen en los arboles sintácticos La sintaxis es abstracta en el sentido que no representa cada detalle que aparezca en la sintaxis verdadera.
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 laforma arbórea; por eso 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 unagramá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.
Árbol de sintaxis abstracta para el siguiente código del algoritmo de Euclides:

while b ≠ 0
if a > b
a := a − b
else
b := b − a
return a

ANTLR
(ANother Tool for LanguageRecognition; en español "otra herramienta para reconocimiento de lenguajes") es una herramienta creada principalmente por Terence Parr, que opera sobre lenguajes, proporcionando un marco para construir reconocedores (parsers), intérpretes, compiladores y traductores de lenguajes a partir de las descripciones gramaticales de los mismos (conteniendo acciones semánticas a realizarse en varios lenguajes deprogramación).
ANTLR cae dentro de la categoría de meta-programas, por ser un programa que escribe otros programas. Partiendo de la descripción formal de la gramática de un lenguaje, ANTLR genera un programa que determina si una sentencia o palabra pertenece a dicho lenguaje (reconocedor), utilizando algoritmos LL(*) de parsing. Si a dicha gramática, se le añaden acciones escritas en un lenguajede programación, el reconocedor se transforma en un traductor o intérprete.
Además, ANTLR proporciona facilidades para la creación de estructuras intermedias de análisis (como ser ASTs - Abstract Syntax Tree), para recorrer dichas estructuras, y provee mecanismos para recuperarse automáticamente de errores y realizar reportes de los mismos.
La forma normal de representar un árbol en ANTLRutiliza 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 los mecanismos que proporciona ANTLR para crear árboles de sintaxis abstracta. Estos aspectos (junto con la notación utilizada pararecorrer 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 sulugar 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...