Sig: Realización del AAA para Sup: Árbol de Análisis Abstracto Ant: Árbol de Análisis Abstracto Err: Si hallas una errata ...

Lenguajes Árbol y Gramáticas Árbol

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.

Definición 11.9.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 \}$.

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 11.9.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 11.9.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)$.

Definición 11.9.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

Definición 11.9.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 11.9.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 11.9.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 11.9.3   Sea $G =(\Sigma,V,P,S)$ con $\Sigma = \{A, CONS, NIL \}$ y $\rho(A) = \rho(NIL) = 0, \rho(CONS) = 2$ y sea $V = \{ E, L \}$. El conjunto de producciones $P$ es:

$P_1 = \{ L \rightarrow NIL, L \rightarrow CONS(E,L),E \rightarrow a \}$

La producción $L \rightarrow CONS(E,L)$ es del tipo $(E,L) \rightarrow L$.

Informalmente, 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$. Debería ser claro que, en este ejemplo, $L(G)$ es el conjunto de las listas en $A$, incluyendo la lista vacía:

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

Ejercicio 11.9.1   Construya una derivación para el árbol $CONS(A, CONS(A,NIL))$. ¿De que tipo es el árbol $CONS(E, CONS(A, CONS(E,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 11.9.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 11.9.2   Redefina el concepto de árbol de análisis concreto dado en la definición 11.5.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 11.9.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 11.9.3 y 11.9.4.

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

Definición 11.9.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 \ldotp 1 \ldotp 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 11.9.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$.

Sig: Realización del AAA para Sup: Árbol de Análisis Abstracto Ant: Árbol de Análisis Abstracto Err: Si hallas una errata ...