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 sintáctico de un compilador. A menudo sirve como una representación intermedia del programa a través de varias etapas que el compilador requiere, y tiene un fuerte impacto en la salida final del compilador.
MotivaciónEdición
Un AST tiene varias propiedades que ayudan a 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.
- Comparado con el código fuente, un AST no incluye puntuación y delimitadores no esenciales (llaves, punto y coma, paréntesis, etc.).
- Un AST suele contener información extra 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 AST son necesarios debido a la naturaleza inherente de los lenguajes de programación y su documentació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 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 CFG no puede predecir los nombres de dichos tipos ni la forma en que deben utilizarse. Incluso si un lenguaje tiene un conjunto predefinido de tipos, la aplicación de un uso adecuado suele requerir algo de contexto. Otro ejemplo es la tipificación de patos, donde el tipo de un elemento puede cambiar dependiendo del contexto. La sobrecarga de operadores es otro caso en el que el uso correcto y la función final se determinan en función del contexto. Java proporciona un excelente ejemplo, donde el operador ‘+’ es tanto una adición numérica como una concatenación de cadenas.
Aunque hay otras estructuras de datos involucradas en el funcionamiento interno de un compilador, el AST realiza una función única. Durante la primera etapa, la etapa de análisis sintáctico, un compilador produce un árbol de análisis sintáctico. Este árbol de análisis sintáctico puede utilizarse para realizar casi todas las funciones de un compilador mediante la traducción dirigida por la sintaxis. Aunque este método puede dar lugar a un compilador más eficiente, va en contra de los principios de la ingeniería del software para escribir y mantener programas. Otra ventaja que tiene el AST sobre un árbol de análisis sintáctico es el tamaño, en particular la menor altura del AST y el menor número de elementos.
DiseñoEdit
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 los siguientes:
- Los tipos de variables deben conservarse, así como la ubicación de cada declaración en el código fuente.
- El orden de las declaraciones ejecutables debe representarse explícitamente y estar 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 pueden utilizarse 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 un número arbitrario de hijos, 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 tal lenguaje tiene que ser también lo suficientemente flexible como para permitir la adición rápida de una cantidad desconocida de hijos.
Para apoyar la verificación del compilador debe 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.
UsageEdit
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 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 llamado un lenguaje intermedio, para la generación de código.