Árbol de sintaxis abstracta

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

• Un árbol de sintaxis abstracta (AST) puede editarse y ampliarse 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 signos de puntuación ni delimitadores no esenciales (llaves, puntos y comas, paréntesis, etc.).
• Un AST suele contener información adicional sobre el programa, debido a las sucesivas etapas de análisis realizadas por el 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 se especifican a menudo como gramáticas libres de contexto (GLC). Sin embargo, existen aspectos de los lenguajes de programación que una GLC no puede expresar, pero que forman 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 GLC 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, garantizar su uso correcto suele requerir cierto contexto. Otro ejemplo es el tipado dinámico (duck typing ), 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 árbol de sintaxis abstracta (AST) suele estar estrechamente vinculado con el diseño de un compilador y sus características previstas.

Los requisitos básicos incluyen lo siguiente:

• Es necesario conservar los tipos de variables, así como la ubicación de cada declaración en el código fuente.
• El orden de las instrucciones ejecutables debe estar representado de forma explícita 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 sentencias de asignación.

Estos requisitos pueden utilizarse para diseñar la estructura de datos del AST.

Algunas operaciones siempre requerirán dos elementos, como los dos términos de la suma. Sin embargo, algunas construcciones del lenguaje requieren un número arbitrariamente grande de elementos secundarios, como las listas de argumentos que se pasan a los programas desde la línea de comandos . Por lo tanto, un árbol de sintaxis abstracta (AST) utilizado para representar código escrito en dicho lenguaje debe ser lo suficientemente flexible como para permitir la adición rápida de una cantidad desconocida de elementos secundarios.

Para facilitar la verificación del compilador, debería ser posible convertir un AST a código fuente. El código fuente resultante, tras la recompilación, debería ser suficientemente similar al original en apariencia e idéntico en ejecución. El AST se utiliza intensivamente durante el análisis semántico , donde el compilador comprueba el uso correcto de los elementos del programa y del lenguaje. Durante este análisis, el compilador también genera tablas de símbolos basadas en el AST. Un recorrido completo del árbol permite verificar la corrección del programa.

Tras verificar su corrección, el AST sirve de 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 comparación de AST, o simplemente comparación de árboles, consiste en calcular la lista de diferencias entre dos AST. ^{[ 1 ] [ 2 ]} Esta lista de diferencias se suele denominar script de edición. El script de edición hace referencia directa 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.

Un AST es una abstracción poderosa para realizar la detección de clones de código . ^{[ 3 ]}

Dejar${\displaystyle S}$ser un conjunto de algún tipo , una aridad es una tupla${\displaystyle (s_{1},\dots ,s_{n},s)}$, para${\displaystyle s_{1},\dots ,s_{n},s\in S}$, también escrito como${\displaystyle (s_{1},\dots ,s_{n})s}$. Más precisamente,${\displaystyle \mathrm {Aridad} (S):=\coprod _{n\in \mathbb {N} }S^{n+1}}$.

Dejar${\displaystyle {\mathcal {O}}=\{{\mathcal {O_{\alpha }}}\}_{\alpha \in \mathrm {Arity} (S)}}$frijol${\displaystyle \mathrm {Aridad} (S)}$Familia indexada de conjuntos disjuntos de operadores . Si${\displaystyle o}$es una aridad de operador${\displaystyle (s_{1},\dots ,s_{n})s}$decimos que${\displaystyle o}$tiene tipo${\displaystyle s}$y tiene${\displaystyle n}$discusiones de algún tipo${\displaystyle s_{1},\dots ,s_{n}}$.

Arreglar${\displaystyle S}$ser un conjunto finito de algún tipo, y${\displaystyle {\mathcal {O}}}$un${\displaystyle \mathrm {Aridad} (S)}$Familia indexada de conjuntos disjuntos de operadores . Sea${\displaystyle {\mathcal {X}}=\{{\mathcal {X}}_{s}\}_{s\in S}}$frijol${\displaystyle S}$Familia indexada de conjuntos disjuntos de variables. La familia${\displaystyle {\mathcal {A}}[{\mathcal {X}}]=\{{\mathcal {A}}[{\mathcal {X}}]_{s}\}_{s\in S}}$de árboles de sintaxis abstracta , o AST , es el más pequeño${\displaystyle S}$Familia indexada de conjuntos disjuntos cerrada bajo las siguientes condiciones:

1. Las variables son AST: si${\displaystyle x\in {\mathcal {X}}_{s}}$, entonces${\displaystyle x\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$.
2. Los operadores combinan AST: Si${\displaystyle o}$es un operador de aridad${\displaystyle (s_{1},\dots ,s_{n})s}$, y${\displaystyle a_{i}\in {\mathcal {A}}[{\mathcal {X}}]_{s_{i}}}$a pesar de${\displaystyle 1\leq i\leq n}$, entonces${\displaystyle o(a_{1};\dots ;a_{n})\in {\mathcal {A}}[{\mathcal {X}}]_{s}}$.