Ingeniero

ARBOLES DE DERIVACION

Un árbol de derivación (o árbol sintáctico) es una representación gráfica de como se deriva una forma sentencial a partir del símbolo no-terminal inicial.
Un árbol esun grafo dirigido acíclico en el cual cada nodo se conecta con un nodo distinguido, llamadonodo raíz mediante un único camino. Un nodo n 1 se dice descendiente de otro nodo n 2 si se puede llegar a n 1 apartir de n 1. El nodo raíz no es descendiente de ningún nodo, y los nodos que no tienen descendientes se denominan hojas. El resto de los nodos se denominan nodos interiores.

Un árbol dederivación tiene las siguientes propiedades:
1. El nodo raíz está rotulado con el símbolo distinguido (inicial) de la Gramatica.
2. Cada hoja corresponde a un símbolo terminal o un símbolo no-terminal.3. Cada nodo interior corresponde a un símbolo no-terminal.
Un arbol de derivación muestra gráficamente las derivaciones (substituciones de símbolos no terminales) que hay que llevar a cabo parallegar a una Forma Sentencial a partir del símbolo inicial.
| Las hojas en un arbol de derivación tomadas de izquierda a derecha constituyen una Forma Sentencial de la Gramatica subyacente. |
EjemplosLa siguiente definición BNF describe en forma simplificada la sintaxis de una sentencia de asignación de un lenguaje tipo Pascal:
<sent_asig> ::= <var> ':=' <expresion> <expresion> ::= <expresion> '+' <termino> | <expresion> '-' <termino> | <termino> 
<termino> ::= <termino> '*' <factor> |<termino> '/'<factor> | <factor> 
<factor> ::= ( <expresion> ) |<var> | <num> 
<var> ::= 'A'..'Z' 
<num> ::= '0'..'9'
Un arbol de derivación correspondiente a la sentencia:C := D - E * F
es el siguiente:

Árboles de Derivación y Gramáticas Ambiguas
Una Gramatica Ambigua permite más de una Derivacion para la misma Forma Sentencial por lo que también habrá más...