ARBOLES SINTÁCTICOS DE DERIVACIÓN

UNIVERSIDAD DE GUADALAJARA
CENTRO UNIVERSITARIO DE CIENCIAS EXACTAS E INGENIERIAS
NÚMERO DE INVESTIGACION: 1
NOMBRE DEL TEMA:
ARBOLES SINTACTICOS DE DERIVACIÓN
FECHA DE ENTREGA:
11 / FEBRERO / 2015
NOMBRE DE LA MATERIA:
LENGUAJES DE PROGRAMACION COMPARADOS
CLAVE DE LA MATERIA:

CC208

DATOS DEL ALUMNO
NOMBRE DEL ALUMNO:
OLIVERA LÓPEZ ANA MARÍA
CARRERA:
ING EN COMPUTACIÓN
CÓDIGO:213215839

SECCIÓN:

D05

NOMBRE DE LA MAESTRA:
MURILLO LEAÑO MARÍA MAGDALENA

Arboles sintácticos de derivación

ÁRBOLES SINTACTICOS DE DERIVACIÓN

CONCEPTO: Es una forma de indicar gráficamente cómo una Gramática
Independiente de Contexto deriva una palabra particular. En este árbol matemático,
los nodos de las hojas del árbol son símbolos terminales y los nodos interioresson los
no terminales. En este caso ocurre que secuencias de derivación diferentes
corresponden al mismo árbol de derivación, ya que en esta representación no se
conoce el orden en que se aplicó cada composición.
Es útil en muchos casos presentar las derivaciones como árboles. Estos diagramas
conocidos también como árboles de análisis gramatical o de análisis sintáctico
suponen una estructurasobre las palabras de un Lenguaje y son de utilidad en
aplicaciones tales como la compilación de los Lenguajes de programación.
El símbolo inicial se define como el nodo raíz del árbol. Si se va a emplear la regla
A→x1 x2 …….xn , al ver que en ese momento A es un vértice terminal, entonces al
mencionado nodo se le asignan sus hijos, que estarán etiquetados como, x1 x2 ,…….,xn
siendo cada unode ellos colocado en una rama por separado. Se debe derivar
hasta que todas las hojas sean terminales.
EJEMPLO:
Dada la Gramática G = ( {a, b}, {0, 1}, {a 0ab |a1| b0, b 0a |1}, {a} ), determinar
alguna cadena s | s  L(G).
Originalmente, se obtenían las cadenas con la derivación en la forma tradicional, de la
siguiente manera:
a ⇒ 0ab ⇒ 0a1b ⇒ 0a10a ⇒ 0a110a ⇒ 0b0110a ⇒ 0b0110b0 ⇒010110b0 ⇒
01011010
s = (01)2 (10) 2
|s| = 8
El árbol de derivación que se hubiera diseñado con el mismo fin, es el siguiente:

a
a

0
a
a
b
1
Olivera López Ana María

1
1

0

b
0

a
b

0

1
s = 01011010
1

Arboles sintácticos de derivación

El árbol se lee primero en profundidad en forma similar a como se hace con los que se
utilizan en las estructuras de datos.Al analizar el árbol notaremos que todo nodo interior constituye el lado izquierdo de
una composición utilizada en ese momento, y la concatenación de los nodos hijos
representarían el lado derecho de la misma.
Obsérvese cómo en la producción original por derivaciones sucesivas no hay dudas en
cuanto al orden de aplicación de las composiciones, pero sí cuando se obtiene el árbol
y deseamossaber cómo se realizaron las derivaciones que lo produjeron. Como en
muchas ocasiones no importa ese orden, esta limitación no representa problema
alguno.
Ni la derivación por la derecha ni por la izquierda se pueden expresar por árboles de
derivación, porque en estos no se conoce el orden en que se han utilizado las reglas.

GRAMÁTICAS AMBIGUAS Y UNÍVOCAS
Una Gramática puede tener más de unárbol de derivación que genere una cadena
determinada, en cuyo caso se la llamará ambigua. Para demostrar que una
Gramática es ambigua lo único que se requiere es encontrar una cadena que tenga
más de un árbol de derivación que la produzca. En contraposición, la unívoca es una
Gramática Libre de Contexto que tiene asociado un solo árbol de derivación para
toda cadena de L(G).
Un Lenguaje L sellama AMBIGUO si existe una Gramática ambigua que lo genere y si
no es así, en contraposición se lo llama UNIVOCO.
Teóricamente, para afirmar que una Gramática es univoca, debería demostrarse
que todas y cada una de las cadenas que produce, son generadas con un único
posible árbol de derivación. Como esto no es posible, debe analizarse la
estructura general de las composiciones. No basta...