Un árbol de derivación permite mostrar
gráficamente cómo se puede derivar cualquier cadena de un lenguaje a partir del
símbolo distinguido de una gramática que genera ese lenguaje.
Un
árbol es un conjunto de puntos, llamados nodos, unidos por líneas, llamadas
arcos. Un arco conecta dos nodos distintos. Para ser un árbol un conjunto de
nodos y arcos debe satisfacer ciertas propiedades:
-
hay un único nodo distinguido, llamado raíz (se dibuja en la parte superior)
que no tiene arcos incidentes.
-
todo nodo c excepto el nodo raíz está conectado con un arco a otro nodo k,
llamado el padre de c (c es el hijo de k). El padre de un nodo, se dibuja por
encima del nodo.
-
todos los nodos están conectados al nodo raíz mediante un único camino.
-
los nodos que no tienen hijos se denominan hojas, el resto de los nodos se
denominan nodos interiores.
El
árbol de derivación tiene las siguientes propiedades:
-
el nodo raíz está rotulado con el símbolo distinguido de la gramática;
-
cada hoja corresponde a un símbolo terminal o un símbolo no terminal;
-
cada nodo interior corresponde a un símbolo no terminal.
Para cada cadena del lenguaje generado por
una gramática es posible construir (al menos) un árbol de derivación, en el
cual cada hoja tiene como rótulo uno de los símbolos de la cadena.
La siguiente definición BNF describe la
sintaxis (simplificada) de una sentencia de asignación de un lenguaje tipo
Pascal:
Por ejemplo, la sentencia A:= A + B es una
sentencia de asignación que pertenece al lenguaje definido por la definición
BNF dada, y cuyo árbol de derivación se construye como se muestra a
continuación:
El árbol de derivación correspondiente a la sentencia C:=
D – E * F es el siguiente:
