mientras b ≠ 0 : si a > b : a := a - b de lo contrario : 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 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 .
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.
Un AST tiene varias propiedades que facilitan los pasos posteriores del proceso de compilación:
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.
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:
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 respaldar la verificación del compilador, debería ser posible descomponer un AST en forma de código fuente. El código fuente producido debería ser lo suficientemente similar al original en apariencia e idéntico en ejecución, al volver a compilarlo. El AST se utiliza intensivamente durante el análisis semántico , donde el compilador verifica 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.
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.
Un AST es una abstracción poderosa para realizar la detección de clones de código . [2]
