Árbol de sintaxis abstracta

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Á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

En ciencias de la computación, un árbol de sintaxis abstracta (AST), o simplemente un árbol de sintaxis, 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. 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.

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[editar]

El Árbol de sintaxis abstracta es una structura de datos usada extensamente en compiladores, debido a su propiedad de representar la estructura del codigo 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 estapas que requiere el compilador, y tiene un impacto fuerte en la salida final del compilador.

Motivación[editar]

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

  • Comparado al codigó fuente, un AST no incluye ciertos elementos, como puntuacion no esencial y delimitadores (corchetes, punto y coma, paréntesis, entre otros.).
  • Una difierencia 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 codigó fuente de un programa, mientras que esto implicaria cambiarlo.
  • Al mismo tiempo, un AST usualmente contiene información extra sobre el programa, debido a las etapas consecutivas de analisis 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 amenudo 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 estan 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 funcion final esta determinada basada en el contexto. Java provee un ejemplo excelente donde el operador '+' es tambien una adición numérico y concadenacion de cadenas.

Aunque hay otras estructuras de datos implicadas en el funcionamiento interno de un compilador, el AST realiza una unica funcion. 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 conduciar a un compilador mas eficiente, esto va contra los principios de la ingieneria 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 numero de elementos.

Diseño[editar]

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 deven ser preservados, tambien como la localización de cada declaración en el codigó fuente.
  • El orden de las declaraciones ejecutables tienen que ser representadas explicitamente y bien definidas.
  • Los componentes izquierdos y derechos de las operaciones binarias tienen que ser guardadas y 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 elementoss, tal como los dos terminos 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 linea de comandos. Como resultado, un AST necesita ser suficientemente flexible para permitir la facil adición de hijos sin conocer la cantidad.

Otro mayor requisito para un AST es que tiene que ser decompilable en la forma de codigó fuente. El codigó fuente tiene que ser suficientemente similar al original en apariencia y identicamente en ejecución despues de la recompilación.

Patrones de diseño[editar]

Debido a la complejidad de los requisitos de un AST y toda la complejidad de un compilador, es beneficioso aplicar los principios de desarrollo del los software de sonido. Uno de esos es usar patrones de diseño para una mejor modularidad y facil desarrollo.

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

Porque el compilador atraviesa varias veces para determinar lo correcto de una sintaxis, es importante para recorrer el árbol en una operación sencilla. El compilador ejecuta un conjunto de instrucciones especificas, dependiendo en el tipo de cada nodo, al alcanzar este, asi que este a menudo tiene sentido usar el patrón visitor.

Uso[editar]

Los ASTs son usado intensamente durante el analisis semantico, donde el compilador chequea el correcto uso de los elementos del prorgama y el lenguaje. El compilador también genera tablas de simbolos basado en el AST durante el analisis semantico. Un completo recorrido del árbol permite la verificación de la exactitud del programa.

Despues de verificar la exactitud, el AST sirve como la base de la generación de codigó. El AST es a menudo usado para generar la 'representación inmediata' '(IR)', algunas veces llamado lenguaje intermediario, para la generación del codigó.

Véase también[editar]

Referencias[editar]

Enlaces externos[editar]