Árbol de sintaxis abstracta

Un árbol de sintaxis abstracto para el siguiente código para el algoritmo de Euclidean:

mientras b ل 0: si a ■ b: a := a - b más: b := b - aretorno a

En informática, un árbol de sintaxis abstracta (AST), o simplemente árbol de sintaxis, es una representación de árbol de la estructura sintáctica abstracta de texto (a menudo código fuente) escrito en un lenguaje formal. Cada nodo del árbol denota una construcción que ocurre en el texto.

La sintaxis es "abstracto" en el sentido de que no representa todos los detalles que aparecen en la sintaxis real, sino solo 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. Del mismo modo, una construcción sintáctica como una declaración si-condición-entonces se puede denotar por medio de un solo nodo con tres ramas.

Esto distingue los árboles de sintaxis abstractos de los árboles de sintaxis concretos, designados tradicionalmente como árboles de análisis. Los árboles de análisis generalmente los crea 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.

Aplicación en compiladores

Los árboles de sintaxis abstracta son estructuras de datos muy utilizadas en los 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.

Motivación

Un AST tiene varias propiedades que ayudan en los pasos posteriores del proceso de compilación:

• Un AST puede ser editado y mejorado con información como propiedades y anotaciones para cada elemento que contiene. Tal edición y anotación es imposible con el código fuente de un programa, ya que implicaría cambiarlo.
• En comparación con el código fuente, un AST no incluye punción y delimitadores inesenciales (cerebros, semicolonias, paréntesis, etc.).
• Un AST generalmente contiene información extra sobre el programa, debido a las etapas consecutivas de análisis por el compilador. Por ejemplo, puede almacenar la posición de cada elemento en el código fuente, permitiendo al compilador imprimir mensajes de error útiles.

Los AST son necesarios debido a la naturaleza inherente de los lenguajes de programación y su documentación. Los lenguajes son a menudo ambiguos por naturaleza. Para evitar esta ambigüedad, los lenguajes de programación a menudo se especifican como una 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 son parte del lenguaje y están documentados en su especificación. Estos son detalles que requieren un contexto para determinar su validez y comportamiento. Por ejemplo, si un idioma 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 la tipificación de patos, 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 relacionado con el diseño de un compilador y sus características esperadas.

Los requisitos básicos incluyen lo siguiente:

• Deben conservarse tipos variables, así como la ubicación de cada declaración en código fuente.
• El orden de las declaraciones ejecutables debe estar explícitamente representado y bien definido.
• Los componentes izquierdo y derecho de las operaciones binarias deben ser almacenados e identificados correctamente.
• Los identificadores y sus valores asignados deben ser almacenados para 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 de 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 el 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 elementos secundarios.

Para admitir la verificación del compilador, debería ser posible desanalizar un AST en forma de código fuente. El código fuente producido debe ser lo suficientemente similar al original en apariencia e idéntico en ejecución, luego de la recompilación. El AST se usa intensamente durante el análisis semántico, donde el compilador verifica el uso correcto 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 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 usa 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 AST

La diferenciación de AST, o para abreviar la diferenciación en árbol, consiste en calcular la lista de diferencias entre dos AST. Esta lista de diferencias se suele denominar script de edición. El script de edición se refiere 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 representa una función.

Detección de clones

Un AST es una poderosa abstracción para realizar la detección de clones de código.