Inicio

Árbol de Sintaxis Abstracto (AST)

Qué es un AST

Debido a los problemas que presenta el árbol concreto, se crea en su lugar el árbol de sintaxis abstracta o abstract syntax tree (AST).

El AST es el árbol mínimo que preserva la semántica de la entrada. Se caracteriza por no tener los dos problemas del árbol concreto:

  • Por definición, no tiene nodos redundantes. El AST deja la información mínima que vayan a necesitar las demás fases (la esencia de la entrada).
  • Aunque cambie la gramática, si el lenguaje no cambia, el AST generado para una misma entrada sigue siendo el mismo. Esto es porque no se basa en los símbolos de la gramática para crear los nodos.

Cómo se Obtiene

¿Qué nodos tiene que tener el AST de un lenguaje? En el caso del árbol concreto no hay que hacerse esta pregunta, ya que los nodos son los símbolos de la gramática.

En el caso del AST, sí que hay que identificarlos y definirlos. Tienen que ser:

  • suficientes nodos como para que se pueda representar en forma de árbol cualquier entrada válida del lenguaje.
  • y solamente esos nodos (que no haya nodos que se pudieran eliminar sin perder información).

Antes de ver cómo obtener estos nodos, es importante tener claro de dónde no se obtienen:

  • El AST no se diseña a partir de la gramática. De hecho, podrían definirse los nodos del AST antes de haber hecho esta. Si el AST se diseñara a partir de la gramática, habría que cambiar su diseño cada vez que esta cambiara (como ocurre con el árbol concreto).
  • De la misma manera, el AST no es una reducción o transformación del árbol concreto; no es coger este último y quitarle los nodos que sobran. El AST no se obtiene a partir del árbol concreto. No se trata, por desgracia, de aplicar una serie de pasos al concreto para obtener un AST. Sus nodos no tienen ninguna relación. De hecho, lo habitual será que el AST tenga nodos que no estén en el árbol concreto.

Por tanto, si el AST no viene de la gramática ni del árbol concreto ¿de dónde viene? Viene de las necesidades de las demás fases del traductor. Se deberá diseñar el AST con el objetivo de que facilite al máximo las tareas que tengan que realizar las fases que lo van a utilizar. Por tanto, diseñar un AST no es más que un ejercicio normal de diseño orientado a objetos en el que, para conseguir dicho objetivo, como es habitual, hay que determinar:

  • Qué nodos/objetos se necesitan.
  • Con qué propiedades.
  • Qué relaciones hay entre los nodos (padre-hijo, composición, ...).

Por tanto, la única herramienta que se requiere para crear el AST es el adecuado conocimiento de diseño orientado a objetos.

Nota

📌 Podría plantearse la duda de que, si el diseño del AST es aquel que facilite las fases posteriores del traductor, cómo es posible hacerlo antes de que se construyan estas. Esto es cierto, por lo que hay que contar con los previsibles cambios del AST que se presentarán cuando se hagan estas fases. Es totalmente normal que el AST se vaya ajustando a medida que avance el traductor

Ejemplo

Supóngase la siguiente entrada:

print a;
while a {
    print b;
}

¿Cuál es la información mínima que representa lo que hace dicho programa? Una forma de averiguarlo, por ejemplo, sería plantearse qué es lo único que necesitan saber de esa entrada las demás fases (por ejemplo, el generador de código). En el caso de la entrada anterior, la esencia de dicha entrada es:

  • Que hay dos sentencias: una escritura y un bucle while.
  • La escritura imprime el valor de a (no aporta nada el punto y coma para generar el código).
  • La condición del while es el valor de la a y, si se cumple, imprime b.

Pues esa esencia es lo único que debe incluir el AST de dicha entrada.

Se pueden comparar el árbol concreto y el AST de la misma entrada.

Como puede observarse:

  • El AST es mucho más pequeño y fácil de entender.
  • El AST no está acoplado a la gramática, ya que la estructura del árbol no se basa en la forma de las producciones de ésta.