U.T.N. – F.R.T.

Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

Sheila Adele Greibach:

Nacida el 06 de octubre 1939 en la ciudad de
Nueva York, es una matemática que trabaja
principalmente en la informática teórica.
Su aporte más significativo en este campo es una
forma estándar para las gramáticas libres del
contexto, que en su honor se conoce como Forma
Normal de Greibach.
En 1960, obtuvo su título de grado en Radcliffe College, en Lingüística y Matemática Aplicada y en 1962
se graduó como Magister con summa cum laude. Hizo su doctorado en Matemática Aplicada durante
1963, en la Universidad de Harvard.
En 1969 se trasladó a la Universidad de California en Los Angeles (UCLA), donde trabaja desde 1970
como profesora en el Departamento de Ciencias de la Computación.

NN , tT , WN*

FNG N → tW y como excepción S→λ , pero sin S a la derecha.
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

Para obtener la FNG de una GIC debemos realizar los siguientes pasos:

1) Obtener la GIC simplificada o bien formada: Eliminar reglas

innecesarias, de borrado y de redenominación.
2) Eliminar reglas recursivas por izquierda: Es decir reglas de la forma
N → N (recursividad directa) o reglas que conducen a una
recursividad por izquierda en varios pasos, o sea N * N.
3) Eliminación de reglas que comiencen con no-terminal: A efectos que
todas las reglas comiencen con un terminal, se debe realizar una serie
de sustituciones.
4) Sustitución de sufijos con terminales: Con el fin de llegar a la FNG se
transforma las reglas que tengan a la derecha sufijos con terminales.
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

ELIMINACIÓN DE RECURSIVIDADES POR IZQUIERDA:

1) Para la eliminación de la recursividad por izquierda directa se
reemplaza las reglas de la forma:
N → N1 | N2 | ... | Nn | 1 | 2 | ... | m
por las siguientes reglas equivalentes:
N → 1N’ | 2N’ | ... | mN’
N’ → 1N’ | 2N’ | ... | nN’ | 
Como puede verse en general las reglas recursivas generan secuencias de
“” que comienzan con “”. En las primeras reglas se comienza a
generar las secuencias de “” y se concluye con un “” adelante.
Las reglas equivalentes no recursivas generan primero una secuencia  y
luego la repetición de las secuencias .
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

ELIMINACIÓN DE RECURSIVIDADES POR IZQUIERDA:

2) Cuando se tiene recursividades por izquierda en varios pasos, se debe
aplicar del siguiente mecanismo:

Entrada: GIC simplificada Salida: GIC sin recursividades por izq.

1.- Ordenar los no-terminales en algún orden: N1 , N2 , ... , Nn
2.- Desde i=1 a n hacer
Desde j=1 a i-1 hacer
Sustituir cada producción de la forma Ni → Nj
por las producciones Ni → 1 | 2 | ... | k
donde Nj → 1 | 2 | ... | k son todas
las producciones actuales de Nj
Eliminar la recursividad directa por la izquierda para Ni
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

Ejemplos de eliminación de recursividad por izquierda:

1) Veamos primero el ejemplo de la GIC24, de expresiones aritméticas:
E → TE’
E→E+T|T E’ → +TE’ | 
T→T*F|F T → FT’
F→(E)|a|b T’ → *FT’ | 
F→(E)|a|b
2) Otro ejemplo de recursividad directa lo constituye la GIC3:

S → AAa S → AAa
A → AAa | b A → bA’
A’ → AaA’ | 

ING. JORGE BUABUD

U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

3) Veamos ahora un ejemplo sencillo de recursividad en varios pasos:

GIC27
S → Aa | a | b 1) Elegimos como orden: A , S
A → Ac | Sd | c 2) i=1 Eliminar [Link]. en A
S → Aa | a | b
A → SdA’ | cA’
1) Elegimos como orden: S , A A’→ cA’ | 
2) i=1 No hay [Link]. en S i=2 j=1 Sustituir S → Aa
i=2 j=1 Sustituir A → Sd S → SdA’a | cA’a | a | b
S → Aa | a | b A → SdA’ | cA’
A → Ac | Aad | ad | bd | c A’→ cÁ’ | 
Eliminar [Link] en A Eliminar [Link]. en S
S → cA’aS’ | aS’ | bS’
S → Aa | a | b S’→ dA’aS’ | 
A → adA’ | bdA’| cA’ A → SdA’ | cA’
A’→ cA’ | adA’ |  A’→ cÁ’ | 
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

ELIMINACIÓN DE REGLAS QUE COMIENCEN CON NO-TERMINAL:

Para realizar este proceso en forma sistemática se parte de una gramática
simplificada; sin recursividades por izquierda y se siguen los siguientes pasos:
1) Establecer un orden cualquiera para los No-terminales: N1 , N2 , ... , Nn
2) Dividir las reglas en 3 grupos:
Grupo 1: Ni → xw (xT , w*)
Grupo 2: Ni → Njw (Ni , Nj N , i<j , w*)
Grupo 3: Ni → Njw (Ni , Nj N , i>j , w*)
3) Seleccionar las reglas del Grupo 3 cuyo “i” sea mínimo en el orden.
y se las sustituye por las que se obtiene al reemplazar Nj por todas las
partes derechas de sus producciones. Repetir en orden ascendente de “i”
hasta que todas las reglas pasen al Grupo 1.
Luego proceder de igual modo con el Grupo 2.
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

Ejemplo de eliminación de reglas que comienzan con no-terminales:

Dada la GIC3 sin recursividades por la izquierda, procedemos a eliminar las
reglas de borrado:

S → AAa S → AAa
A → bA’ A → bA’ | b
A’ → AaA’ |  A’ → AaA’ | Aa

Ahora tomamos como orden de no-terminales: S , A , A’

Dividimos las reglas en tres grupos:
A→ bA’ | b
Grupo 1: A → bA’ | b
S → bA’Aa | bAa
Grupo 2: S → AAa
A’→ bA’aA’ | baA’ | bA’a | ba
Grupo 3: A’ → AaA’ | Aa
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

OBTENCIÓN DE LA FORMA NORMAL DE GREIBACH:

SUSTITUCIÓN DE SUFIJOS CON TERMINALES:

Se parte de una GIC cuyas reglas en sus partes derechas comienzan con un
símbolo terminal, a excepción de la regla S →  si existiera.
Para cada regla que no cumpla con la FNG, porque en su parte derecha tiene
más de un terminal; se reemplaza cada terminal, menos el primero, por un
nuevo no-terminal y luego se agrega la regla “nuevo no-terminal” deriva al
terminal asociado.
De este modo se logra obtener la Forma Normal de Greibach.
Completemos el ejemplo anterior, haciendo las sustituciones necesarias:
A→ bA’ | b
A→ bA’ | b S → bA’AB | bAB
S → bA’Aa | bAa A’→ bA’BA’ | bBA’ | bA’B | bB
A’→ bA’aA’ | baA’ | bA’a | ba B→a
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

FACTORIZACIÓN POR LA IZQUIERDA:

Cuando en una GIC tenemos, para un mismo no-terminal, reglas que

tienen partes derechas con prefijos iguales; se produce una indetermina-
ción en el momento de elegir una de esas reglas para resolver el problema
de análisis de una palabra. En particular para una FNGreibach es
inconveniente tener factores comunes en las reglas del mismo no-terminal.
El proceso que elimina ese problema se denomina factorización por la
izquierda y se define de la siguiente manera:
➢ Por cada NN
➢ Si N → 1 | 2 | ... | k
➢ entonces cambiar esas producciones por:
N → N’
N’ → 1 | 2 | ... | k
ING. JORGE BUABUD
U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

EJEMPLO DE FACTORIZACIÓN POR LA IZQUIERDA:

1) Consideremos la gramática de sentencias hipotéticas:

GIC31 =  N , T , S , P  Factorizada quedaría
N = { S, C } N = { S, A, B, C}
T = {if, then, else, repeat, until, forever, c1 , c2}
S → if C then S A
S → if C then S else S endif
S → repeat S B
S → if C then S endif
P A → else S endif | endif
P S → repeat S until C
B → until C | forever
S → repeat S forever
C → c1 | c2
C → c1 | c2

ING. JORGE BUABUD

U.T.N. – F.R.T. Lenguajes-Gramáticas Independientes
S. y S. de los L.
del Contexto y Autómatas de Pila.

EJEMPLO DE FACTORIZACIÓN POR LA IZQUIERDA:

2) Consideremos la gramática del lenguaje anbn / n0 en su formato FNG:

GIC1 =  N , T , S , P  S → aAB | aB | 
N = { S, A, B} T = {a, b} P A → aAB | aB
B→b

Factorizada quedaría Nuevamente en la FNG

N = { S, A, B, C}
S → aC | 
S → aC | 
P B→b
A → aC
P C → aCB | b
B→b
Eliminamos A →aC por resultar innecesaria.
C → AB | B
ING. JORGE BUABUD