Árbol de Análisis Abstracto

Un árbol de análisis abstracto (denotado AAA, en inglés abstract syntax tree o AST) porta la misma información que el árbol de análisis sintáctico pero de forma mas condensada, eliminándose terminales y producciones que no aportan información.

Alfabeto con Aridad o Alfabeto Árbol

Definición 7.1.1   Un alfabeto con función de aridad es un par $(\Sigma, \rho)$ donde $\Sigma$ es un conjunto finito y $\rho$ es una función $\rho: \Sigma \rightarrow \mathds{N}_0$, denominada función de aridad. Denotamos por $\Sigma_k = \{ a \in \Sigma : \rho(a) = k \}$.

Lenguaje de los Arboles

Definimos el lenguaje árbol homogéneo $B(\Sigma)$ sobre $\Sigma$ inductivamente:

• Todos los elementos de aridad 0 están en $B(\Sigma)$: $a \in \Sigma_0$ implica $a \in B(\Sigma)$
• Si $b_1, \ldots , b_k \in B(\Sigma)$ y $f \in \Sigma_k$ es un elemento $k$-ario, entonces $f(b_1, \ldots , b_k) \in B(\Sigma)$

Los elementos de $B(\Sigma)$ se llaman árboles o términos.

Ejemplo 7.1.1   Sea $\Sigma = \{A, CONS, NIL \}$ con $\rho(A) = \rho(NIL) = 0, \rho(CONS) = 2$. Entonces

$B(\Sigma) = \{ A, NIL, CONS(A,NIL), CONS(NIL, A), CONS(A, A), CONS(NIL,NIL), \ldots \}$

Ejemplo 7.1.2   Una versión simplificada del alfabeto con aridad en el que estan basados los árboles construidos por el compilador de Tutu es:

$\Sigma = \{ID, NUM, LEFTVALUE, STR, PLUS, TIMES, ASSIGN, PRINT \}$

$\rho(ID) = \rho(NUM) = \rho(LEFTVALUE) = \rho(STR) = 0$

$\rho(PRINT) = 1$

$\rho(PLUS) = \rho(TIMES) = \rho(ASSIGN) = 2$.

Observe que los elementos en $B(\Sigma)$ no necesariamente son árboles ``correctos''. Por ejemplo, el árbol $ASSIGN(NUM, PRINT(ID))$ es un elemento de $B(\Sigma)$.

Gramática Árbol

Definición 7.1.2   Una gramática árbol regular es una cuadrupla $((\Sigma, \rho), N, P, S)$, donde:

• $(\Sigma, \rho)$ es un alfabeto con aricidad $\rho: \Sigma \rightarrow \mathds{N}$
• $N$ es un conjunto finito de variables sintácticas o no terminales
• $P$ es un conjunto finito de reglas de producción de la forma $X \rightarrow s$ con $X \in N$ y $s \in B(\Sigma \cup N)$
• $S \in N$ es la variable o símbolo de arranque

Lenguaje Generado por una Gramática Árbol

Definición 7.1.3   Dada una gramática $(\Sigma, N, P, S)$, se dice que un árbol $t \in B(\Sigma \cup N)$ es del tipo $(X_1, \ldots X_k)$ si el $j$-ésimo noterminal, contando desde la izquierda, que aparece en $t$ es $X_j \in N$.

Si $p = X \rightarrow s$ es una producción y $s$ es de tipo $(X_1, \ldots X_n)$, diremos que la producción $p$ es de tipo $(X_1, \ldots X_n) \rightarrow X$.

Definición 7.1.4   Consideremos un árbol $t \in B(\Sigma \cup N)$ que sea del tipo $(X_1, \ldots X_n)$, esto es las variables sintácticas en el árbol leídas de izquierda a derecha son $(X_1, \ldots X_n)$.

• Si $X_i \rightarrow s_i \in P$ para algún $i$, entonces decimos que el árbol $t$ deriva en un paso en el árbol $t'$ resultante de sustituir el nodo $X_i$ por el árbol $s_i$ y escribiremos $t \Longrightarrow t'$. Esto es, $t' = t\{X_i/s_i\}$
• Todo árbol deriva en cero pasos en si mismo $t \stackrel{0}{\Longrightarrow} t$.
• Decimos que un árbol $t$ deriva en $n$ pasos en el árbol $t'$ y escribimos $t \stackrel{n}{\Longrightarrow} t'$ si $t$ deriva en un paso en un árbol $t''$ el cuál deriva en $n-1$ pasos en $t'$. En general, si $t$ deriva en un cierto número de pasos en $t'$ escribiremos $t \stackrel{*}{\Longrightarrow} t'$.

Definición 7.1.5   Se define el lenguaje árbol generado por una gramática $G = (\Sigma, N, P, S)$ como el lenguaje $L(G) = \{ t \in B(\Sigma): \exists S \stackrel{*}{\Longrightarrow} t \}$.

Ejemplo 7.1.3   Sea $G =(\Sigma,V,P,S)$ con $\Sigma = \{A, CONS, NIL \}$ y $\rho(A) = \rho(NIL) = 0, \rho(CONS) = 2$ y sea $V = \{ exp, list \}$. El conjunto de producciones $P$ es:

$P_1 = \{ list \rightarrow NIL, list \rightarrow CONS(exp,list), exp \rightarrow A \}$

La producción $list \rightarrow CONS(exp,list)$ es del tipo $(exp,list) \rightarrow list$.

El lenguaje generado por $G$ se obtiene realizando sustituciones sucesivas (derivando) desde el símbolo de arranque hasta producir un árbol cuyos nodos estén etiquetados con elementos de $\Sigma$. En este ejemplo, $L(G)$ es el conjunto de arboles de la forma:

$L(G) = \{ NIL, CONS(A, NIL), CONS(A, CONS(A,NIL)), \ldots \}$

Ejercicio 7.1.1   Construya una derivación para el árbol $CONS(A, CONS(A,NIL))$. ¿De que tipo es el árbol $CONS(exp, CONS(A, CONS(exp,L)))$?.

Cuando hablamos del AAA producido por un analizador sintáctico, estamos en realidad hablando de un lenguaje árbol cuya definición precisa debe hacerse a través de una gramática árbol regular. Mediante las gramáticas árbol regulares disponemos de un mecanismo para describir formalmente el lenguaje de los AAA que producirá el analizador sintáctico para las sentencias Tutu.

Ejemplo 7.1.4   Sea $G =(\Sigma,V,P,S)$ con

$\Sigma = \{ID, NUM, LEFTVALUE, STR, PLUS, TIMES, ASSIGN, PRINT \}$

$\rho(ID) = \rho(NUM) = \rho(LEFTVALUE) = \rho(STR) = 0$

$\rho(PRINT) = 1$

$\rho(PLUS) = \rho(TIMES) = \rho(ASSIGN) = 2$

$V = \{ st, expr \}$

y las producciones:

$P =$	$\{$
	$st$	$\rightarrow ASSIGN(LEFTVALUE, expr)$
	$st$	$\rightarrow PRINT(expr)$
	$expr$	$\rightarrow PLUS(expr, expr)$
	$expr$	$\rightarrow TIMES(expr, expr)$
	$expr$	$\rightarrow NUM$
	$expr$	$\rightarrow ID$
	$expr$	$\rightarrow STR$
	$\}$

Entonces el lenguaje $L(G)$ contiene árboles como el siguiente:

$ASSIGN$	$($
	$LEFTVALUE$,
	$PLUS$	$($
		$ID$,
		$TIMES$	$($
			$NUM$,
			$ID$
			$)$
		$)$
	$)$

El cual podría corresponderse con una sentencia como a = b + 4 * c.

El lenguaje de árboles descrito por esta gramática árbol es el lenguaje de los AAA de las sentencias de Tutu.

Ejercicio 7.1.2   Redefina el concepto de árbol de análisis concreto dado en la definición 5.1.7 utilizando el concepto de gramática árbol. Con mas precisión, dada una gramática $G =(\Sigma,V,P,S)$ defina una gramática árbol $T = (\Omega, N, R, U)$ tal que $L(T)$ sea el lenguaje de los árboles concretos de $G$. Puesto que las partes derechas de las reglas de producción de $P$ pueden ser de distinta longitud, existe un problema con la aricidad de los elementos de $\Omega$. Discuta posibles soluciones.

Ejercicio 7.1.3   ¿Cómo son los árboles sintácticos en las derivaciones árbol? Dibuje varios árboles sintácticos para las gramáticas introducidas en los ejemplos y .

Intente dar una definición formal del concepto de árbol de análisis sintáctico asociado con una derivación en una gramática árbol

Notación de Dewey o Coordenadas de un Árbol

Definición 7.1.6   La notación de Dewey es una forma de especificar los subárboles de un árbol $t \in B(\Sigma)$. La notación sigue el mismo esquema que la numeración de secciones en un texto: es una palabra formada por números separados por puntos. Así t/2.1.3 denota al tercer hijo del primer hijo del segundo hijo del árbol $t$. La definición formal sería:

• $t/\epsilon = t$
• Si $t = a(t_1, \ldots t_k)$ y $j \in \{ 1 \ldots k \}$ y $n$ es una cadena de números y puntos, se define inductivamente el subárbol $t/j.n$ como el subárbol $n$-ésimo del $j$-ésimo subárbol de $t$. Esto es: $t/j.n = t_j/n$

Ejercicio 7.1.4   Sea el árbol:

$t = ASSIGN$	$($
	$LEFTVALUE$,
	$PLUS$	$($
		$ID$,
		$TIMES$	$($
			$NUM$,
			$ID$
			$)$
		$)$
	$)$

Calcule los subárboles $t/\epsilon$, $t/2\ldotp2\ldotp1$, $t/2\ldotp1$ y $t/2\ldotp1\ldotp2$.