Forma normal de greibach

Solo disponible en BuenasTareas
  • Páginas : 6 (1285 palabras )
  • Descarga(s) : 4
  • Publicado : 6 de junio de 2010
Leer documento completo
Vista previa del texto
FORMA NORMAL DE GREIBACH
Se dice que una gramática independiente del contexto (GIC) está en Forma normal de Greibach (FNG), si todas y cada una de sus reglas de producción tienen un consecuente que empieza por un carácter del alfabeto, también llamado símbolo terminal. Formalmente, cualquiera de las reglas tendrá la estructura:
 A − > aw
Donde "A" es el antecedente de la regla, que en elcaso de las GIC debe ser necesariamente un solo símbolo auxiliar. Por su parte, "a" es el mencionado comienzo del consecuente y, por tanto, un símbolo terminal. Finalmente, "w" representa una concatenación genérica de elementos gramaticales, esto es, una sucesisión exclusivamente de auxiliares, inclusive, pudiera ser la palabra vacía; en este caso particular, se tendría una regla llamada "terminal": A − > a
Definición: Una Gramática Libre de Contexto (GLC) está en Forma Normal de Greibach (FNG) si todas las producciones son de la forma:
A  aB1B2…..Bk
Donde A es un símbolo no Terminal, a es un símbolo Terminal y B1B2…..Bk son símbolos no Terminales.
Además tiene la característica de: Ai →Aj solo si j > i
Ejemplo de FNG:
S → aSB | aB
B → b
Ejemplo que NO es FNG:
S → aSB | aBA → abB
B → b | A

ELIMINACION DE FACTORES COMUNNES DE IZQUIERDA
(En este caso el ¡ es como tener )
Existen gramáticas que tiene producciones de la forma A ¡ å ß1 | å ß2 como por ejemplo:
S ¡ i E t S e S | i E t S
Donde å es el término común en las producciones de A.
Sin embargo para poder llevar a cabo el análisis sintáctico de las mismas mediante algunas técnicas sedebe eliminar los términos comunes izquierdos llevando a cabo el proceso de factorización siguiente:
Las producciones A ¡ å ß1| å ß2 se transforman en las siguientes
A ¡ å A´
A´¡ ß | ß2
Las cuales nos generan el mismo lenguaje. Existe un nuevo símbolo no terminal A´ en la gramática, el cual no altera la gramática del lenguaje.
Generalizando el procedimiento para n producciones de A que tienenfactor común izquierdo:
1. Agrupar todas las producciones de A, sin importar cuantas sean.
A ¡ å ß1 | å ß2 | ... | å ßn | λ
*donde λ representa otras producciones de A que no tienen factor común izquierdo .
2. Remplazar las producciones de A a un conjunto equivalente mediante la siguiente transformación
A ¡ å A´ | λ
A´¡ ß1 | ß2 | ... | ßn

ELIMINACION DE RECURSIVIDAD IZQUIERDA INMEDIATA.¿Qué es la recursividad?

La recursividad consiste en realizar una definición de un concepto en términos del propio concepto que se está definiendo.
Se dice que una función es recursiva cuando se define en función de si misma. No todas la funciones pueden llamarse a si mismas, deben estar diseñadas especialmente para que sean recursivas, de otro modo podrían conducir a bucles infinitos, o a queel programa termine inadecuadamente.
Una gramática tiene recursividad izquierda si tiene un no terminal A tal que existe una derivación A ™A å para algún string å. Algunas técnicas de análisis sintáctico no pueden manejar gramáticas con recursividad izquierda por ello se debe eliminar primero.
Pasos para eliminar la recursividad izquierda inmediata.
1. Agrupar todas las producciones de A, sinimportar cuantas sean.
A ¡ A å1 | A å2 | ... | A åm | ß1 | ß2 | ... | ßn
donde ßi no inicia con A.
2. Reemplazar las producciones de A a un conjunto equivalente mediante la siguiente transformación:
A ¡ ß1 A´ | ß2 A´ | ... | ßn A´
A´ ¡ å1 A´ | å2 A´ | ... | åm A´ |
En el caso de obtener producciones con recursividad izquierda al momento de realizar este segundo paso, se debe repetir elprocedimiento.

ELIMINION DE AMBIGÜEDAD
Una gramática es ambigua si permite construir dos o más árboles de derivación distintos para la misma cadena. Por lo tanto, para demostrar que una gramática es ambigua lo único que se necesita es encontrar una cadena que tenga más de un árbol de derivación. Una gramática en la cual, para toda cadena generada w, todas las derivaciones de w tienen el mismo...
tracking img