Variedad
Páginas: 3 (592 palabras)
Publicado: 7 de junio de 2012
Arboles de derivación
* 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 eselenguaje.
* se les llama árboles de derivación, o también árboles de compilación –por usarse extensivamente en los compiladores– y son de vital importancia para la teoría de los compiladores delos lenguajes de programación.
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 unsímbolo terminal o un símbolo no terminal;
* Cada nodo interior corresponde a un símbolo no terminal.
Formalmente, unárbol se define de la siguiente manera.
* Definición.- Sea G = (V,,R, S) una GLC.
Entonces un árbol de derivación cumple las siguientes propiedades:
* 1. Cada nodo tiene una etiqueta.* 2. La raíz tiene etiqueta S.
* 3. La etiqueta de los nodos que no son hojas debe estar en V , y las de las hojas en [{"}.
* 4. Si un nodo n tiene etiqueta A, y los nodos n1, . . . , nmson sus hijos (de izquierda a derecha), con etiquetas respectivamente A1, . . . ,Am, entonces A ! A1, . . . ,Am 2 R.
* Definición.- La cadena de caracteres que resulta de concatenar loscaracteres terminales encontrados en las etiquetas de los nodos hoja, en un recorrido en orden del árbol de derivación, se llama el producto del árbol.
En este ejemplo, el hecho de que existan dos arbolesde derivación para una misma expresion es indeseable, pues cada árbol indica una manera distinta de estructurar la expresión.
En efecto, en el árbol de la izquierda, al resultado de la suma (x + y)se multiplica con x, mientras que en el de la derecha sumamos x al resultado de multiplicar x con y; por lo tanto el significado que se asocia a ambas expresiones puede ser distinto.
Se dice que...
* 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 eselenguaje.
* se les llama árboles de derivación, o también árboles de compilación –por usarse extensivamente en los compiladores– y son de vital importancia para la teoría de los compiladores delos lenguajes de programación.
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 unsímbolo terminal o un símbolo no terminal;
* Cada nodo interior corresponde a un símbolo no terminal.
Formalmente, unárbol se define de la siguiente manera.
* Definición.- Sea G = (V,,R, S) una GLC.
Entonces un árbol de derivación cumple las siguientes propiedades:
* 1. Cada nodo tiene una etiqueta.* 2. La raíz tiene etiqueta S.
* 3. La etiqueta de los nodos que no son hojas debe estar en V , y las de las hojas en [{"}.
* 4. Si un nodo n tiene etiqueta A, y los nodos n1, . . . , nmson sus hijos (de izquierda a derecha), con etiquetas respectivamente A1, . . . ,Am, entonces A ! A1, . . . ,Am 2 R.
* Definición.- La cadena de caracteres que resulta de concatenar loscaracteres terminales encontrados en las etiquetas de los nodos hoja, en un recorrido en orden del árbol de derivación, se llama el producto del árbol.
En este ejemplo, el hecho de que existan dos arbolesde derivación para una misma expresion es indeseable, pues cada árbol indica una manera distinta de estructurar la expresión.
En efecto, en el árbol de la izquierda, al resultado de la suma (x + y)se multiplica con x, mientras que en el de la derecha sumamos x al resultado de multiplicar x con y; por lo tanto el significado que se asocia a ambas expresiones puede ser distinto.
Se dice que...
Leer documento completo
Regístrate para leer el documento completo.