mientras b ≠ 0 : si a > b : a := a - b else : b := b - a devuelve aUn á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 á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 ocurre en el texto. A veces se le llama 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 es necesario representarlos como nodos separados. De manera similar, una construcción sintáctica como una declaración si-condición-entonces puede denotarse por medio de un solo nodo con tres ramas.
Esto distingue los árboles de sintaxis abstracta de los árboles de sintaxis concreta, tradicionalmente denominados árboles de análisis . Los árboles de análisis suelen ser creados por un analizador durante el proceso de traducción y compilación del código fuente . Una vez construido, se agrega información adicional al AST mediante un procesamiento posterior, por ejemplo, análisis contextual .
Los árboles de sintaxis abstracta también se utilizan en sistemas de análisis y transformación de programas .
Los árboles de sintaxis abstracta son estructuras de datos ampliamente utilizadas en compiladores para representar la estructura del código del programa. Un AST suele ser el resultado de la fase de análisis de sintaxis de un compilador. A menudo sirve como una 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.
Un AST tiene varias propiedades que ayudan en los pasos posteriores del proceso de compilación:
Los AST son necesarios debido a la naturaleza inherente de los lenguajes de programación y su documentación. Los idiomas suelen ser ambiguos por naturaleza. Para evitar esta ambigüedad, los lenguajes de programación suelen especificarse como gramática libre de contexto (CFG). Sin embargo, a menudo hay aspectos de los lenguajes de programación que un CFG no puede expresar, pero que son parte del lenguaje y están documentados en su especificación. Son detalles que requieren de un contexto para determinar su validez y comportamiento. Por ejemplo, si un lenguaje permite declarar nuevos tipos, un CFG no puede predecir los nombres de dichos tipos ni la forma en que deben usarse. Incluso si un idioma tiene un conjunto predefinido de tipos, hacer cumplir el uso adecuado generalmente requiere algo de contexto. Otro ejemplo es el tipeo pato , donde el tipo de un elemento puede cambiar según el contexto. La sobrecarga de operadores es otro caso más en el que el uso correcto y la función final dependen del contexto.
El diseño de un AST suele estar estrechamente relacionado con el diseño de un compilador y sus características esperadas.
Los requisitos básicos incluyen lo siguiente:
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 de la suma. Sin embargo, algunas construcciones del lenguaje requieren una cantidad arbitrariamente grande de elementos secundarios, como las listas de argumentos pasadas 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 como para permitir la adición rápida de una cantidad desconocida de niños.
Para admitir la verificación del compilador, debería ser posible descomponer un AST en forma de código fuente. El código fuente producido debe ser suficientemente similar al original en apariencia e idéntico en ejecución, tras la recompilación. El AST se utiliza intensamente 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 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 del 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.
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 normalmente se denomina script de edición. El script de edición hace referencia directamente al AST del código. Por ejemplo, una acción de edición puede resultar en la adición de un nuevo nodo AST que represente una función.
Un AST es una poderosa abstracción para realizar la detección de clones de código . [2]
