arbolderivacion

4.2.

´
Arbol
de una derivaci´
on

Un ´
arbol con ra´ız es un tipo muy particular de grafo no-dirigido; est´a formado
por un conjunto de v´ertices o nodos conectados entre s´ı por arcos o aristas,con
la siguiente propiedad: existe un nodo especial, llamado la ra´ız del ´arbol, tal
que hay una u
´nica trayectoria entre cualquier nodo y la ra´ız. De esta manera, la
ra´ız se ramifica en nodos,llamados descendientes inmediatos, cada uno de los
cuales puede tener, a su vez, descendientes inmediatos, y as´ı sucesivamente.
La propiedad que caracteriza a un ´arbol garantiza que un nodo puede tener0, 1,
o m´as descendientes inmediatos pero un u
´nico antecesor inmediato. El u
´nico nodo
que no tiene antecesores es la ra´ız. Los nodos que tienen descendientes, excepto la
ra´ız, se denominannodos interiores. Los nodos que no tienen descendientes se
llaman hojas del ´arbol. En la terminolog´ıa usualmente utilizada, los descendientes
de un nodo tambi´en se denominan hijos y los antecesorespadres o ancestros.
El n´
umero de v´ertices (y por lo tanto, el n´
umero de arcos) de un ´arbol puede ser
infinito.
✞

☎

✝

✆

Ejemplo

Algunos ´arboles con ra´ız:

∗

El ´
arbol de una derivaci´
on S⇒ w, w ∈ Σ∗ , en una GIC es un ´arbol con
ra´ız que se forma de la siguiente manera:
1. La ra´ız est´a etiquetada con el s´ımbolo inicial S.
2. Cada nodo interior est´a etiquetado con un noterminal.
3. Cada hoja est´a etiquetada con terminal o con λ.
4. Si en la derivaci´on se utiliza la producci´on A → s1 s2 · · · sk , donde si ∈
(V ∪ Σ)∗ , el nodo A tiene k descendientes inmediatos: s1 , s2 ,.. . , sk , escritos
de izquierda a derecha.
∗

De esta forma, las hojas del ´arbol de derivaci´on de S ⇒ w son precisamente los
s´ımbolos de la cadena w, le´ıdos de izquierda a derecha y,posiblemente, algunos
λ.
La b´
usqueda de un ´arbol de derivaci´on para una cadena w ∈ Σ∗ se denomina
an´
alisis sint´
actico de w. Los ´arboles de derivaci´on tambi´en se suelen llamar
´arboles sint´acticos o...