Árbol de sintaxis abstracta

En lenguajes formales y lingüística computacional, un árbol de sintaxis abstracta (AST), o simplemente un árbol de sintaxis, es una representación de árbol de la estructura sintáctica 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. La sintaxis es abstracta en el sentido que no representa cada detalle que aparezca en la sintaxis verdadera. Por ejemplo, el agrupamiento de los paréntesis está implícito en la estructura arborescente, y una construcción sintáctica tal como IF condición THEN puede ser denotada por un solo nodo con dos ramas.

Á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

Esto hace a los árboles de sintaxis abstracta diferentes de los árboles de sintaxis concreta, llamados tradicionalmente árboles de parser, que son a menudo construidos por la parte parser de la traducción del código fuente y el proceso de compilación (a pesar quizás de un nombramiento no intuitivo). Una vez construido, información adicional es agregada al AST por procesamiento subsecuente, ej., análisis semántico.

Aplicación en compiladores

El Árbol de sintaxis abstracta es una estructura de datos usada extensamente en compiladores, debido a su propiedad de representar la estructura del código de un programa. Un AST es usualmente el resultado del analizador sintáctico en la fase de un compilador. A menudo sirve como un intermediario de la representación del programa a través de etapas que requiere el compilador, y tiene un impacto fuerte en la salida final del compilador.

Motivación

Siendo el producto en la fase análisis sintáctico de un compilador, el AST tiene varias propiedades que son inestimables a los siguientes pasos del proceso de compilación.

• Comparado al código fuente, un AST no incluye ciertos elementos, como puntuación no esencial y delimitadores (corchetes, punto y coma, paréntesis, entre otros.).
• Una diferencia importante es que el AST puede ser editado y mejorado con propiedades y anotaciones para cada elemento que contiene. Esta edición y anotación es imposible con el código fuente de un programa, ya que esto implicaría cambiarlo.
• Al mismo tiempo, un AST usualmente contiene información extra sobre el programa, debido a las etapas consecutivas de análisis del compilador. Un ejemplo simple de la información adicional presente en un AST es la posición de un elemento en el codigó fuente. Esta información es usada en caso de un error en el codigó, para notificar al usuario la locación de un error.

Los ASTs son necesitados debido a la naturaleza de los lenguajes de programación y su documentación. Los lenguajes son a menudo ambiguos por naturaleza. En orden para evitar esta ambigüedad, los lenguajes de programación son especificados con una gramática libre de contexto (CFG). Sin embargo, hay a menudo aspectos de los lenguajes de programación que un CFG no puede expresar, pero son partes del lenguaje y están documentados en su especificación. Esos son detalles que requieren un contexto para determinar su validez y comportamiento. Por ejemplo, si un lenguaje permite que nuevos tipos de datos sean declarados, un CFG no puede predecir los nombres de esos tipos ni el camino en el que deben ser usados. Incluso si un lenguaje tiene unos tipos predefinidos, hacer cumplir su uso requiere algún contexto. Otro ejemplo es el duck typing, donde el tipo de un elemento puede cambiar dependiendo del contexto. La sobrecarga de operadores es todavía otro caso donde el correcto uso y la función final está determinada basada en el contexto. Java provee un ejemplo excelente donde el operador '+' es también una adición numérico y concadenación de cadenas.

Aunque hay otras estructuras de datos implicadas en el funcionamiento interno de un compilador, el AST realiza una única función. Durante la primera etapa, el analizador sintáctico, un compilador produce un árbol de análisis sintáctico. Este árbol de análisis sintáctico puede ser usado para realizar todas las funciones de un compilador por medio de la traducción dirigida por la sintaxis. Aunque este método puede conducir a un compilador más eficiente, esto va contra los principios de la ingeniería de software de escribir y mantener programas. Otra ventaja que un AST tiene sobre un árbol de análisis sintáctico es el tamaño, particularmente la pequeña altura del AST y el pequeño número de elementos.

Diseño

El diseñor de un AST esta cercanamente vinculado con el diseño de un compilador y sus características esperadas.

Los requerimientos básicos incluyen los siguientes:

• Los tipos de variables deben ser preservados, también como la localización de cada declaración en el código fuente.
• El orden de las declaraciones ejecutables tienen que ser representadas explícitamente y bien definidas.
• Los componentes izquierdos y derechos de las operaciones binarias tienen que ser guardadas e identificadas correctamente.
• Los identificadores y sus valores asignados tienen que ser guardados para las instrucciones de asignación.

Esos requerimientos pueden ser usados para diseñar la estructura para el AST.

Algunas operaciones siempre van a requerir dos elementos, tal como los dos términos de adición. Sin embargo, algunos lenguajes construidos requieren una cantidad larga de hijos, como las listas de argumentos pasados a los programas desde la línea de comandos. Como resultado, un AST necesita ser suficientemente flexible para permitir la fácil adición de hijos sin conocer la cantidad.

Otro mayor requisito para un AST es que tiene que ser decompilable en la forma de código fuente. El código fuente tiene que ser suficientemente similar al original en apariencia e idénticamente en ejecución después de la recompilación.

Patrones de diseño

Debido a la complejidad de los requisitos de un AST y toda la complejidad de un compilador, es beneficioso aplicar principios de desarrollo de software sensatos. Una posibilidad es usar patrones de diseño para una mejor modularidad y fácil desarrollo.

Operaciones diferentes no necesariamente tienen tipos diferentes, así que es importante tener una jerarquía sensata de clases nodo. Esto es crucial en la creación y modificación de un AST conforme el compilador progresa.

Puesto que el compilador atraviesa el árbol varias veces para determinar lo correcto de una sintaxis, es importante que recorrer el árbol sea una operación sencilla. El compilador ejecuta un conjunto de instrucciones específicas, dependiendo del tipo de cada nodo, al alcanzar este, así que a menudo tiene sentido usar el patrón visitor.

Uso

Los AST son usados intensamente durante el análisis semántico, donde el compilador comprueba el correcto uso de los elementos del programa y el lenguaje. El compilador también genera tablas de símbolos basadas en el AST durante el análisis semántico. Un recorrido completo del árbol permite la verificación de la exactitud del programa.

Después de verificar la exactitud, el AST sirve como base para la generación de código. El AST es a menudo usado para generar la 'representación intermedia' '(IR)', algunas veces llamado lenguaje intermediario, para la generación del código.

Algunos lenguajes, tales como Groovy, permiten manipular manualmente el AST. Esto se hace con fines tales como añadir automáticamente campos a todas las clases del programa, o para implementar la función de anotaciones de clase.

Véase también

• Analizador sintáctico
• Grafo semántico abstracto (ASG)
• Document Object Model (DOM)
• Árbol de resolución semántica (RST)
• Algoritmo shunting yard
• Tabla de símbolos
• TreeDL
• Árbol sintáctico

Referencias

• Este artículo fue originalmente basado en material de Free On-line Dictionary of Computing, que está licenciado bajo el GFDL.

Enlaces externos

• AST View, an Eclipse plugin to visualize a Java abstract syntax tree
• Good information about the Eclipse AST and Java Code Manipulation
• Paper "Abstract Syntax Tree Implementation Idioms" by Joel Jones (overview of AST implementation in various language families)
• Paper "Abstract Syntax Tree Design" by Nicola Howarth (note that this merely presents the design of *one particular* project's AST, and is not generally informative)
• Paper "Understanding source code evolution using abstract syntax tree matching" by Iulian Neamtiu, Jeffrey S. Foster and Michael Hicks
• Paper "Change Distilling: Tree Differencing for Fine-Grained Source Code Change Extraction" by Beat Fluri, Michael Würsch, Martin Pinzger, and Harald C. Gall.
• Diploma thesis "Improving Abstract Syntax Tree based Source Code Change Detection" by Michael Würsch
• Article "Thoughts on the Visual C++ Abstract Syntax Tree (AST)" by Jason Lucas
• Tutorial "Abstract Syntax Tree Metamodel Standard"
• PMD uses AST representation to control code source quality
• CAST representation
• Abstract Syntax Tree Unparsing

• Datos: Q127380
• Multimedia: Abstract syntax trees / Q127380