Greibach
Páginas: 4 (753 palabras)
Publicado: 4 de noviembre de 2012
Ejemplo gramática libre de contexto
S → A | BCa | aDcd | EDF A → aAb | c B → CD | b | ECd | Ad C → Cc | Bb | AaE | ε D → aDd | Dd | ε E → aaEB | EFG F → aFd | d
S → A1Y1 | c | BY2 | BA1 | CA1 |a | A1Y3 | A1Y4 Y1 → AB1 Y2 → CA1 Y3 → DY4 Y4 → C1D1 A → A1Y1 | c B → CD | CC1 | c | BB1 | b | A1Y5 | A1D1 | DD1 | d | AD1 Y5 → DD1 C → CC1 | c | BB1 | b D → A1Y5 | A1D1 | DD1 | d A1 →a B1 →b C1 →c D1→d
La forma normal de Greibach de una gramatica dada es aquella que solo contiene producciones de la forma Y→xa, donde x es un terminal y a es un string conformado unicamente por variables ypuede tener largo cero (o sea, puede ser el string vacio).
Primer Paso para Obtener una FNG
Ordenar y Enumerar todas las variables, procurando que la variable S sea la primera
Notese quecambiamos de orden a la variable A, al ponerla por debajo de la variable D. El proposito de estas alteraciones en el orden original tienen como fin que, al proceder con la enumeracion, en las produccionesresultantes quede la menor cantidad de producciones Xi → Xja, en donde i sea mayor que j.
Que es recursión: Cuando tenemos una producción de la forma X → Xa, decimos que X es tiene recursividadinmediata por la izquierda. Cuando tenemos por lo menos una producción de la forma X → Ya, y la variable Y tiene por lo menos una producción de la forma Y→Xb decimos que X recursividad por la izquierda.En nuestro caso, las variables que tienen producciones inmediatamente recursivas por la izquierda son X6 , X8 y X9, debido a sus producciones X6 → X6X12, X8 → X8X13 y X9 → X9X14. También tenemosla producción X8→X6X12 que es recursiva a la izquierda para la variable X6, y las producciones X6→X8X9 y X6→X8X13 que son recursivas a la izquierda para la variable X8.
¿Se acuerdan de nuestrapequeña gramática:
?
Pues ahora se ha convertido en esto:
Paso 3: eliminaremos todas las producciones de la forma Xi → Xja, en donde i es mayor que j.
Para hacer esto, reemplazaremos a...
S → A | BCa | aDcd | EDF A → aAb | c B → CD | b | ECd | Ad C → Cc | Bb | AaE | ε D → aDd | Dd | ε E → aaEB | EFG F → aFd | d
S → A1Y1 | c | BY2 | BA1 | CA1 |a | A1Y3 | A1Y4 Y1 → AB1 Y2 → CA1 Y3 → DY4 Y4 → C1D1 A → A1Y1 | c B → CD | CC1 | c | BB1 | b | A1Y5 | A1D1 | DD1 | d | AD1 Y5 → DD1 C → CC1 | c | BB1 | b D → A1Y5 | A1D1 | DD1 | d A1 →a B1 →b C1 →c D1→d
La forma normal de Greibach de una gramatica dada es aquella que solo contiene producciones de la forma Y→xa, donde x es un terminal y a es un string conformado unicamente por variables ypuede tener largo cero (o sea, puede ser el string vacio).
Primer Paso para Obtener una FNG
Ordenar y Enumerar todas las variables, procurando que la variable S sea la primera
Notese quecambiamos de orden a la variable A, al ponerla por debajo de la variable D. El proposito de estas alteraciones en el orden original tienen como fin que, al proceder con la enumeracion, en las produccionesresultantes quede la menor cantidad de producciones Xi → Xja, en donde i sea mayor que j.
Que es recursión: Cuando tenemos una producción de la forma X → Xa, decimos que X es tiene recursividadinmediata por la izquierda. Cuando tenemos por lo menos una producción de la forma X → Ya, y la variable Y tiene por lo menos una producción de la forma Y→Xb decimos que X recursividad por la izquierda.En nuestro caso, las variables que tienen producciones inmediatamente recursivas por la izquierda son X6 , X8 y X9, debido a sus producciones X6 → X6X12, X8 → X8X13 y X9 → X9X14. También tenemosla producción X8→X6X12 que es recursiva a la izquierda para la variable X6, y las producciones X6→X8X9 y X6→X8X13 que son recursivas a la izquierda para la variable X8.
¿Se acuerdan de nuestrapequeña gramática:
?
Pues ahora se ha convertido en esto:
Paso 3: eliminaremos todas las producciones de la forma Xi → Xja, en donde i es mayor que j.
Para hacer esto, reemplazaremos a...
Leer documento completo
Regístrate para leer el documento completo.