Inicio

Diseño de un AST

En el capítulo anterior se comentó que para la obtención de los nodos del AST no se partía de la gramática ni del árbol concreto, sino que es una labor de diseño de software.

En este apartado se verá el proceso de manera informal para, en el siguiente capítulo, formalizar el resultado.

Descripción del lenguaje de ejemplo

Supóngase que se quiere diseñar el AST para un lenguaje del cual la siguiente entrada es un ejemplo.

a = 2;
while (a < 100) {
	 read b;
	 a = a + b ;
}

La especificación informal del lenguaje es:

  • No tiene definición de variables.
  • Sólo tienen las sentencias que se ven en el ejemplo.
  • Los operadores aritméticos son los cuatro básicos (suma, resta, multiplicación y división). Los relacionales son el mayor, menor e igual.

Proceso de Diseño de un AST

Aunque en la práctica se haría todo a la vez, en este ejemplo, para simplificar la explicación, se va a realizar el diseño del AST del lenguaje en dos etapas:

  • Primero se identificarán los nodos necesarios en el lenguaje.
  • Luego se determinarán los hijos de cada uno.

Identificar Nodos

Según el enunciado, para modelar cualquier entrada serán necesarios los siguientes nodos. Con ExprBin (expresión binaria) se representarán tanto las operaciones aritméticas como las relacionales.

Identificar Hijos

Hay que determinar qué hijos tendrá cada nodo. Por cada hijo se crea una rama. Además, a cada rama se le asocia un tipo — el tipo que deben tener los nodos que se quieran conectar en dicha rama. Si no se le pusiera ningún tipo significaría que en dicha rama se podría poner como hijo cualquier nodo. El tipo supone, por tanto, una forma de expresar las restricciones a la hora de conectar nodos.

Nota

📌 El restringir los hijos a un determinado tipo no garantiza la validez del árbol. Se darán casos en los que, aunque los hijos sean del tipo adecuado, el árbol no será válido. Pero las condiciones adicionales sobre los hijos se comprobarán en la siguiente fase, el análisis semántico

A la hora de elegir un tipo para una rama habrá que elegir uno de entre los tres casos siguientes:

  1. El tipo es otro nodo.
  2. El tipo es una categoría sintáctica. Cuando un nodo pueda tener como hijo a nodos de distintos tipos, en vez de indicar cada uno en la rama, se define una categoría sintáctica con todos ellos y es el nombre de ésta la que se pone como tipo de la rama (es decir, es un atajo para poner varios tipos).
  3. El tipo es un tipo propio del lenguaje de implementación del AST. La mayoría de las veces será el tipo string del lenguaje.

Además, si en una rama es multivaluada (puede haber varios hijos en ella) se pondrá un '*' en el tipo para indicarlo. Adelantándonos a la implementación, que se verá más tarde, ya se puede intuir que esta rama se implementará como una lista.

Con lo anterior, quedaría el siguiente diseño de nodos.

A destacar:

  • Los nodos literalEntero y variable tienen un string como hijo (caso 3).
  • El nodo lectura tiene otro nodo como hijo (caso 1).
  • El nodo asigna, como su segundo hijo, puede tener un literalEntero, una variable o una exprBinaria. Para indicar esto, se forma la categoría sintáctica expresión que incluye a todos ellos y es este tipo el que se asocia a la rama.
  • La exprBinaria tiene tres ramas:
    • La primera y la tercera pueden tener como hijos los mismos nodos que forman parte de la categoría expresión. En este caso, dado que todos los nodos coinciden, se reutiliza dicha categoría en vez de crear una nueva.
    • La segunda rama es un string (el operador de la expresión).
  • El programa puede tener como hijos a lectura, a asigna y a while. Para indicar esto, se crea la categoría sentencia y es este tipo el que se asocia a la rama. Además, puede tener varios hijos de este tipo (varias sentencias). Por tanto, se añade el '*' al tipo de la rama para indicar que será una lista de hijos.

Con esto, quedarían definidos todos los nodos del AST del lenguaje.

Aunque en este caso no se ha presentado la situación, podría darse que un nodo estuviera en más de una categoría sintáctica.

Nota

📌 Nótese que, para crear los nodos, se ha partido de analizar las estructuras del lenguaje (con uno o más ejemplos de entradas válidas) pero no de la gramática (que ni siquiera se ha hecho)

Aplicación de los Nodos a una entrada

Una vez definidos todos los nodos, se debería poder modelar en forma de árbol cualquier entrada del lenguaje con ellos.

Supóngase la siguiente entrada correspondiente al lenguaje para el cual se ha hecho el diseño de nodos anterior.

a = 2;
while (a < 100) {
	 read b;
	 a = a + b ;
}

Se propone, como ejercicio para el alumno, usar los nodos definidos anteriormente para dibujar el AST correspondiente a la entrada anterior.