Hispanopedia Wiki
mientras b ≠ 0 :
si a > b :
a := a - b
de lo contrario :
b := b - a
devuelve a
Un árbol de sintaxis abstracta ( AST ) es una estructura de datos utilizada en informática para representar la estructura de un programa o fragmento de código. Es una representación en forma de árbol de la estructura sintáctica abstracta de un texto (a menudo código fuente ) escrito en un lenguaje formal . Cada nodo del árbol denota una construcción que aparece en el texto. A veces se lo denomina simplemente árbol de sintaxis .
La sintaxis es "abstracta" en el sentido de que no representa todos los detalles que aparecen en la sintaxis real, sino sólo los detalles estructurales o relacionados con el contenido. Por ejemplo, los paréntesis de agrupación están implícitos en la estructura de árbol, por lo que no tienen que representarse como nodos separados. Del mismo modo, una construcción sintáctica como una declaración if-condition-then puede denotarse por medio de un solo nodo con tres ramas.
Esto distingue a los árboles de sintaxis abstracta de los árboles de sintaxis concreta, tradicionalmente denominados árboles de análisis sintáctico . Los árboles de análisis sintáctico suelen ser construidos por un analizador sintáctico durante el proceso de traducción y compilación del código fuente . Una vez construidos, se añade información adicional al AST mediante un procesamiento posterior, por ejemplo, análisis contextual .
Los árboles de sintaxis abstracta también se utilizan en el análisis de programas y en sistemas de transformación de programas .
Aplicación en compiladores
Los árboles sintácticos abstractos son estructuras de datos que se utilizan ampliamente en los compiladores para representar la estructura del código del programa. Un AST suele ser el resultado de la fase de análisis sintáctico de un compilador. Suele servir como representación intermedia del programa a través de varias etapas que requiere el compilador y tiene un fuerte impacto en el resultado final del compilador.
Motivación
Un AST tiene varias propiedades que facilitan los pasos posteriores del proceso de compilación:
- Un AST se puede editar y mejorar con información como propiedades y anotaciones para cada elemento que contiene. Dicha edición y anotación es imposible con el código fuente de un programa, ya que implicaría modificarlo.
- En comparación con el código fuente , un AST no incluye puntuación ni delimitadores no esenciales (llaves, punto y coma, paréntesis, etc.).
- Un AST suele contener información adicional sobre el programa, debido a las sucesivas etapas de análisis por parte del compilador. Por ejemplo, puede almacenar la posición de cada elemento en el código fuente, lo que permite al compilador imprimir mensajes de error útiles.
Los lenguajes suelen ser ambiguos por naturaleza. Para evitar esta ambigüedad, los lenguajes de programación suelen especificarse como una gramática libre de contexto (CFG). Sin embargo, a menudo hay aspectos de los lenguajes de programación que una CFG no puede expresar, pero que son parte del lenguaje y están documentados en su especificación. Se trata de detalles que requieren un contexto para determinar su validez y comportamiento. Por ejemplo, si un lenguaje permite declarar nuevos tipos, una CFG no puede predecir los nombres de dichos tipos ni la forma en que deben usarse. Incluso si un lenguaje tiene un conjunto predefinido de tipos, imponer un uso adecuado suele requerir algo de contexto. Otro ejemplo es el tipado pato , donde el tipo de un elemento puede cambiar según el contexto. La sobrecarga de operadores es otro caso en el que el uso correcto y la función final dependen del contexto.
Diseño
El diseño de un AST suele estar estrechamente vinculado con el diseño de un compilador y sus características esperadas.
Los requisitos básicos incluyen lo siguiente:
- Se deben conservar los tipos de variables, así como la ubicación de cada declaración en el código fuente.
- El orden de las sentencias ejecutables debe estar representado explícitamente y bien definido.
- Los componentes izquierdo y derecho de las operaciones binarias deben almacenarse e identificarse correctamente.
- Los identificadores y sus valores asignados deben almacenarse para las declaraciones de asignación.
Estos requisitos se pueden utilizar para diseñar la estructura de datos para el AST.
Algunas operaciones siempre requerirán dos elementos, como los dos términos para la suma. Sin embargo, algunas construcciones del lenguaje requieren una cantidad arbitrariamente grande de elementos secundarios, como las listas de argumentos que se pasan a los programas desde el shell de comandos . Como resultado, un AST utilizado para representar código escrito en dicho lenguaje también debe ser lo suficientemente flexible para permitir la suma rápida de una cantidad desconocida de elementos secundarios.
Para facilitar la verificación del compilador, debería ser posible descomponer un AST en código fuente. El código fuente generado debería ser lo suficientemente similar al original en apariencia e idéntico en ejecución, tras la recompilación. El AST se utiliza de forma intensiva durante el análisis semántico , donde el compilador comprueba el uso correcto de los elementos del programa y del 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 verificar la corrección del programa.
Después de verificar la corrección, el AST sirve como base para la generación de código. El AST se utiliza a menudo para generar una representación intermedia (IR), a veces denominada lenguaje intermedio , para la generación de código.
Otros usos
Diferenciación de AST
La diferenciación de AST, o para abreviar, diferenciación de árboles, consiste en calcular la lista de diferencias entre dos AST. [1] Esta lista de diferencias se denomina normalmente secuencia de comandos de edición. La secuencia de comandos de edición hace referencia directamente al AST del código. Por ejemplo, una acción de edición puede dar como resultado la adición de un nuevo nodo AST que represente una función.
Detección de clones
Un AST es una abstracción poderosa para realizar la detección de clones de código . [2]
Véase también
- Gráfico semántico abstracto (GSA), también llamado gráfico de términos
- Patrón compuesto
- Gráfico de flujo de control
- Gráfico acíclico dirigido (DAG)
- Modelo de objetos de documento (DOM)
- Árbol de expresión
- Forma extendida de Backus-Naur
- Lisp , una familia de lenguajes escritos en árboles, con macros para manipular árboles de código
- Árbol de análisis , también conocido como árbol de sintaxis concreta
- Árbol de resolución semántica (SRT)
- Algoritmo de patio de maniobras
- Tabla de símbolos
- ÁrbolDL
- Intérpretes de árboles de sintaxis abstracta
Referencias
- ^ Fluri, Beat; Wursch, Michael; Pinzger, Martin; Gall, Harald (2007). "Destilación de cambios: diferenciación de árboles para la extracción de cambios de código fuente de grano fino". IEEE Transactions on Software Engineering . 33 (11): 725–743. doi :10.1109/tse.2007.70731. ISSN 0098-5589. S2CID 13659557.
- ^ Koschke, Rainer; Falke, Raimar; Frenzel, Pierre (2006). "Detección de clones mediante árboles de sufijos de sintaxis abstracta". 13.ª Conferencia de trabajo sobre ingeniería inversa de 2006. IEEE. págs. 253–262. doi :10.1109/wcre.2006.18. ISBN. 0-7695-2719-1.S2CID6985484 .
Lectura adicional
- Jones, Joel. "Idiomas de implementación de árboles de sintaxis abstracta" (PDF) .(descripción general de la implementación de AST en varias familias de lenguajes)
- Neamtiu, Iulian; Foster, Jeffrey S.; Hicks, Michael (17 de mayo de 2005). Understanding Source Code Evolution Using Abstract Syntax Tree Matching (Comprender la evolución del código fuente mediante la búsqueda de coincidencias de árboles de sintaxis abstracta ). MSR'05. Saint Louis, Missouri: ACM. CiteSeerX 10.1.1.88.5815 .
- Würsch, Michael. Mejora de la detección de cambios en el código fuente a partir de árboles de sintaxis abstracta (tesis de diploma).
- Lucas, Jason (16 de agosto de 2006). "Reflexiones sobre el árbol de sintaxis abstracta (AST) de Visual C++".
Enlaces externos
- AST View: un complemento de Eclipse para visualizar un árbol de sintaxis abstracta de Java
- "Árbol de sintaxis abstracta y manipulación de código Java en el IDE de Eclipse". eclipse.org .
- "Representación CAST". cs.utah.edu .
- Proyecto eli: análisis sintáctico del árbol de sintaxis abstracta
- "Estándar de metamodelo de árbol de sintaxis abstracta" (PDF) .
- "Modernización impulsada por la arquitectura — ADM: Metamodelado de árbol de sintaxis abstracta — ASTM".( Estándar OMG ).
- JavaParser: la biblioteca JavaParser le proporciona un árbol de sintaxis abstracta de su código Java. La estructura AST le permite trabajar con su código Java de una manera programática sencilla.
- Spoon: una biblioteca para analizar, transformar, reescribir y transpilar código fuente de Java. Analiza archivos fuente para crear un AST bien diseñado con una potente API de análisis y transformación.
- AST Explorer: un sitio web para ayudar a visualizar AST en varios lenguajes populares como Go, Python, Java y JavaScript.
