Arboles de reconocimiento sint ctico




Arboles de reconocimiento sintáctico
Héctor Manuel Huerta Toledo
Sección: D-05
Lenguajes de programación comparados




Arboles de reconocimiento sintáctico
Un árbol de análisis sintáctico es unarepresentación gráfica de una derivación que filtra el orden en el que se aplican las producciones para sustituir los no terminales. Cada nodo interior de un árbol de análisis sintáctico representala aplicación de una producción.{Ejemplo de árbol sintáctico}Las hojas de un árbol de análisis sintáctico se etiquetan mediante no terminales o terminales y ,leídas de izquierda a derecha constituyenuna forma de frase, a la cual se le llama producto o frontera del árbol

Arboles de derivación

Un árbol de derivación permite mostrar gráficamente cómo se puede derivar cualquier cadena de un lenguajea 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.
* Todonodo 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ánconectadosal 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.
Propiedades de un árbol de derivación.
Sea G = (N,T,S,P)una gramática libre de contexto, seauna variable. Diremos que un árbol TA = (N,E) etiquetado es un árbol de derivación asociado a G si verifica las propiedades siguientes:

         La raíz delárbol es un símbolo no terminal
         cada hoja corresponde a un símbolo terminal o λ.
         cada nodo interior corresponde a un símbolo no terminal.

Para cada cadena del lenguaje generado por...