Patrones Árbol y Transformaciones Árbol

Una transformación de un programa puede ser descrita como un conjunto de reglas de transformación o esquema de traducción árbol sobre el árbol abstracto que representa el programa.

En su forma mas sencilla, estas reglas de transformación vienen definidas por ternas $(p, e, action)$, donde la primera componente de la terna $p$ es un patrón árbol que dice que árboles deben ser seleccionados. La segunda componente $e$ dice cómo debe transformarse el árbol que casa con el patrón $p$. La acción $action$ indica como deben computarse los atributos del árbol transformado a partir de los atributos del árbol que casa con el patrón $p$. Una forma de representar este esquema sería:

$p \Longrightarrow e$ { action }

Por ejemplo:

$PLUS(NUM_1, NUM_2) \Longrightarrow NUM_3$ { $NUM_3{VAL} = $NUM_1{VAL} + $NUM_2{VAL} }

cuyo significado es que dondequiera que haya un nódo del AAA que case con el patrón de entrada $PLUS(NUM, NUM)$ deberá sustituirse el subárbol $PLUS(NUM, NUM)$ por el subárbol $NUM$. Al igual que en los esquemas de traducción, enumeramos las apariciones de los símbolos, para distinguirlos en la parte semántica. La acción indica como deben recomputarse los atributos para el nuevo árbol: El atributo VAL del árbol resultante es la suma de los atributos VAL de los operandos en el árbol que ha casado. La transformación se repite hasta que se produce la normalización del árbol.

Las reglas de ``casamiento'' de árboles pueden ser mas complejas, haciendo alusión a propiedades de los atributos, por ejemplo

$ASSIGN(LEFTVALUE, x) and$ { notlive($LEFTVALUE{VAL}) } $\Longrightarrow NIL$

indica que se pueden eliminar aquellos árboles de tipo asignación en los cuáles la variable asociada con el nodo $LEFTVALUE$ no se usa posteriormente.

Otros ejemplos con variables $S_1$ y $S_2$:

$IFELSE(NUM, S_1, S_2)$ and { $NUM{VAL} != 0 } $\Longrightarrow S_1$
$IFELSE(NUM, S_1, S_2)$ and { $NUM{VAL} == 0 } $\Longrightarrow S_2$

Observe que en el patrón de entrada $ASSIGN(LEFTVALUE, x)$ aparece un ``comodín'': la variable-árbol $x$, que hace que el árbol patrón $ASSIGN(LEFTVALUE, x)$ case con cualquier árbol de asignación, independientemente de la forma que tenga su subárbol derecho.

Las siguientes definiciones formalizan una aproximación simplificada al significado de los conceptos patrones árbol y casamiento de árboles.

Patrón Árbol

Definición 7.3.1   Sea $(\Sigma, \rho)$ un alfabeto con función de aridad y un conjunto (puede ser infinito) de variables $V =\{ x_1, x_2, \ldots \}$. Las variables tienen aridad cero:

$\rho(x) = 0 \forall x \in V$.

Un elemento de $B(V \cup \Sigma)$ se denomina patrón sobre $\Sigma$.

Patrón Lineal

Definición 7.3.2   Se dice que un patrón es un patrón lineal si ninguna variable se repite.

Definición 7.3.3   Se dice que un patrón es de tipo $(x_1, \ldots x_k)$ si las variables que aparecen en el patrón leidas de izquierda a derecha en el árbol son $x_1, \ldots x_k$.

Ejemplo 7.3.1   Sea $\Sigma = \{A, CONS, NIL \}$ con $\rho(A) = \rho(NIL) = 0, \rho(CONS) = 2$ y sea $V = \{ x \}$. Los siguientes árboles son ejemplos de patrones sobre $\Sigma$:

{ $x, CONS(A, x), CONS(A, CONS(x, NIL)), \ldots \}$

El patrón $CONS(x, CONS(x, NIL))$ es un ejemplo de patrón no lineal. La idea es que un patrón lineal como éste ``fuerza'' a que los árboles $t$ que casen con el patrón deben tener iguales los dos correspondientes subárboles $t/1$ y $t/2\ldotp1$ situados en las posiciones de las variables ^7.1

Ejercicio 7.3.1   Dado la gramática árbol:

$S \rightarrow S_1(a, S, b)$
$S \rightarrow S_2(NIL)$

la cuál genera los árboles concretos para la gramática

$S \rightarrow aSb$ $\vert$ $\epsilon$

¿Es $S_1(a, X(NIL), b)$ un patrón árbol sobre el conjunto de variables $\{X, Y\}$? ¿Lo es $S_1(X, Y, a)$? ¿Es $S_1(X, Y, Y)$ un patrón árbol?

Ejemplo 7.3.2   Ejemplos de patrones para el AAA definido en el ejemplo para el lenguaje Tutu son:

$x, y, PLUS(x, y), ASSIGN(x, TIMES(y,ID)), PRINT(y) \ldots$

considerando el conjunto de variables $V = \{ x, y \}$. El patrón $ASSIGN(x, TIMES(y,ID))$ es del tipo $(x, y)$.

Sustitución

Definición 7.3.4   Una sustitución árbol es una aplicación $\theta$ que asigna variables a patrones $\theta: V \rightarrow B(V \cup \Sigma)$.

Tal función puede ser naturalmente extendida de las variables a los árboles: los nodos (hoja) etiquetados con dichas variables son sustituidos por los correspondientes subárboles.

$\theta : B(V \cup \Sigma) \rightarrow B(V \cup \Sigma)$

$t \theta = \left \{ \begin{array}{ll} x \theta & \mbox{si $t = x \in V$}\\ ... ...ldots, t_k \theta) & \mbox{si $t = a(t_1, \ldots, t_k)$} \end{array} \right.$

Obsérvese que, al revés de lo que es costumbre, la aplicación de la sustitución $\theta$ al patrón se escribe por detrás: $t \theta$.

También se escribe $t \theta = t\{x_1/x_1 \theta, \ldots x_k/x_k \theta\}$ si las variables que aparecen en $t$ de izquierda a derecha son $x_1, \ldots x_k$.

Ejemplo 7.3.3   Si aplicamos la sustitución $\theta = \{x/A, y/CONS(A, NIL)\}$ al patrón $CONS(x, y)$ obtenemos el árbol $CONS(A, CONS(A,NIL))$. En efecto:

$CONS(x, y)\theta = CONS(x\theta, y\theta) = CONS(A, CONS(A, NIL))$

Ejemplo 7.3.4   Si aplicamos la sustitución $\theta = \{x/PLUS(NUM, x), y/TIMES(ID, NUM)\}$ al patrón $PLUS(x, y)$ obtenemos el árbol $PLUS(PLUS(NUM,x), TIMES(ID, NUM))$:

$PLUS(x, y)\theta = PLUS(x\theta, y\theta) = PLUS(PLUS(NUM,x), TIMES(ID, NUM))$

Casamiento Árbol

Definición 7.3.5   Se dice que un patrón $\tau \in B(V \cup \Sigma)$ con variables $x_1, \ldots x_k$ casa con un árbol $t \in B(\Sigma)$ si existe una sustitución de $\tau$ que produce $t$, esto es, si existen $t_1, \ldots t_k \in B(\Sigma)$ tales que $t = \tau \{x_1/t_1, \ldots x_k/t_k\}$. También se dice que $\tau$ casa con la sustitución $\{x_1/t_1, \ldots x_k/t_k\}$.

Ejemplo 7.3.5   El patrón $\tau = CONS(x, NIL)$ casa con el árbol $t = CONS(CONS(A,NIL),NIL)$ y con el subárbol $t \ldotp 1$. Las respectivas sustituciones son $t\{x/CONS(A,NIL)\}$ y $t \ldotp 1 \{x/A\}$.

$t = \tau \{x/CONS(A,NIL)\}$
$t \ldotp 1 = \tau \{x/A\}$

Ejercicio 7.3.2   Sea $\tau = PLUS(x, y)$ y $t = TIMES(PLUS(NUM, NUM), TIMES(ID, ID))$. Calcule los subárboles $t'$ de $t$ y las sustituciones $\{x/t_1, y/t_2\}$ que hacen que $\tau$ case con $t'$.

Por ejemplo es obvio que para el árbol raíz $t/\epsilon$ no existe sustitución posible:

$t = TIMES(PLUS(NUM, NUM), TIMES(ID, ID)) = \tau\{x/t_1, y/t_2\} = PLUS(x, y)\{x/t_1, y/t_2\}$

ya que un término con raíz $TIMES$ nunca podrá ser igual a un término con raíz $PLUS$.

El problema aquí es equivalente al de las expresiones regulares en el caso de los lenguajes lineales. En aquellos, los autómatas finitos nos proveen con un mecanismo para reconocer si una determinada cadena ``casa''' o no con la expresión regular. Existe un concepto análogo, el de autómata árbol que resuelve el problema del ``casamiento'' de patrones árbol. Al igual que el concepto de autómata permite la construcción de software para la búsqueda de cadenas y su posterior modificación, el concepto de autómata árbol permite la construcción de software para la búsqueda de los subárboles que casan con un patrón árbol dado.