Arboles De Derivacion

Arboles De Derivacion

 Arboles De Derivacion 

Existen básicamente dos formas de describir cómo en una cierta gramática una cadena puede ser derivada desde el símbolo inicial. La forma más simple es listar las cadenas de símbolos consecutivas, comenzando por el símbolo inicial y finalizando con la cadena y las reglas que han sido aplicadas. Si introducimos estrategias como reemplazar siempre el no terminal de más a la izquierda primero, entonces la lista de reglas aplicadas es suficiente. A esto se le llama derivación por la izquierda.

Por ejemplo, si tomamos la siguiente gramática:

(1) S → S + S

2) S → 1

y la cadena “1 + 1 + 1″, su derivación a la izquierda está en la lista [ (1), (1), (2), (2), (2) ]. Análogamente, la derivación por la derecha se define como la lista que obtenemos si siempre reemplazamos primero el no terminal de más a la derecha. En ese caso, la lista de reglas aplicadas para la derivación de la cadena con la gramática anterior sería la [ (1), (2), (1), (2), (2)].

La distinción entre derivación por la izquierda y por la derecha es importante porque en la mayoría de analizadores la transformación de la entrada es definida dando una parte de código para cada producción que es ejecutada cuando la regla es aplicada. De modo que es importante saber qué derivación aplica el analizador, por que determina el orden en el que el código será ejecutado.

Una derivación también puede ser expresada mediante una estructura jerárquica sobre la cadena que está siendo derivada. Por ejemplo, la estructura de la derivación a la izquierda de la cadena “1 + 1 + 1″ con la gramática anterior sería:

:S→S+S (1)

:S→S+S+S (1)

:S→1+S+S (2)

:S→1+1+S (2)

:S→1+1+1 (2)

: { { { 1 }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub> + { 1 }<sub>S</sub> }<sub>S</sub>

donde { … }<sub>S</sub> indica la subcadena reconocida como perteneciente a S. Esta jerarquía también se puede representar mediante un árbol sintáctico:

            S

           /|
          / | 
         /  |  
        S  ‘+’  S

       /|\      |

      / | \     |

     S ‘+’ S   ‘1′

     |     |

    ‘1′   ‘1′

La derivación por la derecha:

:S→ S + S (1)

:S→ 1 + S (2)

:S→ 1 + S + S (1)

:S→ 1 + 1 + S (2)

:S→ 1 + 1 + 1 (2)

define el siguiente árbol sintáctico:

            S 

           /|
          / | 
         /  |  
        S  ‘+’  S

        |      /|
        |     / | 
       ‘1′   S ‘+’ S

             |     |

            ‘1′   ‘1′

Si para una cadena del lenguaje de una gramática hay más de un árbol posible, entonces se dice que la gramática es ambigua. Normalmente estas gramáticas son más difíciles de analizar por que el analizador no puede decidir siempre que producción aplicar.

Conteo de árboles de derivación+’

Para una gramática libre de contexto G=(V,T,P,s0), su serie generativa puede hacérse corresponder con una serie en de manera que las ecuaciones impuestas por las producciones en P se satisfagan también en . En efecto, a cada símbolo s en asociémosle una incógnita Xs. Sea . Tratemos ahora el producto de incógnitas como si fuera conmutativo, pues de hecho lo es en . Con esto, la serie generativa pL de L(G) corresponde con una serie en . Observamos dos características:

la serie generativa no involucra a los símbolos de V, pues esta serie se expande hasta la supresión de los símbolos variables, y

todas las palabras que son permutaciones de un mismo ``multiconjunto’‘ se símbolos corresponden a un mismo monomio en :

Consecuentemente, el coeficiente de un monomio en la serie es el número de posibles árboles de derivación derivables en G correspondientes a una palabra sobre el multiconjunto correspondiente al monomio. Esta transformación da así un método para contar derivaciones. Si la gramática no es ambigua, entonces cada palabra del lenguaje corresponde a un único árbol y, consecuentemente, éste procedimiento cuenta palabras generadas. Ejemplos. 1. Para la gramática que genera palíndromas pares ( ) o sea S=aSa+bSb+1 consideremos la correspondencia inducida por

La producción da la ecuación

X=YXY+ZYZ+1=X(Y2+Z2)+1

y por tanto . La serie correspondiente a la serie generativa ha de ser solución de esta última ecuación. Por tanto, según se vió en la proposición 6.5.2 de la anterior sección,

Así pues para cada hay posibles árboles para palabras de longitud 2m, y para cada hay árboles para palabras de longitud 2m con 2k apariciones del símbolo b. Como la gramática no es ambigua, la cuenta de árboles correponde a la cuenta de palabras.

2. Para la gramática de cadenas equilibradas de paréntesis [ ] o sea S=()+(S)+SS consideremos la correspondencia inducida por La producción da la ecuación

y por tanto . Consideremos por un momento Z=1. Entonces tenemos la ecuación 6.2 de la sección anterior. Consecuentemente, X tiene dos soluciones de la forma donde b0=0,1 y

En nuestro caso no hay ninguna paabra equilibrada con 0 paréntesis derechos. Así pues, el término independiente de la serie generativa debe ser b0=0. Con esta elección de b0 se tiene determinados a los demás coeficientes bm. Cada uno de ellos da el número de árboles de derivación de cadenas equilibradas de paréntesis para formar cadenas equilibradas con m paréntesis derechos. Como la gramática es ambigua el número de árboles excede el de cadenas equilibradas.

Consideremos la gramática con producciones

El lenguaje generado por la gramática es

La gramática se expresa por la ecuación S=SbS+a y mediante la correspondencia

se tiene la ecuación X=YX2+1. Al resolverla con la fórmula de Lagrange 6.3 se tiene

Para cada se tiene

Al evaluar en el punto x=1 obtenemos lo cual significa que para cada m hay derivaciones de la única palabra (ab)ma generable en la gramática que contiene exactamente m b’s. -‘

Si gustan pueden buscar mas informacion aquí

http://delta.cs.cinvestav.mx/~gmorales/ta/node118.html

espero les esa de utilidad

ISC


Mis sitios nuevos:
Emprendedores
Politica de Privacidad